The Halting Problem - Advent of Code - 20171225

ac20171225.js

/*
Begin in state A.
Perform a diagnostic checksum after 12629077 steps.

In state A:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state B.
  If the current value is 1:
    - Write the value 0.
    - Move one slot to the left.
    - Continue with state B.

In state B:
  If the current value is 0:
    - Write the value 0.
    - Move one slot to the right.
    - Continue with state C.
  If the current value is 1:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state B.

In state C:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state D.
  If the current value is 1:
    - Write the value 0.
    - Move one slot to the left.
    - Continue with state A.

In state D:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state E.
  If the current value is 1:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state F.

In state E:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state A.
  If the current value is 1:
    - Write the value 0.
    - Move one slot to the left.
    - Continue with state D.

In state F:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state A.
  If the current value is 1:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state E.
*/

let turingMachine = function(steps) {
  let tape = [0];
  let slot = 0;
  let state = 'a';

  let machine = {
    a: {
      write: [1, 0],
      move: [1, -1],
      nextState: ['b', 'b']
    },
    b: {
      write: [0, 1],
      move: [1, -1],
      nextState: ['c', 'b']
    },
    c: {
      write: [1, 0],
      move: [1, -1],
      nextState: ['d', 'a']
    },
    d: {
      write: [1, 1],
      move: [-1, -1],
      nextState: ['e', 'f']
    },
    e: {
      write: [1, 0],
      move: [-1, -1],
      nextState: ['a', 'd']
    },
    f: {
      write: [1, 1],
      move: [1, -1],
      nextState: ['a', 'e']
    }
  };

  for (let i = 0; i < steps; i++) {
    //console.log(state, slot, tape[slot]);
    if (slot < 0) {
      tape.unshift(0);
      slot = 0;
    }
    if (slot == tape.length) {
      tape.push(0);
    }
    let value = tape[slot];
    tape[slot] = machine[state].write[value];
    slot += machine[state].move[value];
    state = machine[state].nextState[value];
  }

  return tape.filter(v => v == 1).length;
};

let test = 12629077;
let result = turingMachine(test);
console.log(result);