Milestone M0

The Rust Warm-Up

Unlike the milestones that follow, this one builds nothing of the language itself. It is a warm-up: a way to get the tools working and the metalanguage familiar before the interpreter starts. If you already write Rust comfortably, read the specification below, confirm your solution against the self-check tests, and move on to Milestone M1. Work through Appendix A alongside this milestone.

What you will build

A coin purse: a little Rust program for holding coins and counting money. It exercises the enum, struct, match, collection, and ownership patterns every later milestone rests on, and it asks you to make one representation decision: the same kind of decision the interpreter turns on again and again. Nothing here touches Bridger.

Getting Rust running

Install Rust with rustup, then start a fresh library project:

cargo new --lib coin_purse
cd coin_purse
cargo test      # runs the sample test cargo generated

If it reports one passing test, the toolchain is ready. You will write the whole coin purse in src/lib.rs: replace its contents with the scaffold at the end of this chapter and fill in the parts marked for you.

The coins

A coin is one of four kinds, each worth a fixed number of cents:

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Coin { Penny, Nickel, Dime, Quarter }

Coin	Cents
`Penny`	1
`Nickel`	5
`Dime`	10
`Quarter`	25

The derive line is what lets a coin be copied, compared with ==, printed with {:?}, and used as a HashMap key — Appendix A explains each trait. The worth of a coin is a match over Coin, written as the free function cents, and every operation below reuses it.

The purse

A purse is a collection of coins, and it is a struct. Its interface is fixed — the methods in the scaffold, with the signatures given there. What the struct holds is yours to choose: this is the first design decision the book asks of you, the same choice, in miniature, that Values and runtime errors makes for the interpreter’s own values. Three reasonable representations, each making some operations easy and others a loop:

a Vec<Coin> — every coin listed individually; add is one push, value a fold over the coins;
a HashMap<Coin, u64> — each kind paired with how many the purse holds; combine merges counts;
four u64 fields, one count per kind, since the set of coins is finite and known; value is then four multiplications.

Pick one, and be ready to say what it made easy and what it made harder.

The operations, and what each is doing:

value — sum cents over the coins the purse holds. Borrows the purse (&self).
count — how many coins in total. Borrows the purse. It is what lets a test confirm exchange actually reduced the coin count.
add — put one coin in. Mutates the purse (&mut self).
remove — take one coin of kind c out if present, returning true; return false when the purse held none of that kind. Mutates the purse.
combine — take both purses by value (self, other: Purse) and return one holding every coin of each. Taking them by value is natural here: combining consumes them, and Rust’s move rule then stops you from using a purse you have already emptied into another.
exchange — return a purse of the same total value using the fewest coins. With these denominations the greedy rule is optimal: take as many quarters as fit, then dimes, then nickels, then pennies. (That greedy step is not optimal for every possible set of denominations; it is for these four, which is the assumption you may rely on.)

Worked examples

Purse::new().value()                         =  0     // empty
Purse::new().count()                         =  0

{Quarter, Dime, Nickel, Penny}.value()       =  41
{Quarter, Dime, Nickel, Penny}.count()       =  4

{Dime × 4}.exchange()   =  {Quarter, Dime, Nickel}      // 40¢: 4 coins -> 3
{Penny × 30}.exchange() =  {Quarter, Nickel}            // 30¢: 30 coins -> 2

{Quarter}.combine({Dime, Nickel})  =  {Quarter, Dime, Nickel}   // value 40

exchange never changes what a purse is worth — only how many coins carry that worth.

The scaffold

Here is src/lib.rs in full. Fill in the struct’s fields and every todo!() body; the tests are written for you. todo!() is a macro that compiles as any type but panics (runtime error) if it is ever reached, so the file builds even if you haven’t filled in any of the missing components. Try replacing the todo!()s one at a time and running cargo test as you go.

// src/lib.rs — coin purse (Milestone M0)
// Fill in the fields of `Purse` and every `todo!()`. Run `cargo test`.

// use std::collections::HashMap;   // uncomment for the HashMap representation

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Coin { Penny, Nickel, Dime, Quarter }

/// The worth of a single coin, in cents.
fn cents(c: Coin) -> u64 {
    todo!()
}

struct Purse {
    // Your representation. Pick one and delete the others:
    //   coins: Vec<Coin>,                          // every coin, listed
    //   counts: HashMap<Coin, u64>,                // each kind, a count
    //   pennies: u64, nickels: u64,                // one count per kind
    //   dimes: u64, quarters: u64,
}

