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