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 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
41pub fn part2(input: &[i32]) -> usize {
42    let mut jump = input.to_vec();
43    let mut total = 0;
44    let mut index = 0;
45
46    let mut fine = 0;
47    let mut coarse = 0;
48    let mut compact = Vec::new();
49
50    // Precompute all possible combinations for each binary starting number from 0 to 2¹⁶,
51    // starting at any offset from 0..2.
52    let cache: Vec<[_; 0x10000]> =
53        (0..3).map(|offset| from_fn(|value| compute_block(value, offset))).collect();
54
55    while index < jump.len() {
56        if index < coarse {
57            if index % 16 >= 3 {
58                let j = index / 16;
59                let (next, steps, delta) = compute_block(compact[j], index % 16);
60
61                compact[j] = next as usize;
62                total += steps as usize;
63                index += delta as usize;
64            }
65
66            // Index lies within precomputed blocks.
67            for value in &mut compact[(index / 16)..(coarse / 16)] {
68                let (next, steps, delta) = cache[index % 16][*value];
69
70                *value = next as usize;
71                total += steps as usize;
72                index += delta as usize;
73            }
74        } else {
75            // Fall back to part one approach.
76            let next = index.wrapping_add(jump[index] as usize);
77            jump[index] += if jump[index] == 3 { -1 } else { 1 };
78            total += 1;
79
80            // The frontier of twos and threes advances through the jump offsets.
81            // Each time it crosses a block of 16 add to the compact binary representation.
82            if jump[index] == 2 && index == fine {
83                fine += 1;
84                if fine.is_multiple_of(16) {
85                    let value = (coarse..fine).rev().fold(0, |acc, i| (acc << 1) | (jump[i] & 1));
86                    coarse = fine;
87                    compact.push(value as usize);
88                }
89            }
90
91            index = next;
92        }
93    }
94
95    total
96}
97
98#[inline]
99fn compute_block(mut value: usize, mut offset: usize) -> (u16, u8, u8) {
100    let start = offset;
101    let mut steps = 0;
102
103    while offset < 16 {
104        value ^= 1 << offset;
105        steps += 1;
106        offset += 3 - ((value >> offset) & 1);
107    }
108
109    (value as u16, steps, (offset - start) as u8)
110}
aoc/year2017/day05.rs

aoc/year2017/
day05.rs
