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

aoc/year2017/
day25.rs
