## to Book Store in the Java Track

Published at Jan 28 2019 · 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.

# Running the tests

You can run all the tests for an exercise by entering

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

## 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.Collections;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

public class BookStore {

final protected double[] price = {
0.00,     // 0 books, 0 cost
8.00,     // price of 1 book
7.60*2,   // price of 2 different books (-05% = 7.6)
7.20*3,   // price of 3 different books (-10% = 7.2)
6.40*4,   // price of 4 different books (-20% = 6.4)
6.00*5    // price of 5 different books (-25% = 6.0)
};

protected HashMap<String, Double> cache;   // all the calculated best price
protected List<List<Integer[]>> combinations; // how many ways to pick "n" diff books from 5 for n=1-5 {index@0-4}
protected ArrayList<HashMap<String, Integer[]>> toDos; // for the dynamic build up from 1-n books where n is total

public BookStore() {

cache = new HashMap<String, Double>();

combinations = new ArrayList<List<Integer[]>>(5);
fillupCombinations();

Integer[] books = new Integer[6]; // books[0] stores how many books
for(int i=0; i<books.length; i++) books[i] = 0;

// Cheapest if just 0,1-5 different books
cache.put(Arrays.toString(books), price[0]);
for(int i=1; i<books.length;i++) {
books[0] = i; books[i] = 1;
cache.put(Arrays.toString(books), price[i]);
}
}

// We are really only just interested in the number of each different books
// this function just counts how many are there, and sort it largest to smallest.
// sorting from most to least helps in our iteration (we only need to iterate up to max of
// each diff books ie, there will never be eg [2 1 2 1 1] so we don't ever have to look at anything
// where [a b c d e] isn't strictly a>=b>=c>=d>=e; a>0.  Provably, you cannot do better.
// storing books[0] as # of books just helps with the hash and iteration counting.
private Integer[] countDiffBooks( List<Integer> books) {
Integer[] booksCount = new Integer[6];
for(int i =0; i<booksCount.length; i++) booksCount[i]=0;
for(Integer booknum: books) {
booksCount[0]++;
booksCount[booknum]++;
}
Arrays.sort(booksCount,1,6, Collections.reverseOrder());
return booksCount;
}

// below 2 functions just generates all combinations based on src of length 1-5.
// storing all combinations of length=i @ combinations[i-1]
// this is used to allow us to figure out how many ways to add "i" different books
// to any starting book set for our iteration.

protected void genCombination(List<Integer[]> combo, Integer[] src, int len, int start, Integer[] res, int n) {
if (len == 0) {
return;
}
for (int i=start; i<=src.length-len; i++) {
res[n-len] = src[i];
genCombination(combo, src, len-1, i+1,res,n);
}

}

protected void fillupCombinations() {
Integer[] source = {1,2,3,4,5};
for(int i=1; i<6;i++) {
List<Integer[]> li = new ArrayList<Integer[]>();
genCombination(li,source,i,0,new Integer[i],i);
}
}

// given a list of inbooks, calculate the best price with
// the set of discounts.
// this method currently assumes 5 different types of books only,
// but was designed to be generalizable.  It also does not make
// any assumptions on which is the best allocation %age
// e.g. that 3+5 is better than 4+4.
// It dynamically figures out, given a set of n books, how to get from
// 1 book to those n books
// on the premise that from the set of "all legal best price for" i books,
// if we try the 5 discounts [1-5 books], we can see if we do better,
// and keep trying.
// n books is represented, internally, as [n, a,b,c,d,e] where
// a-e are the # of the different types of books sorted such that
// a>=b>=c>=d>=e.
// Sorting makes it easier to reduce the # of combinations considered.
// we also check against a calculated cache (each time the system runs,
// it will build up this cache based on the calculations) first.
// We did not optimize for the fact that we may already have try out
// the specific sum -- ie, to get to 6 books, I would try 2+4 and 4+2 which is equiv.
Integer[] books = countDiffBooks(inBooks);

// check against any previous known best prices.
double checkCost = cache.getOrDefault(Arrays.toString(books), -1.0);
if (checkCost != -1.0) return checkCost;

// we will dynamically go from 1 book to n books
toDos = new ArrayList<HashMap<String,Integer[]>>(books[0]);

for(int bk=0; bk<books[0]; bk++) {
}
// there is only 1 way to have 1 book.  Our start...
Integer[] firstworkitem = new Integer[] {1,1,0,0,0,0};
toDos.get(0).put(Arrays.toString(firstworkitem),firstworkitem);

for(int bk=1; bk<=books[0]; bk++) {
// toDo is the list of legal "bk" number of books priced
// it hashes the legal book set [bk, a,b,c,d,e]
// with the string version as key as is required, and the actual array as value
// so we can get it back and use that as our workitem
HashMap<String,Integer[]> toDo = toDos.get(bk-1);
Iterator<String> it = toDo.keySet().iterator();
while(it.hasNext()) {
Integer[] workItem = toDo.get(it.next());
double price = cache.getOrDefault(Arrays.toString(workItem),0.0);
it.remove();

// from *this* best price item for bk, try out bk+i (i=1-5) discount price
for(int d=1; d<=5; d++) {
if (bk+d <= books[0]) {
getItems(bk+d,d,workItem, price, books);
}
}
}
}

return cache.getOrDefault(Arrays.toString(books), 0.0);
}

// generates all legal sets we want from item that are "d" away
// and check if we need to update price for that item if it's better thatn
protected void getItems(int n, int d, Integer[] item, double base, Integer[] books) {
List<Integer[]> combis = combinations.get(d-1);  // all poss combinations that are d away
HashMap<String,Integer[]> toDo = toDos.get(n-1);
for(Integer[] combi:combis) {
Integer[] newItem = item.clone();

if (isLegal(newItem,combi,books)) {
toDo.put(Arrays.toString(newItem),newItem);
if (cache.containsKey(Arrays.toString(newItem))) {
double bestPrice = cache.get(Arrays.toString(newItem));
if (bestPrice > base+price[d]) {
cache.put(Arrays.toString(newItem), base+price[d]);
}
} else {
cache.put(Arrays.toString(newItem), base+price[d]);
}
}
}
}

// generate and test if item+combi is legal.
// legal means it remains sorted (a>=b>=c>=d>=e) and
// item+combi <= books  [else we really don't care]
protected boolean isLegal(Integer[] item, Integer[] combi, Integer[] books) {
for(int c:combi) {
item[c]++;
item[0]++;
if (item[c] > books[c]) return false;
if (c > 1 && item[c] > item[c-1]) return false;
}
return true;
}

}``````