# charles-wangkai's solution

## to Book Store in the Java Track

Published at Oct 22 2018 · 0 comments
Instructions
Test suite
Solution

To try and encourage more sales of different books from a popular 5 book series, a bookshop has decided to offer discounts on multiple book purchases.

One copy of any of the five books costs \$8.

If, however, you buy two different books, you get a 5% discount on those two books.

If you buy 3 different books, you get a 10% discount.

If you buy 4 different books, you get a 20% discount.

If you buy all 5, you get a 25% discount.

Note: that if you buy four books, of which 3 are different titles, you get a 10% discount on the 3 that form part of a set, but the fourth book still costs \$8.

Your mission is to write a piece of code to calculate the price of any conceivable shopping basket (containing only books of the same series), giving as big a discount as possible.

For example, how much does this basket of books cost?

• 2 copies of the first book
• 2 copies of the second book
• 2 copies of the third book
• 1 copy of the fourth book
• 1 copy of the fifth book

One way of grouping these 8 books is:

• 1 group of 5 --> 25% discount (1st,2nd,3rd,4th,5th)
• +1 group of 3 --> 10% discount (1st,2nd,3rd)

This would give a total of:

• 5 books at a 25% discount
• +3 books at a 10% discount

Resulting in:

• 5 x (8 - 2.00) == 5 x 6.00 == \$30.00
• +3 x (8 - 0.80) == 3 x 7.20 == \$21.60

For a total of \$51.60

However, a different way to group these 8 books is:

• 1 group of 4 books --> 20% discount (1st,2nd,3rd,4th)
• +1 group of 4 books --> 20% discount (1st,2nd,3rd,5th)

This would give a total of:

• 4 books at a 20% discount
• +4 books at a 20% discount

Resulting in:

• 4 x (8 - 1.60) == 4 x 6.40 == \$25.60
• +4 x (8 - 1.60) == 4 x 6.40 == \$25.60

For a total of \$51.20

And \$51.20 is the price with the biggest discount.

## Setup

Go through the setup instructions for Java to install the necessary dependencies:

https://exercism.io/tracks/java/installation

# Running the tests

You can run all the tests for an exercise by entering the following in your terminal:

``````\$ gradle test
``````

Use `gradlew.bat` if you're on Windows

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the `@Ignore("Remove to run test")` annotation.

## Source

Inspired by the harry potter kata from Cyber-Dojo. http://cyber-dojo.org

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### BookStoreTest.java

``````import static org.junit.Assert.assertEquals;

import java.util.Collections;
import java.util.List;
import java.util.Arrays;

import org.junit.Before;
import org.junit.Ignore;
import org.junit.Test;

public class BookStoreTest {

// This is sufficient accuracy since we're handling currency values, which should be equal
// to within 2 decimal places.
private static final double EQUALITY_TOLERANCE = 0.001;

private BookStore bookStore;

@Before
public void setUp() {
bookStore = new BookStore();
}

@Test
public void onlyASingleBook() {
List<Integer> books = Collections.singletonList(1);
}

@Ignore("Remove to run test")
@Test
public void twoOfSameBook() {
List<Integer> books = Arrays.asList(2, 2);
}

@Ignore("Remove to run test")
@Test
List<Integer> books = Collections.emptyList();
}

@Ignore("Remove to run test")
@Test
public void twoDifferentBooks() {
List<Integer> books = Arrays.asList(1, 2);
}

@Ignore("Remove to run test")
@Test
public void threeDifferentBooks() {
List<Integer> books = Arrays.asList(1, 2, 3);
}

@Ignore("Remove to run test")
@Test
public void fourDifferentBooks() {
List<Integer> books = Arrays.asList(1, 2, 3, 4);
}

@Ignore("Remove to run test")
@Test
public void fiveDifferentBooks() {
List<Integer> books = Arrays.asList(1, 2, 3, 4, 5);
}

@Ignore("Remove to run test")
@Test
public void twoGroupsOfFourIsCheaperThanGroupOfFivePlusGroupOfThree() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 5);
}

@Ignore("Remove to run test")
@Test
public void twoGroupsOfFourIsCheaperThanGroupsOfFiveAndThree() {
List<Integer> books = Arrays.asList(1, 1, 2, 3, 4, 4, 5, 5);
}

@Ignore("Remove to run test")
@Test
public void groupOfFourPlusGroupOfTwoIsCheaperThanTwoGroupsOfThree() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 4);
}

@Ignore("Remove to run test")
@Test
public void twoEachOfFirst4BooksAnd1CopyEachOfRest() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5);
}

@Ignore("Remove to run test")
@Test
public void twoCopiesOfEachBook() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5, 5);
}

@Ignore("Remove to run test")
@Test
public void threeCopiesOfFirstBookAnd2EachOfRemaining() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1);
}

@Ignore("Remove to run test")
@Test
public void threeEachOFirst2BooksAnd2EachOfRemainingBooks() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 2);
}

@Ignore("Remove to run test")
@Test
public void fourGroupsOfFourAreCheaperThanTwoGroupsEachOfFiveAndThree() {
List<Integer> books = Arrays.asList(1, 1, 2, 2, 3, 3, 4, 5, 1, 1, 2, 2, 3, 3, 4, 5);
}
}``````
``````import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class BookStore {
static final int PRICE = 8;
static final double[] RATIOS = { -1, 1, 0.95, 0.9, 0.8, 0.75 };

int[] counts = new int[5];
for (int book : books) {
counts[book - 1]++;
}

return search(new HashMap<String, Double>(), counts);
}

double search(Map<String, Double> cache, int[] counts) {
if (Arrays.stream(counts).allMatch(count -> count == 0)) {
return 0;
}

String key = generateKey(counts);

if (cache.containsKey(key)) {
return cache.get(key);
}

double minCost = Double.MAX_VALUE;
for (int code = 1; code < (1 << counts.length); code++) {
boolean[] used = decode(counts.length, code);

if (IntStream.range(0, used.length).anyMatch(i -> counts[i] == 0 && used[i])) {
continue;
}

int bookNum = (int) IntStream.range(0, used.length).filter(i -> used[i]).count();

minCost = Math.min(minCost, bookNum * PRICE * RATIOS[bookNum] + search(cache,
IntStream.range(0, counts.length).map(i -> counts[i] - (used[i] ? 1 : 0)).toArray()));
}

cache.put(key, minCost);
return minCost;
}

String generateKey(int[] counts) {
return String.join(",", Arrays.stream(counts).mapToObj(Integer::toString).collect(Collectors.toList()));
}

boolean[] decode(int size, int code) {
boolean[] result = new boolean[size];
for (int i = 0; i < result.length; i++) {
result[i] = (code & 1) != 0;
code >>= 1;
}
return result;
}
}``````