Exercism v3 launches on Sept 1st 2021. Learn more! ๐๐๐

Published at Feb 21 2021
·
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.

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

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
```

To learn more about Rust tests refer to the online test documentation

Make sure to read the Modules chapter if you haven't already, it will help you with organizing your files.

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
```

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.

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.

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.

```
//! Tests for book-store
//!
//! Generated by [script][script] using [canonical data][canonical-data]
//!
//! [script]: https://github.com/exercism/rust/blob/main/bin/init_exercise.py
//! [canonical-data]: https://raw.githubusercontent.com/exercism/problem-specifications/main/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]
/// Empty basket
fn test_empty_basket() {
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::HashMap;
pub fn lowest_price(books: &[u32]) -> u32 {
let mut books_count: [u8; 5] = [0, 0, 0, 0, 0];
books.iter().for_each(|id| books_count[*id as usize - 1] += 1);
let mut lowest_price: HashMap<[u8; 5], u32> = HashMap::new();
lowest_price.insert([0, 0, 0, 0, 0], 0);
dfs(&books_count, &mut lowest_price)
}
fn dfs(books_count: &[u8; 5], lowest_price: &mut HashMap<[u8; 5], u32>) -> u32 {
if lowest_price.contains_key(books_count) {
return lowest_price[books_count];
}
let mut result = u32::MAX;
for books in 1_u8..32 {
let mut new_books_count = books_count.clone();
let mut valid = true;
for i in 0..5 {
if books & (1 << i) != 0 {
if books_count[i as usize] == 0 {
valid = false;
break;
}
new_books_count[i as usize] -= 1;
}
}
if !valid {
continue;
}
let price = books_price(books.count_ones());
let total_price = price + dfs(&new_books_count, lowest_price);
result = result.min(total_price);
}
lowest_price.insert(*books_count, result);
result
}
fn books_price(different_books_count: u32) -> u32 {
match different_books_count {
0 => 0,
1 => 800,
2 => 8 * 2 * 95,
3 => 8 * 3 * 90,
4 => 8 * 4 * 80,
5 => 8 * 5 * 75,
_ => panic!("different_books_count should be in 0~5")
}
}
```

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,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments