 # ESV's solution

## to Book Store in the Java Track

Published at Oct 09 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.

## 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);
}
}``````

### src/main/java/DiscountGroups.java

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class DiscountGroups {
private final List<DiscountGroup> groups;

public static final DiscountGroups EMPTY = new DiscountGroups();
private DiscountGroups() { this.groups = Collections.emptyList(); }

/**
* Create new discount groupings by starting with `groups` and adding
* `book` to the existing group indicated by `groupIndex`.
*/
private DiscountGroups(
final DiscountGroups previous,
final Book book,
final int groupIndex)
{
Objects.requireNonNull(previous, "previous");
Objects.requireNonNull(book, "book");

if (0 > groupIndex || groupIndex > previous.size()) {
throw new IllegalArgumentException(String.format(
"groupIndex must be in range [0, %d]; it was %d",
previous.size(),
groupIndex));
}

this.groups = new ArrayList<DiscountGroup>(
groupIndex < previous.size()
? previous.size()
: previous.size() + 1);

for (int i = 0; i < previous.size(); i++) {
final var previousGroup = previous.groups.get(i);

if (i == groupIndex) {
} else {
}
}

if (groupIndex == previous.size()) {
}
}

private int size() { return groups.size(); }

double price() {
return groups.stream()
.map(g -> g.price())
.collect(Collectors.summingDouble(Double::doubleValue));
}

public Stream<DiscountGroups> variantsThatInclude(final Book book)
{
Objects.requireNonNull(book, "book");

final Stream.Builder<DiscountGroups> variants = Stream.builder();

for (int i = 0; i < size(); i++) {
}
}

return variants.build();
}

@Override
public String toString() {
final var sb = new StringBuilder("- ");
boolean first = true;
for (var g : groups) {
if (!first) sb.append(' ');
sb.append(g);
first = false;
}
return sb.toString();
}
}``````

### src/main/java/DiscountSearch.java

``````import java.util.List;

public class DiscountSearch {

private static final boolean TRACE = false;

public static double lowestPrice(final List<Book> books) {
if ((null == books) || (books.size() == 0)) {
return 0.0;
}

final var search = new DiscountSearch();
search.findLowestPrice(DiscountGroups.EMPTY, books);
return search.bestPriceSoFar;
}

private DiscountSearch() {
bestPriceSoFar = Double.MAX_VALUE;
}

private double bestPriceSoFar;

private void findLowestPrice(
final DiscountGroups groups,
final List<Book> books)
{
double bestDescendentPrice = Double.MAX_VALUE;

if (books.isEmpty()) {
if (TRACE) print("\$%1.2f as %s\n", groups.price(), groups);
bestDescendentPrice = groups.price();
} else if (groups.price() >= bestPriceSoFar) {
// OPTIMIZATION: We've already found a leaf with a lower price,
// and we can't make this one cheaper by *adding* books.
if (TRACE) print("abandoning >\$%1.2f as %s plus %s\n",
groups.price(),
groups,
books);
return;
} else {
if (TRACE) print("exploring %s plus %s\n", groups, toString(books));
final var booksTail = books.subList(1, books.size());
for (final var variant : (Iterable<DiscountGroups>)variants::iterator) {
findLowestPrice(variant, booksTail);
}
}

bestPriceSoFar = Double.min(bestPriceSoFar, bestDescendentPrice);
}

private static void print(String format, Object... args) {
System.out.format(format, args);
}

private static String toString(final List<Book> books) {
final var sb = new StringBuilder();
sb.append('[');
boolean first = true;
for (var b : books) {
if (!first) sb.append(',');
sb.append(b);
first = false;
}
sb.append(']');
return sb.toString();
}
}``````

### src/main/java/DiscountGroup.java

``````import java.util.EnumSet;
import java.util.Objects;

public class DiscountGroup {
final private EnumSet<Book> books;

/**
* Create a DiscountGroup that includes all members of `group`, plus
*/
public DiscountGroup(DiscountGroup group, Book book) {
this(group);
Objects.requireNonNull(book, "book");

throw new IllegalArgumentException(
"group already contains book; cannot include it twice");
}

}

public DiscountGroup(Book book) {
Objects.requireNonNull(book, "book");
this.books = EnumSet.of(book);
}

private DiscountGroup(DiscountGroup group) {
Objects.requireNonNull(group, "group");
books = EnumSet.copyOf(group.books);
}

public double price() {
switch (books.size()) {
case 1:
return 8.0;
case 2:
return 8.0 * 2.0 * 0.95;
case 3:
return 8.0 * 3.0 * 0.90;
case 4:
return 8.0 * 4.0 * 0.80;
case 5:
return 8.0 * 5.0 * 0.75;
default:
throw new AssertionError(String.format(
"impossible number of books in set; max is 5, was %d",
books.size()));
}
}

Objects.requireNonNull(book, "book");
return !books.contains(book);
}

public DiscountGroup deepCopy() {
return new DiscountGroup(this);
}

@Override
public String toString() {
final var sb = new StringBuilder("{");
boolean first = true;
for (var b : books) {
if (!first) sb.append(',');
sb.append(b);
first = false;
}
return sb.append('}').toString();
}
}``````

### src/main/java/Book.java

``````import java.rmi.UnexpectedException;

public enum Book {
ONE, TWO, THREE, FOUR, FIVE;

public static Book fromVolumeIndex(int volumeIndex) {
switch (volumeIndex) {
case 1: return ONE;
case 2: return TWO;
case 3: return THREE;
case 4: return FOUR;
case 5: return FIVE;
default: throw new RuntimeException(String.format(
"invalid volume number: %d",
volumeIndex));
}
}

@Override
public String toString() {
switch (this) {
case ONE: return "1";
case TWO: return "2";
case THREE: return "3";
case FOUR: return "4";
case FIVE: return "5";
default: throw new RuntimeException("invalid Book enum value");
}
}
}``````

### src/main/java/BookStore.java

``````import java.util.List;
import java.util.stream.Collectors;

public final class BookStore {
public BookStore() { }

.map(i -> Book.fromVolumeIndex(i))
.collect(Collectors.toList()));
}
}``````