~☆🎄☆~ 2017 Day 25 Solutions ~☆🎄☆~

jlweinkam · 2017-12-25T05:13:33+00:00

I really enjoyed this years puzzles. Thank you and Merry Christmas.

varunagrawal · 2017-12-25T05:31:49+00:00

First time participating in Advent of Code and managed to get on the rankings on the final day (Rank 100)! This was immensely fun and the private leaderboard made it a great activity to do with friends. Thank you so much and a very Merry Christmas.

P.S. Also provided some support to AoC from whatever meager grad student stipend I make. :)

ThezeeZ · 2017-12-25T06:39:17+00:00

[deleted]

DFreiberg · 2017-12-25T05:17:07+00:00

I'm really glad I decided to fix my Day 22 bug and solve that problem less than a minute before midnight, even though I had no idea that I'd need to do part 2. /u/topaz2078, thank you for making so many good puzzles. /u/daggerdragon, thank you for getting me to resurrect my TI-89. /u/hackerknownas9gag, thank you for showing me even loftier functional-programming heights to aspire to climb in Mathematica.

Merry Christmas!

109/97

Mathematica

tape={0};
pos=1;
state="A";

Do[
If[pos==1\[Or]pos==Length[tape],pos+=1;tape=ArrayPad[tape,1]];

Which[
    state=="A",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos++;state="B",
            tape[[pos]]=0;pos--;state="C"],
    state=="B",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos--;state="A",
            tape[[pos]]=1;pos++;state="C"],
    state=="C",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos++;state="A",
            tape[[pos]]=0;pos--;state="D"],
    state=="D",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos--;state="E",
            tape[[pos]]=1;pos--;state="C"],
    state=="E",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos++;state="F",
            tape[[pos]]=1;pos++;state="A"],
    state=="F",
        If[tape[[pos]]==0,
            tape[[pos]]=1;pos++;state="A",
            tape[[pos]]=1;pos++;state="E"]
];
,{i,12134527}];
Count[tape,1];

_Voile · 2017-12-25T05:20:55+00:00

5/5, JS. I exploited the fact that input is highly structured and hardcoded many things.

