--- /dev/null
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 19 - Advent of Code 2018</title>
+<!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
+<link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'>
+<link rel="stylesheet" type="text/css" href="/static/style.css?19"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+</head><!--
+
+
+
+
+Oh, hello! Funny seeing you here.
+
+I appreciate your enthusiasm, but you aren't going to find much down here.
+There certainly aren't clues to any of the puzzles. The best surprises don't
+even appear in the source until you unlock them for real.
+
+Please be careful with automated requests; I'm not Google, and I can only take
+so much traffic. Please be considerate so that everyone gets to play.
+
+If you're curious about how Advent of Code works, it's running on some custom
+Perl code. Other than a few integrations (auth, analytics, ads, social media),
+I built the whole thing myself, including the design, animations, prose, and
+all of the puzzles.
+
+The puzzles are most of the work; the easiest ones take 3-4 hours each, but the
+harder ones take 6-8 hours, and a few even longer than that. A lot of effort
+went into building this thing - I hope you're enjoying playing it as much as I
+enjoyed making it for you!
+
+If you'd like to hang out, I'm @ericwastl on Twitter.
+
+- Eric Wastl
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+-->
+<body>
+<header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2018/about">[About]</a></li><li><a href="/2018/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode" target="_blank">[Shop]</a></li><li><a href="/2018/settings">[Settings]</a></li><li><a href="/2018/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2018/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">38*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap"></span><a href="/2018">2018</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2018">[Calendar]</a></li><li><a href="/2018/support">[AoC++]</a></li><li><a href="/2018/sponsors">[Sponsors]</a></li><li><a href="/2018/leaderboard">[Leaderboard]</a></li><li><a href="/2018/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2018/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://aoc.prodo.ai/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Alfie by Prodo</a> - a more immediate, feedback-driven coding experience. Try our online JavaScript playground with Advent of Code!</div></div>
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 19: Go With The Flow ---</h2><p>With the Elves well on their way constructing the North Pole base, you turn your attention back to understanding the inner workings of programming the device.</p>
+<p>You can't help but notice that the <a href="16">device's opcodes</a> don't contain any <em>flow control</em> like jump instructions. The device's <a href="16">manual</a> goes on to explain:</p>
+<p>"In programs where flow control is required, the <a href="https://en.wikipedia.org/wiki/Program_counter">instruction pointer</a> can be <em>bound to a register</em> so that it can be manipulated directly. This way, <code>setr</code>/<code>seti</code> can function as absolute jumps, <code>addr</code>/<code>addi</code> can function as relative jumps, and other opcodes can cause <span title="Good luck maintaining a program that uses a bitwise operation on its instruction pointer, though.">truly fascinating</span> effects."</p>
+<p>This mechanism is achieved through a declaration like <code>#ip 1</code>, which would modify register <code>1</code> so that accesses to it let the program indirectly access the instruction pointer itself. To compensate for this kind of binding, there are now <em>six</em> registers (numbered <code>0</code> through <code>5</code>); the five not bound to the instruction pointer behave as normal. Otherwise, the same rules apply as <a href="16">the last time you worked with this device</a>.</p>
+<p>When the <em>instruction pointer</em> is bound to a register, its value is written to that register just before each instruction is executed, and the value of that register is written back to the instruction pointer immediately after each instruction finishes execution. Afterward, move to the next instruction by adding one to the instruction pointer, even if the value in the instruction pointer was just updated by an instruction. (Because of this, instructions must effectively set the instruction pointer to the instruction <em>before</em> the one they want executed next.)</p>
+<p>The instruction pointer is <code>0</code> during the first instruction, <code>1</code> during the second, and so on. If the instruction pointer ever causes the device to attempt to load an instruction outside the instructions defined in the program, the program instead immediately halts. The instruction pointer starts at <code>0</code>.</p>
+<p>It turns out that this new information is already proving useful: the CPU in the device is not very powerful, and a background process is occupying most of its time. You dump the background process' declarations and instructions to a file (your puzzle input), making sure to use the names of the opcodes rather than the numbers.</p>
+<p>For example, suppose you have the following program:</p>
+<pre><code>#ip 0
+seti 5 0 1
+seti 6 0 2
+addi 0 1 0
+addr 1 2 3
+setr 1 0 0
+seti 8 0 4
+seti 9 0 5
+</code></pre>
+<p>When executed, the following instructions are executed. Each line contains the value of the instruction pointer at the time the instruction started, the values of the six registers before executing the instructions (in square brackets), the instruction itself, and the values of the six registers after executing the instruction (also in square brackets).</p>
+<pre><code>ip=0 [0, 0, 0, 0, 0, 0] seti 5 0 1 [0, 5, 0, 0, 0, 0]
+ip=1 [1, 5, 0, 0, 0, 0] seti 6 0 2 [1, 5, 6, 0, 0, 0]
+ip=2 [2, 5, 6, 0, 0, 0] addi 0 1 0 [3, 5, 6, 0, 0, 0]
+ip=4 [4, 5, 6, 0, 0, 0] setr 1 0 0 [5, 5, 6, 0, 0, 0]
+ip=6 [6, 5, 6, 0, 0, 0] seti 9 0 5 [6, 5, 6, 0, 0, 9]
+</code></pre>
+<p>In detail, when running this program, the following events occur:</p>
+<ul>
+<li>The first line (<code>#ip 0</code>) indicates that the instruction pointer should be bound to register <code>0</code> in this program. This is not an instruction, and so the value of the instruction pointer does not change during the processing of this line.</li>
+<li>The instruction pointer contains <code>0</code>, and so the first instruction is executed (<code>seti 5 0 1</code>). It updates register <code>0</code> to the current instruction pointer value (<code>0</code>), sets register <code>1</code> to <code>5</code>, sets the instruction pointer to the value of register <code>0</code> (which has no effect, as the instruction did not modify register <code>0</code>), and then adds one to the instruction pointer.</li>
+<li>The instruction pointer contains <code>1</code>, and so the second instruction, <code>seti 6 0 2</code>, is executed. This is very similar to the instruction before it: <code>6</code> is stored in register <code>2</code>, and the instruction pointer is left with the value <code>2</code>.</li>
+<li>The instruction pointer is <code>2</code>, which points at the instruction <code>addi 0 1 0</code>. This is like a <em>relative jump</em>: the value of the instruction pointer, <code>2</code>, is loaded into register <code>0</code>. Then, <code>addi</code> finds the result of adding the value in register <code>0</code> and the value <code>1</code>, storing the result, <code>3</code>, back in register <code>0</code>. Register <code>0</code> is then copied back to the instruction pointer, which will cause it to end up <code>1</code> larger than it would have otherwise and skip the next instruction (<code>addr 1 2 3</code>) entirely. Finally, <code>1</code> is added to the instruction pointer.</li>
+<li>The instruction pointer is <code>4</code>, so the instruction <code>setr 1 0 0</code> is run. This is like an <em>absolute jump</em>: it copies the value contained in register <code>1</code>, <code>5</code>, into register <code>0</code>, which causes it to end up in the instruction pointer. The instruction pointer is then incremented, leaving it at <code>6</code>.</li>
+<li>The instruction pointer is <code>6</code>, so the instruction <code>seti 9 0 5</code> stores <code>9</code> into register <code>5</code>. The instruction pointer is incremented, causing it to point outside the program, and so the program ends.</li>
+</ul>
+<p><em>What value is left in register <code>0</code></em> when the background process halts?</p>
+</article>
+<p>Your puzzle answer was <code>2640</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>A new background process immediately spins up in its place. It appears identical, but on closer inspection, you notice that <em>this time, register <code>0</code> started with the value <code>1</code></em>.</p>
+<p><em>What value is left in register <code>0</code></em> when this new background process halts?</p>
+</article>
+<p>Your puzzle answer was <code>27024480</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, you should <a href="/2018">return to your advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="19/input" target="_blank">get your puzzle input</a>.</p>
+<p>You can also <span class="share">[Share<span class="share-content">on
+ <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Go+With+The+Flow%22+%2D+Day+19+%2D+Advent+of+Code+2018&url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F19&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F19&title=I%27ve+completed+%22Go+With+The+Flow%22+%2D+Day+19+%2D+Advent+of+Code+2018" target="_blank">Reddit</a
+></span>]</span> this puzzle.</p>
+</main>
+
+<!-- ga -->
+<script>
+(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+ga('create', 'UA-69522494-1', 'auto');
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file
--- /dev/null
+{-# LANGUAGE NegativeLiterals #-}
+{-# LANGUAGE FlexibleContexts #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE TypeFamilies #-}
+
+
+import Debug.Trace
+
+-- import Prelude hiding ((++))
+import Data.Text (Text)
+import qualified Data.Text as T
+import qualified Data.Text.IO as TIO
+
+import Data.Void (Void)
+import Text.Megaparsec hiding (State)
+import Text.Megaparsec.Char
+import qualified Text.Megaparsec.Char.Lexer as L
+import qualified Control.Applicative as CA
+
+import qualified Data.Map.Strict as M
+import Data.Map.Strict ((!))
+import Data.Bits ((.&.), (.|.))
+
+import Control.Monad (when)
+import Control.Monad.State.Lazy
+import Control.Monad.Reader
+import Control.Monad.Writer
+
+type Memory = M.Map Integer Integer
+
+data Location = Literal Integer | Register Integer deriving (Show, Eq)
+data Instruction =
+ Addr Integer Integer Integer
+ | Addi Integer Integer Integer
+ | Mulr Integer Integer Integer
+ | Muli Integer Integer Integer
+ | Banr Integer Integer Integer
+ | Bani Integer Integer Integer
+ | Borr Integer Integer Integer
+ | Bori Integer Integer Integer
+ | Setr Integer Integer Integer
+ | Seti Integer Integer Integer
+ | Gtir Integer Integer Integer
+ | Gtri Integer Integer Integer
+ | Gtrr Integer Integer Integer
+ | Eqir Integer Integer Integer
+ | Eqri Integer Integer Integer
+ | Eqrr Integer Integer Integer
+ deriving (Eq, Show, Ord)
+
+
+data Machine = Machine { _registers :: M.Map Integer Integer
+ , _pc :: Int
+ -- , _pcReg :: Integer
+ }
+ deriving (Show, Eq)
+
+type ProgrammedMachine = WriterT [Integer] (ReaderT (Integer, [Instruction]) (State Machine)) ()
+
+emptyMachine = Machine {_registers = M.fromList (zip [0..5] (repeat 0)),
+ _pc = 0}
+
+main :: IO ()
+main = do
+ text <- TIO.readFile "data/advent19.txt"
+ let (ip, instrs) = successfulParse text
+ print (ip, instrs)
+ -- print $ part1 ip instrs
+ print $ sum [i | i <- [1..1032], 1032 `mod` i == 0]
+ -- print $ part2 ip instrs
+ print $ sum [i | i <- [1..10551432], 10551432 `mod` i == 0]
+
+part1 ip instructions =
+ runState (
+ runReaderT (
+ runWriterT executeInstructions
+ )
+ (ip, instructions)
+ )
+ emptyMachine
+
+part2 ip instructions =
+ runState (
+ runReaderT (
+ runWriterT executeInstructions
+ )
+ (ip, instructions)
+ )
+ m2
+ where emptyRegisters = _registers emptyMachine
+ m2 = emptyMachine {_registers = M.insert 0 1 emptyRegisters}
+
+executeInstructions =
+ do (_, instrs) <- ask
+ m <- get
+ when (_pc m >= 0 && _pc m < length instrs)
+ $
+ do executeInstruction
+ executeInstructions
+
+executeInstruction :: ProgrammedMachine
+executeInstruction =
+ do (pcIs, instrs) <- ask
+ m <- get
+ let instr = instrs!!(_pc m)
+ let memory0 = _registers m
+ let memory1 = M.insert pcIs (fromIntegral (_pc m)) memory0
+ let memory2 = if canPeep1 instrs (_pc m) memory1 -- sample1 == sample1Target
+ then memoryPeep1 memory1
+ else perform instr memory1
+ -- let memory2 = perform instr memory1
+ let pc' = fromIntegral ((memory2!pcIs) + 1)
+ -- let aaa = trace ("pc: " ++ show (_pc m) ++ " m0: " ++ show memory0 ++ " m1: " ++ show memory1 ++ "m2: " ++ show memory2 ++ "pc': " ++ show pc') $! True
+ let m' = m {_registers = memory2, _pc = pc'}
+ put m'
+ where sample1 pcVal instructions = take (length sample1Target) $ drop pcVal instructions
+ sample1Target = [ Mulr 3 1 4
+ , Eqrr 4 2 4
+ , Addr 4 5 5
+ , Addi 5 1 5
+ , Addr 3 0 0
+ , Addi 1 1 1
+ , Gtrr 1 2 4
+ , Addr 5 4 5
+ , Seti 2 7 5
+ ]
+ canPeep1 instructions pcVal mem = False -- ((sample1 pcVal instructions) == sample1Target) && ((mem!4) == 0)
+ memoryPeep1 mem = M.union (M.fromList [(0, mem!0 + (if (((mem!2) `mod` (mem!3)) == 0) then mem!3 else 0)), (1, mem!2), (4, mem!2)]) mem
+ -- M.insert 0 (mem!0 + mem!3) $ M.insert 1 (mem!2) $ M.insert 4 (mem!2) mem
+
+
+perform :: Instruction -> Memory -> Memory
+-- perform instr memory | ((memory!5 == 7) || ((memory!5 == 3) && (memory!1 == 1))) && (trace ("Perform " ++ show instr ++ " " ++ show memory) False) = undefined
+perform instr memory | trace ("Perform " ++ show instr ++ " " ++ show memory) False = undefined
+perform (Addr a b c) memory = M.insert c (memory!a + memory!b) memory
+perform (Addi a b c) memory = M.insert c (memory!a + b) memory
+perform (Mulr a b c) memory = M.insert c (memory!a * memory!b) memory
+perform (Muli a b c) memory = M.insert c (memory!a * b) memory
+perform (Banr a b c) memory = M.insert c (memory!a .&. memory!b) memory
+perform (Bani a b c) memory = M.insert c (memory!a .&. b) memory
+perform (Borr a b c) memory = M.insert c (memory!a .|. memory!b) memory
+perform (Bori a b c) memory = M.insert c (memory!a .|. b) memory
+perform (Setr a b c) memory = M.insert c (memory!a) memory
+perform (Seti a b c) memory = M.insert c a memory
+perform (Gtir a b c) memory = M.insert c (if a > (memory!b) then 1 else 0) memory
+perform (Gtri a b c) memory = M.insert c (if (memory!a) > b then 1 else 0) memory
+perform (Gtrr a b c) memory = M.insert c (if (memory!a) > (memory!b) then 1 else 0) memory
+perform (Eqir a b c) memory = M.insert c (if a == memory!b then 1 else 0) memory
+perform (Eqri a b c) memory = M.insert c (if (memory!a) == b then 1 else 0) memory
+perform (Eqrr a b c) memory = M.insert c (if (memory!a) == (memory!b) then 1 else 0) memory
+
+
+-- evaluate :: Machine -> Location -> Integer
+-- evaluate _ (Literal i) = i
+-- evaluate m (Register r) = M.findWithDefault 0 r (registers m)
+
+
+
+type Parser = Parsec Void Text
+
+sc :: Parser ()
+sc = L.space (skipSome spaceChar) CA.empty CA.empty
+
+lexeme = L.lexeme sc
+integer = lexeme L.decimal
+symb = L.symbol sc
+
+
+instructionsP = (,) <$> headerP <*> many instructionP
+instructionP = choice [ addrP, addiP, mulrP, muliP, banrP, baniP,
+ borrP, boriP, setrP, setiP, gtirP, gtriP, gtrrP,
+ eqirP, eqriP, eqrrP ]
+
+headerP = symb "#ip" *> integer
+
+addrP = Addr <$> (try (symb "addr") *> integer) <*> integer <*> integer
+addiP = Addi <$> (try (symb "addi") *> integer) <*> integer <*> integer
+mulrP = Mulr <$> (try (symb "mulr") *> integer) <*> integer <*> integer
+muliP = Muli <$> (try (symb "muli") *> integer) <*> integer <*> integer
+banrP = Banr <$> (try (symb "banr") *> integer) <*> integer <*> integer
+baniP = Bani <$> (try (symb "bani") *> integer) <*> integer <*> integer
+borrP = Borr <$> (try (symb "borr") *> integer) <*> integer <*> integer
+boriP = Bori <$> (try (symb "bori") *> integer) <*> integer <*> integer
+setrP = Setr <$> (try (symb "setr") *> integer) <*> integer <*> integer
+setiP = Seti <$> (try (symb "seti") *> integer) <*> integer <*> integer
+gtirP = Gtir <$> (try (symb "gtir") *> integer) <*> integer <*> integer
+gtriP = Gtri <$> (try (symb "gtri") *> integer) <*> integer <*> integer
+gtrrP = Gtrr <$> (try (symb "gtrr") *> integer) <*> integer <*> integer
+eqirP = Eqir <$> (try (symb "eqir") *> integer) <*> integer <*> integer
+eqriP = Eqri <$> (try (symb "eqri") *> integer) <*> integer <*> integer
+eqrrP = Eqrr <$> (try (symb "eqrr") *> integer) <*> integer <*> integer
+
+successfulParse :: Text -> (Integer, [Instruction])
+successfulParse input =
+ case parse instructionsP "input" input of
+ Left _error -> (0, []) -- TIO.putStr $ T.pack $ parseErrorPretty err
+ Right instructions -> instructions
\ No newline at end of file
projects / advent-of-code-18.git / commitdiff