Wolfram Cloud Document

“The Elves have good news and bad news.

The good news is that they’ve discovered project management! This has given them the tools they need to prevent their usual Christmas emergency. For example, they now know that the North Pole decorations need to be finished soon so that other critical tasks can start on time.

The bad news is that they’ve realized they have a different emergency: according to their resource planning, none of them have any time left to decorate the North Pole! Full puzzle” https://adventofcode.com/2025/day/1

Theory

Why a Turing Machine(TM)

A Turing machine is Turing-complete: it can simulate any algorithm, and the AoC Day 1 dial puzzle is an algorithm, just a deterministic state update repeated over a list of instructions. The dial position is always a number in {0,…,99}, and each instruction transforms that position in a predictable way.

While other methods like using modular arithmetic can be used to solve the puzzle efficiently, the fun experiment here is different: instead of writing the algorithm in the usual high-level way, we’ll encode it as a Turing machine and let the machine simulate it step by step. Once the input is on the tape, all we need is a transition rule set that reads each instruction, updates the internal state, and increments a counter whenever the dial hits zero.

What the TM is computing

Let the current position be ρ ϵ {0,…,99}, starting at ρ = 50. Each line is either:

◼

Rn meaning ρ = (ρ + n) mod 100

◼

Ln meaning ρ = (ρ - n) mod 100

After applying the update for a line, if ρ = 0, increment a counter.

What lives in the TM’s finite control

We store:

◼

Dial position ρ (100 possibilities/states)

◼

Direction d ϵ {L,R} (2 possibilities)

◼

Remainder while reading the distance r = n mod 100 (100 possibilities): Only the remainder matters here and not just n

How the machine processes one line

Given line L68\nL30\nR20 or {“L68”, “L30”, “R20”}:

Step A: read L or R

If it reads L, set d = L
If it reads R, set d = R

Step B: read the number, but only keep mod 100

Init remainder r = 0. As each digit c (0-9) is read, update:

r <= (10r + digit(c)) mod 100

This ensures r stays in 0..99, finite control

Example: reading 68

In[]:=

r=0;

Read 6:

In[]:=

r=Mod[(10×0+6),100]

Out[]=

Read 8:

In[]:=

r=Mod[(10×6+8),100]

Out[]=

Step C: at newline, update dial position

In[]:=

p=50

Out[]=

If d = R:

ρ <= (ρ + r) mod 100

In[]:=

p=Mod[(50+68),100]

Out[]=

If d = L: ρ <= (ρ - r) mod 100

In[]:=

p=Mod[(50-68),100]

Out[]=

Step D: if ρ = 0, increment the counter in the head state

Rule properties and encoding

Rule specifications

The good news is Wolfram’s TuringMachine lets the head state s be any expression, not just an integer. So we can:

◼

{“ScanDir”, p, c}: ready to read L or R, current dial position p(0..99) and read only c for the counter

◼

{“ReadDigits”, p, dir, r, c}: reading digits, where

◼

dir is +1 for R, -1 for L

◼

r is the distance read so far, kept as Mod[..., 100]

◼

c is the counter for the zero clicks

Example:

rule: {{ “ScanDir”, p_, c_}, L} -> {{ “ReadDigits”, p, c, -1, 0}, L, 1}

rule: {{ “ScanDir”, p_, c_}, R} -> {{ “ReadDigits”, p, c, 1, 0}, R, 1},

Tape alphabet encoding

One simple encoding:

◼

0 = blank

◼

3 = L

◼

4 = R

◼

5 = newline/end of instruction

Digits are encoded as 10..19 meaning 0..9:

◼

digit d => symbol 10 + d

So the input line R48 becomes tape symbols: 4, 14, 18, 5

Code

In[]:=

blank=0;Ls=3;Rs=4;NL=5;

In[]:=

rules={{{"ScanDir",p_,c_},Ls}->{{"ReadDigits",p,c,-1,0},Ls,1},{{"ScanDir",p_,c_},Rs}->{{"ReadDigits",p,c,1,0},Rs,1},{{"ReadDigits",p_,c_,dir_,r_},d_Integer/;10<=d<=19}->{{"ReadDigits",p,c,dir,Mod[10r+digitVal[d],100]},d,1},{{"ReadDigits",p_,c_,dir_,r_}/;Mod[p+dir*r,100]==0,NL}->{{"ScanDir",0,c+1},NL,1},{{"ReadDigits",p_,c_,dir_,r_}/;Mod[p+dir*r,100]!=0,NL}->{{"ScanDir",Mod[p+dir*r,100],c},NL,1}};

In[]:=

encodeTape[{"L68","L30","R48","L5","R60","L55","L1","L99","R14","L82"},True]

Out[]=

{3,16,18,5,3,13,10,5,4,14,18,5,3,15,5,4,16,10,5,3,15,15,5,3,11,5,3,19,19,5,4,11,14,5,3,18,12,5}

In[]:=

init=makeInit[{"L68","L30","R48","L5","R60","L55","L1","L99","R14","L82"},True];

In[]:=

init

Out[]=

{{{ScanDir,50,0},1},{{3,16,18,5,3,13,10,5,4,14,18,5,3,15,5,4,16,10,5,3,15,15,5,3,11,5,3,19,19,5,4,11,14,5,3,18,12,5},0}}

In[]:=

evolveLast=FixedPoint[TuringMachine[rules],init,50000];

In[]:=

evolveLast

Out[]=

{{{ScanDir,32,3},39,38},{{3,16,18,5,3,13,10,5,4,14,18,5,3,15,5,4,16,10,5,3,15,15,5,3,11,5,3,19,19,5,4,11,14,5,3,18,12,5,0},0}}

In[]:=

evolveLast[[1,1,3]]

Out[]=

In[]:=

evolveList=FixedPointList[TuringMachine[rules],init,50000];

In[]:=

evolveList

Out[]=

Part II rules

In[]:=

rules2={{{"ScanDir",p_,c_},sep}->{{"ScanDir",p,c},sep,1},{{"ScanDir",p_,c_},Ls}->{{"ReadDigits",p,c,-1,0},Ls,1},{{"ScanDir",p_,c_},Rs}->{{"ReadDigits",p,c,1,0},Rs,1},{{"ReadDigits",p_,c_,dir_,r_},d_Integer/;10<=d<=19}->{{"ReadDigits",p,c,dir,10r+digitVal[d]},d,1},{{"ReadDigits",p_,c_,dir_,r_},NL}->Module[{h=hitsOnPath[p,dir,r],newP=Mod[p+dir*r,100]},{{"ScanDir",newP,c+h},NL,1}]};