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

aoc/year2017/
day25.rs
