samgeo.codes

Day 2

Alright, day 2.

Problem statement

Rock Paper Scissors!

We are given a "strategy guide" that looks like:

A Y
B X
C Z

and we need to follow the provided scheme.

We save the example as input/02/example.txt and our input as input/02/input.txt.

Python time!

We create our solution in 2022/py/day02/sol.py and add a blank 2022/py/day02/__init__.py.

Software engineering best practices be damned, let's hard code everything! Since we know the score associated with each combination of moves, we can create a dictionary that maps each combination to the final score:

# 2022/py/day02/sol.py

from py.read_input import read_input


def main() -> int:
    input = read_input(2)
    scores = {
        "A X": 4,  # 3 + 1
        "A Y": 8,  # 6 + 2
        "A Z": 3,  # 0 + 3
        "B X": 1,  # 0 + 1
        "B Y": 5,  # 3 + 2
        "B Z": 9,  # 6 + 3
        "C X": 7,  # 6 + 1
        "C Y": 2,  # 0 + 2
        "C Z": 6,  # 3 + 3
    }
    result = sum(scores[line.strip()] for line in input.splitlines())
    print(f"Part one: {result}")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Part two involves a different scoring scheme, so we can take the same approach but with a different scores table:

# 2022/py/day02/sol.py

from typing import Final, Iterable, Mapping

from py.read_input import read_input


P1_SCORES: Final[dict[str, int]] = {
    "A X": 4,  # 3 + 1
    "A Y": 8,  # 6 + 2
    "A Z": 3,  # 0 + 3
    "B X": 1,  # 0 + 1
    "B Y": 5,  # 3 + 2
    "B Z": 9,  # 6 + 3
    "C X": 7,  # 6 + 1
    "C Y": 2,  # 0 + 2
    "C Z": 6,  # 3 + 3
}

P2_SCORES: Final[dict[str, int]] = {
    "A X": 3,  # 3 + 0
    "A Y": 4,  # 1 + 3
    "A Z": 8,  # 2 + 6
    "B X": 1,  # 1 + 0
    "B Y": 5,  # 2 + 3
    "B Z": 9,  # 3 + 6
    "C X": 2,  # 2 + 0
    "C Y": 6,  # 3 + 3
    "C Z": 7,  # 1 + 6
}


def score(games: Iterable[str], table: Mapping[str, int]) -> int:
    return sum(table[game] for game in games)


def main() -> int:
    input = read_input(2)
    games = [line.strip() for line in input.splitlines()]
    print(f"Part one: {score(games, P1_SCORES)}")
    print(f"Part two: {score(games, P2_SCORES)}")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

I guess one interesting note is the use of the Iterable type instead of list[str] for the games argument and the Mapping type instead of dict[str, int] for the table argument. In general when using type hints, it can be nice to get in the habit of accepting more general abstract types. It's not likely for this program, but you could imagine that someone might swap to using a set or frozenset to represent some collection. By using argument types like Iterable, you can enable users of functions to pass in a larger variety of inputs without additional copies or allocations. Additionally, immutable container types are covariant on their value types. Using immutable container argument types often makes your interfaces much more flexible.

Efficiency

This solution is optimal in terms of asymptotic complexity (it runs in linear time over the length of the input). But one idea we could try would be to use a match statement instead of a lookup table. It's unlikely that this will yield performance benefits since dictionary lookups are well optimized in Python. I'm more curious to see how these approaches fare in Rust, but let's try it in Python, just to see!

# 2022/py/day02/sol.py

from time import perf_counter
from typing import Callable, Final, Iterable, Mapping, Sequence

from py.read_input import read_input


P1_SCORES: Final[dict[str, int]] = {
    "A X": 4,  # 3 + 1
    "A Y": 8,  # 6 + 2
    "A Z": 3,  # 0 + 3
    "B X": 1,  # 0 + 1
    "B Y": 5,  # 3 + 2
    "B Z": 9,  # 6 + 3
    "C X": 7,  # 6 + 1
    "C Y": 2,  # 0 + 2
    "C Z": 6,  # 3 + 3
}

P2_SCORES: Final[dict[str, int]] = {
    "A X": 3,  # 3 + 0
    "A Y": 4,  # 1 + 3
    "A Z": 8,  # 2 + 6
    "B X": 1,  # 1 + 0
    "B Y": 5,  # 2 + 3
    "B Z": 9,  # 3 + 6
    "C X": 2,  # 2 + 0
    "C Y": 6,  # 3 + 3
    "C Z": 7,  # 1 + 6
}


