From: Neil Smith <neil.git@njae.me.uk>
Date: Tue, 11 Dec 2018 18:14:21 +0000 (+0000)
Subject: Day 11
X-Git-Url: https://git.njae.me.uk/?p=advent-of-code-18.git;a=commitdiff_plain;h=83d84c049176a0a18772dee13c1eb099b242daed
Day 11
---
diff --git a/advent-of-code.cabal b/advent-of-code.cabal
index 83c71a9..2910874 100644
--- a/advent-of-code.cabal
+++ b/advent-of-code.cabal
@@ -120,3 +120,42 @@ executable advent09pl
, megaparsec
, containers
, pointedlist
+
+executable advent10
+ hs-source-dirs: src/advent10
+ main-is: advent10.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , text
+ , megaparsec
+ , containers
+
+executable advent10iz
+ hs-source-dirs: src/advent10
+ main-is: advent10-iterate-zip.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , text
+ , megaparsec
+ , containers
+
+executable advent11
+ hs-source-dirs: src/advent11
+ main-is: advent11.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , containers
+
+executable advent11m
+ hs-source-dirs: src/advent11
+ main-is: advent11-map.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , containers
+
+executable advent11naive
+ hs-source-dirs: src/advent11
+ main-is: advent11-naive.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , containers
diff --git a/problems/day11.html b/problems/day11.html
new file mode 100644
index 0000000..89e94a0
--- /dev/null
+++ b/problems/day11.html
@@ -0,0 +1,173 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 11 - 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?18"/>
+<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">22*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">{year=></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://clubhouse.io/?utm_source=spon&utm_medium=ch&utm_campaign=aoc2018" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Clubhouse</a> - The first project management platform for software development that brings everyone on every team together to build better products. AoC participants get two free months by signing up at r.clbh.se/mze9q9P Also, we're hiring!</div></div>
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 11: Chronal Charge ---</h2><p>You watch the Elves and their sleigh fade into the distance as they head toward the North Pole.</p>
+<p>Actually, you're the one fading. The <span title="wheeeeeeeeeeeeeeeeee">falling sensation</span> returns.</p>
+<p>The low fuel warning light is illuminated on your wrist-mounted device. Tapping it once causes it to project a hologram of the situation: a <em>300x300</em> grid of fuel cells and their current power levels, some negative. You're not sure what negative power means in the context of time travel, but it can't be good.</p>
+<p>Each fuel cell has a coordinate ranging <em>from 1 to 300</em> in both the X (horizontal) and Y (vertical) direction. In <code>X,Y</code> notation, the top-left cell is <code>1,1</code>, and the top-right cell is <code>300,1</code>.</p>
+<p>The interface lets you select <em>any 3x3 square</em> of fuel cells. To increase your chances of getting to your destination, you decide to choose the 3x3 square with the <em>largest total power</em>.</p>
+<p>The power level in a given fuel cell can be found through the following process:</p>
+<ul>
+<li>Find the fuel cell's <em>rack ID</em>, which is its <em>X coordinate plus 10</em>.</li>
+<li>Begin with a power level of the <em>rack ID</em> times the <em>Y coordinate</em>.</li>
+<li>Increase the power level by the value of the <em>grid serial number</em> (your puzzle input).</li>
+<li>Set the power level to itself multiplied by the <em>rack ID</em>.</li>
+<li>Keep only the <em>hundreds digit</em> of the power level (so <code>12<em>3</em>45</code> becomes <code>3</code>; numbers with no hundreds digit become <code>0</code>).</li>
+<li><em>Subtract 5</em> from the power level.</li>
+</ul>
+<p>For example, to find the power level of the fuel cell at <code>3,5</code> in a grid with serial number <code>8</code>:</p>
+<ul>
+<li>The rack ID is <code>3 + 10 = <em>13</em></code>.</li>
+<li>The power level starts at <code>13 * 5 = <em>65</em></code>.</li>
+<li>Adding the serial number produces <code>65 + 8 = <em>73</em></code>.</li>
+<li>Multiplying by the rack ID produces <code>73 * 13 = <em>949</em></code>.</li>
+<li>The hundreds digit of <code><em>9</em>49</code> is <code><em>9</em></code>.</li>
+<li>Subtracting 5 produces <code>9 - 5 = <em>4</em></code>.</li>
+</ul>
+<p>So, the power level of this fuel cell is <code><em>4</em></code>.</p>
+<p>Here are some more example power levels:</p>
+<ul>
+<li>Fuel cell at <code>122,79</code>, grid serial number <code>57</code>: power level <code>-5</code>.</li>
+<li>Fuel cell at <code>217,196</code>, grid serial number <code>39</code>: power level <code>0</code>.</li>
+<li>Fuel cell at <code>101,153</code>, grid serial number <code>71</code>: power level <code>4</code>.</li>
+</ul>
+<p>Your goal is to find the 3x3 square which has the largest total power. The square must be entirely within the 300x300 grid. Identify this square using the <code>X,Y</code> coordinate of its <em>top-left fuel cell</em>. For example:</p>
+<p>For grid serial number <code>18</code>, the largest total 3x3 square has a top-left corner of <code><em>33,45</em></code> (with a total power of <code>29</code>); these fuel cells appear in the middle of this 5x5 region:</p>
+<pre><code>-2 -4 4 4 4
+-4 <em> 4 4 4 </em>-5
+ 4 <em> 3 3 4 </em>-4
+ 1 <em> 1 2 4 </em>-3
+-1 0 2 -5 -2
+</code></pre>
+<p>For grid serial number <code>42</code>, the largest 3x3 square's top-left is <code><em>21,61</em></code> (with a total power of <code>30</code>); they are in the middle of this region:</p>
+<pre><code>-3 4 2 2 2
+-4 <em> 4 3 3 </em> 4
+-5 <em> 3 3 4 </em>-4
+ 4 <em> 3 3 4 </em>-3
+ 3 3 3 -5 -1
+</code></pre>
+<p><em>What is the <code>X,Y</code> coordinate of the top-left fuel cell of the 3x3 square with the largest total power?</em></p>
+</article>
+<p>Your puzzle answer was <code>21,34</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You discover a dial on the side of the device; it seems to let you select a square of <em>any size</em>, not just 3x3. Sizes from 1x1 to 300x300 are supported.</p>
+<p>Realizing this, you now must find the <em>square of any size with the largest total power</em>. Identify this square by including its size as a third parameter after the top-left coordinate: a 9x9 square with a top-left corner of <code>3,5</code> is identified as <code>3,5,9</code>.</p>
+<p>For example:</p>
+<ul>
+<li>For grid serial number <code>18</code>, the largest total square (with a total power of <code>113</code>) is 16x16 and has a top-left corner of <code>90,269</code>, so its identifier is <code><em>90,269,16</em></code>.</li>
+<li>For grid serial number <code>42</code>, the largest total square (with a total power of <code>119</code>) is 12x12 and has a top-left corner of <code>232,251</code>, so its identifier is <code><em>232,251,12</em></code>.</li>
+</ul>
+<p><em>What is the <code>X,Y,size</code> identifier of the square with the largest total power?</em></p>
+</article>
+<p>Your puzzle answer was <code>90,244,16</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>Your puzzle input was <code class="puzzle-input">5719</code>.</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+%22Chronal+Charge%22+%2D+Day+11+%2D+Advent+of+Code+2018&url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F11&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F11&title=I%27ve+completed+%22Chronal+Charge%22+%2D+Day+11+%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
diff --git a/src/advent11/advent11-map.hs b/src/advent11/advent11-map.hs
new file mode 100644
index 0000000..9549660
--- /dev/null
+++ b/src/advent11/advent11-map.hs
@@ -0,0 +1,58 @@
+{-# LANGUAGE OverloadedStrings #-}
+
+import Data.List
+import qualified Data.Map.Strict as M
+-- import Data.Map.Strict ((!))
+-- import qualified Data.Set as S
+-- import Data.Function (on)
+import Data.Ord (comparing)
+
+type Coord = (Integer, Integer) -- x, y
+type Grid = M.Map Coord Integer
+
+key = 5719
+-- key = 42
+
+main :: IO ()
+main = do
+ let g = makeGrid key
+ print $ part1 g
+ print $ part2 g
+
+
+part1 grid = keyOfMaxValue sg
+ where sg = allSubCellPower 3 grid
+
+
+part2 grid = maximumBy (comparing snd) $ [bestInGrid size grid | size <- [3..300]]
+
+-- bestSubCell size grid =
+
+makeGrid :: Integer -> Grid
+makeGrid key = M.fromList [((x, y), powerLevel x y key) | x <- [1..300], y <- [1..300] ]
+
+powerLevel :: Integer -> Integer -> Integer -> Integer
+powerLevel x y key = ((interim `div` 100) `mod` 10) - 5
+ where rackID = x + 10
+ interim = ((rackID) * y + key) * rackID
+
+subCellPower :: Integer -> Integer -> Integer -> Grid -> Integer
+subCellPower size x y grid = M.foldr (+) 0 subGrid
+ where subGrid = M.filterWithKey inBounds grid
+ inBounds (kx, ky) _ = (kx >= x) && (kx < x+size) && (ky >= y) && (ky < y+size)
+
+allSubCellPower :: Integer -> Grid -> Grid
+allSubCellPower size grid = M.fromList [((x, y), subCellPower size x y grid)| x <- [1..(301-size)], y <- [1..(301-size)]]
+
+
+keyAndMaxValue :: Ord b => M.Map a b -> (a, b)
+keyAndMaxValue m = M.foldrWithKey mergeKV (M.findMin m) m
+ where mergeKV k v (bestK, bestV) =
+ if v > bestV then (k, v) else (bestK, bestV)
+
+keyOfMaxValue :: Ord b => M.Map a b -> a
+keyOfMaxValue m = fst $ keyAndMaxValue m
+
+bestInGrid :: Integer -> Grid -> ((Integer, Integer, Integer), Integer)
+bestInGrid size grid = ((x, y, size), p)
+ where ((x, y), p) = keyAndMaxValue $ allSubCellPower size grid
diff --git a/src/advent11/advent11-naive.hs b/src/advent11/advent11-naive.hs
new file mode 100644
index 0000000..d79ebb4
--- /dev/null
+++ b/src/advent11/advent11-naive.hs
@@ -0,0 +1,56 @@
+{-# LANGUAGE OverloadedStrings #-}
+
+import Data.List
+import qualified Data.Map.Strict as M
+import Data.Map.Strict ((!))
+-- import qualified Data.Set as S
+-- import Data.Function (on)
+import Data.Ord (comparing)
+
+type Coord = (Integer, Integer) -- x, y
+type Grid = M.Map Coord Integer
+
+key = 5719
+-- key = 42
+
+main :: IO ()
+main = do
+ let g = makeGrid key
+ print $ part1 g
+ print $ part2 g
+
+
+part1 grid = keyOfMaxValue sg
+ where sg = allSubCellPower 3 grid
+
+
+part2 grid = maximumBy (comparing snd) $ [bestInGrid size grid | size <- [3..300]]
+
+-- bestSubCell size grid =
+
+makeGrid :: Integer -> Grid
+makeGrid key = M.fromList [((x, y), powerLevel x y key) | x <- [1..300], y <- [1..300] ]
+
+powerLevel :: Integer -> Integer -> Integer -> Integer
+powerLevel x y key = ((interim `div` 100) `mod` 10) - 5
+ where rackID = x + 10
+ interim = ((rackID) * y + key) * rackID
+
+subCellPower :: Integer -> Integer -> Integer -> Grid -> Integer
+subCellPower size x y grid = sum [grid!(sx, sy) | sx <- [x..(x+size-1)], sy <- [y..(y+size-1)]]
+
+allSubCellPower :: Integer -> Grid -> Grid
+allSubCellPower size grid = M.fromList [((x, y), subCellPower size x y grid)| x <- [1..(301-size)], y <- [1..(301-size)]]
+
+
+keyAndMaxValue :: Ord b => M.Map a b -> (a, b)
+keyAndMaxValue m = M.foldrWithKey mergeKV (M.findMin m) m
+ where mergeKV k v (bestK, bestV) =
+ if v > bestV then (k, v) else (bestK, bestV)
+
+keyOfMaxValue :: Ord b => M.Map a b -> a
+keyOfMaxValue m = fst $ keyAndMaxValue m
+
+bestInGrid :: Integer -> Grid -> ((Integer, Integer, Integer), Integer)
+bestInGrid size grid = ((x, y, size), p)
+ where ((x, y), p) = keyAndMaxValue $ allSubCellPower size grid
diff --git a/src/advent11/advent11.hs b/src/advent11/advent11.hs
new file mode 100644
index 0000000..1472f31
--- /dev/null
+++ b/src/advent11/advent11.hs
@@ -0,0 +1,73 @@
+{-# LANGUAGE OverloadedStrings #-}
+
+-- Using a summed-area table, e.g. see https://en.wikipedia.org/wiki/Summed-area_table
+
+import Data.List
+import qualified Data.Map.Strict as M
+import Data.Map.Strict ((!))
+-- import qualified Data.Set as S
+-- import Data.Function (on)
+import Data.Ord (comparing)
+
+type Coord = (Integer, Integer) -- x, y
+type Grid = M.Map Coord Integer
+
+key = 5719
+-- key = 42
+
+main :: IO ()
+main = do
+ let g = makeGrid key
+ print $ part1 g
+ print $ part2 g
+
+
+part1 grid = keyOfMaxValue sg
+ where sg = allSubCellPower 3 grid
+
+
+part2 grid = maximumBy (comparing snd) $ [bestInGrid size grid | size <- [3..300]]
+
+-- bestSubCell size grid =
+
+makeGrid :: Integer -> Grid
+-- makeGrid key = M.fromList [((x, y), powerLevel x y key) | x <- [1..300], y <- [1..300] ]
+makeGrid key = foldl' addSummedArea M.empty [((x, y), powerLevel x y key) | x <- [0..300], y <- [0..300] ]
+
+addSummedArea :: Grid -> ((Integer, Integer), Integer) -> Grid
+addSummedArea grid ((x, y), power) = M.insert (x, y) (power + upper + left - upperLeft) grid
+ where upper = M.findWithDefault 0 (x-1, y) grid
+ left = M.findWithDefault 0 (x, y-1) grid
+ upperLeft = M.findWithDefault 0 (x-1, y-1) grid
+
+
+powerLevel :: Integer -> Integer -> Integer -> Integer
+powerLevel 0 y _ = 0
+powerLevel x 0 _ = 0
+powerLevel x y key = ((interim `div` 100) `mod` 10) - 5
+ where rackID = x + 10
+ interim = ((rackID) * y + key) * rackID
+
+subCellPower :: Integer -> Integer -> Integer -> Grid -> Integer
+-- subCellPower size x y grid = sum [grid!(sx, sy) | sx <- [x..(x+size-1)], sy <- [y..(y+size-1)]]
+subCellPower size x0 y0 grid = grid!(x,y) + grid!(x',y') - grid!(x,y') - grid!(x',y)
+ where x = x0 - 1
+ x' = x + size
+ y = y0 - 1
+ y' = y + size
+
+allSubCellPower :: Integer -> Grid -> Grid
+allSubCellPower size grid = M.fromList [((x, y), subCellPower size x y grid)| x <- [1..(301-size)], y <- [1..(301-size)]]
+
+
+keyAndMaxValue :: Ord b => M.Map a b -> (a, b)
+keyAndMaxValue m = M.foldrWithKey mergeKV (M.findMin m) m
+ where mergeKV k v (bestK, bestV) =
+ if v > bestV then (k, v) else (bestK, bestV)
+
+keyOfMaxValue :: Ord b => M.Map a b -> a
+keyOfMaxValue m = fst $ keyAndMaxValue m
+
+bestInGrid :: Integer -> Grid -> ((Integer, Integer, Integer), Integer)
+bestInGrid size grid = ((x, y, size), p)
+ where ((x, y), p) = keyAndMaxValue $ allSubCellPower size grid