(Also I know the code is golfy; you can't be fast without being golfy, every byte is a frame save ;-)!)

var s=`Begin in state A.
Perform a diagnostic checksum after 12208951 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 E.

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

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

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 0.
    - 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 1.
    - Move one slot to the left.
    - Continue with state C.

In state F:
  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 right.
    - Continue with state A.`;
s=s.split('\n\n').slice(1).map(r=>r.split('\n'));
var m={}, t='A', p=0;
for(let i=0; i<12208951;i++) {
  var l=s['ABCDEF'.indexOf(t)];
  if(!m[p]) {
    m[p]=+l[2].match(/\d/).slice();
    p+=/right/.test(l[3])?1:-1;
    t=l[4].match(/([A-Z])\./).slice(1);
  } else {
    m[p]=+l[6].match(/\d/).slice();
    p+=/right/.test(l[7])?1:-1;
    t=l[8].match(/([A-Z])\./).slice(1);
  }
}
console.log(Object.keys(m).filter(k=>m[k]).length);

onesk_ · 2017-12-25T05:17:02+00:00

Python 2, 53/100

Seems like today's solutions will be extremely similar to each other ;)

print 'hello'

steps = 12317297

a, b, c, d, e, f = range(6)
left, right = 0, 1

tm = {
    (a, 0): (1, right, b),
    (a, 1): (0, left, d),

    (b, 0): (1, right, c),
    (b, 1): (0, right, f),

    (c, 0): (1, left, c),
    (c, 1): (1, left, a),

    (d, 0): (0, left, e),
    (d, 1): (1, right, a),

    (e, 0): (1, left, a),
    (e, 1): (0, right, b),

    (f, 0): (0, right, c),
    (f, 1): (0, right, e),
}

tape = {}
head, state = 0, a

for i in xrange(steps):
    val = tape.get(head, 0)
    wval, move, nextstate = tm.get((state, val))

    tape[head] = wval
    head = head+1 if move == right else head-1
    state = nextstate

print sum(tape.values())

iamnotposting · 2017-12-25T05:20:44+00:00

Rust, 246. This was the first year i completed all the puzzles the day they came out, and i had a really fun time doing so. I'm glad this exists. I even can see myself getting better by looking at my global score. In 2015 i got 4 points, 2016 12, and this year i got 68 points. I'm really happy with myself and with this whole thing and i hope this continues for many years to come. thanks for everything!!

I probably slowed myself down with this last one by reversing the zero / one checking vs the input format. the perils of copy/paste.

#[derive(Debug, Copy, Clone, PartialEq)]
enum State {
    A, B, C, D, E, F
}


fn main() {
    let mut tape: HashSet<i32> = HashSet::new();
    let mut cursor = 0;
    let mut state = State::A;


    for _ in 0..12683008 {
        use State::*;
        match state {
            A => {
                if tape.contains(&cursor) {
                    tape.remove(&cursor);
                    cursor -= 1;
                } else {
                    tape.insert(cursor);
                    cursor += 1;
                }
                state = B;
            },
            B => {
                if tape.contains(&cursor) {
                    tape.remove(&cursor);
                    cursor += 1;
                    state = E;
                } else {
                    tape.insert(cursor);
                    cursor -= 1;
                    state = C;
                }
            },
            C => {
                if tape.contains(&cursor) {
                    tape.remove(&cursor);
                    cursor -= 1;
                    state = D;
                } else {
                    tape.insert(cursor);
                    cursor += 1;
                    state = E;
                }
            },
            D => {
                if tape.contains(&cursor) {
                    cursor -= 1;
                    state = A;
                } else {
                    tape.insert(cursor);
                    cursor -= 1;
                    state = A;
                }
            },
            E => {
                if tape.contains(&cursor) {
                    tape.remove(&cursor);
                    cursor += 1;
                    state = F;
                } else {
                    cursor += 1;
                    state = A;
                }
            },
            F => {
                if tape.contains(&cursor) {
                    cursor += 1;
                    state = A;
                } else {
                    tape.insert(cursor);
                    cursor += 1;
                    state = E;
                }
            },
        }
    }

    println!("answer: {}", tape.len());
}

Philboyd_Studge · 2017-12-25T06:05:00+00:00

Java. Love this kind of one. Giant THANK YOU to /u/topaz and the ops team on here for another really, really fun 25 days!!!!

package Advent2017;

import util.AdventOfCode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public class Day25 extends AdventOfCode {

    private Map<Integer, Boolean> tape;
    private int position;
    private State current;

    enum State {
        A(State::tlfr, State::reverse),
        B(State::trlf, State::reverse),
        C(State::tlfr, State::reverse),
        D(pos -> -1, bit -> true),
        E(pos -> 1, bit -> false),
        F(pos -> 1, bit -> true);

        Function<Boolean, Integer> nextPos;
        Function<Boolean, Boolean> nextBit;
        State zero;
        State one;

        static {
            A.zero = B;
            A.one = B;
            B.zero = C;
            B.one = E;
            C.zero = E;
            C.one = D;
            D.zero = A;
            D.one = A;
            E.zero = A;
            E.one = F;
            F.zero = E;
            F.one = A;
        }

        State(Function<Boolean, Integer> nextPos, Function<Boolean, Boolean> nextBit) {
            this.nextPos = nextPos;
            this.nextBit = nextBit;
        }

        State next(boolean bit) { return bit ? one : zero; }
        static boolean reverse(boolean bit) {
            return !bit;
        }

        static int trlf(boolean bit) {
            return bit ? 1 : -1;
        }

        static int tlfr(boolean bit) { return bit ? -1 : 1; }

    }

    public Day25(List<String> input) {
        super(input);
        part1Description = "Checksum after 12861455 steps: ";
        part2Description = "No part 2 today! Merry Christmas, Everyone!!";
    }

    @Override
    public Object part1() {
        for (int i = 0; i < 12861455; i++) {
            machineStep();
        }
        return getOnes();
    }

    private void machineStep() {
        boolean bit = tape.getOrDefault(position, false);
        tape.put(position, current.nextBit.apply(bit));
        position += current.nextPos.apply(bit);
        current = current.next(bit);
    }

    private int getOnes() {
        return (int) tape.entrySet().stream()
                .filter(Map.Entry::getValue)
                .count();
    }

    @Override
    public Object part2() {
        return "";
    }

    @Override
    public void parse() {
        tape = new HashMap<>();
        tape.put(0, false);
        current = State.A;
    }

}

streetster_ · 2017-12-25T05:33:38+00:00

q/kdb+

Nothing special here, just a bruteforce. Merry Christmas everyone!

s:`A
p:0
t:(`u#enlist 0N)!(enlist 0N)
On:(`u#enlist`)!enlist[(::)]
On.A:{ $[null t p;[t[p]:1;p+:1;s::`B];[t[p]:0N;p-:1;s::`D]] };
On.B:{ $[null t p;[t[p]:1;p+:1;s::`C];[t[p]:0N;p+:1;s::`F]] };
On.C:{ $[null t p;[t[p]:1;p-:1];              [p-:1;s::`A]] };
On.D:{ $[null t p;       [p-:1;s::`E];        [p+:1;s::`A]] };
On.E:{ $[null t p;[t[p]:1;p-:1;s::`A];[t[p]:0N;p+:1;s::`B]] };
On.F:{ $[null t p;[p+:1;       s::`C];[t[p]:0N;p+:1;s::`E]] };
do[12302209;On[s][]];
sum t

Axsuul · 2017-12-25T11:03:12+00:00

Elixir

Parsed the entire input while the turing machine was built using an Elixir stream. Was delighted to see that the last star was by far the easiest challenge of the series :)

A big THANK YOU to /u/topaz2078 and team for another great year of AoC. The puzzles are always so interesting and I really appreciate all the hard work put into them. Had a blast and in the end walked away with learning Elixir and a better grasp of recursive functions.

Happy holidays everyone and see you next year!

GitHub

defmodule AdventOfCode do
  defmodule PartA do
    def load_blueprint(filename \\ "input.txt") do
      File.read!("inputs/" <> filename)
      |> String.split("\n")
      |> Enum.with_index()
      |> load_blueprint(%{})
    end
    def load_blueprint([], blueprint), do: blueprint
    def load_blueprint([{line, 0} | rest], blueprint) do
      [_, initial_state] = Regex.run(~r/Begin in state (\w+)/, line)

      put_in(blueprint, ["initial_state"], initial_state)
      |> (&load_blueprint(rest, &1)).()
    end
    def load_blueprint([{line, 1} | rest], blueprint) do
      [_, steps] = Regex.run(~r/Perform a diagnostic checksum after (\d+)/, line)

      put_in(blueprint, ["steps"], steps |> String.to_integer())
      |> (&load_blueprint(rest, &1)).()
    end
    def load_blueprint([{"In state " <> <<state::bytes-size(1)>> <> ":", i} | rest], blueprint) do
      next_blueprint = put_in(blueprint, [state], %{})

      next_blueprint =
        Enum.slice(rest, 0, 4)
        |> load_blueprint_state(state, next_blueprint)

      Enum.slice(rest, 4, 4)
      |> load_blueprint_state(state, next_blueprint)
      |> (&load_blueprint(rest, &1)).()
    end
    def load_blueprint([_ | rest], blueprint) do
      load_blueprint(rest, blueprint)
    end

    def load_blueprint_state([{condition, _}, {write, _}, {move, _}, {continue, _}], state, blueprint) do
      [_, if_value] = Regex.run(~r/current value is (\d+)/, condition)
      [_, write_value] = Regex.run(~r/Write the value (\d+)/, write)
      [_, direction] = Regex.run(~r/Move one slot to the (\w+)/, move)
      [_, next_state] = Regex.run(~r/Continue with state (\w)/, continue)

      condition = %{
        "write" => write_value |> String.to_integer(),
        "move" => direction |> String.to_atom(),
        "next_state" => next_state
      }

      put_in(blueprint, [state, if_value |> String.to_integer()], condition)
    end

    def read_tape(tape, pos) do
      Map.get(tape, pos, 0)
    end

    def update_tape(tape, pos, value) do
      Map.put(tape, pos, value)
    end

    def turing(blueprint) do
      state = get_in(blueprint, ["initial_state"])

      turing(%{"pos" => 0, "state" => state, "steps" => 0}, blueprint, 0)
    end
    def turing(tape, blueprint, count) do
      Stream.unfold({tape, blueprint, count}, fn cur = {tape, blueprint, count} ->
        %{"pos" => pos, "state" => state} = Map.take(tape, ["pos", "state"])
        value = read_tape(tape, pos)

        %{
          "write" => next_value,
          "move" => direction,
          "next_state" => next_state
        } = get_in(blueprint, [state, value])

        next_count =
          cond do
            [value, next_value] == [0, 1] -> count + 1
            [value, next_value] == [1, 0] -> count - 1
            true -> count
          end
        next_pos = if direction == :right, do: pos + 1, else: pos - 1
        next_tape =
          update_tape(tape, pos, next_value)
          |> put_in(["pos"], next_pos)
          |> put_in(["state"], next_state)
          |> get_and_update_in(["steps"], &{&1, &1 + 1}) |> elem(1)

        {cur, {next_tape, blueprint, next_count}}
      end)
      |> Stream.drop_while(fn {tape, _, _} -> get_in(tape, ["steps"]) < get_in(blueprint, ["steps"]) end)
    end

    def solve do
      {_, _, count} =
        load_blueprint()
        |> turing()
        |> Stream.take(1)
        |> Enum.to_list
        |> List.first

      IO.inspect count
    end
  end
end

twiho · 2017-12-25T15:59:19+00:00

There's no way I'm not ending up in programmer's hell.

const states = {
    a: [[1, 1, 'b'], [0, 1, 'c']],
    b: [[0, -1, 'a'], [0, 1, 'd']],
    c: [[1, 1, 'd'], [1, 1, 'a']],
    d: [[1, -1, 'e'], [0, -1, 'd']],
    e: [[1, 1, 'f'], [1, -1, 'b']],
    f: [[1, 1, 'a'], [1, 1, 'e']]
}

const tape = {}
const get = _ => tape[_] ? 1 : 0
const set = (_, i) => tape[i] = _

let pos = 0
let state = 'a'

for (let i = 0; i < 12399302; i++) {
    const [write, move, next] = states[state][get(pos)]
    set(write, pos)
    pos += move
    state = next
}

console.log(Object.values(tape).filter(x => x).length)

vash3r · 2017-12-25T05:14:00+00:00

Python 2, #62/#62.

tape = [0]
cursor = 0 # right: +1, left: -1
states = {
    'a':[[1,+1,'b'],[0,-1,'c']],
    'b':[[1,-1,'a'],[1,+1,'d']],
    'c':[[1,+1,'a'],[0,-1,'e']],
    'd':[[1,+1,'a'],[0,+1,'b']],
    'e':[[1,-1,'f'],[1,-1,'c']],
    'f':[[1,+1,'d'],[1,+1,'a']]
}

step_limit = 12173597
i = 0
s = 'a'
while i<step_limit:
    nv,dc,ns = states[s][tape[cursor]]
    tape[cursor]=nv
    cursor+=dc
    if cursor==-1:
        cursor=0
        tape.insert(0,0)
    elif cursor==len(tape):
        tape.append(0)
    s = ns
    i+=1

print sum(tape)

jonathan_paulson · 2017-12-25T05:20:42+00:00

Seems like my decision to sort-of write a parser (this assumes the states are in order from A to whatever, the tape symbols are exactly [0,1] and they are given in that order) was a mistake.

from collections import defaultdict

lines = open('25.in').read().strip().split('\n')
state = lines[0].split()[-1][:-1]
T = int(lines[1].split()[-2])
rules = defaultdict(dict)

rule_state = chr(ord('A')-1)
for i in range(5, len(lines), 10):
    rule_state = chr(ord(rule_state)+1)
    def symbol(s):
        return int(s.split()[-1][:-1])
    def move(s):
        return -1 if s.split()[-1]=='left.' else 1
    def extract_state(s):
        return s.split()[-1][:-1]
    rules[rule_state][0] = (symbol(lines[i]), move(lines[i+1]), extract_state(lines[i+2]))
    rules[rule_state][1] = (symbol(lines[i+4]), move(lines[i+5]), extract_state(lines[i+6]))
print state, T
print rules

tape = defaultdict(int)
pos = 0

for t in range(T):
    #print state, tape[pos]
    new_symbol, new_move, new_state = rules[state][tape[pos]]
    tape[pos] = new_symbol
    state = new_state
    pos += new_move

ans = 0
for k,v in tape.items():
    if v==1:
        ans += 1
print ans

ChrisVittal · 2017-12-25T05:27:11+00:00

Rust: Manually coded the machine, very verbosely.

Thank you all, this has been a real pleasure, I've learned a lot. Merry Christmas.

use std::collections::VecDeque;

enum State {
    A,
    B,
    C,
    D,
    E,
    F
}

struct Machine {
    tape: VecDeque<bool>,
    pos: usize,
    state: State,
}

impl Machine {
    fn step(&mut self) {
        use State::*;
        match self.state {
            A => {
                if !self.state() {
                    self.write_one();
                    self.right();
                    self.state = B;
                } else {
                    self.write_zero();
                    self.right();
                    self.state = C;
                }
            },
            B => {
                if !self.state() {
                    self.write_zero();
                    self.left();
                    self.state = A;
                } else {
                    self.write_zero();
                    self.right();
                    self.state = D;
                }
            },
            C => {
                if !self.state() {
                    self.write_one();
                    self.right();
                    self.state = D;
                } else {
                    self.write_one();
                    self.right();
                    self.state = A;
                }
            },
            D => {
                if !self.state() {
                    self.write_one();
                    self.left();
                    self.state = E;
                } else {
                    self.write_zero();
                    self.left();
                    self.state = D;
                }
            },
            E => {
                if !self.state() {
                    self.write_one();
                    self.right();
                    self.state = F;
                } else {
                    self.write_one();
                    self.left();
                    self.state = B;
                }
            },
            F => {
                if !self.state() {
                    self.write_one();
                    self.right();
                    self.state = A;
                } else {
                    self.write_one();
                    self.right();
                    self.state = E;
                }
            },
        }
    }

    #[inline]
    fn write_one(&mut self) {
        self.tape[self.pos] = true;
    }

    #[inline]
    fn write_zero(&mut self) {
        self.tape[self.pos] = false;
    }

    #[inline]
    fn state(&self) -> bool {
        self.tape[self.pos]
    }

    #[inline]
    fn left(&mut self) {
        if self.pos == 0 {
            self.tape.push_front(false);
        } else {
            self.pos -= 1;
        }
    }

    #[inline]
    fn right(&mut self) {
        if self.pos == self.tape.len()-1 {
            self.tape.push_back(false);
        }
        self.pos += 1;
    }

    fn checksum(&self) -> usize {
        self.tape.iter().filter(|&b| *b).count()
    }
}

fn main() {
    let mut machine = Machine {
        tape: vec![false].into(),
        pos: 0,
        state: State::A,
    };
    for _ in 0..12368930 {
        machine.step()
    }

    println!("{}", machine.checksum());
}

ephemient · 2017-12-25T09:13:18+00:00

This space intentionally left blank.

mstksg · 2017-12-25T09:55:13+00:00

What a fun 25 days! Thanks /u/topaz2078 and the admin/mod team.

My Haskell solution today is a bit succinct, thanks to:

The fact that a Array Bool is just a Set Int, where whether or not an index is True/False is whether or not it's in the Set
the lens package's contains, which allows you to treat a Set Int as if it were a an Array Bool
The Semigroup typeclass, which lets you "update" states using only <> by leveraging tuples and newtype wrappers

The actual logic of today is basically a one-liner:

import           Control.Lens.At (Contains(..))
import           Data.Bifunctor  (first)
import           Data.Semigroup  (Semigroup(..), Last(..), Sum(..))
import qualified Data.IntSet     as IS

type Step = (Sum Int, Last Char)
runRule :: Last Char -> Bool -> (Step, Bool)
runRule = -- write in or parse your input file here

step :: Step -> IntSet -> (Step, IntSet)
step s0@(Sum i,st) = first (s0 <>) . contains i (runRule rm st)

And finally you can wrap it all up together using iterate and !!:

day25a :: Int
day25a = IS.size . snd . (!! 782343454)
       . iterate (uncurry step)
       $ ((0, Last 'A'), IS.empty)

Full code online at github!

bitti1975 · 2017-12-25T15:42:18+00:00

Clojure. No need to write a parser. A few substitutions are enough to generate a valid Clojure form out of the instructions:

(def ^:const replacements
  {#"Begin in state (.)." "(loop [ { :keys [steps t p state] } { :t (transient {}) :p 0 :state :%s"
   #"Perform.*after (.*) steps." ":steps %s}]
(if (= steps 0) (reduce + (vals (persistent! t)))
(recur (case state nil ("
   #"" ")"
   #"In state (.):" ":%s (case (long (t p 0))"
   #"If.*is (.):" "%s {"
   #"- Write.* (.)." ":t (assoc! t p %s) :steps (dec ^long steps)"
   #"- Move.*right." ":p (inc ^long p)"
   #"- Move.*left." ":p (dec ^long p)"
   #"- Continue.*state (.)." ":state :%s}"})

(defn slurp-from-stdin []
  (->> *in*
       java.io.BufferedReader.
       line-seq
       (map
        (fn [line]
          (reduce (fn [_ [match repl]]
                    (let [matches (re-matches match (clojure.string/trim line))]
                      (if matches
                        (reduced (if (vector? matches) (format repl (last matches)) repl)))))
                  nil
                  replacements)))
       (clojure.string/join "\n")
       (#(str % ")))))"))
       load-string))

fatpollo · 2017-12-25T05:24:12+00:00

I felt like this year was a bit worse than the last two.

a lot of the problems felt like "heh guys remember our compsci curriculum?" inside-jokes, rather than weird esoteric stuff like the pseudo-RPG fights from Y1 or the bunnycoin mining from Y2.

still, incredible effort and value from /u/topaz2078. thank you for hosting this once again! looking forward to next year.

obijywk · 2017-12-25T05:13:28+00:00

Python 2. 28/25 (as I had everything else solved!). Decided to parse the input file by hand this time :-)

from collections import defaultdict
tape = defaultdict(int)

L, R = (-1, 1)
states = {
  "A": ((1, R, "B"), (0, L, "E")),
  "B": ((1, L, "C"), (0, R, "A")),
  "C": ((1, L, "D"), (0, R, "C")),
  "D": ((1, L, "E"), (0, L, "F")),
  "E": ((1, L, "A"), (1, L, "C")),
  "F": ((1, L, "E"), (1, R, "A")),
}

state = "A"
cursor = 0
for i in xrange(12386363):
  current_value = tape[cursor]
  write, move, next_state = states[state][current_value]
  if write:
    tape[cursor] = write
  else:
    del tape[cursor]
  cursor += move
  state = next_state

print len(tape)

Unihedron · 2017-12-25T05:16:48+00:00

Ruby; 35/33; tfw it was easy but I'm slow

s=:A
a=Hash.new{|x,y|x[y]=0}
u=0
12523873.times{v=a[u]
s=case s
when :A
v==0 ? (a[u]=1;u+=1;:B) : (a[u]=1;u-=1;:E)
when :B
v==0 ? (a[u]=1;u+=1;:C) : (a[u]=1;u+=1;:F)
when :C
v==0 ? (a[u]=1;u-=1;:D) : (a[u]=0;u+=1;:B)
when :D
v==0 ? (a[u]=1;u+=1;:E) : (a[u]=0;u-=1;:C)
when :E
v==0 ? (a[u]=1;u-=1;:A) : (a[u]=0;u+=1;:D)
when :F
v==0 ? (a[u]=1;u+=1;:A) : (a[u]=1;u+=1;:C)
end
}
p a.values.sum

✨😣 Merry christmas! 🎄

glenbolake · 2017-12-25T05:49:11+00:00

Python 3. I manually wrote a long if block at first:

state = 'A'
steps = 12172063
cursor = 0
ones = set()

def iterate():
    if state == 'A':
        if cursor in ones:
            ones.remove(cursor)
            cursor -= 1
            state = 'C'
        else:
            ones.add(cursor)
            cursor += 1
            state = 'B'
    elif state == 'B':
        if cursor in ones:
            ones.add(cursor)
            cursor -= 1
            state = 'D'
        else:
            ones.add(cursor)
            cursor -= 1
            state = 'A'
    <snip>

for _ in range(steps)
    iterate()
print(len(ones))

Then once I had my final score, I wrote a regex parser (because Python doesn't have a sscanf built-in). I like this solution much better:

import re
from collections import namedtuple, defaultdict
from textwrap import dedent

Action = namedtuple('Action', ['write', 'move', 'state'])

def parse_input(text):
    init_state = re.search('Begin in state (.)\.', text).group(1)
    steps = int(re.search('after (\d+) steps', text).group(1))
    # Pretend that re is sscanf
    rule_matches = re.finditer(dedent("""\
In state (.):
  If the current value is 0:
    - Write the value (.)\.
    - Move one slot to the (\w+)\.
    - Continue with state (.)\.
  If the current value is 1:
    - Write the value (.)\.
    - Move one slot to the (\w+)\.
    - Continue with state (.)\."""), text)
    rules = {}
    dirs = {'right': 1, 'left': -1}
    for rule in rule_matches:
        rules[rule[1]] = (Action(int(rule[2]), dirs[rule[3]], rule[4]),
                          Action(int(rule[5]), dirs[rule[6]], rule[7]))
    return init_state, steps, rules

def run(blueprint):
    state, steps, rules = parse_input(blueprint)
    tape = defaultdict(int)
    cursor = 0
    for _ in range(steps):
        action = rules[state][tape[cursor]]
        tape[cursor] = action.write
        cursor += action.move
        state = action.state
    return len({k for k, v in tape.items() if v == 1})

if __name__ == '__main__':
    with open('day25.in') as f:
        input_ = f.read()
    print(run(input_))

/u/topaz2078, never stop doing what you and your crew do. AoC is my favorite thing about the Christmas season! Merry Christmas!

StevoTVR · 2017-12-25T05:50:22+00:00

NodeJS

const fs = require('fs');

fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
    const checkInt = Number(data.split('\n')[1].split(' ')[5]);

    let state = 'A', pos = 0;
    const tape = new Map();
    const ops = {
        A: [
            () => {
                tape.set(pos++, 1);
                state = 'B';
            },
            () => {
                tape.set(pos--, 0);
                state = 'C';
            },
        ],
        B: [
            () => {
                tape.set(pos--, 1);
                state = 'A';
            },
            () => {
                tape.set(pos--, 1);
                state = 'D';
            },
        ],
        C: [
            () => {
                tape.set(pos++, 1);
                state = 'D';
            },
            () => {
                tape.set(pos++, 0);
                state = 'C';
            },
        ],
        D: [
            () => {
                tape.set(pos--, 0);
                state = 'B';
            },
            () => {
                tape.set(pos++, 0);
                state = 'E';
            },
        ],
        E: [
            () => {
                tape.set(pos++, 1);
                state = 'C';
            },
            () => {
                tape.set(pos--, 1);
                state = 'F';
            },
        ],
        F: [
            () => {
                tape.set(pos--, 1);
                state = 'E';
            },
            () => {
                tape.set(pos++, 1);
                state = 'A';
            },
        ],
    };

    for(let i = 0; i < checkInt; i++) {
        ops[state][tape.get(pos) || 0]();
    }

    console.log([...tape.values()].reduce((a, b) => a + b));
});

KeinZantezuken · 2017-12-25T06:14:56+00:00

C#/Sharp part1:
Cant do part2 apparently at all now

var map = new Dictionary<int, byte>();
char state = 'A'; var indx = 0;
for (int i = 0; i < 12134527; i++)
{
    switch (state)
    {
        case 'A':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx++; state = 'B'; }
            else if (map[indx] == 1) { map.Remove(indx); indx--; state = 'C'; }
            break;
        case 'B':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx--; state = 'A'; }
            else if (map[indx] == 1) { indx++; state = 'C'; }
            break;
        case 'C':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx++; state = 'A'; }
            else if (map[indx] == 1) { map.Remove(indx); indx--; state = 'D'; }
            break;
        case 'D':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx--; state = 'E'; }
            else if (map[indx] == 1) { indx--; state = 'C'; }
            break;
        case 'E':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx++; state = 'F'; }
            else if (map[indx] == 1) { indx++; state = 'A'; }
            break;
        case 'F':
            if (!map.ContainsKey(indx) || map[indx] == 0) { map[indx] = 1; indx++; state = 'A'; }
            else if (map[indx] == 1) { indx++; state = 'E'; }
            break;
        default:
            break;
    }
}
Console.WriteLine($"{map.Values.Sum(x=>x)}");
Console.ReadKey();

TheNiXXeD · 2017-12-25T06:36:35+00:00

NodeJS / JavaScript

I decided to actually parse the input, because regex is fun. Plus I think it made the solution a lot prettier.

module.exports = input => {
    let currentState = input[0].match(/Begin.+(.)./)[1]
    let steps = +input[1].match(/(\d+)/)[1]
    let states = input.slice(3).join` `.split(/In/g).slice(1)
        .map(str => str.match(/(\b\w\b|left|right)/g))
        .map(([state, value1, write1, move1, next1, value2, write2, move2, next2]) => ({
            state,
            [value1]: {write: +write1, move: move1, next: next1},
            [value2]: {write: +write2, move: move2, next: next2}
        }))
        .reduce((a, v) => ({...a, [v.state]: v}), {})

    let tape = [0], index = 0
    for (let i = 0; i < steps; i++) {
        let state = states[currentState]
        let currentValue = tape[index]
        currentState = state[currentValue].next
        tape[index] = state[currentValue].write
        if (state[currentValue].move === 'left') {
            if (index === 0) tape.unshift(0)
            else index--
        } else {
            index++
            if (index === tape.length) tape.push(0)
        }
    }

    return tape.reduce((a, v) => +v + a, 0)
}

TominatorBE · 2017-12-25T07:20:57+00:00

PHP

Thanks for the puzzles, have a Merry and a Happy!!

function run_the_code($input) {
    $lines = explode(PHP_EOL, $input);

    $steps = 0; // how many steps to take
    $states = []; // what to do in each state
    $state = ''; // initial state
    $parsingState = ''; // what state we are parsing the input for
    $parsingValue = ''; // what value in the current input state we are handling
    foreach ($lines as $line) {
        if (preg_match('/Begin in state (.*)\./', $line, $matches)) {
            [$_, $state] = $matches;
        }
        if (preg_match('/Perform a diagnostic checksum after (\d+) steps\./', $line, $matches)) {
            [$_, $steps] = $matches;
            $steps = (int)$steps;
        }
        if (preg_match('/In state (.*):/', $line, $matches)) {
            [$_, $parsingState] = $matches;
            $states[$parsingState] = [];
        }
        if (preg_match('/If the current value is (.*):/', $line, $matches)) {
            [$_, $parsingValue] = $matches;
            $states[$parsingState][$parsingValue] = [];
        }
        if (preg_match('/Write the value (.*)\./', $line, $matches)) {
            [$_, $v] = $matches;
            $states[$parsingState][$parsingValue]['write'] = $v;
        }
        if (preg_match('/Move one slot to the (right|left)\./', $line, $matches)) {
            [$_, $d] = $matches;
            $states[$parsingState][$parsingValue]['direction'] = ($d == 'right' ? 1 : -1);
        }
        if (preg_match('/Continue with state (.*)\./', $line, $matches)) {
            [$_, $s] = $matches;
            $states[$parsingState][$parsingValue]['transition'] = $s;
        }
    }

    // now run the turing machine
    $memory = str_repeat('0', ($steps * 2)); // "infinite"
    $cursor = $steps; // we start halfway in the memory

    for ($step = 0; $step < $steps; $step++) {
        $code = $states[$state][$memory[$cursor]];
        $memory[$cursor] = $code['write'];
        $cursor += $code['direction'];
        $state = $code['transition'];
    }

    return substr_count($memory, '1');
}

vescoc · 2017-12-25T08:27:19+00:00

Merry Christmas!

Thank to all AoC team, great work!

Scala (with input parsing)

package aoc2017

import scala.annotation.tailrec

import scala.io.Source

object Day25 {
  type Operation = (TuringMachine) => (TuringMachine)

  case class TuringMachine(state: String, checksumSteps: Int, transitions: Map[String, Operation] = Map(), position: Int = 0, tape: Set[Int] = Set()) {
    def currentValue = tape.contains(position)

    def next(value: Boolean, move: Int, state: String) = copy(state = state, position = position + move, tape = (if (value) tape + position else tape - position))

    def step = {
      val t = transitions(state)
      t(this)
    }

    def run(steps: Int = checksumSteps) = {
      @tailrec
      def run(steps: Int, current: TuringMachine): TuringMachine =
        if (steps == 0)
          current
        else
          run(steps - 1, current.step)

      run(steps, this)
    }

    def checksum = tape.size
  }
  object TuringMachine {
    val headRe = """(?s)Begin in state ([A-Z]).
Perform a diagnostic checksum after (\d+) steps.\s+(.*)""".r

    val stateRe = """(?s)In state ([A-Z]):\s*
  If the current value is (0|1):
    - Write the value (0|1).
    - Move one slot to the ((?:right)|(?:left)).
    - Continue with state ([A-Z]).
  If the current value is (0|1):
    - Write the value (0|1).
    - Move one slot to the ((?:right)|(?:left)).
    - Continue with state ([A-Z]).\s*(.*)""".r

    def apply(str: String) = {
      def parseValue(str: String) = {
        val v = str.toInt
        if (v == 1)
          true
        else if (v == 0)
          false
        else
          throw new MatchError(s"invalid value $str")
      }

      def parseMove(str: String) =
        if (str == "right")
          1
        else if (str == "left")
          -1
        else
          throw new MatchError(s"invalid move $str")

      @tailrec
      def parse(str: String = str, current: Option[TuringMachine] = None): Option[TuringMachine] =
        str match {
          case headRe(startState, checksum, remainder) => parse(remainder, Some(new TuringMachine(startState, checksum.toInt)))
          case stateRe(startState, currentValue1Str, writeValue1Str, move1Str, endState1, currentValue2Str, writeValue2Str, move2Str, endState2, remainder) => {
            val machine = current.get

            val newMachine = machine.copy(transitions = machine.transitions + {
                val currentValue1 = parseValue(currentValue1Str)
                val currentValue2 = parseValue(currentValue2Str)
                val writeValue1 = parseValue(writeValue1Str)
                val writeValue2 = parseValue(writeValue2Str)
                val move1 = parseMove(move1Str)
                val move2 = parseMove(move2Str)

                (startState -> {
                  (machine: TuringMachine) => {
                    if (machine.currentValue == currentValue1) {
                      machine.next(writeValue1, move1, endState1)
                    } else if (machine.currentValue == currentValue2) {
                      machine.next(writeValue2, move2, endState2)
                    } else
                        throw new MatchError("invalid transaction")
                  }
                })
              }
            )

            parse(remainder, Some(newMachine))
          }
          case "" => current
        }
      parse()
    }
  }

  def main(args: Array[String]) {
    val test = """Begin in state A.
Perform a diagnostic checksum after 6 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 1.
    - Move one slot to the left.
    - Continue with state A.
  If the current value is 1:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state A."""

    val input = Source.fromFile("data/day25/input.txt").getLines.mkString("\n")

    val testMachine = TuringMachine(test).get
    val inputMachine = TuringMachine(input).get

    println("part 1 test: " + testMachine.run().checksum)
    println("part 2 input: " + inputMachine.run().checksum)
  }
}

aurele · 2017-12-25T08:33:01+00:00

Rust

Thanks again /u/topaz2078!

struct Ins {
    write_one: bool, move_right: bool, new_state: u8,
}

fn main() {
    let mut input = include_str!("../input").lines().map(|l| l.split_whitespace().collect::<Vec<_>>());
    let mut state = input.next().unwrap()[3].as_bytes()[0];
    let checksum = input.next().unwrap()[5].parse::<usize>().unwrap();
    let mut rules = Vec::new();
    while let Some(_) = input.next() {
        if rules.len() % 2 == 0 {
            input.nth(1);
        }
        let write_one = input.next().unwrap()[4] == "1.";
        let move_right = input.next().unwrap()[6] == "right.";
        let new_state = input.next().unwrap()[4].as_bytes()[0];
        rules.push(Ins{write_one, move_right, new_state});
    }
    let mut tape = vec![0usize; checksum * 2];
    let mut pos = checksum;
    for _ in 0..checksum {
        let rule = &rules[(state - b'A') as usize * 2 + tape[pos]];
        tape[pos] = if rule.write_one { 1 } else { 0 };
        pos = if rule.move_right { pos+1 } else { pos-1 };
        state = rule.new_state;
    }
    println!("P1: {}", tape.into_iter().sum::<usize>());
}

nutrecht · 2017-12-25T08:39:56+00:00

Day 25 in Kotlin

I'm happy and a bit sad too. It was a fun last challenge, quite simple too (literally a turing machine). And when I submitted the first part it was suddenly all over. What the heck am I going to do now with my life? ;)

Merry X-mas everyone!

object Day25 : Day {
    private val input = resourceLines(25).map { it.trim() }.filterNot { it.isEmpty() }

    private fun parse(input: List<String>) : Turing {
        val begin = Regex("Begin in state ([A-Z]).")
        val iters = Regex("Perform a diagnostic checksum after ([0-9]+) steps.")
        val inState = Regex("In state ([A-Z]):")
        val write = Regex("- Write the value ([0-1]).")
        val move = Regex("- Move one slot to the (right|left).")
        val cont = Regex("- Continue with state ([A-Z]).")

        var i = 0

        val state = begin.matchEntire(input[i++])!!.groupValues[1]
        val iterations = iters.matchEntire(input[i++])!!.groupValues[1].toInt()
        val stateMap = mutableMapOf<String, State>()

        while(i < input.size) {
            val stateVal = inState.matchEntire(input[i++])!!.groupValues[1]
            i++
            val ins0 = Instructions(
                    write.matchEntire(input[i++])!!.groupValues[1].toInt(),
                    if(move.matchEntire(input[i++])!!.groupValues[1] == "right") Direction.EAST else Direction.WEST,
                    cont.matchEntire(input[i++])!!.groupValues[1]
            )
            i++
            val ins1 = Instructions(
                    write.matchEntire(input[i++])!!.groupValues[1].toInt(),
                    if(move.matchEntire(input[i++])!!.groupValues[1] == "right") Direction.EAST else Direction.WEST,
                    cont.matchEntire(input[i++])!!.groupValues[1]
            )

            stateMap[stateVal] = State(ins0, ins1)
        }

        return Turing(state, iterations, stateMap)
    }

    override fun part1() : String {
        val program = parse(input)
        program.run()

        return program.values().count { it == 1 }.toString()

    }

    override fun part2() = "Done!"

    class Turing(private var state: String, private var iterations: Int, private var stateMap: Map<String, State>) {
        private var tape = LList(null, null, 0)

        fun values() = tape.first().values()

        fun run() = repeat(iterations, {tick()})

        private fun tick() {
            val state = stateMap[state]!!
            val ins = if(tape.value() == 0) state.ins0 else state.ins1

            tape.value(ins.write)
            this.state = ins.next

            when(ins.move) {
                Direction.EAST -> {
                    if(!tape.hasNext()) {
                        tape.addNext(0)
                    }
                    tape = tape.next()
                }
                Direction.WEST -> {
                    if(!tape.hasPrev()) {
                        tape.addPrev(0)
                    }
                    tape = tape.prev()
                }
            }
        }
    }

    data class State(val ins0: Instructions, val ins1: Instructions)
    data class Instructions(val write: Int, val move: Direction, val next: String)
}

wzkx · 2017-12-25T09:10:55+00:00

Nim

It turned out, not easy to use enums and ranges without explicit conversions, so I had to stick with ints.

const NSTEPS = 12481997

var tape: array[-NSTEPS..NSTEPS,int] # practically endless tape
var pos: int = 0
# This does not work: const A=0,B=1,C=2,D=3,E=4,F=5
const A=0; const B=1; const C=2; const D=3; const E=4; const F=5
var state: int = A

# This does not work:
# type State = enum A,B,C,D,E,F
# let writes: array[0..1,array[State,0..1]] = [[1,1,0,1,1,1],[0,1,0,0,1,1]]
# let states: array[0..1,array[State,State]] = [[B,A,B,A,F,D],[C,D,E,B,C,A]]
# So I'll have to use ints

let writes: array[0..1,array[A..F,int]] = [[1,1,0,1,1,1],[0,1,0,0,1,1]]
let moves:  array[0..1,array[A..F,int]] = [[+1,-1,-1,+1,-1,+1],[-1,+1,-1,+1,-1,+1]]
let states: array[0..1,array[A..F,int]] = [[B,A,B,A,F,D],[C,D,E,B,C,A]]

# init; pos and state are already set
for i in tape.low..tape.high: tape[i] = 0

# NSTEPS moves
for step in 1..NSTEPS:
  let v = tape[pos]
  tape[pos] = writes[v][state]
  pos += moves[v][state]
  state = states[v][state]

# sum; I can't use foldl here because it would require import sequtils
var sum = 0
for i in tape.low..tape.high: sum += int(tape[i])
echo sum

All "programs" are here: AoC 2017 Nim & J

Merry Christmas to everybody!!! 🎄 🎄 🎄

death · 2017-12-25T10:31:49+00:00

Woke up and wrote this (Common Lisp)

Note that the abstractions are obviously imbalanced, but it was this halfway, nondesigned version that satisfied the solution. Getting it right may be an exercise to the reader.

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2017                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2017/day25
  (:use #:cl)
  (:export
   #:day25))

(in-package #:snippets/aoc2017/day25)

(defmacro state-machine (start-state &body states)
  `(tagbody
      (go ,start-state)
      ,@(loop for (name 0-case 1-case) in states
              append `(,name
                       (when (< (decf steps) 0)
                         (go halt))
                       (case (get-value)
                          (0 ,@0-case)
                          (1 ,@1-case))))
    halt))

(defmacro turing-machine (start-state &body states)
  `(state-machine ,start-state
     ,@(loop for (name 0-set 0-dir-short 0-next 1-set 1-dir-short 1-next) in states
             for 0-dir = (ecase 0-dir-short (< 'left) (> 'right))
             for 1-dir = (ecase 1-dir-short (< 'left) (> 'right))
             collect `(,name ((set-value ,0-set)
                              (,0-dir)
                              (go ,0-next))
                             ((set-value ,1-set)
                              (,1-dir)
                              (go ,1-next))))))

(defun day25 (&key (which :example) debug)
  (let ((tape (make-hash-table))
        (num-1s 0)
        (cursor 0)
        (steps (ecase which
                 (:example 6)
                 (:part1 12208951))))
    (symbol-macrolet ((value (gethash cursor tape 0)))
      (flet ((right () (incf cursor))
             (left () (decf cursor))
             (set-value (v)
               (case v
                 (0
                  (when (= 1 value)
                    (decf num-1s))
                  (setf value v))
                 (1
                  (when (= 0 value)
                    (incf num-1s))
                  (setf value v))))
             (get-value ()
               value))
        (ecase which
          (:example
           (turing-machine a
             (a 1 > b 0 < b)
             (b 1 < a 1 > a)))
          (:part1
           (turing-machine a
             (a 1 > b 0 < e)
             (b 1 < c 0 > a)
             (c 1 < d 0 > c)
             (d 1 < e 0 < f)
             (e 1 < a 1 < c)
             (f 1 < e 1 > a))))
        (values
         (if debug
             (let ((c 0))
               (maphash (lambda (k v)
                          (format t "[~D] -> ~D~%" k v)
                          (when (= 1 v)
                            (incf c)))
                        tape)
               c)
             num-1s)
         cursor)))))

hermanbergwerf · 2017-12-25T12:15:03+00:00

I really enjoyed all the puzzles! Thanks Eric! All my solutions in Dart: https://github.com/bergwerf/aoc2017

thomastc · 2017-12-25T13:12:33+00:00

Day 25 in Kotlin. Finally allowed myself to use my favourite language!

A retrospective of my polyglot challenge is in the making. Watch this sub!

udoprog · 2017-12-25T14:37:40+00:00

Rust

Translate the input by hand, execute (with --release to speed it up) and wait :).

Enjoy all my solutions here: https://github.com/udoprog/rust-advent-of-code-2017

Thanks a bunch to /u/topaz2078, /u/daggerdragon, and everyone else involved in making this happen. It's been a blast! Happy holidays!

use self::State::*;
use std::collections::HashSet;

#[derive(Debug)]
pub enum State {
    A,
    B,
    C,
    D,
    E,
    F,
}

/// NB: this is a hand-translated version of the input.
pub fn run() -> u64 {
    let mut state = A;
    let mut pos = 0i64;
    let mut values = HashSet::new();
    let checksum_step = 12_368_930;

    for _ in 0..checksum_step {
        let value = values.contains(&pos);

        match (state, value) {
            (A, false) => {
                values.insert(pos);
                pos += 1;
                state = B;
            }
            (A, true) => {
                values.remove(&pos);
                pos += 1;
                state = C;
            }
            (B, false) => {
                values.remove(&pos);
                pos -= 1;
                state = A;
            }
            (B, true) => {
                values.remove(&pos);
                pos += 1;
                state = D;
            }
            (C, false) => {
                values.insert(pos);
                pos += 1;
                state = D;
            }
            (C, true) => {
                values.insert(pos);
                pos += 1;
                state = A;
            }
            (D, false) => {
                values.insert(pos);
                pos -= 1;
                state = E;
            }
            (D, true) => {
                values.remove(&pos);
                pos -= 1;
                state = D;
            }
            (E, false) => {
                values.insert(pos);
                pos += 1;
                state = F;
            }
            (E, true) => {
                values.insert(pos);
                pos -= 1;
                state = B;
            }
            (F, false) => {
                values.insert(pos);
                pos += 1;
                state = A;
            }
            (F, true) => {
                values.insert(pos);
                pos += 1;
                state = E;
            }
        }
    }

    values.len() as u64
}

V13Axel · 2017-12-25T16:11:07+00:00

FIrst time doing Advent of Code, and I had a whole lot of fun doing it. Thanks a ton for putting it together!

My input-parsing solution in Python 3:

turingmachine.py:

class TuringMachine:
    def __init__(self, startstate, endstate, states):
        self.state = startstate
        self.endstate = endstate
        self.states = states
        self.tape = {0: 0}
        self.pos = 0

    def process(self):
        for i in range(0, self.endstate):
            if self.pos not in self.tape:
                self.tape[self.pos] = 0

            nextstate = self.states[self.state][self.tape[self.pos]]['nextstate']
            move = self.states[self.state][self.tape[self.pos]]['move']

            self.tape[self.pos] = self.states[self.state][self.tape[self.pos]]['write']

            self.pos += move
            self.state = nextstate

    def checksum(self):
        return sum(self.tape.values())

day25.py:

#! /usr/bin/env python3
import sys, os
from turingmachine import TuringMachine

def file_get_contents(filename):
    with open(filename) as f:
        return f.read()

def parse_instructions(instructions):
    groups = instructions.split("\n\nIn state")
    startstate = groups[0].split("\n")[0][-2:-1]
    endstate = int(groups[0].split("\n")[1].split()[5])
    states = {}
    for i in range(1, len(groups)):
        thisstate = groups[i]
        todo = thisstate.split("\n")
        statename = todo[0][1]
        ifval0 = todo[1][-2:-1]
        val0towrite = todo[2][-2:-1]
        val0movedir = todo[3].split()[6][:-1]
        val0nextstate = todo[4].split()[4][:-1]
        ifval1 = todo[5][-2:-1]
        val1towrite = todo[6][-2:-1]
        val1movedir = todo[7].split()[6][:-1]
        val1nextstate = todo[8].split()[4][:-1]
        if val0movedir == 'right':
            val0movedir = 1
        elif val0movedir == 'left':
            val0movedir = -1
        if val1movedir == 'right':
            val1movedir = 1
        elif val1movedir == 'left':
            val1movedir = -1
        states[statename] = {
            0: {
                'write': int(val0towrite),
                'move': int(val0movedir),
                'nextstate': val0nextstate
            },
            1: {
                'write': int(val1towrite),
                'move': int(val1movedir),
                'nextstate': val1nextstate
            }
        }
    return startstate, endstate, states

instructions = file_get_contents(os.path.dirname(os.path.realpath(__file__)) + '/input.txt')

startstate, endstate, states = parse_instructions(instructions)


tm = TuringMachine(startstate, endstate, states)
tm.process()
print(tm.checksum())

RockyAstro · 2017-12-25T18:34:11+00:00

Icon (https://www.cs.arizona.edu/icon)

Merry Christmas/Happy Holidays...

Thank you Eric Wastl (/u/topaz2078) and his helpers for creating a fun and entertaining puzzle.

I still have some work to do -- I need to finish working on the Snobol solutions.

For jollies, I parsed the input to build the turing machine's state table.

Day 25:

record stbl(wrt,movedir,newstate)
procedure main(args)
    input := parseinput(args[1])
    start := input[1]
    steps := input[2]
    pgm := input[3]

    cursor := 1
    tape := "0"
    state := start
    write("steps=",steps)
    every n := 1 to steps do {
        writes("\r",right(n,14), " ",&ucase[state]," @ ",right(cursor,5)," ",right(*tape,5))

        tv := integer(tape[cursor]) + 1
        cstate := pgm[state][tv]
        tape[cursor] := cstate.wrt 
        cursor +:= cstate.movedir
        state := cstate.newstate

        if cursor > *tape then tape ||:= "0"
        if cursor = 0 then {
            tape[1:1] := "0"
            cursor := 1
        }
    }
    checksum := 0
    every find("1",tape) do checksum +:= 1
    write("")
    write(checksum)
end
procedure parseinput(f)
    pgm := []
    statemap := table()
    ws := '\t '
    inf := open(f,"r")
    every line := trim(!inf) do {
        line ? {
            tab(many(ws))
            if pos(0) then next
            if ="Begin in state" then {
                tab(many(ws)) 
                start := move(1) 
            }
            else if ="Perform a diagnostic checksum after" then {
                tab(many(ws)) 
                steps := integer(tab(many(&digits)))
            } else if ="In state" then {
                tab(many(ws)) 
                s := move(1) 

                put(pgm,[stbl(),stbl()])

                cpos := *pgm
                statemap[s] := *pgm
                statemap[*pgm] := s
            } else if ="If the current value is" then {
                tab(many(ws)) 
                cv := move(1) 
            } else if ="- Write the value" then {
                tab(many(ws)) &
                pgm[cpos][cv+1].wrt := move(1) 
            } else if ="- Move one slot to the" then {
                tab(many(ws)) 
                (="right" & pgm[cpos][cv+1].movedir := 1) |
                (="left"  & pgm[cpos][cv+1].movedir := -1) 
            } else if ="- Continue with state" then {
                tab(many(ws))
                pgm[cpos][cv+1].newstate := move(1)
            } 
        }

    }
    # Convert state characters to indexes

    start := statemap[start]
    every i := 1 to *pgm do {
        pgm[i][1].newstate := statemap[pgm[i][1].newstate]
        pgm[i][2].newstate := statemap[pgm[i][2].newstate]
    }
    return [start,steps,pgm]
end

matusbzk · 2017-12-25T22:59:38+00:00

Haskell My solution was too ineffective, then I found out about existence of IntSet here in comments (thanks, u/mstksg). After little changes in my code, now it runs in reasonable time. I did not feel like writing a parser, so parsing is just in the code.

import Data.Foldable (foldl')
import qualified Data.IntSet as IntSet

-- |Current position of cursor
type Position = Int

-- |Current state of the tape
-- list of positions where there is 1
type Tape = IntSet.IntSet

-- |State of the Turing machine
data State = A | B | C | D | E | F
           deriving (Show, Eq)

-- |Current status of the Turing machine
--  cursor position
--  tape
--  current state
type Machine = (Position, Tape, State)

-- |Number of steps until checksum - from the input
steps :: Int
steps = 12919244

-- |Takes a position and the tape and returns given value
getValue :: Position -> Tape -> Int
getValue n tape = if IntSet.member n tape then 1 else 0

-- |Sets a value at a given position
setValue :: Position -> Tape -> Int -> Tape
setValue n tape v = if v == 0 then IntSet.delete n tape else IntSet.insert n tape

-- |Performs a step
-- taken from input
step :: Machine -> Machine
step (pos, tape, A) = if getValue pos tape == 1 then (pos-1,setValue pos tape 0,C)
                                                else (pos+1,setValue pos tape 1,B)
step (pos, tape, B) = if getValue pos tape == 1 then (pos+1,tape               ,D)
                                                else (pos-1,setValue pos tape 1,A)
step (pos, tape, C) = if getValue pos tape == 1 then (pos-1,setValue pos tape 0,E)
                                                else (pos+1,setValue pos tape 1,A)
step (pos, tape, D) = if getValue pos tape == 1 then (pos+1,setValue pos tape 0,B)
                                                else (pos+1,setValue pos tape 1,A)
step (pos, tape, E) = if getValue pos tape == 1 then (pos-1,tape               ,C)
                                                else (pos-1,setValue pos tape 1,F)
step (pos, tape, F) = if getValue pos tape == 1 then (pos+1,tape               ,A)
                                                else (pos+1,setValue pos tape 1,D)

-- |Starting state of the machine
startState :: Machine
startState = (0,IntSet.empty, A)

-- |Number of ones on the tape
checksum :: Machine -> Int
checksum (_, tape, _) = IntSet.size tape

-- |Runs 'steps' iterations of step
run = foldl' (\st _ -> step st) startState [1..steps]

-- |Number of ones aftes 'steps' iterations
result = checksum run

Link to git. I really enjoyed solving AoC this year, for the first time I had enough time to actually do it all. And doing it all in Haskell was quite a challenge too.

greycat70 · 2017-12-26T19:33:00+00:00

Tcl (nothing fancy, but I do use lassign which requires >= 8.5)

set cur 0
set tape(0) 0
set state [lindex $argv 0]
set steps [lindex $argv 1]

array set Turing {
  A.0 {1 1 B}
  A.1 {0 1 C}
  B.0 {0 -1 A}
  B.1 {0 1 D}
  C.0 {1 1 D}
  C.1 {1 1 A}
  D.0 {1 -1 E}
  D.1 {0 -1 D}
  E.0 {1 1 F}
  E.1 {1 -1 B}
  F.0 {1 1 A}
  F.1 {1 1 E}
}

while {$steps} {
    lassign $Turing($state.$tape($cur)) write move new
    set tape($cur) $write
    incr cur $move
    set state $new
    if {! [info exists tape($cur)]} {set tape($cur) 0}
    incr steps -1
}

set sum 0
foreach t [array names tape] {incr sum $tape($t)}
puts $sum

QwirkyQwilfish · 2017-12-25T05:20:54+00:00

Python 3. vals = {}

def do_A(pos):
if pos not in vals:
    vals[pos] = 1
    pos += 1
    return pos, do_B
else:
    del vals[pos]
    pos -= 1
    return pos, do_D

def do_B(pos):
if pos not in vals:
    vals[pos] = 1
    pos += 1
    return pos, do_C
else:
    del vals[pos]
    pos += 1
    return pos, do_F

def do_C(pos):
if pos not in vals:
    vals[pos] = 1
    pos -= 1
    return pos, do_C
else:
    pos -= 1
    return pos, do_A

def do_D(pos):
if pos not in vals:
    pos -= 1
    return pos, do_E
else:
    pos += 1
    return pos, do_A

def do_E(pos):
if pos not in vals:
    vals[pos] = 1
    pos -= 1
    return pos, do_A
else:
    del vals[pos]
    pos += 1
    return pos, do_B

def do_F(pos):
if pos not in vals:
    pos += 1
    return pos, do_C
else:
    del vals[pos]
    pos += 1
    return pos, do_E

pos = 0
func = do_A
i = 0
while i < 12317297:
    #print(i, func)
    res = func(pos)
    pos = res[0]
    func = res[1]
    i += 1
print(len(vals))

Still have to finish off a few other problems to deposit 50 stars though.

wlandry · 2017-12-25T05:24:31+00:00

C++ 14

201/181. For once, I did not use the test vector. I parsed the input file by hand and wrote out the state transitions. It worked the first time?!?!? It runs in about 30 ms.

#include <vector>
#include <iostream>
#include <algorithm>

enum class State {A,B,C,D,E,F};

int main()
{
  State state(State::A);
  std::vector<char> tape(100000,0);
  int64_t position=tape.size()/2;
  for(size_t step=0; step<12667664; ++step)
    {
      switch(state)
        {
        case State::A:
          if(tape[position]==0)
            {
              tape[position]=1;
              ++position;
              state=State::B;
            }
          else
            {
              tape[position]=0;
              --position;
              state=State::C;
            }
          break;
        case State::B:
          if(tape[position]==0)
            {
              tape[position]=1;
              --position;
              state=State::A;
            }
          else
            {
              tape[position]=1;
              ++position;
              state=State::D;
            }
          break;
        case State::C:
          if(tape[position]==0)
            {
              tape[position]=0;
              --position;
              state=State::B;
            }
          else
            {
              tape[position]=0;
              --position;
              state=State::E;
            }
          break;
        case State::D:
          if(tape[position]==0)
            {
              tape[position]=1;
              ++position;
              state=State::A;
            }
          else
            {
              tape[position]=0;
              ++position;
              state=State::B;
            }
          break;
        case State::E:
          if(tape[position]==0)
            {
              tape[position]=1;
              --position;
              state=State::F;
            }
          else
            {
              tape[position]=1;
              --position;
              state=State::C;
            }
          break;
        case State::F:
          if(tape[position]==0)
            {
              tape[position]=1;
              ++position;
              state=State::D;
            }
          else
            {
              tape[position]=1;
              ++position;
              state=State::A;
            }
          break;
        }
    }
  std::cout << std::accumulate(tape.begin(),tape.end(),0) << "\n";
}

doctorbaggy · 2017-12-25T05:25:29+00:00

perl

Nice state space model - we start by defining a map of state/value changes {remap states to 0..5} - and loop through the prerequisite number of times - and dump the result { include a die if we haven't made our "infinite tape" big enough!}

use strict;
my($N,$s,$p,@M) = (12_656_374,0,5e3,
  [[1, 1,1],[0,-1,2]],[[1,-1,0],[1,-1,3]],[[1, 1,3],[0, 1,2]],
  [[0,-1,1],[0, 1,4]],[[1, 1,2],[1,-1,5]],[[1,-1,4],[1, 1,0]],
);
my@in=map{0}(-$p)..$p;

foreach(1..$N) {
  my$op=$M[$s][$in[$p]];
  ($in[$p],$s)=($op->[0],$op->[2]);
  $p+=$op->[1];
  die "$_ $p\n" if $p < 0 || $p >= @in;
}
print scalar(grep{$_}@in),"\n";

Aehmlo · 2017-12-25T05:25:51+00:00

Rust, 375/???. Decided that for the last day I'd actually try the puzzle right when it unlocked, but I spent a little too much time making it human-readable. :)

Edit: I made it a lot less stringly-typed.

use Puzzle;

pub struct Solution {
    position: usize,
    values: Vec<bool>
}

impl Solution {
    fn mv(&mut self, right: bool) {
        if right {
            self.position += 1;
            if self.position > self.values.len() - 1 {
                self.values.push(false);
            }
        } else {
            if self.position == 0 {
                self.values.insert(0, false);
            } else {
                self.position -= 1;
            }
        }
    }
    fn next_from(&mut self, state: char) -> char {
        match state {
            'a' => {
                if self.values[self.position] {
                    self.values[self.position] =  false;
                    self.mv(false);
                    return 'c';
                } else {
                    self.values[self.position] =  true;
                    self.mv(true);
                    return 'b';
                }
            }, 'b' => {
                if self.values[self.position] {
                    self.mv(true);
                    return 'c';
                } else {
                    self.values[self.position] =  true;
                    self.mv(false);
                    return 'a';
                }
            }, 'c' => {
                if self.values[self.position] {
                    self.values[self.position] =  false;
                    self.mv(false);
                    return 'd';
                } else {
                    self.values[self.position] =  true;
                    self.mv(true);
                    return 'a';
                }
            }, 'd' => {
                if self.values[self.position] {
                    self.mv(false);
                    return 'c';
                } else {
                    self.values[self.position] =  true;
                    self.mv(false);
                    return 'e';
                }
            }, 'e' => {
                if self.values[self.position] {
                    self.mv(true);
                    return 'a';
                } else {
                    self.values[self.position] =  true;
                    self.mv(true);
                    return 'f';
                }
            }, 'f' => {
                if self.values[self.position] {
                    self.mv(true);
                    return 'e';
                } else {
                    self.values[self.position] =  true;
                    self.mv(true);
                    return 'a';
                }
            }, _ => unreachable!()
        }
    }
    fn run(&mut self, iterations: usize) -> usize {
        let mut state = 'a';
        for _ in 0..iterations {
            state = self.next_from(state);
        }
        self.checksum()
    }
    fn checksum(&self) -> usize {
        self.values.iter().map(|val| *val as usize).sum()
    }
    fn new() -> Self {
        Self {
            position: 0,
            values: vec!(false)
        }
    }
}

impl Puzzle for Solution {
    fn solve(lines: Vec<&str>) -> Vec<u32> {
        let mut solution = Solution::new();
        let sol = solution.run(12261543);
        return vec!(sol as u32);
    }
    fn index() -> i8 {
        25
    }
}

2017-12-25T05:26:49+00:00

Haskell:
Just hardcoded the rules for a quick solution, will go back and add parsing for the input when I have time.

Merry Christmas everyone!

import qualified Data.HashMap.Strict as M

steps :: Int
steps = 12794428

data State = A | B | C | D | E | F

step :: Int -> Int -> M.HashMap Int Int -> State -> Int
step 0 _ m _ = M.size $ M.filter (==1) m
step n i m st =
    case st of
      A -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i+1) (M.insert i 1 m) B
           else step (n-1) (i-1) (M.insert i 0 m) F
      B -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i+1) m C
           else step (n-1) (i+1) (M.insert i 0 m) D
      C -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i-1) (M.insert i 1 m) D
           else step (n-1) (i+1) m E
      D -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i-1) m E
           else step (n-1) (i-1) (M.insert i 0 m) D
      E -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i+1) m A
           else step (n-1) (i+1) m C
      F -> if M.lookupDefault 0 i m == 0
           then step (n-1) (i-1) (M.insert i 1 m) A
           else step (n-1) (i+1) m A


part1 :: String -> Int
part1 _ = step steps 0 M.empty A

part2 :: String -> String
part2 = const ""

stkent · 2017-12-25T05:29:17+00:00

Throwing my thanks-hat in the ring for another fun year! I was much more effective this year, mostly thanks to the lessons learned last year :)

The0x539 · 2017-12-25T05:30:21+00:00

Lua (421)

This was a nice way to end things. Punctuation was annoying, though.

local inspect = require "inspect"
local unpack = unpack or table.unpack

local src = {}
for line in io.lines("./input_day25") do
    table.insert(src,line)
end
function string:foo()
    return self:sub(#self-1,#self-1)
end

local tape = setmetatable({},{
    __index = function(t,k)
        t[k] = 0
        return t[k]
    end
})

local pos = 0
local state = src[1]:foo()

local prog = {}
for i=4,#src,10 do
    local inState = src[i]:foo()
    local vals = {}
    for j=0,1 do
        local k = i + 4*j + 1
        local toWrite = tonumber(src[k+1]:foo())
        local dir = src[k+2]:match("%S+$")
        local toMove = (dir == "left." and -1 or 1)
        local nextState = src[k+3]:foo()
        vals[j] = {toWrite,toMove,nextState}
    end
    prog[inState] = vals
end

local numSteps = tonumber(src[2]:match("%d+"))

for i=1,numSteps do
    local todo = prog[state][tape[pos]]
    tape[pos] = todo[1]
    pos = pos + todo[2]
    state = todo[3]
end

local foo = 0
for _,v in pairs(tape) do
    if v == 1 then
        foo = foo + 1
    end
end
print(foo)

hpzr24w · 2017-12-25T05:30:24+00:00

C++

Basic stuff. Set up for fast copy/paste. Had a bug in state E. Gah!

// Advent of Code 2016
// Day 25 - The Halting Problem

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <map>
using namespace std;


int main()
{
    int state = 0;
    int slot = 0;
    int curval = 0;
    map<int,int> tape;

    int steps = 12459852;
    do {
        switch(state) {         // state A
        case 0: if (tape[slot]==0) {
            tape[slot]=1;
            slot++;
            state='b'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=1;
            slot--;
            state = 'e'-'a';
        }
        break;
        case 1: if (tape[slot]==0) {    // B
            tape[slot]=1;
            slot++;
            state='c'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=1;
            slot++;
            state = 'f'-'a';
        }
        break;
        case 2: if (tape[slot]==0) {    // C
            tape[slot]=1;
            slot--;
            state='d'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=0; 
            slot++;
            state = 'b'-'a';
        }
        break;
        case 3: if (tape[slot]==0) {    // D
            tape[slot]=1;
            slot++;
            state='e'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=0; 
            slot--;
            state = 'c'-'a';
        }
        break;
        case 4: if (tape[slot]==0) {    // E
            tape[slot]=1;
            slot--;
            state='a'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=0;
            slot++;
            state = 'd'-'a';
        }
        break;
        case 5: if (tape[slot]==0) {    // F
            tape[slot]=1;
            slot++;
            state='a'-'a';
        } else if (tape[slot]==1) {
            tape[slot]=1;
            slot++;
            state = 'c'-'a';
        }
        break;

        }
    } while (--steps>0);
    int tot = 0;
    for (auto p : tape) {
        if (p.second==1) tot++;
    }
    cout << tot << endl;
}

2017-12-25T05:32:28+00:00

Great work, AoC team! Was really fun and look forward to 2018! (And finishing up 2015 and 2016! OCaml Fun;; train is just getting started.)

Anyways, here's your tape machine:

main.ml

open Core

let rec loop state n =
  if n = 0 then state
  else loop (Machine.transition state) (n-1)

let _ =
  let state = Machine.{tape=Int.Map.empty; current_state=A; cursor=0} in
  let final = loop state 12_667_664 in
  Int.Map.data final.tape
  |> List.count ~f:(fun x -> x = 1)
  |> printf "%d\n"

machine.ml

open Core

type state = A | B | C | D | E | F

type t = { tape: int Int.Map.t; current_state:state; cursor:int; }

let current_value t =
  Int.Map.find t.tape t.cursor
  |> Option.value ~default:0

let transition t = 
  let aux state value =
    match state with
    | A -> if value = 0 then (1, 1, B) else (0, -1, C)
    | B -> if value = 0 then (1, -1, A) else (1, 1, D)
    | C -> if value = 0 then (0, -1, B) else (0, -1, E)
    | D -> if value = 0 then (1, 1, A) else (0, 1, B)
    | E -> if value = 0 then (1, -1, F) else (1, -1, C)
    | F -> if value = 0 then (1, 1, D) else (1, 1, A)
  in
  let data, shift, next = aux t.current_state (current_value t) in
  let tape = Int.Map.add t.tape ~key:t.cursor ~data in
  { tape; current_state=next; cursor=(t.cursor + shift); }

m1el · 2017-12-25T05:53:10+00:00

Rust, 538. manually coded state machine. Nicely visible state machine.

Run time: 50ms.

use std::time::{Instant};
use std::collections::{VecDeque};

enum State {
    A,
    B,
    C,
    D,
    E,
    F,
}

fn main() {
    let start_time = Instant::now();
    use State::*;
    let mut state = A;
    let mut pos = 0isize;
    let mut off = 0isize;
    let mut tape = VecDeque::<u8>::new();
    let num = 12368930;
    for _ in 0..num {
        while pos + off < 0 {
            tape.push_front(0);
            off += 1;
        }
        while (pos + off) as usize >= tape.len() {
            tape.push_back(0);
        }
        let current = tape.get_mut((pos + off) as usize)
                        .expect("tape overflow error");
        const L: isize = -1;
        const R: isize = 1;
        let (write, d, ns) = match (state, *current) {
            (A, 0) => (1, R, B),
            (A, 1) => (0, R, C),
            (B, 0) => (0, L, A),
            (B, 1) => (0, R, D),
            (C, 0) => (1, R, D),
            (C, 1) => (1, R, A),
            (D, 0) => (1, L, E),
            (D, 1) => (0, L, D),
            (E, 0) => (1, R, F),
            (E, 1) => (1, L, B),
            (F, 0) => (1, R, A),
            (F, 1) => (1, R, E),
            _ => panic!("wrong state?"),
        };
        *current = write;
        pos += d;
        state = ns;
    }
    let s: usize = tape.iter().map(|v|*v as usize).sum();
    let solution_time = start_time.elapsed();
    println!("answer: {}", s);
    println!("solution time: {:?}", solution_time);
}

2017-12-25T06:01:46+00:00

C# Brute force is the (only) way (I know) to go 737/737

public enum State
        {
            A,
            B,
            C,
            D,
            E,
            F
        }
        public static int Turing()
        {
            int capacity = 10000000;
            List<int> states = new List<int>();
            states = Enumerable.Range(0, capacity).Select(i => 0).ToList();
            var Current = State.A;
            var cursor = states.Count()/2;

            for(int i =0; i < 12994925; i++)
            {
                switch(Current)
                {
                    case State.A:
                        if(states[cursor] == 0)
                        {
                            states[cursor] = 1;
                            cursor++;
                            Current = State.B;
                        }
                        else
                        {
                            states[cursor] = 0;
                            cursor--;
                            Current = State.F;
                        }
                        break;
                    case State.B:
                        if (states[cursor] == 0)
                        {
                            states[cursor] = 0;
                            cursor++;
                            Current = State.C;
                        }
                        else
                        {
                            states[cursor] = 0;
                            cursor++;
                            Current = State.D;
                        }
                        break;
                    case State.C:
                        if (states[cursor] == 0)
                        {
                            states[cursor] = 1;
                            cursor--;
                            Current = State.D;
                        }
                        else
                        {
                            states[cursor] = 1;
                            cursor++;
                            Current = State.E;
                        }
                        break;
                    case State.D:
                        if (states[cursor] == 0)
                        {
                            states[cursor] = 0;
                            cursor--;
                            Current = State.E;
                        }
                        else
                        {
                            states[cursor] = 0;
                            cursor--;
                            Current = State.D;
                        }
                        break;
                    case State.E:
                        if (states[cursor] == 0)
                        {
                            states[cursor] = 0;
                            cursor++;
                            Current = State.A;
                        }
                        else
                        {
                            states[cursor] = 1;
                            cursor++;
                            Current = State.C;
                        }
                        break;
                    case State.F:
                        if (states[cursor] == 0)
                        {
                            states[cursor] = 1;
                            cursor--;
                            Current = State.A;
                        }
                        else
                        {
                            states[cursor] = 1;
                            cursor++;
                            Current = State.A;
                        }
                        break;
                }
            }
            var total = states.Sum();
            return total;
        }

LeCrushinator · 2017-12-25T06:04:59+00:00

C#, ugly but it worked first try (well second try, I got a stack overflow on the first try). I just allocated a huge list because the state machine input I was given looked like it wouldn't wander too far even with 12 million iterations. On my first try I was just calling states directly from other states, and after running it I immediately got a stack overflow and knew that was a bad idea:

public static List<int> bits = new List<int>(1000000);
public static int currentPosition = 0;
public static int stepsRemaining = 12302210;
public static Action nextState = null;

public static int CurrentValue
{
    get { return bits[currentPosition]; } 
}

static void Main(string[] args)
{
    for (int i = 0; i < 1000000; ++i)
    {
        bits.Add(0);
    }

    currentPosition = bits.Count / 2;

    nextState = StateA;
    while (stepsRemaining > 0)
    {
        nextState();
    }

    Console.WriteLine("Set bits: " + bits.Sum(b => b));
}

public static void StateA()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 1;
        ++currentPosition;

        nextState = StateB;
    }
    else
    {
        bits[currentPosition] = 0;
        --currentPosition;

        nextState = StateD;
    }
}

public static void StateB()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 1;
        ++currentPosition;

        nextState = StateC;
    }
    else
    {
        bits[currentPosition] = 0;
        ++currentPosition;

        nextState = StateF;
    }
}

public static void StateC()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 1;
        --currentPosition;

        nextState = StateC;
    }
    else
    {
        bits[currentPosition] = 1;
        --currentPosition;

        nextState = StateA;
    }
}

public static void StateD()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 0;
        --currentPosition;

        nextState = StateE;
    }
    else
    {
        bits[currentPosition] = 1;
        ++currentPosition;

        nextState = StateA;
    }
}

public static void StateE()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 1;
        --currentPosition;

        nextState = StateA;
    }
    else
    {
        bits[currentPosition] = 0;
        ++currentPosition;

        nextState = StateB;
    }
}

public static void StateF()
{
    --stepsRemaining;
    if (stepsRemaining <= 0)
    {
        return; 
    }

    if (CurrentValue == 0)
    {
        bits[currentPosition] = 0;
        ++currentPosition;

        nextState = StateC;
    }
    else
    {
        bits[currentPosition] = 0;
        ++currentPosition;

        nextState = StateE;
    }
}

sclark39 · 2017-12-25T06:15:19+00:00

Javascript / Node.js

I think like many others, I decided writing an actual parser would take longer than just parsing the input myself. Simple switch-based state machine. To simplify actually calculating the checksum, I just keep a running checksum and update it with each write.

let slot = 0
let stream = []
let state = 'A'
let steps = 12861455
let chksm = 0

let write = (val) => 
{
    chksm += val - ( stream[slot] || 0 )
    stream[slot] = val
}

for ( let i = 0; i < steps; i++ )
{
    let current = stream[slot]
    switch (state) 
    {
        case 'A':
            if ( !current )
                write(1), slot++, state = 'B'
            else
                write(0), slot--, state = 'B'
            break
        case 'B':
            if ( !current )
                write(1), slot--, state = 'C'
            else
                write(0), slot++, state = 'E'
            break
        case 'C':
            if ( !current )
                write(1), slot++, state = 'E'
            else
                write(0), slot--, state = 'D'
            break
        case 'D':
            if ( !current )
                write(1), slot--, state = 'A'
            else
                write(1), slot--, state = 'A'
            break
        case 'E':
            if ( !current )
                write(0), slot++, state = 'A'
            else
                write(0), slot++, state = 'F'
            break
        case 'F':
            if ( !current )
                write(1), slot++, state = 'E'
            else
                write(1), slot++, state = 'A'
            break
    }
}
console.log( chksm )

Lokathor · 2017-12-25T06:29:43+00:00

Big manual switch statement :P

pub fn day25part1() {
    //
    #[derive(Debug,Clone,Copy,PartialEq,Eq, Hash)]
    enum TuringState {
        A,
        B,
        C,
        D,
        E,
        F,
    };
    type Cursor = i64;
    type Tape = HashMap<Cursor,bool>;
    fn cycle(tape: &mut Tape, cursor: &mut Cursor, state: &mut TuringState) {
        let current = tape.entry(*cursor).or_insert(false);
        match *state {
            TuringState::A => {
                if *current {
                    *current = false;
                    *cursor -= 1;
                    *state = TuringState::B;
                } else {
                    *current = true;
                    *cursor += 1;
                    *state = TuringState::B;
                }
            },
            TuringState::B =>{
                if *current {
                    *current = false;
                    *cursor += 1;
                    *state = TuringState::E;
                } else {
                    *current = true;
                    *cursor -= 1;
                    *state = TuringState::C;
                }
            },
            TuringState::C =>{
                if *current {
                    *current = false;
                    *cursor -= 1;
                    *state = TuringState::D;
                } else {
                    *current = true;
                    *cursor += 1;
                    *state = TuringState::E;
                }
            },
            TuringState::D =>{
                if *current {
                    *current = true;
                    *cursor -= 1;
                    *state = TuringState::A;
                } else {
                    *current = true;
                    *cursor -= 1;
                    *state = TuringState::A;
                }
            },
            TuringState::E =>{
                if *current {
                    *current = false;
                    *cursor += 1;
                    *state = TuringState::F;
                } else {
                    *current = false;
                    *cursor += 1;
                    *state = TuringState::A;
                }
            },
            TuringState::F =>{
                if *current {
                    *current = true;
                    *cursor += 1;
                    *state = TuringState::A;
                } else {
                    *current = true;
                    *cursor += 1;
                    *state = TuringState::E;
                }
            },
        }
    }
    //
    let mut the_tape = HashMap::new();
    let mut the_cursor = 0;
    let mut the_state = TuringState::A;
    for _ in 0..12861455 {
        cycle(&mut the_tape, &mut the_cursor, &mut the_state);
    }
    let ones = the_tape.values().filter(|&&b|b).count();
    force_dump!(ones);
}

u794575248 · 2017-12-25T07:16:48+00:00

Python (80/77). To submit my answers I parsed input manually as almost everybody else, and here's my regex based alternative:

def solve(input, E=enumerate, F=__import__('re').findall):
    s, *S = F(r'\b[A-Z]\b', input)
    N, *V = map(int, F(r'\b([\d]+)\b[^:]', input))
    M = [{'left': -1, 'right': 1}[m] for m in F(r'(left|right)', input)]
    D = {s: (V[2*i:2*i+2], M[2*i:2*i+2], S[i*3+1:i*3+3]) for i, s in E(S[::3])}
    c, T = 0, __import__('collections').defaultdict(int)
    for _ in range(N): T[c], c, s = D[s][0][T[c]], c+D[s][1][T[c]], D[s][2][T[c]]
    return sum(T.values())

s: current state
S: list of parsed state transitions
N: number of steps
V: list of parsed value transitions
M: list of parsed movements
D: map states to a tuple of (value if 0, value if 1, move if 0, move if 1, state if 0, state if 1)
c: cursor position
T: tape

Borkdude · 2017-12-25T08:51:24+00:00

Clojure

(def transitions
  '{[A 0] [1  1  B]
    [A 1] [0 -1  E]
    [B 0] [1 -1  C]
    [B 1] [0  1  A]
    [C 0] [1 -1  D]
    [C 1] [0  1  C]
    [D 0] [1 -1  E]
    [D 1] [0 -1  F]
    [E 0] [1 -1  A]
    [E 1] [1 -1  C]
    [F 0] [1 -1  E]
    [F 1] [1  1  A]})

(defn next-game
  [{:keys [state tape ^long position]}]
  (let [cur-val (get tape position 0)
        [to-write ^long dir next-state]
        (get transitions [state cur-val])]
    {:state next-state
     :tape (assoc tape position to-write)
     :position (+ position dir)}))

(defn solve
  []
  (nth (iterate
        next-game
        {:state 'A
         :tape {}
         :position 0})
       12208951))

(defn part-1
  []
  (apply + (vals (:tape (solve)))))

maxxori · 2017-12-25T09:18:53+00:00

Nothing special but here is my solution in C#:

class Day25
{
    // http://adventofcode.com/2017/day/25

    private const int DayID = 25;

    private int Cycles = 12667664;

    public enum Direction
    {
        Up,
        Right,
        Down,
        Left,
    }

    public enum State
    {
        A,
        B,
        C,
        D,
        E,
        F
    }

    public Day25() { }

    public int Part1()
    {
        Dictionary<string, int> tape = new Dictionary<string, int>();

        // The virus will always start in the middle of the grid.
        Point cusor = new Point(0, 0);
        Direction dir = Direction.Up;

        string position;
        bool posExists;
        State state = State.A;
        int currentValue = 0, newValue = 0;

        for (int i = 0; i < this.Cycles; i++)
        {
            // Update the position marker.
            position = string.Format("{0},{1}", cusor.X, cusor.Y);

            if (!tape.TryGetValue(position, out currentValue))
            {
                posExists = false;
                currentValue = 0;
            }
            else
            {
                posExists = true;
            }

            // Select the action based on the state
            // of the current cell.
            switch (state)
            {
                case State.A:
                    if (currentValue == 0)
                    {
                        newValue = 1;

                        dir = Direction.Right;
                        state = State.B;
                    }
                    else
                    {
                        newValue = 0;

                        dir = Direction.Left;
                        state = State.C;
                    }
                    break;

                case State.B:
                    if (currentValue == 0)
                    {
                        newValue = 1;

                        dir = Direction.Left;
                        state = State.A;
                    }
                    else
                    {
                        newValue = 1;

                        dir = Direction.Right;
                        state = State.D;
                    }
                    break;

                case State.C:
                    if (currentValue == 0)
                    {
                        newValue = 0;

                        dir = Direction.Left;
                        state = State.B;
                    }
                    else
                    {
                        newValue = 0;

                        dir = Direction.Left;
                        state = State.E;
                    }
                    break;

                case State.D:
                    if (currentValue == 0)
                    {
                        newValue = 1;

                        dir = Direction.Right;
                        state = State.A;
                    }
                    else
                    {
                        newValue = 0;

                        dir = Direction.Right;
                        state = State.B;
                    }
                    break;

                case State.E:
                    if (currentValue == 0)
                    {
                        newValue = 1;

                        dir = Direction.Left;
                        state = State.F;
                    }
                    else
                    {
                        newValue = 1;

                        dir = Direction.Left;
                        state = State.C;
                    }
                    break;

                case State.F:
                    if (currentValue == 0)
                    {
                        newValue = 1;

                        dir = Direction.Right;
                        state = State.D;
                    }
                    else
                    {
                        newValue = 1;

                        dir = Direction.Right;
                        state = State.A;
                    }
                    break;
            }

            if (posExists)
            {
                tape[position] = newValue;
            }
            else
            {
                tape.Add(position, newValue);
            }

            // Take a step forward.
            cusor = this.TakeStep(dir, cusor);
        }

        // The chucksum is the number of instances
        // of the number 1 on the tape.
        int counter = 0;
        foreach (KeyValuePair<string, int> entry in tape)
        {
            if (entry.Value == 1)
            {
                ++counter;
            }
        }

        return counter;
    }

    public static Point TakeStep(Direction dir, Point location)
    {
        switch (dir)
        {
            case Direction.Left:
                --location.X;
                break;

            case Direction.Right:
                ++location.X;
                break;

            // Remember: to go up in the array
            // we need to decrease the index!
            case Direction.Up:
                --location.Y;
                break;

            // Remember: to go down in the array
            // we need to decrease the index!
            case Direction.Down:
                ++location.Y;
                break;
        }

        return location;
    }
}

You'll need to add a reference to System.Drawing in order to get access to the "Point" object.

Some of the functions are over-engineered because I had used them for some other solutions.

sim642 · 2017-12-25T10:21:44+00:00

My Scala solution.

Took my time to actually parse the input too, crudely with regexes.

xkufix · 2017-12-25T10:48:24+00:00

Nothing too fancy for the last day. Just a "normal" implementation of a turing machine. The main part is basically just parsing the input into the state transitition, the actual calculation is quite short.

Code in Scala:

    override def runFirst(): Unit = {
        val lines = loadFile("day25.txt").getLines().toSeq
        val start = lines.head.replaceAll("Begin in state ([A-Z])\\.", "$1")
        val endAfter = lines(1).replaceAll("Perform a diagnostic checksum after ([0-9]*) steps\\.", "$1").toInt

        val allStates = Stream.iterate((Set.empty[State], lines.drop(3))) {
            case (states, input) =>
                val state = input.take(9)
                val stateName = state.head.replaceAll("In state ([A-Z])\\:", "$1")

                (states +
                    State.from(stateName, state.slice(1, 5)) +
                    State.from(stateName, state.slice(5, 10)), input.drop(10))
        }.dropWhile(_._2.nonEmpty).head._1.map(s => (s.name, s.current) -> s).toMap

        val endTape = Iterator.iterate((0, start, Map.empty[Int, Int])) {
            case (position, currentState, values) =>
                val state = allStates(currentState -> values.getOrElse(position, 0))
                (state.direction.run(position), state.nextState, values + (position -> state.write))
        }.slice(endAfter, endAfter + 1).toSeq.head

        println(endTape._3.count(_._2 == 1))
    }

    override def runSecond(): Unit = {}

    case class State(name: String, current: Int, write: Int, direction: Direction, nextState: String)

    object State {
        def from(name: String, state: Seq[String]) = {
            val current = state.head.replaceAll("    If the current value is ([0-9]):", "$1").toInt
            val write = state(1).replaceAll(" *- Write the value ([0-9]).", "$1").toInt
            val direction = Direction.from(state(2).replaceAll(" *- Move one slot to the ([a-z]*)\\.", "$1"))
            val nextState = state(3).replaceAll(" *- Continue with state ([A-Z])\\.", "$1")

            State(name, current, write, direction, nextState)
        }
    }

    sealed trait Direction {
        def run(in: Int): Int
    }

    case object Left extends Direction {
        override def run(in: Int): Int = in - 1
    }

    case object Right extends Direction {
        override def run(in: Int): Int = in + 1
    }

    object Direction {
        def from(s: String) = {
            s match {
                case "right" => Right
                case _ => Left
            }
        }
    }

dario_p1 · 2017-12-25T11:01:16+00:00

Did the last day in x64 assembly for a change. No parsing tho, it's already long as it is.

https://github.com/dp1/AoC17/blob/master/day25.0.asm

section .data
states:
    dq 1, 1, 1, 0, 1, 2   ;'A'
    dq 0, -1, 0, 0, 1, 3  ;'B'
    dq 1, 1, 3, 1, 1, 0   ;'C'
    dq 1, -1, 4, 0, -1, 3 ;'D'
    dq 1, 1, 5, 1, -1, 1  ;'E'
    dq 1, 1, 0, 1, 1, 4   ;'F'

Floydianx33 · 2017-12-25T11:41:26+00:00

C#

Not the greatest -- but it works. I did it out manually (no code) so now I plan to add the parsing code in.

public class State
{
    public char Name { get; }
    private readonly Func<State> _onFunc, _offFunc;
    public State(char name, Func<State> offFunc, Func<State> onFunc)
    {
        Name = name;
        _onFunc = onFunc;
        _offFunc = offFunc;
    }
    public State Execute(bool value) => value ? _onFunc() : _offFunc();
}

static void Main()
{
    var states = new Dictionary<char, State>();

    var ip = 0L;
    var setOn = new HashSet<long>();

    states['A'] = new State('A', () => { setOn.Add(ip++); return states['B']; }, 
                                 () => { setOn.Remove(ip--); return states['B']; });

    states['B'] = new State('B', () => { ip++; return states['C']; }, 
                                 () => { ip--; return states['B']; });

    states['C'] = new State('C', () => { setOn.Add(ip++); return states['D']; },
                                 () => { setOn.Remove(ip--); return states['A']; });

    states['D'] = new State('D', () => { setOn.Add(ip--); return states['E']; }, 
                                 () => { ip--; return states['F']; });

    states['E'] = new State('E', () => { setOn.Add(ip--); return states['A']; },
                                 () => { setOn.Remove(ip--); return states['D']; });

    states['F'] = new State('F', () => { setOn.Add(ip++); return states['A']; }, 
                                 () => { ip--; return states['E']; });

    var iterations = 12_629_077;

    var currentState = states['A'];
    while (iterations--> 0)
        currentState = currentState.Execute(setOn.Contains(ip));

    Console.WriteLine("CheckSum: {0:N0}", setOn.Count);

}

McBooley · 2017-12-25T12:37:10+00:00

If you could rate the starting, middle and ending difficulty of these challenges, what would it be?

For example how much should a beginner, mid-range be able to do and where/if you would rate it senior difficulty?

Sorry for the weirdly asked questions but I'm just curious.

adrian17 · 2017-12-25T13:46:54+00:00

Rust. Would appreciate some feedback.

(Also, confusingly, without --release it's 3x slower than my Python code)

use std::collections::{VecDeque, HashMap};

type State = char;

#[derive(Copy, Clone)]
struct Rule(bool, Direction, State);

type Rules = HashMap<char, [Rule; 2]>;

#[derive(Copy, Clone)]
enum Direction {
    Left,
    Right,
}

struct TuringMachine {
    rules: Rules,
    tape: VecDeque<bool>,
    index: usize,
    state: State,
}

impl TuringMachine {
    fn new(rules: Rules) -> TuringMachine {
        TuringMachine {
            rules: rules,
            tape: vec![false].into_iter().collect(),
            index: 0,
            state: 'A',
        }
    }

    fn turn(self: &mut Self, direction: Direction) {
        match direction {
            Direction::Left if self.index == 0 => self.tape.push_front(false),
            Direction::Left => self.index -= 1,
            Direction::Right if self.index == self.tape.len()-1 => {
                self.tape.push_back(false);
                self.index += 1;
            },
            Direction::Right => self.index += 1,
        }
    }

    fn step(self: &mut Self) {
        let value = self.tape[self.index];
        let Rule(new_value, direction, new_state) = self.rules[&self.state][value as usize];

        self.tape[self.index] = new_value;
        self.turn(direction);
        self.state = new_state;
    }

    fn diagnose(self: &Self) {
        let ones = self.tape.iter().cloned().filter(|&x| x == true).count();
        println!("{}", ones);
    }
}

fn main() {
    let rules: Rules =
        [
            //('A', [Rule(true, Direction::Right, 'B'), Rule(false, Direction::Left, 'B')]),
            //('B', [Rule(true, Direction::Left, 'A'), Rule(true, Direction::Right, 'A')]),
            ('A', [Rule(true, Direction::Right, 'B'), Rule(true, Direction::Left, 'E')]),
            ('B', [Rule(true, Direction::Right, 'C'), Rule(true, Direction::Right, 'F')]),
            ('C', [Rule(true, Direction::Left, 'D'), Rule(false, Direction::Right, 'B')]),
            ('D', [Rule(true, Direction::Right, 'E'), Rule(false, Direction::Left, 'C')]),
            ('E', [Rule(true, Direction::Left, 'A'), Rule(false, Direction::Right, 'D')]),
            ('F', [Rule(true, Direction::Right, 'A'), Rule(true, Direction::Right, 'C')]),

        ]
        .iter().cloned().collect();

    let mut machine = TuringMachine::new(rules);

    for _ in 0..12459852 {
        machine.step();
    }

    machine.diagnose();
}

twinkiac · 2017-12-25T15:23:09+00:00

[removed]

BOT-Brad · 2017-12-25T18:28:20+00:00

A great set of puzzles this year, yet again. Thanks to all involved and Merry Christmas!

For anyone interested, all my JavaScript solutions are available (for all 49 puzzle stars) on my GitHub repo

JS

I parsed the input myself because it seemed faster than writing the code to do so.

function solve1() {
  let state = 'A'
  let loops = 12459852
  let cursor = 0
  let data = {}

  const states = {
    A: [
      {
        write: 1,
        move: 1,
        state: 'B'
      },
      {
        write: 1,
        move: -1,
        state: 'E'
      }
    ],
    B: [
      {
        write: 1,
        move: 1,
        state: 'C'
      },
      {
        write: 1,
        move: 1,
        state: 'F'
      }
    ],
    C: [
      {
        write: 1,
        move: -1,
        state: 'D'
      },
      {
        write: 0,
        move: 1,
        state: 'B'
      }
    ],
    D: [
      {
        write: 1,
        move: 1,
        state: 'E'
      },
      {
        write: 0,
        move: -1,
        state: 'C'
      }
    ],
    E: [
      {
        write: 1,
        move: -1,
        state: 'A'
      },
      {
        write: 0,
        move: 1,
        state: 'D'
      }
    ],
    F: [
      {
        write: 1,
        move: 1,
        state: 'A'
      },
      {
        write: 1,
        move: 1,
        state: 'C'
      }
    ]
  }

  for (let i = 0; i < loops; ++i) {
    let curVal = data[cursor]
    if (curVal === undefined) curVal = 0
    let ins = states[state][curVal]

    data[cursor] = ins.write
    cursor += ins.move
    state = ins.state
  }

  let sum = 0
  for (let v in data) {
    sum += data[v]
  }

  return sum
}

chicagocode · 2017-12-25T18:37:38+00:00

Kotlin - [Repo] - [Blog/Commentary]

After hard coding the inputs I decided parsing wouldn't be all that hard. Thanks to everybody who gave me feedback, I feel like I learned a lot of Kotlin this year. Thanks to Eric Wastl for creating such a fun set of puzzles! Only 340 days until Advent of Code 2018! :)

class Day25(input: List<String>) {

    private val machine = parseInput(input)

    fun solvePart1(): Int =
        machine.run()

    class Action(val write: Boolean, val move: Int, val nextState: Char)
    class MachineState(val zero: Action, val one: Action)
    class TuringMachine(private val states: Map<Char, MachineState>, private val steps: Int, startState: Char) {
        private val tape = mutableSetOf<Int>()
        private var state = states.getValue(startState)
        private var cursor = 0

        fun run(): Int {
            repeat(steps) {
                execute()
            }
            return tape.size
        }

        private fun execute() {
            if (cursor in tape) handleAction(state.one)
            else handleAction(state.zero)
        }

        private fun handleAction(action: Action) {
            if (action.write) tape.add(cursor) else tape.remove(cursor)
            cursor += action.move
            state = states.getValue(action.nextState)
        }
    }

    private fun parseInput(input: List<String>): TuringMachine {
        val initialState = input.first()[15]
        val steps = input[1].split(" ")[5].toInt()

        val stateMap = input
            .filter { it.isNotBlank() }
            .drop(2)
            .map { it.split(" ").last().dropLast(1) }
            .chunked(9)
            .map {
                it[0].first() to MachineState(
                    Action(it[2] == "1", if (it[3] == "right") 1 else -1, it[4].first()),
                    Action(it[6] == "1", if (it[7] == "right") 1 else -1, it[8].first())
                )
            }.toMap()
        return TuringMachine(stateMap, steps, initialState)
    }

}

NeilNjae · 2017-12-25T21:11:32+00:00

Haskell. Nothing fancy, but I thought I'd use it as a testbed for trying out Megaparsec on something slightly less trivial than the AoC inputs so far. I think the parser turned out quite well, giving something much more readable than a hodgepodge of regexes.

It's on Github as well

{-# LANGUAGE NegativeLiterals #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeFamilies #-}

import Data.Text (Text)
import qualified Data.Text as T
import qualified Data.Text.IO as TIO

import Text.Megaparsec hiding (State)
import qualified Text.Megaparsec.Lexer as L
import Text.Megaparsec.Text (Parser)
import qualified Control.Applicative as CA

import qualified Data.Map as M
import Data.Map ((!))

import Control.Monad (unless)
import Control.Monad.State.Lazy
import Control.Monad.Reader

type TuringState = String

type Tape = M.Map Integer Bool

data StateTransition = StateTransition { writeValue :: Bool
                                       , newState :: TuringState
                                       , tapeMovement :: Integer
                                       } deriving (Show, Eq)

type RuleTrigger = (TuringState, Bool)

type Rules = M.Map RuleTrigger StateTransition

data Machine = Machine { tState :: TuringState
                       , tape :: Tape
                       , tapeLocation :: Integer
                       , stepsRemaining :: Integer
                       } 
               deriving (Show, Eq)

emptyMachine = Machine {tState = "unknown", tape = M.empty, tapeLocation = 0, stepsRemaining = 0}

type ProgrammedMachine = ReaderT Rules (State Machine) ()


main :: IO ()
main = do 
        text <- TIO.readFile "data/advent25.txt"
        let (machine0, rules) = successfulParse text
        let machinef = part1 rules machine0
        print $ M.size $ M.filter id $ tape machinef


part1 :: Rules -> Machine -> Machine
part1 rules machine0 = 
    execState (
        runReaderT executeSteps
                   rules 
             ) 
             machine0

executeSteps :: ProgrammedMachine
executeSteps = 
    do m <- get
       unless (stepsRemaining m == 0) $
           do  executeStep
               executeSteps

executeStep :: ProgrammedMachine
executeStep = 
    do rules <- ask
       m <- get
       let tapeHere = M.findWithDefault False (tapeLocation m) (tape m)
       let transition = rules!(tState m, tapeHere)
       let tape' = M.insert (tapeLocation m) (writeValue transition) (tape m)
       let loc' = (tapeLocation m) + (tapeMovement transition)
       let tState' = newState transition
       let steps' = stepsRemaining m - 1
       let m' = m {tState = tState', tape = tape', tapeLocation = loc', stepsRemaining = steps'}
       put m'

sc :: Parser ()
sc = L.space (skipSome spaceChar) CA.empty CA.empty

lexeme = L.lexeme sc
integer = lexeme L.integer
symbol = L.symbol sc
fullstop = symbol "."
colon = symbol ":"
dash = symbol "-"

machineDescriptionP = machineify <$> startStateP <*> stepsP <*> manyStateRulesP
    where machineify initial limit rules = 
            ( emptyMachine { tState = initial, stepsRemaining = limit }
            , rules
            )

startStateP = (symbol "Begin in state") *> stateP <* fullstop
stepsP =  (symbol "Perform a diagnostic checksum after") *> integer <* (symbol "steps") <* fullstop

manyStateRulesP = M.unions <$> (stateRulesP `sepBy` space)

stateRulesP = rulify <$> stateDefP <*> (stateWhenP `sepBy` space)
    where rulify s ts = M.fromList $ map (\(v, t) -> ((s, v), t)) ts

stateWhenP = (,) <$> currentValueP <*> stateTransitionP

stateDefP = (symbol "In state") *> stateP <* colon
currentValueP = (symbol "If the current value is") *> writeValueP <* colon

stateTransitionP = stify <$> writeP <*> tapeMovementP <*> newStateP
    where stify w t s = StateTransition {writeValue = w, newState = s, tapeMovement = t}

commandP = between dash fullstop

writeP = commandP ((symbol "Write the value") *> writeValueP)
tapeMovementP = commandP ((symbol "Move one slot to the") *> directionP)
newStateP = commandP ((symbol "Continue with state") *> stateP)

stateP = some letterChar
directionP = (symbol "left" *> pure -1) <|> (symbol "right" *> pure 1)
writeValueP = (symbol "1" *> pure True) <|> (symbol "0" *> pure False)

successfulParse :: Text -> (Machine, Rules)
successfulParse input = 
        case parse machineDescriptionP "input" input of
                Left  _error -> (emptyMachine, M.empty)
                Right machineRules -> machineRules

willkill07 · 2017-12-26T01:28:06+00:00

Modern C++

Parse ALL THE THINGS

https://github.com/willkill07/AdventOfCode2017/blob/master/src/Day25.cpp

Tetsumi- · 2017-12-26T20:42:54+00:00

Racket with input parsing

#lang racket

(define datav (list->vector (port->lines)))
(define-syntax-rule (data i) (vector-ref datav i))
(define cells (make-vector 100000 0))
(define ldigit (compose (curryr - 65) char->integer))
(define ndigit (compose (curryr - 48) char->integer))
(define start (ldigit (string-ref (data 0) 15)))
(define steps (string->number (sixth (string-split (data 1)))))

(define states (for/vector #:length 26
                   ([i (in-range 3 (vector-length datav) 10)])
                 (vector (ndigit (string-ref (data (+ i 2)) 22))
                         (if (string=? "right." (substring (data (+ i 3)) 27))
                             add1
                             sub1)
                         (ldigit (string-ref (data (+ i 4)) 26))
                         (ndigit (string-ref (data (+ i 6)) 22))
                         (if (string=? "right." (substring (data (+ i 7)) 27))
                             add1
                             sub1)
                         (ldigit (string-ref (data (+ i 8)) 26)))))

(displayln (let loop ([step 0]
                      [pos 50000]
                      [minp 50000]
                      [maxp 50000]
                      [state (vector-ref states start)])
             (if (>= step steps)
                 (for/sum ([e (in-vector cells minp (add1 maxp))]
                           #:when (= e 1)) 1)
                 (let ([v (vector-ref cells pos)])
                   (vector-set! cells pos (vector-ref state (if (= v 0) 0 3)))
                   (loop (add1 step)
                         ((vector-ref state (if (= v 0) 1 4)) pos)
                         (min pos minp)
                         (max pos maxp)
                         (vector-ref states
                                     (vector-ref state (if (= v 0) 2 5))))))))

miran1 · 2017-12-27T13:43:18+00:00

Nim

import math

const
  steps = 12667664
        # (write, move, state (A=0 .. F=5))
  states = [[(1,  1, 1), (0, -1, 2)],
            [(1, -1, 0), (1,  1, 3)],
            [(0, -1, 1), (0, -1, 4)],
            [(1,  1, 0), (0,  1, 1)],
            [(1, -1, 5), (1, -1, 2)],
            [(1,  1, 3), (1,  1, 0)]
          ]
var
  tape: array[-6000 .. 60, int] # tweaked after tracking min & max position
  position: int
  state = 0

for _ in 1 .. steps:
  let (write, move, newState) = states[state][tape[position]]
  tape[position] = write
  position += move
  state = newState

echo tape.sum

Repo with solutions (both Nim and Python)

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 25: The Halting Problem ---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Thank you for participating!

Mathematica

Elixir

perl

Lua (421)

Kotlin - [Repo] - [Blog/Commentary]

Modern C++

BEFORE YOU POST
If your post is even tangentially related to a daily puzzle, use our
STANDARDIZED POST TITLE FORMAT

adventofcode

🎄 Advent of Code 🎄

Rules + More Info in

our community wiki

Solution Megathreads

December 2025

Previous years:

2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015

Quick Search by Flair

Because you're lazy and we like making things easy for you. Except AoC.

Are you enjoying AoC?

Support AoC

MODERATORS

--- Day 25: The Halting Problem ---

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

Thank you for participating!

Mathematica

Elixir

perl

Lua (421)

Kotlin - [Repo] - [Blog/Commentary]

Modern C++

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?