From: Neil Smith <neil.git@njae.me.uk>
Date: Fri, 23 Dec 2016 18:10:27 +0000 (+0000)
Subject: Day 23
X-Git-Url: https://git.njae.me.uk/?p=advent-of-code-16.git;a=commitdiff_plain;h=879988b4a618a218a8bc78507717b330b1030c3a
Day 23
---
diff --git a/adventofcode16/adventofcode16.cabal b/adventofcode16/adventofcode16.cabal
index 39c0942..6216e51 100644
--- a/adventofcode16/adventofcode16.cabal
+++ b/adventofcode16/adventofcode16.cabal
@@ -332,6 +332,16 @@ executable advent22library
, hashable
default-language: Haskell2010
+executable advent23
+ hs-source-dirs: app
+ main-is: advent23.hs
+ ghc-options: -O2 -threaded -rtsopts -with-rtsopts=-N
+ build-depends: base
+ , adventofcode16
+ , parsec
+ , parsec-numbers
+ , mtl
+ default-language: Haskell2010
executable adventofcode16-exe
hs-source-dirs: app
diff --git a/adventofcode16/app/advent23.hs b/adventofcode16/app/advent23.hs
new file mode 100644
index 0000000..42cd15f
--- /dev/null
+++ b/adventofcode16/app/advent23.hs
@@ -0,0 +1,198 @@
+module Main(main) where
+
+import Text.Parsec hiding (State)
+import Text.ParserCombinators.Parsec.Number
+import Control.Monad.State.Lazy
+-- import Debug.Trace
+
+data Location = Literal Int | Register Char deriving (Show, Eq)
+data Instruction = Cpy Location Location
+ | Inc Location
+ | Dec Location
+ | Jnz Location Location
+ | Tgl Location
+ deriving (Show, Eq)
+
+data Machine = Machine { a :: Int
+ , b :: Int
+ , c :: Int
+ , d :: Int
+ , pc :: Int
+ , instructions :: [Instruction]}
+ deriving (Show, Eq)
+
+
+testInstructions = "cpy 2 a\n\
+\tgl a\n\
+\tgl a\n\
+\tgl a\n\
+\cpy 1 a\n\
+\dec a\n\
+\dec a"
+
+
+emptyMachine :: Machine
+emptyMachine = Machine {a=0, b=0, c=0, d=0, pc=0, instructions=[]}
+
+main :: IO ()
+main = do
+ text <- readFile "data/advent23.txt"
+ let instructions = successfulParse $ parseIfile text
+ part1 instructions
+ part2 instructions
+
+
+part1 :: [Instruction] -> IO ()
+part1 instrs =
+ do let m0 = emptyMachine {instructions=instrs, a = 7}
+ let mf = snd $ runState runMachine m0
+ print (a mf)
+
+part2 :: [Instruction] -> IO ()
+part2 instrs =
+ do let m0 = emptyMachine {instructions=instrs, a = 12}
+ let mf = snd $ runState runMachine m0
+ print (a mf)
+
+
+runMachine :: State Machine ()
+runMachine =
+ do m <- get
+ if (pc m) >= (length $ instructions m)
+ then return ()
+ else do executeStep
+ runMachine
+
+executeStep :: State Machine ()
+executeStep =
+ do m <- get
+ let i = (instructions m)!!(pc m)
+ put (executeInstructionPeep i m)
+ -- put (executeInstruction i m)
+
+executeInstructionPeep :: Instruction -> Machine -> Machine
+executeInstructionPeep i m =
+ if sample1 == sample1Target
+ -- then trace ("Peeping 1 " ++ (show m) ++ " to " ++ (show m1)) m1
+ then m1
+ else if sample2 == sample2Target
+ -- then trace ("Peeping 2 " ++ (show m) ++ " to " ++ (show m2)) m2
+ then m2
+ else executeInstruction i m
+ where sample1 = take (length sample1Target) $ drop (pc m) $ instructions m
+ sample1Target = [ Cpy (Literal 0) (Register 'a')
+ , Cpy (Register 'b') (Register 'c')
+ , Inc (Register 'a')
+ , Dec (Register 'c')
+ , Jnz (Register 'c') (Literal (-2))
+ , Dec (Register 'd')
+ , Jnz (Register 'd') (Literal (-5)) ]
+ m1 = m {a = b m * d m, c = 0, d = 0, pc = pc m + (length sample1)}
+ sample2 = take (length sample2Target) $ drop (pc m) $ instructions m
+ sample2Target = [ Dec (Register 'b')
+ , Cpy (Register 'b') (Register 'c')
+ , Cpy (Register 'c') (Register 'd')
+ , Dec (Register 'd')
+ , Inc (Register 'c')
+ , Jnz (Register 'd') (Literal (-2)) ]
+ m2 = m {b = b m - 1, c = (b m - 1) * 2, d = 0, pc = pc m + (length sample2)}
+
+
+executeInstruction :: Instruction -> Machine -> Machine
+executeInstruction (Inc r@(Register _)) m = m' {pc=pc1}
+ where pc1 = (pc m) + 1
+ v = evaluate m r
+ m' = writeValue m r (v+1)
+executeInstruction (Inc (Literal _)) m = m {pc=pc1}
+ where pc1 = (pc m) + 1
+executeInstruction (Dec r@(Register _)) m = m' {pc=pc1}
+ where pc1 = (pc m) + 1
+ v = evaluate m r
+ m' = writeValue m r (v-1)
+executeInstruction (Dec (Literal _)) m = m {pc=pc1}
+ where pc1 = (pc m) + 1
+executeInstruction (Cpy s d@(Register _)) m = m' {pc=pc1}
+ where pc1 = (pc m) + 1
+ v = evaluate m s
+ m' = writeValue m d v
+executeInstruction (Cpy s (Literal _)) m = m {pc=pc1}
+ where pc1 = (pc m) + 1
+executeInstruction (Jnz s d) m
+ | v == 0 = m {pc=pc1}
+ | otherwise = m {pc=pcj}
+ where pc1 = (pc m) + 1
+ ed = evaluate m d
+ pcj = (pc m) + ed
+ v = evaluate m s
+executeInstruction (Tgl a) m
+ | v < (length $ instructions m) = m {instructions = (replace (instructions m) i' v),
+ pc=pc1}
+ | otherwise = m {pc=pc1}
+ where pc1 = pc m + 1
+ v = evaluate m a + pc m
+ i = (instructions m)!!v
+ i' = case i of
+ Inc x -> Dec x
+ Dec x -> Inc x
+ Tgl x -> Inc x
+ Cpy x y -> Jnz x y
+ Jnz x y -> Cpy x y
+ replace xs x i = take i xs ++ [x] ++ drop (i+1) xs
+
+
+evaluate :: Machine -> Location -> Int
+evaluate _ (Literal i) = i
+evaluate m (Register r) =
+ case r of
+ 'a' -> (a m)
+ 'b' -> (b m)
+ 'c' -> (c m)
+ 'd' -> (d m)
+
+writeValue :: Machine -> Location -> Int -> Machine
+writeValue m (Literal i) _ = m
+writeValue m (Register r) v =
+ case r of
+ 'a' -> m {a=v}
+ 'b' -> m {b=v}
+ 'c' -> m {c=v}
+ 'd' -> m {d=v}
+
+
+instructionFile = instructionLine `sepEndBy` newline
+-- instructionLine = choice [cpyL, incL, decL, jnzL]
+instructionLine = incL <|> decL <|> cpyL <|> jnzL <|> tglL
+
+-- incL = incify <$> (string "inc" *> spaces *> (oneOf "abcd"))
+-- where incify r = Inc (Register r)
+incL = (Inc . Register) <$> (string "inc" *> spaces *> (oneOf "abcd"))
+-- decL = decify <$> (string "dec" *> spaces *> (oneOf "abcd"))
+-- where decify r = Dec (Register r)
+decL = (Dec . Register) <$> (string "dec" *> spaces *> (oneOf "abcd"))
+cpyL = cpyify <$> (string "cpy" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter))))
+ <*> (spaces *> (oneOf "abcd"))
+ where cpyify s r = Cpy s (Register r)
+jnzL = jnzify <$> (string "jnz" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter))))
+ <*> (spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter))))
+ where jnzify r o = Jnz r o
+tglL = Tgl <$> (string "tgl" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter))))
+ -- where tglify r = Tgl r
+
+
+-- readLocation :: Int -> Location
+-- readLocation l = Literal l
+
+-- readLocation :: String -> Location
+-- readLocation l
+-- | all (isDigit) l = Literal (read l)
+-- | otherwise = Register (head l)
+
+parseIfile :: String -> Either ParseError [Instruction]
+parseIfile input = parse instructionFile "(unknown)" input
+
+parseIline :: String -> Either ParseError Instruction
+parseIline input = parse instructionLine "(unknown)" input
+
+successfulParse :: Either ParseError [a] -> [a]
+successfulParse (Left _) = []
+successfulParse (Right a) = a
\ No newline at end of file
diff --git a/adventofcode16/data/advent23.txt b/adventofcode16/data/advent23.txt
new file mode 100644
index 0000000..93f25d2
--- /dev/null
+++ b/adventofcode16/data/advent23.txt
@@ -0,0 +1,26 @@
+cpy a b
+dec b
+cpy a d
+cpy 0 a
+cpy b c
+inc a
+dec c
+jnz c -2
+dec d
+jnz d -5
+dec b
+cpy b c
+cpy c d
+dec d
+inc c
+jnz d -2
+tgl c
+cpy -16 c
+jnz 1 c
+cpy 94 c
+jnz 99 d
+inc a
+inc d
+jnz d -2
+inc c
+jnz c -5
\ No newline at end of file
diff --git a/day23.html b/day23.html
new file mode 100644
index 0000000..27e2e00
--- /dev/null
+++ b/day23.html
@@ -0,0 +1,167 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 23 - Advent of Code 2016</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?9"/>
+<link rel="shortcut icon" href="/favicon.ico?2"/>
+</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 probably took the longest; the easiest ones were around 45 minutes
+each, but the harder ones took 2-3 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="/2016/about">[About]</a></li><li><a href="/2016/support">[AoC++]</a></li><li><a href="/2016/events">[Events]</a></li><li><a href="/2016/settings">[Settings]</a></li><li><a href="/2016/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">46*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">0xffff&</span><a href="/2016">2016</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2016">[Calendar]</a></li><li><a href="/2016/leaderboard">[Leaderboard]</a></li><li><a href="/2016/stats">[Stats]</a></li><li><a href="/2016/sponsors">[Sponsors]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2016/sponsors">sponsors</a> help make AoC possible:</div><p><a href="https://info.esparklearning.com/join-our-team-full-stack-engineer" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);">eSpark Learning</a> - Solve the greatest puzzle of our day - transform education</p></div>
+<div id="ad">
+<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
+<!-- Advent of Code Wide Skyscraper -->
+<ins class="adsbygoogle"
+ style="display:inline-block;width:160px;height:600px"
+ data-ad-client="ca-pub-9420604735624631"
+ data-ad-slot="8014013294"></ins>
+<script>
+(adsbygoogle = window.adsbygoogle || []).push({});
+</script>
+</div><!--/ad-->
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 23: Safe Cracking ---</h2><p>This is one of the top floors of the nicest tower in EBHQ. The Easter Bunny's private office is here, complete with a safe hidden behind a painting, and who <em>wouldn't</em> hide a star in a safe behind a painting?</p>
+<p>The safe has a digital screen and keypad for code entry. A sticky note attached to the safe has a password hint on it: "eggs". The painting is of a large rabbit coloring some eggs. You see <code>7</code>.</p>
+<p>When you go to type the code, though, nothing appears on the display; instead, the keypad comes apart in your hands, apparently having been smashed. Behind it is some kind of socket - one that matches a connector in your <a href="11">prototype computer</a>! You pull apart the smashed keypad and extract the logic circuit, plug it into your computer, and plug your computer into the safe.</p>
+</p>Now, you just need to figure out what output the keypad would have sent to the safe. You extract the <a href="12">assembunny code</a> from the logic chip (your puzzle input).</p>
+<p>The code looks like it uses <em>almost</em> the same architecture and instruction set that the <a href="12">monorail computer</a> used! You should be able to <em>use the same assembunny interpreter</em> for this as you did there, but with one new instruction:</p>
+<p><code>tgl x</code> <em>toggles</em> the instruction <code>x</code> away (pointing at instructions like <code>jnz</code> does: positive means forward; negative means backward):</p>
+<ul>
+<li>For <em>one-argument</em> instructions, <code>inc</code> becomes <code>dec</code>, and all other one-argument instructions become <code>inc</code>.</li>
+<li>For <em>two-argument</em> instructions, <code>jnz</code> becomes <code>cpy</code>, and all other two-instructions become <code>jnz</code>.</li>
+<li>The arguments of a toggled instruction are <em>not affected</em>.</li>
+<li>If an attempt is made to toggle an instruction outside the program, <em>nothing happens</em>.</li>
+<li>If toggling produces an <em>invalid instruction</em> (like <code>cpy 1 2</code>) and an attempt is later made to execute that instruction, <em>skip it instead</em>.</li>
+<li>If <code>tgl</code> toggles <em>itself</em> (for example, if <code>a</code> is <code>0</code>, <code>tgl a</code> would target itself and become <code>inc a</code>), the resulting instruction is not executed until the next time it is reached.</li>
+</ul>
+<p>For example, given this program:</p>
+<pre><code>cpy 2 a
+tgl a
+tgl a
+tgl a
+cpy 1 a
+dec a
+dec a
+</code></pre>
+<ul>
+<li><code>cpy 2 a</code> initializes register <code>a</code> to <code>2</code>.</li>
+<li>The first <code>tgl a</code> toggles an instruction <code>a</code> (<code>2</code>) away from it, which changes the third <code>tgl a</code> into <code>inc a</code>.</li>
+<li>The second <code>tgl a</code> also modifies an instruction <code>2</code> away from it, which changes the <code>cpy 1 a</code> into <code>jnz 1 a</code>.</li>
+<li>The fourth line, which is now <code>inc a</code>, increments <code>a</code> to <code>3</code>.</li>
+<li>Finally, the fifth line, which is now <code>jnz 1 a</code>, jumps <code>a</code> (<code>3</code>) instructions ahead, skipping the <code>dec a</code> instructions.</li>
+</ul>
+<p>In this example, the final value in register <code>a</code> is <code>3</code>.</p>
+<p>The rest of the electronics seem to place the keypad entry (the number of eggs, <code>7</code>) in register <code>a</code>, run the code, and then send the value left in register <code>a</code> to the safe.</p>
+<p><em>What value</em> should be sent to the safe?</p>
+</article>
+<p>Your puzzle answer was <code>14346</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>The safe doesn't open, but it <em>does</em> make several <span title="SUCH INCORRECT! VERY LOCK! WOW!">angry noises</span> to express its frustration.</p>
+<p>You're quite sure your logic is working correctly, so the only other thing is... you check the painting again. As it turns out, colored eggs are still eggs. Now you count <code>12</code>.</p>
+<p>As you run the program with this new input, the prototype computer begins to <em>overheat</em>. You wonder what's taking so long, and whether the lack of any instruction more powerful than "add one" has anything to do with it. Don't bunnies usually <em>multiply</em>?</p>
+<p>Anyway, <em>what value</em> should actually be sent to the safe?</p>
+</article>
+<p>Your puzzle answer was <code>479010906</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="/2016">return to your advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="23/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+%22Safe+Cracking%22+%2D+Day+23+%2D+Advent+of+Code+2016&url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F23&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F23" target="_blank">Google+</a>
+ <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F23&title=I%27ve+completed+%22Safe+Cracking%22+%2D+Day+23+%2D+Advent+of+Code+2016" 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