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