ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# gvissers's solution

## to Book Store in the Rust Track

Published at Nov 10 2020 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

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.

## Rust Installation

Refer to the exercism help page for Rust installation and learning resources.

## Writing the Code

Execute the tests with:

``````\$ cargo test
``````

All but the first test have been ignored. After you get the first test to pass, open the tests source file which is located in the `tests` directory and remove the `#[ignore]` flag from the next test and get the tests to pass again. Each separate test is a function with `#[test]` flag above it. Continue, until you pass every test.

If you wish to run all ignored tests without editing the tests source file, use:

``````\$ cargo test -- --ignored
``````

To run a specific test, for example `some_test`, you can use:

``````\$ cargo test some_test
``````

If the specific test is ignored use:

``````\$ cargo test some_test -- --ignored
``````

## Further improvements

After you have solved the exercise, please consider using the additional utilities, described in the installation guide, to further refine your final solution.

To format your solution, inside the solution directory use

``````cargo fmt
``````

To see, if your solution contains some common ineffective use cases, inside the solution directory use

``````cargo clippy --all-targets
``````

## Submitting the solution

Generally you should submit all files in which you implemented your solution (`src/lib.rs` in most cases). If you are using any external crates, please consider submitting the `Cargo.toml` file. This will make the review process faster and clearer.

## Feedback, Issues, Pull Requests

The exercism/rust repository on GitHub is the home for all of the Rust exercises. If you have feedback about an exercise, or want to help implement new exercises, head over there and create an issue. Members of the rust track team are happy to help!

If you want to know more about Exercism, take a look at the contribution guide.

## 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.rs

``````//! Tests for book-store
//!
//! Generated by [script][script] using [canonical data][canonical-data]
//!
//! [script]: https://github.com/exercism/rust/blob/master/bin/init_exercise.py
//! [canonical-data]: https://raw.githubusercontent.com/exercism/problem-specifications/master/exercises/book-store/canonical_data.json

use book_store::*;

/// Process a single test case for the property `total`
///
/// All cases for the `total` property are implemented
/// in terms of this function.
///
/// Expected input format: ('basket', 'targetgrouping')
fn process_total_case(input: (Vec<u32>, Vec<Vec<u32>>), expected: u32) {
assert_eq!(lowest_price(&input.0), expected)
}

// Return the total basket price after applying the best discount.
// Calculate lowest price for a shopping basket containing books only from
// a single series.  There is no discount advantage for having more than
// one copy of any single book in a grouping.

#[test]
/// Only a single book
fn test_only_a_single_book() {
process_total_case((vec![1], vec![vec![1]]), 800);
}

#[test]
#[ignore]
/// Two of the same book
fn test_two_of_the_same_book() {
process_total_case((vec![2, 2], vec![vec![2], vec![2]]), 1_600);
}

#[test]
#[ignore]
process_total_case((vec![], vec![]), 0);
}

#[test]
#[ignore]
/// Two different books
fn test_two_different_books() {
process_total_case((vec![1, 2], vec![vec![1, 2]]), 1_520);
}

#[test]
#[ignore]
/// Three different books
fn test_three_different_books() {
process_total_case((vec![1, 2, 3], vec![vec![1, 2, 3]]), 2_160);
}

#[test]
#[ignore]
/// Four different books
fn test_four_different_books() {
process_total_case((vec![1, 2, 3, 4], vec![vec![1, 2, 3, 4]]), 2_560);
}

#[test]
#[ignore]
/// Five different books
fn test_five_different_books() {
process_total_case((vec![1, 2, 3, 4, 5], vec![vec![1, 2, 3, 4, 5]]), 3_000);
}

#[test]
#[ignore]
/// Two groups of four is cheaper than group of five plus group of three
fn test_two_groups_of_four_is_cheaper_than_group_of_five_plus_group_of_three() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 5],
vec![vec![1, 2, 3, 4], vec![1, 2, 3, 5]],
),
5_120,
);
}

#[test]
#[ignore]
/// Group of four plus group of two is cheaper than two groups of three
fn test_group_of_four_plus_group_of_two_is_cheaper_than_two_groups_of_three() {
process_total_case(
(vec![1, 1, 2, 2, 3, 4], vec![vec![1, 2, 3, 4], vec![1, 2]]),
4_080,
);
}