def table_score(games: Iterable[str], table: Mapping[str, int]) -> int:
    return sum(table[game] for game in games)


def table_sol(games: Sequence[str]) -> tuple[int, int]:
    return table_score(games, P1_SCORES), table_score(games, P2_SCORES)


def score_fn_p1(game: str) -> int:
    match game:
        case "A X":
            return 4
        case "A Y":
            return 8
        case "A Z":
            return 3
        case "B X":
            return 1
        case "B Y":
            return 5
        case "B Z":
            return 9
        case "C X":
            return 7
        case "C Y":
            return 2
        case "C Z":
            return 6
        case _:
            raise ValueError(f"Invalid game: {game}")


def score_fn_p2(game: str) -> int:
    match game:
        case "A X":
            return 3
        case "A Y":
            return 4
        case "A Z":
            return 8
        case "B X":
            return 1
        case "B Y":
            return 5
        case "B Z":
            return 9
        case "C X":
            return 2
        case "C Y":
            return 6
        case "C Z":
            return 7
        case _:
            raise ValueError(f"Invalid game: {game}")


def match_score(games: Iterable[str], score_fn: Callable[[str], int]) -> int:
    return sum(score_fn(game) for game in games)


def match_sol(games: Sequence[str]) -> tuple[int, int]:
    return match_score(games, score_fn_p1), match_score(games, score_fn_p2)


def main() -> int:
    input = read_input(2)
    games = [line.strip() for line in input.splitlines()]
    expected_output = table_sol(games)
    print(f"Part one: {expected_output[0]}")
    print(f"Part two: {expected_output[1]}")

    def benchmark(solution: Callable[[Sequence[str]], tuple[int, int]]) -> float:
        start = perf_counter()
        for _ in range(1000):
            assert solution(games) == expected_output
        end = perf_counter()
        return end - start

    print(f"Table solution takes {benchmark(table_sol)}s")
    print(f"Match solution takes {benchmark(match_sol)}s")

    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Running this on my machine yields this result:

$ python -m py.day02.sol
Part one: 11906
Part two: 11186
Table solution takes 0.1719587080006022s
Match solution takes 0.38245958300103666s

So the match-based solution takes more than twice as long as the lookup table approach. I'm glad that Python now has some form of structural pattern matching, but a little bit sad about the performance gap to lookup tables, especially when compared with compiled languages like Rust or Standard ML.

So for Python, we'll stick with our original lookup table approach.

Rust!

Let's try the same exercise in Rust.

You know most of the boilerplate from day 1, so I'll gloss over most of those details.

We'll use the phf crate to build our lookup table.

$ cargo add phf phf_macros

use phf_macros::phf_map;

fn parse_games(input: &str) -> Vec<&str> {
    input.lines().map(str::trim).collect::<Vec<_>>()
}

static P1_SCORES: phf::Map<&'static str, i32> = phf_map! {
    "A X" => 3 + 1,
    "A Y" => 6 + 2,
    "A Z" => 0 + 3,
    "B X" => 0 + 1,
    "B Y" => 3 + 2,
    "B Z" => 6 + 3,
    "C X" => 6 + 1,
    "C Y" => 0 + 2,
    "C Z" => 3 + 3,
};

static P2_SCORES: phf::Map<&'static str, i32> = phf_map! {
    "A X" => 3 + 0,
    "A Y" => 1 + 3,
    "A Z" => 2 + 6,
    "B X" => 1 + 0,
    "B Y" => 2 + 3,
    "B Z" => 3 + 6,
    "C X" => 2 + 0,
    "C Y" => 3 + 3,
    "C Z" => 1 + 6,
};

fn table_score(games: &[&str], table: &phf::Map<&'static str, i32>) -> i32 {
    games
        .iter()
        .map(|game| table.get(game).expect("invalid game"))
        .sum()
}

pub fn table_sol(input: &str) -> (i32, i32) {
    let games = parse_games(input);
    (
        table_score(&games, &P1_SCORES),
        table_score(&games, &P2_SCORES),
    )
}

