Date: Mon, 25 Dec 2017 20:51:43 +0000 Subject: [PATCH] Some updates --- problems/day25-completed.html | 179 +++++++++++++++++++++++++++++++++ problems/day25.html | 181 ++++++++++++++++++++++++++++++++++ src/advent25/advent25.hs | 7 +- src/advent25/advent25.ipynb | 140 ++++++++++++++++++++++++-- 4 files changed, 497 insertions(+), 10 deletions(-) create mode 100644 problems/day25-completed.html create mode 100644 problems/day25.html diff --git a/problems/day25-completed.html b/problems/day25-completed.html new file mode 100644 index 0000000..6a1a73b --- /dev/null +++ b/problems/day25-completed.html @@ -0,0 +1,179 @@ + + + + +Day 25 - Advent of Code 2017 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 49*

0.0.0.0:2017

+ + + +

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

Following the twisty passageways deeper and deeper into the CPU, you finally reach the core of the computer. Here, in the expansive central chamber, you find a grand apparatus that fills the entire room, suspended nanometers above your head.

You had always imagined CPUs to be noisy, chaotic places, bustling with activity. Instead, the room is quiet, motionless, and dark.

Suddenly, you and the CPU's garbage collector startle each other. "It's not often we get many visitors here!", he says. You inquire about the stopped machinery.

"It stopped milliseconds ago; not sure why. I'm a garbage collector, not a doctor." You ask what the machine is for.

"Programs these days, don't know their origins. That's the Turing machine! It's what makes the whole computer work." You try to explain that Turing machines are merely models of computation, but he cuts you off. "No, see, that's just what they want you to think. Ultimately, inside every CPU, there's a Turing machine driving the whole thing! Too bad this one's broken. We're doomed!"

You ask how you can help. "Well, unfortunately, the only way to get the computer running again would be to create a whole new Turing machine from scratch, but there's no way you can-" He notices the look on your face, gives you a curious glance, shrugs, and goes back to sweeping the floor.

You find the Turing machine blueprints (your puzzle input) on a tablet in a nearby pile of debris. Looking back up at the broken Turing machine above, you can start to identify its parts:

A tape which contains 0 repeated infinitely to the left and right.
A cursor, which can move left or right along the tape and read or write values at its current position.
A set of states, each containing rules about what to do based on the current value under the cursor.

Each slot on the tape has two possible values: 0 (the starting value for all slots) and 1. Based on whether the cursor is pointing at a 0 or a 1, the current state says what value to write at the current position of the cursor, whether to move the cursor left or right one slot, and which state to use next.

For example, suppose you found the following blueprint:

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.
+

Running it until the number of steps required to take the listed diagnostic checksum would result in the following tape configurations (with the cursor marked in square brackets):

... 0  0  0 [0] 0  0 ... (before any steps; about to run state A)
+... 0  0  0  1 [0] 0 ... (after 1 step;     about to run state B)
+... 0  0  0 [1] 1  0 ... (after 2 steps;    about to run state A)
+... 0  0 [0] 0  1  0 ... (after 3 steps;    about to run state B)
+... 0 [0] 1  0  1  0 ... (after 4 steps;    about to run state A)
+... 0  1 [1] 0  1  0 ... (after 5 steps;    about to run state B)
+... 0  1  1 [0] 1  0 ... (after 6 steps;    about to run state A)
+

The CPU can confirm that the Turing machine is working by taking a diagnostic checksum after a specific number of steps (given in the blueprint). Once the specified number of steps have been executed, the Turing machine should pause; once it does, count the number of times 1 appears on the tape. In the above example, the diagnostic checksum is 3.

Recreate the Turing machine and save the computer! What is the diagnostic checksum it produces once it's working again?

Your puzzle answer was 2846.

The first half of this puzzle is complete! It provides one gold star: *

--- Part Two ---

The Turing machine, and soon the entire computer, springs back to life. A console glows dimly nearby, awaiting your command.

> reboot printer
+Error: That command requires priority 50. You currently have priority 0.
+You must deposit 50 stars to increase your priority to the required level.
+

The console flickers for a moment, and then prints another message:

Star accepted.
+You must deposit 49 stars to increase your priority to the required level.
+

The garbage collector winks at you, then continues sweeping.

+ +

You can also [Shareon + Twitter + Google+ + Reddit] this puzzle.

+ + + + + + \ No newline at end of file diff --git a/problems/day25.html b/problems/day25.html new file mode 100644 index 0000000..2a5dd99 --- /dev/null +++ b/problems/day25.html @@ -0,0 +1,181 @@ + + + + +Day 25 - Advent of Code 2017 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 50*

0xffff&2017

+ + + +

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

You had always imagined CPUs to be noisy, chaotic places, bustling with activity. Instead, the room is quiet, motionless, and dark.

Suddenly, you and the CPU's garbage collector startle each other. "It's not often we get many visitors here!", he says. You inquire about the stopped machinery.

"It stopped milliseconds ago; not sure why. I'm a garbage collector, not a doctor." You ask what the machine is for.

