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 combination for blocks of size 16, using this to accelerate
17//! part two.
18use crate::util::parse::*;
19
20const WIDTH: usize = 16;
21const LENGTH: usize = 1 << WIDTH;
22
23pub fn parse(input: &str) -> Vec<i32> {
24    input.iter_signed().collect()
25}
26
27/// Brute force implementation.
28pub fn part1(input: &[i32]) -> usize {
29    let mut jump = input.to_vec();
30    let mut total = 0;
31    let mut index = 0;
32
33    while index < jump.len() {
34        let next = index.wrapping_add(jump[index] as usize);
35        jump[index] += 1;
36        total += 1;
37        index = next;
38    }
39
40    total
41}
42
43#[expect(clippy::needless_range_loop)]
44pub fn part2(input: &[i32]) -> usize {
45    let mut jump = input.to_vec();
46    let mut total = 0;
47    let mut index = 0;
48
49    let mut fine = 0;
50    let mut coarse = 0;
51    let mut compact = Vec::new();
52    let mut cache = vec![[(0_u16, 0_u8, 0_u8); LENGTH]; WIDTH];
53
54    // Precompute all possible combinations. For each binary starting number we can start at any
55    // offset from 0..16.
56    for i in 0..WIDTH {
57        for j in 0..LENGTH {
58            let mut offset = i as u16;
59            let mut value = j as u16;
60            let mut steps = 0;
61
62            while offset < 16 {
63                value ^= 1 << offset;
64                steps += 1;
65                offset += 3 - ((value >> offset) & 1);
66            }
67
68            cache[i][j] = (value, steps, offset as u8 - i as u8);
69        }
70    }
71
72    while index < jump.len() {
73        if index < coarse {
74            // Index lies withing precomputed blocks.
75            let base = index / 16;
76            let offset = index % 16;
77            let value = compact[base] as usize;
78            let (next, steps, delta) = cache[offset][value];
79
80            compact[base] = next;
81            total += steps as usize;
82            index += delta as usize;
83        } else {
84            // Fall back to part one approach.
85            let next = index.wrapping_add(jump[index] as usize);
86            jump[index] += if jump[index] == 3 { -1 } else { 1 };
87            total += 1;
88
89            // The frontier of twos and threes advances through the jump offsets.
90            // Each time it crosses a block of 16 add to the compact binary representation.
91            if jump[index] == 2 && index == fine {
92                fine += 1;
93                if fine.is_multiple_of(16) {
94                    let value = (coarse..fine).rev().fold(0, |acc, i| (acc << 1) | (jump[i] & 1));
95                    coarse = fine;
96                    compact.push(value as u16);
97                }
98            }
99
100            index = next;
101        }
102    }
103
104    total
105}
aoc/year2017/day05.rs

aoc/year2017/
day05.rs
