aoc/year2017/
day25.rs

1//! # The Halting Problem
2//!
3//! The input is parsed into a 2-dimensional array covering each possible combination of state
4//! and tape value at the cursor. Each transition is then computed via a lookup into this array.
5//!
6//! To speed things up by about ten times, multiple transitions are then precomputed to allow
7//! skipping forward multiple steps at a time. Blocks 128 cells wide are cached once the cursor
8//! moves off either end.
9//!
10//! Interestingly, the total number of distinct cached blocks is very low, approximately 200.
11//! The cursor also doesn't move too far, only covering a range of about 6,000 steps.
12use std::iter::repeat_with;
13
14use crate::util::hash::*;
15use crate::util::parse::*;
16
17const UPPER: u128 = u128::MAX << 64;
18const LOWER: u128 = u128::MAX >> 64;
19
20pub struct Input {
21    state: usize,
22    steps: u32,
23    rules: Vec<[Rule; 2]>,
24}
25
26struct Rule {
27    next_state: usize,
28    next_tape: bool,
29    advance: bool,
30}
31
32impl Rule {
33    fn parse(block: &[&[u8]]) -> Self {
34        let next_tape = block[0][22] == b'1';
35        let advance = block[1][27] == b'r';
36        let next_state = (block[2][26] - b'A') as usize;
37        Self { next_state, next_tape, advance }
38    }
39}
40
41struct Skip {
42    next_state: usize,
43    next_tape: u128,
44    steps: u32,
45    advance: bool,
46}
47
48/// Parse the input into 12 rules for each possible combination of state and value at the cursor.
49pub fn parse(input: &str) -> Input {
50    let lines: Vec<_> = input.lines().map(str::as_bytes).collect();
51
52    let state = (lines[0][15] - b'A') as usize;
53    let steps = input.unsigned();
54    let rules: Vec<_> = lines[3..]
55        .chunks(10)
56        .map(|chunk| [Rule::parse(&chunk[2..5]), Rule::parse(&chunk[6..9])])
57        .collect();
58
59    Input { state, steps, rules }
60}
61
62pub fn part1(input: &Input) -> u32 {
63    let mut state = input.state;
64    let mut remaining = input.steps;
65    let mut tape = 0;
66    let mut left = Vec::new();
67    let mut right = Vec::new();
68    let mut cache: Vec<_> = repeat_with(FastMap::new).take(input.rules.len()).collect();
69
70    loop {
71        // Lookup the next batch state transition.
72        let Skip { next_state, next_tape, steps, advance } = *cache[state]
73            .entry(tape)
74            .or_insert_with(|| turing(&input.rules, state, tape, u32::MAX));
75
76        // Handle any remaining transitions less than the batch size one step at a time.
77        if steps > remaining {
78            let Skip { next_tape, .. } = turing(&input.rules, state, tape, remaining);
79            left.push(next_tape);
80            break;
81        }
82
83        state = next_state;
84        tape = next_tape;
85        remaining -= steps;
86
87        // Use a vector to simulate an empty tape. In practice the cursor doesn't move more than
88        // a few thousand steps in any direction, so this approach is as fast as a fixed-size
89        // array, but much more robust.
90        if advance {
91            left.push(tape & UPPER);
92            tape = (tape << 64) | right.pop().unwrap_or(0);
93        } else {
94            right.push(tape & LOWER);
95            tape = (tape >> 64) | left.pop().unwrap_or(0);
96        }
97    }
98
99    left.into_iter().chain(right).map(u128::count_ones).sum()
100}
101
102pub fn part2(_input: &Input) -> &'static str {
103    "n/a"
104}
105
106/// Precompute state transitions up to some maximum value of steps.
107#[inline]
108fn turing(rules: &[[Rule; 2]], mut state: usize, mut tape: u128, max_steps: u32) -> Skip {
109    let mut mask = 1 << 63;
110    let mut steps = 0;
111
112    // `0` means the cursor has advanced to the next half on the right.
113    // `128` means that the cursor is on the left edge of the high half.
114    while 0 < mask && mask < (1 << 127) && steps < max_steps {
115        let current = usize::from(tape & mask != 0);
116        let rule = &rules[state][current];
117
118        tape = if rule.next_tape { tape | mask } else { tape & !mask };
119        mask = if rule.advance { mask >> 1 } else { mask << 1 };
120        state = rule.next_state;
121        steps += 1;
122    }
123
124    Skip { next_state: state, next_tape: tape, steps, advance: mask == 0 }
125}
aoc/year2017/day25.rs

aoc/year2017/
day25.rs