impl Purse {
    /// An empty purse.
    fn new() -> Purse { todo!() }

    /// Put one coin into the purse.
    fn add(&mut self, c: Coin) { todo!() }

    /// Take one coin of kind `c` out, if the purse has one.
    /// Reports whether a coin was actually removed.
    fn remove(&mut self, c: Coin) -> bool { todo!() }

    /// The total worth of the purse, in cents.
    fn value(&self) -> u64 { todo!() }

    /// How many coins the purse holds in total.
    fn count(&self) -> u64 { todo!() }

    /// One purse holding every coin of `self` and `other`.
    fn combine(self, other: Purse) -> Purse { todo!() }

    /// A purse of the same total value using the fewest coins.
    fn exchange(&self) -> Purse { todo!() }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_purse_is_worth_nothing() {
        let p = Purse::new();
        assert_eq!(p.value(), 0);
        assert_eq!(p.count(), 0);
    }

    #[test]
    fn value_and_count_add_up() {
        let mut p = Purse::new();
        p.add(Coin::Quarter);
        p.add(Coin::Dime);
        p.add(Coin::Nickel);
        p.add(Coin::Penny);
        assert_eq!(p.value(), 41);
        assert_eq!(p.count(), 4);

        // another of a kind already present keeps counting
        p.add(Coin::Penny);
        assert_eq!(p.value(), 42);
        assert_eq!(p.count(), 5);
    }

    #[test]
    fn remove_reports_whether_it_found_a_coin() {
        let mut p = Purse::new();
        p.add(Coin::Quarter);
        p.add(Coin::Dime);

        assert_eq!(p.remove(Coin::Quarter), true);   // was there
        assert_eq!(p.remove(Coin::Quarter), false);  // now gone
        assert_eq!(p.remove(Coin::Nickel), false);   // never there
        assert_eq!(p.value(), 10);                   // only the dime
        assert_eq!(p.count(), 1);
    }

    #[test]
    fn combine_holds_every_coin_of_both() {
        let mut a = Purse::new();
        a.add(Coin::Quarter);
        let mut b = Purse::new();
        b.add(Coin::Dime);
        b.add(Coin::Nickel);

        let c = a.combine(b);            // consumes a and b
        assert_eq!(c.value(), 40);
        assert_eq!(c.count(), 3);
    }

    #[test]
    fn combine_with_empty_changes_nothing() {
        let mut a = Purse::new();
        a.add(Coin::Dime);
        let c = a.combine(Purse::new());
        assert_eq!(c.value(), 10);
        assert_eq!(c.count(), 1);
    }

    #[test]
    fn exchange_preserves_value_and_minimizes_coins() {
        let mut p = Purse::new();
        for _ in 0..30 { p.add(Coin::Penny); }       // 30¢ in 30 coins

        let mut q = p.exchange();
        assert_eq!(q.value(), 30);                    // same money
        assert_eq!(q.count(), 2);                     // a quarter, a nickel
        assert!(q.remove(Coin::Quarter));             // exactly those two
        assert!(q.remove(Coin::Nickel));
        assert_eq!(q.count(), 0);
    }

    #[test]
    fn exchange_of_four_dimes() {
        let mut p = Purse::new();
        for _ in 0..4 { p.add(Coin::Dime); }          // 40¢ in 4 coins
        let q = p.exchange();
        assert_eq!(q.value(), 40);
        assert_eq!(q.count(), 3);                     // quarter, dime, nickel
    }

    #[test]
    fn exchange_of_a_minimal_purse_keeps_the_count() {
        let mut p = Purse::new();
        p.add(Coin::Quarter);
        p.add(Coin::Nickel);                          // already minimal, 30¢
        let q = p.exchange();
        assert_eq!(q.value(), 30);
        assert_eq!(q.count(), 2);
    }

    #[test]
    fn exchange_of_empty_is_empty() {
        let q = Purse::new().exchange();
        assert_eq!(q.value(), 0);
        assert_eq!(q.count(), 0);
    }
}

Any correct implementation should satisfy the following two properties:
p.exchange().value() == p.value(), and p.exchange().count() <= p.count().
I.e., exchanging a purse always gives a purse of equal value using a fewer or equal number of coins.

Keyboard shortcuts