Day 11 done
authorNeil Smith <neil.git@njae.me.uk>
Thu, 12 Dec 2019 09:55:34 +0000 (09:55 +0000)
committerNeil Smith <neil.git@njae.me.uk>
Thu, 12 Dec 2019 09:55:34 +0000 (09:55 +0000)
advent11/package.yaml [new file with mode: 0644]
advent11/src/advent11.hs [new file with mode: 0644]
data/advent11.txt [new file with mode: 0644]
problems/day11.html [new file with mode: 0644]
stack.yaml

diff --git a/advent11/package.yaml b/advent11/package.yaml
new file mode 100644 (file)
index 0000000..eda3fb6
--- /dev/null
@@ -0,0 +1,60 @@
+# This YAML file describes your package. Stack will automatically generate a
+# Cabal file when you run `stack build`. See the hpack website for help with
+# this file: <https://github.com/sol/hpack>.
+
+name: advent11
+synopsis: Advent of Code
+version: '0.0.1'
+
+default-extensions:
+- AllowAmbiguousTypes
+- ApplicativeDo
+- BangPatterns
+- BlockArguments
+- DataKinds
+- DeriveFoldable
+- DeriveFunctor
+- DeriveGeneric
+- DeriveTraversable
+- EmptyCase
+- FlexibleContexts
+- FlexibleInstances
+- FunctionalDependencies
+- GADTs
+- GeneralizedNewtypeDeriving
+- ImplicitParams
+- KindSignatures
+- LambdaCase
+- MonadComprehensions
+- MonoLocalBinds
+- MultiParamTypeClasses
+- MultiWayIf
+- NegativeLiterals
+- NumDecimals
+- OverloadedLists
+- OverloadedStrings
+- PartialTypeSignatures
+- PatternGuards
+- PatternSynonyms
+- PolyKinds
+- RankNTypes
+- RecordWildCards
+- ScopedTypeVariables
+- TemplateHaskell
+- TransformListComp
+- TupleSections
+- TypeApplications
+- TypeInType
+- TypeOperators
+- ViewPatterns
+
+
+executables:
+  advent11:
+    main: advent11.hs
+    source-dirs: src
+    dependencies:
+    - base >= 2 && < 6
+    - text
+    - containers
+    - intcode
diff --git a/advent11/src/advent11.hs b/advent11/src/advent11.hs
new file mode 100644 (file)
index 0000000..264ce31
--- /dev/null
@@ -0,0 +1,140 @@
+import Debug.Trace
+
+import Intcode
+
+import qualified Data.Text.IO as TIO
+
+import qualified Data.Map.Strict as M
+-- import Data.Map.Strict ((!))
+-- import Data.List
+-- import Data.Function (on)
+
+type Position = (Int, Int) -- x, y
+data Colour = Black | White deriving (Show, Eq, Ord)
+data Direction = North | East | South | West deriving (Show, Eq, Ord, Enum, Bounded)
+
+data Ant = Ant 
+    { _machine :: Machine
+    , _executionState :: ExecutionState
+    , _currentInput :: [Integer]
+    , _machineOutput :: [Integer]
+    , _currentPosition :: Position
+    , _currentDirection :: Direction
+    } deriving (Show, Eq)
+
+type Hull = M.Map Position Colour
+
+
+main :: IO ()
+main = do 
+        text <- TIO.readFile "data/advent11.txt"
+        let mem = parseMachineMemory text
+        -- print mem
+        print $ part1 mem
+        putStrLn $ part2 mem
+
+
+part1 mem = M.size hull
+    where ant = encapsulate mem []
+          hull = runAnt ant M.empty
+
+part2 mem = showHull hull
+    where ant = encapsulate mem []
+          hull = runAnt ant (M.singleton (0, 0) White)
+
+encapsulate :: [Integer] -> [Integer] -> Ant
+encapsulate mem input = Ant 
+    { _machine = makeMachine mem
+    , _executionState = Runnable
+    , _machineOutput = []
+    , _currentInput = input
+    , _currentPosition = (0, 0)
+    , _currentDirection = North
+    }
+
+
+runAnt :: Ant -> Hull -> Hull
+-- runAnt ant hull | trace (show ant ++ " -> " ++ (show (runAntStep ant)) ++ " -- " ++ show hull) False = undefined
+runAnt ant hull = hull''
+    where ant' = runAntStep ant
+          output = _machineOutput ant'
+          hull' = if (null output) then hull else paint hull ant' (output!!0)
+          ant'' = if (null output) then ant' else move ant' (output!!1)
+          ant''' = camera ant'' hull
+          hull'' =  if (_executionState ant' == Terminated)
+                    then hull'
+                    else runAnt ant''' hull'
+
+
+paint :: Hull -> Ant -> Integer -> Hull
+paint hull ant 0 = M.insert (_currentPosition ant) Black hull
+paint hull ant 1 = M.insert (_currentPosition ant) White hull
+
+move :: Ant -> Integer -> Ant
+move ant angle = ant { _currentDirection = direction', _currentPosition = position' }
+    where direction' = turn (_currentDirection ant) angle
+          delta = directionDelta direction'
+          position' = sumPos delta $ _currentPosition ant
+
+camera :: Ant -> Hull -> Ant
+camera ant hull = ant { _currentInput = input' }
+    where colour = M.findWithDefault Black (_currentPosition ant) hull
+          input = _currentInput ant
+          input' = input ++ [colourNum colour]
+
+colourNum :: Colour -> Integer
+colourNum Black = 0
+colourNum White = 1
+
+turn :: Direction -> Integer -> Direction
+turn direction 0 = predW direction
+turn direction 1 = succW direction
+
+directionDelta :: Direction -> Position
+directionDelta North = ( 0 ,  1)
+directionDelta East  = ( 1 ,  0)
+directionDelta South = ( 0 , -1)
+directionDelta West  = (-1 ,  0)
+
+sumPos :: Position -> Position -> Position
+sumPos (a, b) (c, d) = (a + c, b + d)
+
+
+runAntStep :: Ant -> Ant
+runAntStep a = a { _machine = machine'
+                 , _executionState = halted
+                 , _machineOutput = output
+                 }
+    where   machine = _machine a
+            input = _currentInput a
+            (halted, machine', output) = runMachine input machine
+
+
+showHull :: Hull -> String
+showHull hull = unlines rows
+    where   minX = minimum $ map fst $ M.keys hull
+            minY = minimum $ map snd $ M.keys hull
+            maxX = maximum $ map fst $ M.keys hull
+            maxY = maximum $ map snd $ M.keys hull
+            rows = [showHullRow hull minX maxX y | y <- reverse [minY..maxY]]
+
+showHullRow :: Hull -> Int -> Int -> Int -> String
+showHullRow hull minX maxX y = [showHullCell hull x y | x <- [minX..maxX]] 
+
+showHullCell :: Hull -> Int -> Int -> Char
+showHullCell hull x y
+    | colour == White = '\x2588'
+    | colour == Black = ' '
+    where colour = M.findWithDefault Black (x, y) hull
+
+
+-- | a `succ` that wraps 
+succW :: (Bounded a, Enum a, Eq a) => a -> a 
+succW dir | dir == maxBound = minBound
+          | otherwise = succ dir
+
+-- | a `pred` that wraps
+predW :: (Bounded a, Enum a, Eq a) => a -> a
+predW dir | dir == minBound = maxBound
+          | otherwise = pred dir
+
diff --git a/data/advent11.txt b/data/advent11.txt
new file mode 100644 (file)
index 0000000..1db3e3c
--- /dev/null
@@ -0,0 +1 @@
+3,8,1005,8,314,1106,0,11,0,0,0,104,1,104,0,3,8,1002,8,-1,10,1001,10,1,10,4,10,108,1,8,10,4,10,1002,8,1,28,2,2,16,10,1,1108,7,10,1006,0,10,1,5,14,10,3,8,102,-1,8,10,101,1,10,10,4,10,108,1,8,10,4,10,102,1,8,65,1006,0,59,2,109,1,10,1006,0,51,2,1003,12,10,3,8,102,-1,8,10,1001,10,1,10,4,10,108,1,8,10,4,10,1001,8,0,101,1006,0,34,1,1106,0,10,1,1101,17,10,3,8,102,-1,8,10,101,1,10,10,4,10,1008,8,0,10,4,10,1001,8,0,135,3,8,1002,8,-1,10,101,1,10,10,4,10,108,0,8,10,4,10,1001,8,0,156,3,8,1002,8,-1,10,101,1,10,10,4,10,108,0,8,10,4,10,1001,8,0,178,1,108,19,10,3,8,102,-1,8,10,101,1,10,10,4,10,108,0,8,10,4,10,1002,8,1,204,1,1006,17,10,3,8,102,-1,8,10,101,1,10,10,4,10,108,1,8,10,4,10,102,1,8,230,1006,0,67,1,103,11,10,1,1009,19,10,1,109,10,10,3,8,102,-1,8,10,101,1,10,10,4,10,1008,8,0,10,4,10,101,0,8,268,3,8,102,-1,8,10,101,1,10,10,4,10,1008,8,1,10,4,10,1002,8,1,290,2,108,13,10,101,1,9,9,1007,9,989,10,1005,10,15,99,109,636,104,0,104,1,21101,48210224024,0,1,21101,0,331,0,1105,1,435,21101,0,937264165644,1,21101,0,342,0,1105,1,435,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,21101,235354025051,0,1,21101,389,0,0,1105,1,435,21102,29166169280,1,1,21102,400,1,0,1105,1,435,3,10,104,0,104,0,3,10,104,0,104,0,21102,709475849060,1,1,21102,1,423,0,1106,0,435,21102,868498428684,1,1,21101,434,0,0,1105,1,435,99,109,2,21201,-1,0,1,21101,0,40,2,21102,1,466,3,21101,456,0,0,1105,1,499,109,-2,2105,1,0,0,1,0,0,1,109,2,3,10,204,-1,1001,461,462,477,4,0,1001,461,1,461,108,4,461,10,1006,10,493,1101,0,0,461,109,-2,2106,0,0,0,109,4,2102,1,-1,498,1207,-3,0,10,1006,10,516,21102,1,0,-3,21201,-3,0,1,21201,-2,0,2,21102,1,1,3,21102,535,1,0,1106,0,540,109,-4,2106,0,0,109,5,1207,-3,1,10,1006,10,563,2207,-4,-2,10,1006,10,563,21202,-4,1,-4,1106,0,631,21201,-4,0,1,21201,-3,-1,2,21202,-2,2,3,21101,582,0,0,1105,1,540,22102,1,1,-4,21102,1,1,-1,2207,-4,-2,10,1006,10,601,21101,0,0,-1,22202,-2,-1,-2,2107,0,-3,10,1006,10,623,22102,1,-1,1,21101,623,0,0,105,1,498,21202,-2,-1,-2,22201,-4,-2,-4,109,-5,2105,1,0
diff --git a/problems/day11.html b/problems/day11.html
new file mode 100644 (file)
index 0000000..9e50c29
--- /dev/null
@@ -0,0 +1,173 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 11 - Advent of Code 2019</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?24"/>
+<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 a massive company, 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; preparing a new calendar and a new set of
+puzzles each year takes all of my free time for 4-5 months. 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="/2019/about">[About]</a></li><li><a href="/2019/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2019/settings">[Settings]</a></li><li><a href="/2019/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2019/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">22*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">0x0000|</span><a href="/2019">2019</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2019">[Calendar]</a></li><li><a href="/2019/support">[AoC++]</a></li><li><a href="/2019/sponsors">[Sponsors]</a></li><li><a href="/2019/leaderboard">[Leaderboard]</a></li><li><a href="/2019/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2019/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://formlabs.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Formlabs</a> - You don&apos;t need elves when you have 3D printers...</div></div>
+</div><!--/sidebar-->
+
+<main>
+<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
+<article class="day-desc"><h2>--- Day 11: Space Police ---</h2><p>On the way to Jupiter, you're <a href="https://www.youtube.com/watch?v=KwY28rpyKDE">pulled over</a> by the <em>Space Police</em>.</p>
+<p>"Attention, unmarked spacecraft! You are in violation of Space Law! All spacecraft must have a clearly visible <em>registration identifier</em>! You have 24 hours to comply or be sent to <a href="https://www.youtube.com/watch?v=BVn1oQL9sWg&t=5">Space Jail</a>!"</p>
+<p>Not wanting to be sent to Space Jail, you radio back to the Elves on Earth for help. Although it takes almost three hours for their reply signal to reach you, they send instructions for how to power up the <em>emergency hull painting robot</em> and even provide a small <a href="9">Intcode program</a> (your puzzle input) that will cause it to paint your ship appropriately.</p>
+<p>There's just one problem: you don't have an emergency hull painting robot.</p>
+<p>You'll need to build a new emergency hull painting robot. The robot needs to be able to move around on the grid of square panels on the side of your ship, detect the color of its current panel, and paint its current panel <em>black</em> or <em>white</em>. (All of the panels are currently <em>black</em>.)</p>
+<p>The Intcode program will serve as the brain of the robot. The program uses input instructions to access the robot's camera: provide <code>0</code> if the robot is over a <em>black</em> panel or <code>1</code> if the robot is over a <em>white</em> panel. Then, the program will output two values:</p>
+<ul>
+<li>First, it will output a value indicating the <em>color to paint the panel</em> the robot is over: <code>0</code> means to paint the panel <em>black</em>, and <code>1</code> means to paint the panel <em>white</em>.</li>
+<li>Second, it will output a value indicating the <em>direction the robot should turn</em>: <code>0</code> means it should turn <em>left 90 degrees</em>, and <code>1</code> means it should turn <em>right 90 degrees</em>.</li>
+</ul>
+<p>After the robot turns, it should always move <em>forward exactly one panel</em>. The robot starts facing <em>up</em>.</p>
+<p>The robot will continue running for a while like this and halt when it is finished drawing.  Do not restart the Intcode computer inside the robot during this process.</p>
+<p>For example, suppose the robot is about to start running.  Drawing black panels as <code>.</code>, white panels as <code>#</code>, and the robot pointing the direction it is facing (<code>&lt; ^ &gt; v</code>), the initial state and region near the robot looks like this:</p>
+<pre><code>.....
+.....
+..^..
+.....
+.....
+</code></pre>
+<p>The panel under the robot (not visible here because a <code>^</code> is shown instead) is also black, and so any input instructions at this point should be provided <code>0</code>. Suppose the robot eventually outputs <code>1</code> (paint white) and then <code>0</code> (turn left). After taking these actions and moving forward one panel, the region now looks like this:</p>
+<pre><code>.....
+.....
+.&lt;#..
+.....
+.....
+</code></pre>
+<p>Input instructions should still be provided <code>0</code>. Next, the robot might output <code>0</code> (paint black) and then <code>0</code> (turn left):</p>
+<pre><code>.....
+.....
+..#..
+.v...
+.....
+</code></pre>
+<p>After more outputs (<code>1,0</code>, <code>1,0</code>):</p>
+<pre><code>.....
+.....
+..^..
+.##..
+.....
+</code></pre>
+<p>The robot is now back where it started, but because it is now on a white panel, input instructions should be provided <code>1</code>.  After several more outputs (<code>0,1</code>, <code>1,0</code>, <code>1,0</code>), the area looks like this:</p>
+<pre><code>.....
+..&lt;#.
+...#.
+.##..
+.....
+</code></pre>
+<p>Before you deploy the robot, you should probably have an estimate of the area it will cover: specifically, you need to know the <em>number of panels it paints at least once</em>, regardless of color. In the example above, the robot painted <em><code>6</code> panels</em> at least once. (It painted its starting panel twice, but that panel is <a href="https://www.youtube.com/watch?v=KjsSvjA5TuE">still only counted once</a>; it also never painted the panel it ended on.)</p>
+<p>Build a new emergency hull painting robot and run the Intcode program on it. <em>How many panels does it paint at least once?</em></p>
+</article>
+<p>Your puzzle answer was <code>2343</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You're not sure what it's trying to paint, but it's definitely not a <em>registration identifier</em>.  The Space Police are getting impatient.</p>
+<p>Checking your external ship cameras again, you notice a white panel marked "emergency hull painting robot starting panel". The rest of the panels are <em>still black</em>, but it looks like the robot was expecting to <em>start on a white panel</em>, not a black one.</p>
+<p>Based on the <span title="Just be glad it wasn't a full set of Space Law Space Books; the number of pages is *astronomical*.">Space Law Space Brochure</span> that the Space Police attached to one of your windows, a valid registration identifier is always <em>eight capital letters</em>. After starting the robot on a single <em>white panel</em> instead, <em>what registration identifier does it paint</em> on your hull?</p>
+</article>
+<p>Your puzzle answer was <code>JFBERBUH</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="/2019">return to your Advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="11/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+%22Space+Police%22+%2D+Day+11+%2D+Advent+of+Code+2019&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F11&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
+  <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Space+Police%22+%2D+Day+11+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F11'}else{return false;}" target="_blank">Mastodon</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('set', 'anonymizeIp', true);
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file
index 1e2f684867af1f2b3901e61df4179b0e5db332a4..70ad0dde7b223e7f0d957d04b0bd60e3e8a9ac5f 100644 (file)
@@ -48,6 +48,7 @@ packages:
 - advent08
 - advent09
 - advent10
+- advent11
 
 
 # Dependency packages to be pulled from upstream that are not in the resolver.