You find the Turing machine blueprints (your puzzle input) on a tablet in a nearby pile of debris. Looking back up at the broken Turing machine above, you can start to identify its parts:

A tape which contains 0 repeated infinitely to the left and right.
A cursor, which can move left or right along the tape and read or write values at its current position.
A set of states, each containing rules about what to do based on the current value under the cursor.

For example, suppose you found the following blueprint:

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.
+

Running it until the number of steps required to take the listed diagnostic checksum would result in the following tape configurations (with the cursor marked in square brackets):

... 0  0  0 [0] 0  0 ... (before any steps; about to run state A)
+... 0  0  0  1 [0] 0 ... (after 1 step;     about to run state B)
+... 0  0  0 [1] 1  0 ... (after 2 steps;    about to run state A)
+... 0  0 [0] 0  1  0 ... (after 3 steps;    about to run state B)
+... 0 [0] 1  0  1  0 ... (after 4 steps;    about to run state A)
+... 0  1 [1] 0  1  0 ... (after 5 steps;    about to run state B)
+... 0  1  1 [0] 1  0 ... (after 6 steps;    about to run state A)
+

Recreate the Turing machine and save the computer! What is the diagnostic checksum it produces once it's working again?

Your puzzle answer was 2846.

--- Part Two ---

The Turing machine, and soon the entire computer, springs back to life. A console glows dimly nearby, awaiting your command.

> reboot printer
+Error: That command requires priority 50. You currently have priority 0.
+You must deposit 50 stars to increase your priority to the required level.
+

The console flickers for a moment, and then prints another message:

Star accepted.
+You must deposit 49 stars to increase your priority to the required level.
+

The garbage collector winks at you, then continues sweeping.

+ +

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, all that is left is for you to admire your advent calendar.

If you still want to see it, you can get your puzzle input.

You can also [Shareon + Twitter + Google+ + Reddit] this puzzle.

+ + + + + + \ No newline at end of file diff --git a/src/advent25/advent25.hs b/src/advent25/advent25.hs index 55f5c5c..656c775 100644 --- a/src/advent25/advent25.hs +++ b/src/advent25/advent25.hs @@ -48,17 +48,19 @@ main :: IO () main = do text <- TIO.readFile "data/advent25.txt" let (machine0, rules) = successfulParse text - let (result, machinef) = part1 rules machine0 + let machinef = part1 rules machine0 print $ M.size $ M.filter id $ tape machinef +part1 :: Rules -> Machine -> Machine part1 rules machine0 = - runState ( + execState ( runReaderT executeSteps rules ) machine0 +executeSteps :: ProgrammedMachine executeSteps = do m <- get unless (stepsRemaining m == 0) $ @@ -66,6 +68,7 @@ executeSteps = executeSteps +executeStep :: ProgrammedMachine executeStep = do rules <- ask m <- get diff --git a/src/advent25/advent25.ipynb b/src/advent25/advent25.ipynb index 0813c7f..dd9ab06 100644 --- a/src/advent25/advent25.ipynb +++ b/src/advent25/advent25.ipynb @@ -611,13 +611,127 @@ }, { "cell_type": "code", - "execution_count": 29, + "execution_count": 35, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "

Eta reduce

Found:

part1 rules machine0\n", + " = execState (runReaderT executeSteps rules) machine0

Why Not:

part1 rules = execState (runReaderT executeSteps rules)

" + ], + "text/plain": [ + "Line 1: Eta reduce\n", + "Found:\n", + "part1 rules machine0\n", + " = execState (runReaderT executeSteps rules) machine0\n", + "Why not:\n", + "part1 rules = execState (runReaderT executeSteps rules)" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "part1 rules machine0 = \n", + " execState (\n", + " runReaderT executeSteps\n", + " rules \n", + " ) \n", + " machine0" + ] + }, + { + "cell_type": "code", + "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ - "((),Machine {state = \"B\", tape = fromList [(0,True)], tapeLocation = 1, stepsRemaining = 5})" + "Machine {state = \"B\", tape = fromList [(0,True)], tapeLocation = 1, stepsRemaining = 5}" ] }, "metadata": {}, @@ -625,12 +739,12 @@ } ], "source": [ - "runState ( runReaderT executeStep sampleRules ) sampleMachine" + "execState ( runReaderT executeStep sampleRules ) sampleMachine" ] }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 37, "metadata": {}, "outputs": [], "source": [ @@ -638,13 +752,13 @@ "main = do \n", " text <- TIO.readFile \"../../data/advent25.txt\"\n", " let (machine0, rules) = successfulParse text\n", - " let (result, machinef) = part1 rules machine0\n", + " let machinef = part1 rules machine0\n", " print $ M.size $ M.filter id $ tape machinef\n" ] }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 38, "metadata": {}, "outputs": [], "source": [ @@ -658,9 +772,19 @@ }, { "cell_type": "code", - "execution_count": null, + "execution_count": 39, "metadata": {}, - "outputs": [], + "outputs": [ + { + "data": { + "text/plain": [ + "2846" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], "source": [ "main" ] -- 2.34.1