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 storing the entire row
4//! in a [`u128`]. We then use bitwise logic to calculate the next row.
5//!
6//! Writing out the [truth table](https://en.wikipedia.org/wiki/Truth_table) for the rules:
7//!
8//! | Left | Center | Right |
9//! | ---- | ------ | ----- |
10//! |    1 |      1 |     0 |
11//! |    0 |      1 |     1 |
12//! |    1 |      0 |     0 |
13//! |    0 |      0 |     1 |
14//!
15//! We can see that the value of the center doesn't matter and that the next tile will be a trap
16//! if the left and right values are different. We calculate this for all traps at the same time
17//! with a bitwise [XOR](https://en.wikipedia.org/wiki/XOR_gate).
18pub fn parse(input: &str) -> &str {
19    input.trim()
20}
21
22pub fn part1(input: &str) -> u32 {
23    count(input, 40)
24}
25
26pub fn part2(input: &str) -> u32 {
27    count(input, 400_000)
28}
29
30fn count(input: &str, rows: u32) -> u32 {
31    let width = input.len() as u32;
32    // We don't use the full 128 bit width so create a mask the same width as the input
33    // to prevent bits spilling over.
34    let mask = (1 << width) - 1;
35
36    // Represent each trap as a `1` bit.
37    let mut total = 0;
38    let mut row = input.bytes().fold(0, |acc, b| (acc << 1) | (b == b'^') as u128);
39
40    for _ in 0..rows {
41        // Count the traps in each row.
42        total += row.count_ones();
43        // Only consider the left and right values for the next row.
44        row = ((row << 1) ^ (row >> 1)) & mask;
45    }
46
47    // We want the number of safe tiles so convert from the number of traps.
48    rows * width - total
49}
aoc/year2016/day18.rs

aoc/year2016/
day18.rs