#[test]
#[ignore]
/// Two each of first 4 books and 1 copy each of rest
fn test_two_each_of_first_4_books_and_1_copy_each_of_rest() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 4, 5],
vec![vec![1, 2, 3, 4, 5], vec![1, 2, 3, 4]],
),
5_560,
);
}

#[test]
#[ignore]
/// Two copies of each book
fn test_two_copies_of_each_book() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 4, 5, 5],
vec![vec![1, 2, 3, 4, 5], vec![1, 2, 3, 4, 5]],
),
6_000,
);
}

#[test]
#[ignore]
/// Three copies of first book and 2 each of remaining
fn test_three_copies_of_first_book_and_2_each_of_remaining() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1],
vec![vec![1, 2, 3, 4, 5], vec![1, 2, 3, 4, 5], vec![1]],
),
6_800,
);
}

#[test]
#[ignore]
/// Three each of first 2 books and 2 each of remaining books
fn test_three_each_of_first_2_books_and_2_each_of_remaining_books() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 2],
vec![vec![1, 2, 3, 4, 5], vec![1, 2, 3, 4, 5], vec![1, 2]],
),
7_520,
);
}

#[test]
#[ignore]
/// Four groups of four are cheaper than two groups each of five and three
fn test_four_groups_of_four_are_cheaper_than_two_groups_each_of_five_and_three() {
process_total_case(
(
vec![1, 1, 2, 2, 3, 3, 4, 5, 1, 1, 2, 2, 3, 3, 4, 5],
vec![
vec![1, 2, 3, 4],
vec![1, 2, 3, 5],
vec![1, 2, 3, 4],
vec![1, 2, 3, 5],
],
),
10_240,
);
}``````
``````use std::collections::HashSet;

const MAX_SET_SIZE: usize = 5;
const NR_TITLES: usize = 5;

type SetSizeDistr = [u32; MAX_SET_SIZE];

/// Find all possible distributions of set sizes after adding `count` copies of a new title
/// to already existing sets of size at least `idx+1`, starting from size distribution
/// `distribution`.
fn add_to_existing_set(distribution: SetSizeDistr, count: u32, idx: usize) -> Vec<SetSizeDistr>
{
if count == 0
{
// Nothing to do
vec![distribution]
}
else if idx >= MAX_SET_SIZE - 1
{
// Can't add to sets of maximum size
vec![]
}
else
{
let mut res = vec![];
for i in 0..=count.min(distribution[idx])
{
for mut d2 in add_to_existing_set(distribution, count-i, idx+1)
{
d2[idx] -= i;
d2[idx+1] += i;
res.push(d2);
}
}
res
}
}

/// Find all possible distributions of set sizes after adding `count` copies of a new title,
/// starting from size distribution `distribution`, and add them to `new_distributions`.
fn distribute(distribution: SetSizeDistr, count: u32, new_distributions: &mut HashSet<SetSizeDistr>)
{
for i in 0..=count
{
let d2s = add_to_existing_set(distribution, i, 0);
for mut d2 in d2s
{
d2[0] += count-i;
new_distributions.insert(d2);
}
}
}

/// Find the lowest price for buying the books in `books`. We do so by finding all ways that the
/// books can be combined into sets of different sizes, and returning the price for the size
/// distribution with the lowest cost.
pub fn lowest_price(books: &[u32]) -> u32 {
static COSTS: [u32; MAX_SET_SIZE] = [
800,
1_520,
2_160,
2_560,
3_000
];

// Count how many books of each title are bought
let mut counts = [0; NR_TITLES];
for book in books
{
counts[*book as usize - 1] += 1;
}

// For each title, find all possible ways to distribute its number of bought copies over the
// sets, starting from each of the possible size distribution generated by the previous titles,
// and comnbine the results into a new set of size distributions.
let mut distributions = HashSet::new();
distributions.insert([0; 5]);
for count in counts.iter().filter(|&&count| count > 0)
{
let mut new_distributions = HashSet::new();
for distribution in distributions
{
distribute(distribution, *count, &mut new_distributions);
}

distributions = new_distributions;
}

// Return the price of the cheapest distribution
distributions.iter()
.map(|d| d.iter().zip(COSTS.iter()).map(|(n, c)| n*c).sum::<u32>())
.min()
.unwrap()
}``````