aoc/year2017/
day22.rs

1//! # Sporifica Virus
2//!
3//! Brute force solution using a fixed size grid, relying on the properties of the input to never
4//! exceed the bounds. Some bit manipulation tricks are used to speeds things up slightly.
5use crate::util::grid::*;
6use crate::util::point::*;
7
8pub fn parse(input: &str) -> Grid<u8> {
9    Grid::parse(input)
10}
11
12pub fn part1(input: &Grid<u8>) -> usize {
13    simulate(input, 10_000, 2)
14}
15
16pub fn part2(input: &Grid<u8>) -> usize {
17    simulate(input, 10_000_000, 1)
18}
19
20fn simulate(input: &Grid<u8>, bursts: usize, delta: usize) -> usize {
21    // Assume that the carrier will never go outside the range [0, 512] in both x and y axis.
22    // starting at the center (256, 256).
23    let full = 512;
24    let half = 256;
25    // Right, Down, Left, Up
26    let offsets = [1, full, 0_usize.wrapping_sub(1), 0_usize.wrapping_sub(full)];
27
28    // Copy input
29    let mut grid = vec![1; full * full];
30    let offset = half - (input.width / 2) as usize;
31
32    for x in 0..input.width {
33        for y in 0..input.height {
34            if input[Point::new(x, y)] == b'#' {
35                let index = full * (offset + y as usize) + (offset + x as usize);
36                grid[index] = 3; // Infected
37            }
38        }
39    }
40
41    let mut index = full * half + half; // Center
42    let mut direction = 3; // Up
43    let mut result = 0;
44
45    for _ in 0..bursts {
46        // Change state by adding either `2` for part one (flipping between clean and infected)
47        // or `1` for part two (using all four states).
48        // Clean => 1
49        // Weakened => 2
50        // Infected => 3
51        // Flagged => 0
52        let current = grid[index] as usize;
53        let next = (current + delta) & 0x3;
54        grid[index] = next as u8;
55        // Infected nodes result in a value of 4 >> 2 = 1, all other nodes result in 0.
56        result += (next + 1) >> 2;
57        // Change direction by adding an index modulo 4 depending on node type.
58        // Clean => 1 + 2 => 3 (left)
59        // Weakened => 2 + 2 => 0 (straight)
60        // Infected => 3 + 2 => 1 (right)
61        // Flagged => 0 + 2 => 2 (reverse)
62        direction = (direction + current + 2) & 0x3;
63        index = index.wrapping_add(offsets[direction]);
64    }
65
66    result
67}
aoc/year2017/day22.rs

aoc/year2017/
day22.rs
