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 jump offsets
4//! will eventually flip-flop between 2 and 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 std::array::from_fn;
19
20use crate::util::parse::*;
21
22pub fn parse(input: &str) -> Vec<isize> {
23    input.iter_signed().collect()
24}
25
26/// Brute force implementation.
27pub fn part1(input: &[isize]) -> usize {
28    let mut jump = input.to_vec();
29    let mut total = 0;
30    let mut index = 0;
31
32    while index < jump.len() {
33        let next = index.wrapping_add_signed(jump[index]);
34        jump[index] += 1;
35        total += 1;
36        index = next;
37    }
38
39    total
40}
41
42pub fn part2(input: &[isize]) -> 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¹⁶,
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 value in &mut compact[(index / 16)..(coarse / 16)] {
69                let (next, steps, delta) = cache[index % 16][*value];
70
71                *value = next as usize;
72                total += steps as usize;
73                index += delta as usize;
74            }
75        } else {
76            // Fall back to part one approach.
77            let next = index.wrapping_add_signed(jump[index]);
78            jump[index] += if jump[index] == 3 { -1 } else { 1 };
79            total += 1;
80
81            // The frontier of twos and threes advances through the jump offsets.
82            // Each time it crosses a block of 16 add to the compact binary representation.
83            if jump[index] == 2 && index == fine {
84                fine += 1;
85                if fine.is_multiple_of(16) {
86                    let value = (coarse..fine).rev().fold(0, |acc, i| (acc << 1) | (jump[i] & 1));
87                    coarse = fine;
88                    compact.push(value as usize);
89                }
90            }
91
92            index = next;
93        }
94    }
95
96    total
97}
98
99#[inline]
100fn compute_block(mut value: usize, mut offset: usize) -> (u16, u8, u8) {
101    let start = offset;
102    let mut steps = 0;
103
104    while offset < 16 {
105        value ^= 1 << offset;
106        steps += 1;
107        offset += 3 - ((value >> offset) & 1);
108    }
109
110    (value as u16, steps, (offset - start) as u8)
111}
aoc/year2017/day05.rs

aoc/year2017/
day05.rs
