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}