aoc/year2017/
day05.rs

1//! # A Maze of Twisty Trampolines, All Alike
2//!
3//! Part one brute forces the jumps. For part two we can make an observation that the jumps offsets
4//! will eventually flip flop between 2 or 3 starting from the beginning, for example:
5//!
6//! ```none
7//!     2 3 2 3 -1
8//! ```
9//!
10//! The twos and threes can be represented in binary compact form, using 0 for 2 and 1 for 3:
11//!
12//! ```none
13//!     0101
14//! ```
15//!
16//! We then precompute all possible combinations for blocks of width 16,
17//! using this to accelerate part two.
18use crate::util::parse::*;
19use std::array::from_fn;
20
21pub fn parse(input: &str) -> Vec<i32> {
22    input.iter_signed().collect()
23}
24
25/// Brute force implementation.
26pub fn part1(input: &[i32]) -> usize {
27    let mut jump = input.to_vec();
28    let mut total = 0;
29    let mut index = 0;
30
31    while index < jump.len() {
32        let next = index.wrapping_add(jump[index] as usize);
33        jump[index] += 1;
34        total += 1;
35        index = next;
36    }
37
38    total
39}
40
41#[expect(clippy::needless_range_loop)]
42pub fn part2(input: &[i32]) -> usize {
43    let mut jump = input.to_vec();
44    let mut total = 0;
45    let mut index = 0;
46
47    let mut fine = 0;
48    let mut coarse = 0;
49    let mut compact = Vec::new();
50
51    // Precompute all possible combinations for each binary starting number from 0 to 2^16,
52    // starting at any offset from 0..2.
53    let cache: Vec<[_; 0x10000]> =
54        (0..3).map(|offset| from_fn(|value| compute_block(value, offset))).collect();
55
56    while index < jump.len() {
57        if index < coarse {
58            if index % 16 >= 3 {
59                let j = index / 16;
60                let (next, steps, delta) = compute_block(compact[j], index % 16);
61
62                compact[j] = next as usize;
63                total += steps as usize;
64                index += delta as usize;
65            }
66
67            // Index lies within precomputed blocks.
68            for j in (index / 16)..(coarse / 16) {
69                let value = compact[j];
70                let (next, steps, delta) = cache[index % 16][value];
71
72                compact[j] = next as usize;
73                total += steps as usize;
74                index += delta as usize;
75            }
76        } else {
77            // Fall back to part one approach.
78            let next = index.wrapping_add(jump[index] as usize);
79            jump[index] += if jump[index] == 3 { -1 } else { 1 };
80            total += 1;
81
82            // The frontier of twos and threes advances through the jump offsets.
83            // Each time it crosses a block of 16 add to the compact binary representation.
84            if jump[index] == 2 && index == fine {
85                fine += 1;
86                if fine.is_multiple_of(16) {
87                    let value = (coarse..fine).rev().fold(0, |acc, i| (acc << 1) | (jump[i] & 1));
88                    coarse = fine;
89                    compact.push(value as usize);
90                }
91            }
92
93            index = next;
94        }
95    }
96
97    total
98}
99
100#[inline]
101fn compute_block(mut value: usize, mut offset: usize) -> (u16, u8, u8) {
102    let start = offset;
103    let mut steps = 0;
104
105    while offset < 16 {
106        value ^= 1 << offset;
107        steps += 1;
108        offset += 3 - ((value >> offset) & 1);
109    }
110
111    (value as u16, steps, (offset - start) as u8)
112}
aoc/year2017/day05.rs

aoc/year2017/
day05.rs
