🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of coolPoint

coolPoint's solution

to Book Store in the Rust Track

Published at Nov 07 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

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.

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]
/// 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::cell::RefCell;
use std::cmp::Ordering;
use std::collections::hash_map::DefaultHasher;
use std::collections::{BTreeSet, HashSet};
use std::hash::{Hash, Hasher};
use std::mem;

type Book = u32;
type GroupedBasket = Vec<Group>;
type Price = u32;
const BOOK_PRICE: Price = 800;

#[derive(Debug, Clone, PartialEq, Eq)]
struct Group(RefCell<BTreeSet<Book>>);

impl Group {
    fn new() -> Group {
        Group(RefCell::new(BTreeSet::new()))
    }

    fn new_containing(book: Book) -> Group {
        let g = Group::new();
        g.0.borrow_mut().insert(book);
        g
    }

    fn price(&self) -> Price {
        (self.0.borrow().len() as Price) * BOOK_PRICE * match self.0.borrow().len() {
            2 => 95,
            3 => 90,
            4 => 80,
            5 => 75,
            _ => 100,
        } / 100
    }
}

impl Ord for Group {
    // we want to order groups first by qty contained DESC, then by lowest value ASC
    fn cmp(&self, other: &Group) -> Ordering {
        match other.0.borrow().len().cmp(&self.0.borrow().len()) {
            Ordering::Equal => {
                if self.0.borrow().len() == 0 {
                    Ordering::Equal
                } else {
                    self.0
                        .borrow()
                        .iter()
                        .next()
                        .unwrap()
                        .cmp(other.0.borrow().iter().next().unwrap())
                }
            }
            otherwise => otherwise,
        }
    }
}

impl PartialOrd for Group {
    fn partial_cmp(&self, other: &Group) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Hash for Group {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.0.borrow().hash(hasher);
    }
}

fn basket_price(basket: &GroupedBasket) -> Price {
    basket.iter().map(|g| g.price()).sum()
}

/// Compute the hash of a GroupedBasket
///
/// Note that we don't actually care at all about the _values_ within
/// the groups, only their lengths. Therefore, let's hash not the actual
/// GB but its lengths.
fn hash_of(basket: &GroupedBasket) -> u64 {
    let lengths = basket
        .iter()
        .map(|g| g.0.borrow().len())
        .collect::<Vec<_>>();
    let mut hasher = DefaultHasher::new();
    lengths.hash(&mut hasher);
    hasher.finish()
}

pub fn lowest_price(books: &[Book]) -> Price {
    DecomposeGroups::new(books)
        .map(|gb| basket_price(&gb))
        .min()
        .unwrap_or(0)
}

struct DecomposeGroups {
    prev_states: HashSet<u64>,
    next: Option<GroupedBasket>,
}

impl Iterator for DecomposeGroups {
    type Item = GroupedBasket;
    fn next(&mut self) -> Option<Self::Item> {
        // our goal here: produce a stream of valid groups, differentiated by their
        // counts, from most compact to most dispersed.
        //
        // Algorithm:
        //  - Start with the most compact groups possible
        //  - If the number of groups == 0 or the max population of any group == 1, return None
        //  - For every item in the most populous group:
        //      - Try removing it and adding it to a smaller group.
        //          - Can any smaller group accept it? if yes, move it there and return
        //  - If it cannot be added to any smaller group, try the next item from this set
        //  - If no item from the most populous group can be added to any smaller group,
        //    then move the last item from the most populous group into a new group, alone,
        //    and return
        let return_value = self.next.clone();
        if let Some(groups) = mem::replace(&mut self.next, None) {
            if !(groups.is_empty() || groups.iter().all(|g| g.0.borrow().len() == 1)) {
                let mut hypothetical;
                for mpg_book in groups[0].0.borrow().iter() {
                    for (idx, other_group) in groups[1..].iter().enumerate() {
                        if !other_group.0.borrow().contains(mpg_book) {
                            hypothetical = groups.clone();
                            hypothetical[0].0.borrow_mut().remove(mpg_book);
                            hypothetical[1 + idx].0.borrow_mut().insert(*mpg_book);
                            hypothetical.sort();
                            let hypothetical_hash = hash_of(&hypothetical);
                            if !self.prev_states.contains(&hypothetical_hash) {
                                self.prev_states.insert(hypothetical_hash);
                                mem::replace(&mut self.next, Some(hypothetical));
                                return return_value;
                            }
                        }
                    }
                }
                // we've gone through all the items of the most populous group,
                // and none of them can be added to any other existing group.
                // We need to create a new group;
                let book = {
                    let backing_bt = groups[0].0.borrow();
                    let mut book_iter = backing_bt.iter();
                    book_iter.next().unwrap().clone()
                };
                hypothetical = groups.clone();
                hypothetical[0].0.borrow_mut().remove(&book);
                hypothetical.push(Group::new_containing(book));
                hypothetical.sort();
                self.prev_states.insert(hash_of(&hypothetical));
                mem::replace(&mut self.next, Some(hypothetical));
            }
        }
        return_value
    }
}

impl DecomposeGroups {
    fn new(books: &[Book]) -> DecomposeGroups {
        let mut book_groups = GroupedBasket::new();
        'nextbook: for book in books {
            for idx in 0..book_groups.len() {
                if !book_groups[idx].0.borrow().contains(&book) {
                    book_groups[idx].0.borrow_mut().insert(*book);
                    continue 'nextbook;
                }
            }
            // if we're here, we still haven't found a place for the book.
            // better add it to a new group
            book_groups.push(Group::new_containing(*book));
        }
        book_groups.sort();

        DecomposeGroups {
            next: Some(book_groups),
            prev_states: HashSet::new(),
        }
    }
}

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?