Avatar of w1zeman1p

w1zeman1p's solution

to Book Store in the Ruby Track

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

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.

book_store_test.rb

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

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

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?