year2017/
day05.rs

1use utils::prelude::*;
2
3/// Counting steps through a maze of jump instructions.
4#[derive(Clone, Debug)]
5pub struct Day05 {
6    jumps: Vec<i32>,
7}
8
9type Compressed = usize;
10const BITS: usize = Compressed::BITS as usize;
11
12impl Day05 {
13    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
14        Ok(Self {
15            jumps: parser::i32().parse_lines(input)?,
16        })
17    }
18
19    #[must_use]
20    pub fn part1(&self) -> u64 {
21        let mut jumps = self.jumps.clone();
22        let mut steps = 0;
23        let mut pc = 0;
24
25        while pc < jumps.len() {
26            let offset = jumps[pc];
27            jumps[pc] += 1;
28            pc = pc.wrapping_add_signed(offset as isize);
29            steps += 1;
30        }
31
32        steps
33    }
34
35    #[must_use]
36    pub fn part2(&self) -> u64 {
37        let mut jumps = self.jumps.clone();
38        let mut steps = 0;
39        let mut pc = 0;
40
41        // After each jump instruction is run enough times the offset oscillates back and forth
42        // between 2 and 3. Once this happens, represent the jump as a single bit in a compressed
43        // bit mask, which allows processing multiple jumps at once without each one requiring a
44        // random memory read.
45        let mut threes: Vec<Compressed> = vec![0; jumps.len().next_multiple_of(BITS) / BITS];
46        // boundary represents the point where all prior jumps have stabilized on oscillating
47        // between 2 and 3
48        let mut boundary = 0;
49
50        while pc < jumps.len() {
51            let offset = jumps[pc];
52            jumps[pc] += if offset >= 3 { -1 } else { 1 };
53
54            if pc == boundary && (jumps[pc] == 2 || jumps[pc] == 3) {
55                // Next jump after the boundary stabilized on 2/3
56                boundary += 1;
57
58                let element_index = pc / BITS;
59                let bit_index = pc % BITS;
60                threes[element_index] |= ((jumps[pc] & 1) as Compressed) << bit_index;
61            }
62
63            pc = pc.wrapping_add_signed(offset as isize);
64            steps += 1;
65
66            while pc < boundary {
67                // While inside the boundary loop over each compressed element and handle the jumps
68                // in bulk
69                let element_index = pc / BITS;
70                let mut element = threes[element_index];
71
72                let bit_index = pc % BITS;
73                let mut bit = 1 << bit_index;
74
75                let max = boundary.min((element_index + 1) * BITS);
76                while pc < max {
77                    let offset = 2 + usize::from(element & bit != 0);
78                    element ^= bit;
79                    bit <<= offset;
80                    pc += offset;
81                    steps += 1;
82                }
83
84                threes[element_index] = element;
85            }
86        }
87
88        steps
89    }
90}
91
92examples!(Day05 -> (u64, u64) [
93    {input: "0\n3\n0\n1\n-3", part1: 5, part2: 10},
94]);
year2017/day05.rs

year2017/
day05.rs
