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.
8//!
9//! For each of the 6 * 256 = 1536 combinations of a tape with 4 values to the left and 3 values
10//! to the right of the cursor, the turing machine is computed one steps at a time until the cursor
11//! leaves the area to the left or to the right. For example:
12//!
13//! ```none
14//!     State: A            => State: B
15//!       1 0 1 0 [1] 0 0 1     [0] 0 1 0 0 1 1 0
16//!
17//!     State: B
18//!       t t t t [0] 0 1 0
19//! ```
20//!
21//! In this example the tape then advances four bits to the left, loading the four values of `t`
22//! then the next batch lookup is performed.
23use crate::util::parse::*;
24use std::array::from_fn;
25
26pub struct Input {
27    state: usize,
28    steps: u32,
29    rules: Vec<[Rule; 2]>,
30}
31
32struct Rule {
33    next_state: usize,
34    next_tape: usize,
35    advance: bool,
36}
37
38impl Rule {
39    fn parse(block: &[&[u8]]) -> Self {
40        let next_tape = (block[0][22] - b'0') as usize;
41        let advance = block[1][27] == b'r';
42        let next_state = (block[2][26] - b'A') as usize;
43        Rule { next_state, next_tape, advance }
44    }
45}
46
47struct Skip {
48    next_state: usize,
49    next_tape: usize,
50    steps: u32,
51    ones: i32,
52    advance: bool,
53}
54
55/// Parse the input into 12 rules for each possible combination of state and value at the cursor.
56pub fn parse(input: &str) -> Input {
57    let lines: Vec<_> = input.lines().map(str::as_bytes).collect();
58
59    let state = (lines[0][15] - b'A') as usize;
60    let steps = input.unsigned();
61    let rules: Vec<_> = lines[3..]
62        .chunks(10)
63        .map(|chunk| [Rule::parse(&chunk[2..5]), Rule::parse(&chunk[6..9])])
64        .collect();
65
66    Input { state, steps, rules }
67}
68
69pub fn part1(input: &Input) -> i32 {
70    // Precompute state transitions in larger amount in order to skip forward several transitions
71    // at a time. 100 max_steps is a safety valve in case some state transitions do not halt
72    // although this is unlikely for the inputs that are provided.
73    let table: Vec<[Skip; 256]> = (0..input.rules.len())
74        .map(|state| from_fn(|tape| turing(&input.rules, state, tape, 100)))
75        .collect();
76
77    let mut state = input.state;
78    let mut remaining = input.steps;
79    let mut tape = 0;
80    let mut checksum = 0;
81    let mut left = Vec::new();
82    let mut right = Vec::new();
83
84    loop {
85        // Lookup the next batch state transition.
86        let Skip { next_state, next_tape, steps, ones, advance } = table[state][tape];
87
88        // Handle any remaining transitions less than the batch size one step at a time.
89        if steps > remaining {
90            let Skip { ones, .. } = turing(&input.rules, state, tape, remaining);
91            break checksum + ones;
92        }
93
94        state = next_state;
95        tape = next_tape;
96        remaining -= steps;
97        checksum += ones;
98
99        // Use a vector to simulate an empty tape. In practise the cursor doesn't move more than
100        // a few thousand steps in any direction, so this approach is as fast as a fixed size
101        // array, but much more robust.
102        if advance {
103            left.push(tape & 0xf0);
104            tape = ((tape & 0xf) << 4) | right.pop().unwrap_or(0);
105        } else {
106            right.push(tape & 0xf);
107            tape = (tape >> 4) | left.pop().unwrap_or(0);
108        }
109    }
110}
111
112pub fn part2(_input: &Input) -> &'static str {
113    "n/a"
114}
115
116// Precompute state transitions up to some maximum value of steps.
117fn turing(rules: &[[Rule; 2]], mut state: usize, mut tape: usize, max_steps: u32) -> Skip {
118    let mut mask = 0b00001000;
119    let mut steps = 0;
120    let mut ones = 0;
121
122    // `0`` means the cursor has advanced to the next nibble on the right.
123    // `128` means that the cursor is on the left edge of the high nibble.
124    while 0 < mask && mask < 128 && steps < max_steps {
125        let current = ((tape & mask) != 0) as usize;
126        let Rule { next_state, next_tape, advance } = rules[state][current];
127
128        if next_tape == 1 {
129            tape |= mask;
130        } else {
131            tape &= !mask;
132        }
133
134        if advance {
135            mask >>= 1;
136        } else {
137            mask <<= 1;
138        }
139
140        state = next_state;
141        steps += 1;
142        // Count the total numbers of ones by summing the number of ones written minus the
143        // number of ones erased.
144        ones += next_tape as i32 - current as i32;
145    }
146
147    Skip { next_state: state, next_tape: tape, steps, ones, advance: mask == 0 }
148}
aoc/year2017/day25.rs

aoc/year2017/
day25.rs