fn score_fn_p1(game: &str) -> i32 {
    match game {
        "A X" => 3 + 1,
        "A Y" => 6 + 2,
        "A Z" => 0 + 3,
        "B X" => 0 + 1,
        "B Y" => 3 + 2,
        "B Z" => 6 + 3,
        "C X" => 6 + 1,
        "C Y" => 0 + 2,
        "C Z" => 3 + 3,
        _ => panic!("invalid game: {game}"),
    }
}

fn score_fn_p2(game: &str) -> i32 {
    match game {
        "A X" => 3 + 0,
        "A Y" => 1 + 3,
        "A Z" => 2 + 6,
        "B X" => 1 + 0,
        "B Y" => 2 + 3,
        "B Z" => 3 + 6,
        "C X" => 2 + 0,
        "C Y" => 3 + 3,
        "C Z" => 1 + 6,
        _ => panic!("invalid game: {game}"),
    }
}

fn match_score(games: &[&str], score_fn: impl Fn(&str) -> i32) -> i32 {
    games.iter().cloned().map(score_fn).sum()
}

pub fn match_sol(input: &str) -> (i32, i32) {
    let games = parse_games(input);
    (
        match_score(&games, score_fn_p1),
        match_score(&games, score_fn_p2),
    )
}

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

    const EXAMPLE: &str = r#"A Y
B X
C Z"#;

    #[test]
    fn test_table_sol() {
        assert_eq!(table_sol(EXAMPLE), (15, 12));
    }

    #[test]
    fn test_match_sol() {
        assert_eq!(match_sol(EXAMPLE), (15, 12));
    }
}

Let's hook it all up in our main function:

use std::error::Error;

use day02::{match_sol, table_sol};

fn main() -> Result<(), Box<dyn Error>> {
    let input = include_str!("../../../../input/02/input.txt");
    let (tp1, tp2) = table_sol(input);
    println!("Table sol p1: {tp1}, p2: {tp2}");
    let (mp1, mp2) = match_sol(input);
    println!("Match sol p1: {mp1}, p2: {mp2}");
    Ok(())
}

We can run it and get our expected results:

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running `/Users/sgeisenh/projects/aoc/2022/rust/day02/target/debug/main`
Table sol p1: 11906, p2: 11186
Match sol p1: 11906, p2: 11186

Similarly, we add a benchmark file for criterion to use:

use std::hint::black_box;

use criterion::{criterion_group, criterion_main, Criterion};

static INPUT: &str = include_str!("../../../input/02/input.txt");

pub fn criterion_benchmark(c: &mut Criterion) {
    c.bench_function("table_sol", |b| {
        b.iter(|| day02::table_sol(black_box(INPUT)))
    });
    c.bench_function("match_sol", |b| {
        b.iter(|| day02::match_sol(black_box(INPUT)))
    });
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

And finally, we run our benchmarks:

$ cargo bench
    Finished bench [optimized] target(s) in 0.03s
     Running unittests src/lib.rs (/Users/sgeisenh/projects/aoc/2022/rust/day02/target/release/deps/day02-14b54ca39dda7916)

running 2 tests
test tests::test_match_sol ... ignored
test tests::test_table_sol ... ignored

test result: ok. 0 passed; 0 failed; 2 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/bin/main.rs (/Users/sgeisenh/projects/aoc/2022/rust/day02/target/release/deps/main-ea2d4c751f6a8144)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running benches/my_benchmark.rs (/Users/sgeisenh/projects/aoc/2022/rust/day02/target/release/deps/my_benchmark-24b0eacb110149e1)
Gnuplot not found, using plotters backend
table_sol               time:   [105.59 µs 105.63 µs 105.69 µs]
                        change: [-0.1857% -0.0658% +0.0629%] (p = 0.31 > 0.05)
                        No change in performance detected.
Found 4 outliers among 100 measurements (4.00%)
  1 (1.00%) high mild
  3 (3.00%) high severe

match_sol               time:   [47.056 µs 47.131 µs 47.222 µs]
                        change: [-6.3413% -5.8155% -5.1458%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
  1 (1.00%) high mild
  4 (4.00%) high severe

As expected, the match-based solution is significantly faster than the table lookup solution in Rust.

That's it!

I'm a little bit sad that day 1 had some more interesting algorithmic ideas to explore than day 2. Oh well. I'll probably jump to something like day 20 for my next post so we can get into some juicy ideas.