Published at Mar 10 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.

For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

```
gem install minitest
```

If you would like color output, you can `require 'minitest/pride'`

in
the test file, or note the alternative instruction, below, for running
the test file.

Run the tests from the exercise directory using the following command:

```
ruby book_store_test.rb
```

To include color from the command line:

```
ruby -r minitest/pride book_store_test.rb
```

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

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

```
require 'minitest/autorun'
require_relative 'book_store'
# Common test data version: 1.4.0 33c6b60
class BookStoreTest < Minitest::Test
def test_only_a_single_book
# skip
basket = [1]
assert_equal 8.00, BookStore.calculate_price(basket)
end
def test_two_of_the_same_book
skip
basket = [2, 2]
assert_equal 16.00, BookStore.calculate_price(basket)
end
def test_empty_basket
skip
basket = []
assert_equal 0.00, BookStore.calculate_price(basket)
end
def test_two_different_books
skip
basket = [1, 2]
assert_equal 15.20, BookStore.calculate_price(basket)
end
def test_three_different_books
skip
basket = [1, 2, 3]
assert_equal 21.60, BookStore.calculate_price(basket)
end
def test_four_different_books
skip
basket = [1, 2, 3, 4]
assert_equal 25.60, BookStore.calculate_price(basket)
end
def test_five_different_books
skip
basket = [1, 2, 3, 4, 5]
assert_equal 30.00, BookStore.calculate_price(basket)
end
def test_two_groups_of_four_is_cheaper_than_group_of_five_plus_group_of_three
skip
basket = [1, 1, 2, 2, 3, 3, 4, 5]
assert_equal 51.20, BookStore.calculate_price(basket)
end
def test_two_groups_of_four_is_cheaper_than_groups_of_five_and_three
skip
basket = [1, 1, 2, 3, 4, 4, 5, 5]
assert_equal 51.20, BookStore.calculate_price(basket)
end
def test_group_of_four_plus_group_of_two_is_cheaper_than_two_groups_of_three
skip
basket = [1, 1, 2, 2, 3, 4]
assert_equal 40.80, BookStore.calculate_price(basket)
end
def test_two_each_of_first_4_books_and_1_copy_each_of_rest
skip
basket = [1, 1, 2, 2, 3, 3, 4, 4, 5]
assert_equal 55.60, BookStore.calculate_price(basket)
end
def test_two_copies_of_each_book
skip
basket = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
assert_equal 60.00, BookStore.calculate_price(basket)
end
def test_three_copies_of_first_book_and_2_each_of_remaining
skip
basket = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1]
assert_equal 68.00, BookStore.calculate_price(basket)
end
def test_three_each_of_first_2_books_and_2_each_of_remaining_books
skip
basket = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 2]
assert_equal 75.20, BookStore.calculate_price(basket)
end
def test_four_groups_of_four_are_cheaper_than_two_groups_each_of_five_and_three
skip
basket = [1, 1, 2, 2, 3, 3, 4, 5, 1, 1, 2, 2, 3, 3, 4, 5]
assert_equal 102.40, BookStore.calculate_price(basket)
end
end
```

```
class BookStore
DISCOUNT = {
0 => 0,
1 => 0,
2 => 5,
3 => 10,
4 => 20,
5 => 25
}
@groups = {}
def self.calculate_price(basket)
return 0 if basket.empty?
best_price = Float::INFINITY
make_groups(basket).each do |group|
current_price = price(group)
if current_price < best_price
best_price = current_price
end
end
best_price
end
def self.make_groups(basket)
return [] if basket.empty?
return [[basket]] if basket.length == 1
if @groups.key?(basket)
return @groups[basket]
end
results = make_groups(basket[1..-1])
item = basket.first
groups = []
results.each do |result|
groups << result + [[item]]
result.each do |sub_result|
# Prune tree by ignoring sub groups
# with duplicate items.
if !sub_result.include?(item)
other_results = result.select{|r| r.object_id != sub_result.object_id}
this_result = sub_result + [item]
groups << other_results + [this_result]
end
end
end
@groups[basket] = groups
groups
end
def self.price(groups)
# memoize prices so we only calculate once per group.
@prices = {}
groups.sum do |g|
if @prices.key?(g)
@prices[g]
else
@prices[g] = BookStore.new(g).calculate
end
end
end
def initialize(items)
@items = items
end
def calculate
group_count = @items.uniq.count
full_price = (@items.length - group_count) * 8.0
discount = DISCOUNT[group_count] || 0
full_price + (8.00 * group_count) * (100 - discount) / 100
end
end
```

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

- What compromises have been made?
- Are there new concepts here that you could read more about to improve your understanding?

Level up your programming skills with 3,089 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments