Done day 25
authorNeil Smith <neil.git@njae.me.uk>
Mon, 26 Dec 2016 12:15:16 +0000 (12:15 +0000)
committerNeil Smith <neil.git@njae.me.uk>
Mon, 26 Dec 2016 12:15:16 +0000 (12:15 +0000)
adventofcode1625/adventofcode1625.cabal [new file with mode: 0644]
adventofcode1625/app/advent25.hs [new file with mode: 0644]
data/advent25.txt [new file with mode: 0644]
day25.html [new file with mode: 0644]
stack.yaml

diff --git a/adventofcode1625/adventofcode1625.cabal b/adventofcode1625/adventofcode1625.cabal
new file mode 100644 (file)
index 0000000..5523756
--- /dev/null
@@ -0,0 +1,48 @@
+name:                adventofcode1625
+version:             0.1.0.0
+synopsis:            Initial project template from stack
+description:         Please see README.md
+homepage:            https://github.com/neilnjae/adventofcode16#readme
+license:             BSD3
+license-file:        LICENSE
+author:              Neil Smith
+maintainer:          noone@njae.me.uk
+copyright:           2016 Neil Smith
+category:            None
+build-type:          Simple
+extra-source-files:  README.md
+cabal-version:       >=1.10
+
+library
+  hs-source-dirs:      src
+  build-depends:       base >= 4.7 && < 5
+  default-language:    Haskell2010
+
+executable advent25
+  hs-source-dirs:      app
+  main-is:             advent25.hs
+  ghc-options:         -O2 -threaded -rtsopts -with-rtsopts=-N
+  build-depends:       base
+                     , adventofcode1625
+                     , adventofcode16
+                     , parsec
+                     , parsec-numbers
+                     , mtl
+  default-language:    Haskell2010
+
+test-suite adventofcode1625-test
+  type:                exitcode-stdio-1.0
+  hs-source-dirs:      test
+  main-is:             Spec.hs
+  build-depends:       base
+                     , adventofcode1625
+                     , adventofcode16
+                     , parsec
+                     , parsec-numbers
+                     , mtl
+  ghc-options:         -threaded -rtsopts -with-rtsopts=-N
+  default-language:    Haskell2010
+
+source-repository head
+  type:     git
+  location: https://github.com/neilnjae/adventofcode16
diff --git a/adventofcode1625/app/advent25.hs b/adventofcode1625/app/advent25.hs
new file mode 100644 (file)
index 0000000..077201f
--- /dev/null
@@ -0,0 +1,206 @@
+module Main(main) where
+
+import Text.Parsec hiding (State)
+import Text.ParserCombinators.Parsec.Number
+import Control.Monad.State.Lazy
+
+-- import Control.Monad.Writer
+import Control.Monad.Reader
+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
+                   | Out Location
+                   deriving (Show, Eq)
+
+data Machine = Machine { a :: Int
+                       , b :: Int
+                       , c :: Int
+                       , d :: Int
+                       , pc :: Int
+                       , instructions :: [Instruction]
+                       , execCount :: Int
+                       } 
+               deriving (Show, Eq)
+
+data AppConfig = AppConfig { cfgMaxRun :: Int } deriving (Show)
+
+
+type App = ReaderT AppConfig (State Machine) String
+
+
+testInstructions1 = "\
+\cpy 5 d\n\
+\cpy 7 c\n\
+\cpy 362 b\n\
+\inc d\n\
+\dec b\n\
+\jnz b -2\n\
+\dec c\n\
+\jnz c -5\n\
+\out d"
+
+testInstructions2 = "jnz 1 0"
+
+target :: String
+target = cycle "01"
+
+emptyMachine :: Machine
+emptyMachine = Machine {a=0, b=0, c=0, d=0, pc=0, instructions=[], execCount=0}
+
+main :: IO ()
+main = do 
+    text <- readFile "data/advent25.txt" 
+    -- let text = testInstructions1
+    let instructions = successfulParse $ parseIfile text
+    part1 instructions
+
+
+part1 :: [Instruction] -> IO ()
+part1 instrs = 
+    print $ head validInputs
+    where m0 = emptyMachine {instructions=instrs}
+          inputs = [0..]
+          validInputs = filter (validMachine) inputs
+          validMachine i = valid $ evalMachine m0 i
+    -- let config = AppConfig {cfgMaxRun = 500000}
+    --     m0 = emptyMachine {instructions=instrs}
+    --     -- res = runState (runReaderT (runMachine "") config) st
+    --     res = evalState (runReaderT (runMachine "") config) m0
+    -- in print res -- (signal, st')
+
+
+valid :: String -> Bool
+valid output = all (\p -> fst p == snd p) $ zip target output
+
+evalMachine :: Machine -> Int -> String
+evalMachine machine0 input = evalState (runReaderT (runMachine "") config) m
+    where m = machine0 {a = input}
+          config = AppConfig {cfgMaxRun = 500000}
+
+runMachine :: String -> App -- State Machine String
+runMachine output = 
+    do  cfg <- ask
+        m <- get
+        if (pc m) >= (length $ instructions m) || execCount m > cfgMaxRun cfg
+            then return output
+            else do thisOutput <- executeStep
+                    runMachine (output ++ thisOutput)
+
+
+executeStep :: App -- State Machine String
+executeStep = 
+    do  m <- get
+        let i = (instructions m)!!(pc m)
+        let output = generateOutput i m
+        put (executeInstructionPeep i m) {execCount = (execCount m) + 1}
+        -- put (executeInstruction i m) {execCount = (execCount m) + 1}
+        return output
+
+generateOutput :: Instruction -> Machine -> String
+generateOutput (Out a) m = show $ evaluate m a
+generateOutput _ _ = ""
+
+executeInstructionPeep :: Instruction -> Machine -> Machine
+executeInstructionPeep i m =
+    if sample == sampleTarget
+        -- then trace ("Peeping 1 " ++ (show m) ++ " to " ++ (show m1)) m1
+        then m1
+        else executeInstruction i m
+    where sample = take (length sampleTarget) $ drop (pc m) $ instructions m 
+          sampleTarget = [  Inc (Register 'd')
+                          , Dec (Register 'b')
+                          , Jnz (Register 'b') (Literal (-2))
+                          , Dec (Register 'c')
+                          , Jnz (Register 'c') (Literal (-5)) ]
+          m1 = m {d = d m + c m * b m, c = 0, b = 0, pc = pc m + (length sample)}
+
+
+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
+executeInstruction (Out _) m = m {pc = pc m + 1}
+
+
+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 = incL <|> decL <|> cpyL <|> jnzL <|> tglL <|> outL
+
+incL = Inc <$> (string "inc" *> spaces *> register)
+decL = Dec <$> (string "dec" *> spaces *> register)
+cpyL = Cpy <$> (string "cpy" *> spaces *> location) <*> (spaces *> register)
+jnzL = Jnz <$> (string "jnz" *> spaces *> location) <*> (spaces *> location)
+tglL = Tgl <$> (string "tgl" *> spaces *> location)
+outL = Out <$> (string "out" *> spaces *> location)
+
+location = (Literal <$> int) <|> register
+register = Register <$> (oneOf "abcd")
+
+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
diff --git a/data/advent25.txt b/data/advent25.txt
new file mode 100644 (file)
index 0000000..ae27d4b
--- /dev/null
@@ -0,0 +1,30 @@
+cpy a d
+cpy 7 c
+cpy 362 b
+inc d
+dec b
+jnz b -2
+dec c
+jnz c -5
+cpy d a
+jnz 0 0
+cpy a b
+cpy 0 a
+cpy 2 c
+jnz b 2
+jnz 1 6
+dec b
+dec c
+jnz c -4
+inc a
+jnz 1 -7
+cpy 2 b
+jnz c 2
+jnz 1 4
+dec b
+dec c
+jnz 1 -4
+jnz 0 0
+out b
+jnz a -19
+jnz 1 -21
\ No newline at end of file
diff --git a/day25.html b/day25.html
new file mode 100644 (file)
index 0000000..e4cb6e0
--- /dev/null
@@ -0,0 +1,148 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 25 - 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?10"/>
+<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">50*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">/*</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://infi.nl/vacature/infi-zoekt-een-ontwikkelaar/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);">Infi</a> - Fvzcry gbpu? Xbz arkg-yriry glcra va Hgerpug bc baf areqxjnegvre!</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>
+<style>article *[title]{border-bottom:1px dotted #ffff66;}</style><article class="day-desc"><h2>--- Day 25: Clock Signal ---</h2><p>You open the door and find yourself on the roof. The city sprawls away from you for miles and miles.</p>
+<p>There's not much time now - it's already Christmas, but you're nowhere near the North Pole, much too far to deliver these stars to the sleigh in time.</p>
+<p>However, maybe the <em>huge antenna</em> up here can offer a solution. After all, the sleigh doesn't need the stars, exactly; it needs the timing data they provide, and you happen to have a massive signal generator right here.</p>
+<p>You connect the stars you have to your prototype computer, connect that to the antenna, and begin the transmission.</p>
+<p><span title="Then again, if something ever works on the first try, you should be *very* suspicious.">Nothing happens.</span></p>
+<p>You call the service number printed on the side of the antenna and quickly explain the situation. "I'm not sure what kind of equipment you have connected over there," he says, "but you need a clock signal." You try to explain that this is a signal for a clock.</p>
+<p>"No, no, a <a href="https://en.wikipedia.org/wiki/Clock_signal">clock signal</a> - timing information so the antenna computer knows how to read the data you're sending it. An endless, alternating pattern of <code>0</code>, <code>1</code>, <code>0</code>, <code>1</code>, <code>0</code>, <code>1</code>, <code>0</code>, <code>1</code>, <code>0</code>, <code>1</code>...." He trails off.</p>
+<p>You ask if the antenna can handle a clock signal at the frequency you would need to use for the data from the stars. "There's <em>no way</em> it can! The only antenna we've installed capable of <em>that</em> is on top of a top-secret Easter Bunny installation, and you're <em>definitely</em> not-" You hang up the phone.</p>
+<p>You've extracted the antenna's clock signal generation <a href="12">assembunny</a> code (your puzzle input); it looks mostly compatible with code you worked on <a href="23">just recently</a>.</p>
+<p>This antenna code, being a signal generator, uses one extra instruction:</p>
+<ul>
+<li><code>out x</code> <em>transmits</em> <code>x</code> (either an integer or the <em>value</em> of a register) as the next value for the clock signal.</li>
+</ul>
+<p>The code takes a value (via register <code>a</code>) that describes the signal to generate, but you're not sure how it's used. You'll have to find the input to produce the right signal through experimentation.</p>
+<p><em>What is the lowest positive integer</em> that can be used to initialize register <code>a</code> and cause the code to output a clock signal of <code>0</code>, <code>1</code>, <code>0</code>, <code>1</code>... repeating forever?</p>
+</article>
+<p>Your puzzle answer was <code>196</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>The antenna is ready. Now, all you need is the <em class="star">fifty stars</em> required to generate the signal for the sleigh, but you don't have enough.</p>
+<p>You look toward the sky in desperation... suddenly noticing that a lone star has been installed at the top of the antenna!  Only <em>49 more</em> to go.</p>
+</article>
+<form method="post" action="25/answer"><input type="hidden" name="level" value="2"/><input type="hidden" name="answer" value="0"/><p>If you like, you can <input type="submit" value="[Retransmit the Signal]"/>.</p></form>
+<p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, all that is left is for you to <a href="/2016">admire your advent calendar</a>.</p>
+<p>If you still want to see it, you can <a href="25/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+%22Clock+Signal%22+%2D+Day+25+%2D+Advent+of+Code+2016&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F25&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
+  <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F25" target="_blank">Google+</a>
+  <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F25&amp;title=I%27ve+completed+%22Clock+Signal%22+%2D+Day+25+%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
index b51ba57042d141bea041e024fb3d1f301bc779ed..cf9451a0a5119f6cdb62f8b6a2445f52746c6e9d 100644 (file)
@@ -5,6 +5,7 @@ packages:
 - adventofcode1601
 - adventofcode1602
 - adventofcode1624
 - adventofcode1601
 - adventofcode1602
 - adventofcode1624
+- adventofcode1625
 system-ghc: true
 extra-deps:
 - astar-0.3.0.0
 system-ghc: true
 extra-deps:
 - astar-0.3.0.0