aoc/year2016/day18.rs
1//! # Like a Rogue
2//!
3//! We represent a trap with a 1 bit and a safe tile with a 0 bit.
4//! Writing out the [truth table](https://en.wikipedia.org/wiki/Truth_table) for the rules:
5//!
6//! | Left | Center | Right | Output |
7//! | ---- | ------ | ----- | ------ |
8//! | 1 | 1 | 0 | 1 |
9//! | 0 | 1 | 1 | 1 |
10//! | 1 | 0 | 0 | 1 |
11//! | 0 | 0 | 1 | 1 |
12//! | 1 | 1 | 1 | 0 |
13//! | 0 | 1 | 0 | 0 |
14//! | 1 | 0 | 1 | 0 |
15//! | 0 | 0 | 0 | 0 |
16//!
17//! We can see that the value of the center doesn't matter and that the next tile will be a trap
18//! if the left and right values are different. We calculate this for all traps at the same time
19//! with a bitwise [XOR](https://en.wikipedia.org/wiki/XOR_gate).
20//!
21//! Since even columns depend only on odd columns and vice-versa, we split the input into two,
22//! storing each half using 50 bits of a `u64`.
23pub fn parse(input: &str) -> &str {
24 input.trim()
25}
26
27pub fn part1(input: &str) -> usize {
28 count(input, 40)
29}
30
31pub fn part2(input: &str) -> usize {
32 count(input, 400_000)
33}
34
35fn count(input: &str, rows: usize) -> usize {
36 // We don't use all the bits in each `u64` so create a mask the same width as
37 // half the input to prevent bits spilling over.
38 let mask = (1 << (input.len() / 2)) - 1;
39 // Represent each trap as a `1` bit.
40 let traps = |acc: u64, b: u8| (acc << 1) | (b == b'^') as u64;
41
42 // Split traps into two halves.
43 let mut even = input.bytes().step_by(2).fold(0, traps);
44 let mut odd = input.bytes().skip(1).step_by(2).fold(0, traps);
45 let mut total = 0;
46
47 for _ in 0..rows {
48 // Count the traps in each row.
49 total += even.count_ones() + odd.count_ones();
50
51 // Calculate the next row of even traps from odd traps and vice-versa.
52 (even, odd) = (odd ^ (odd >> 1), even ^ ((even << 1) & mask));
53 }
54
55 // We want the number of safe tiles so convert from the number of traps.
56 input.len() * rows - total as usize
57}