From 864aa7e1075c6b7c75037dc4b11afe4a30d73618 Mon Sep 17 00:00:00 2001
From: Neil Smith <neil.git@njae.me.uk>
Date: Thu, 6 Dec 2018 09:25:16 +0000
Subject: [PATCH] Day 6
---
advent-of-code.cabal | 9 ++
data/advent06.txt | 50 +++++++++++
problems/day06.html | 186 +++++++++++++++++++++++++++++++++++++++
src/advent06/advent06.hs | 119 +++++++++++++++++++++++++
4 files changed, 364 insertions(+)
create mode 100644 data/advent06.txt
create mode 100644 problems/day06.html
create mode 100644 src/advent06/advent06.hs
diff --git a/advent-of-code.cabal b/advent-of-code.cabal
index 9196505..f4fb19a 100644
--- a/advent-of-code.cabal
+++ b/advent-of-code.cabal
@@ -58,3 +58,12 @@ executable advent05
main-is: advent05.hs
default-language: Haskell2010
build-depends: base >= 4.7 && < 5
+
+executable advent06
+ hs-source-dirs: src/advent06
+ main-is: advent06.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , text
+ , megaparsec
+ , containers
\ No newline at end of file
diff --git a/data/advent06.txt b/data/advent06.txt
new file mode 100644
index 0000000..bb0948a
--- /dev/null
+++ b/data/advent06.txt
@@ -0,0 +1,50 @@
+77, 279
+216, 187
+72, 301
+183, 82
+57, 170
+46, 335
+55, 89
+71, 114
+313, 358
+82, 88
+78, 136
+339, 314
+156, 281
+260, 288
+125, 249
+150, 130
+210, 271
+190, 258
+73, 287
+187, 332
+283, 353
+66, 158
+108, 97
+237, 278
+243, 160
+61, 52
+353, 107
+260, 184
+234, 321
+181, 270
+104, 84
+290, 109
+193, 342
+43, 294
+134, 211
+50, 129
+92, 112
+309, 130
+291, 170
+89, 204
+186, 177
+286, 302
+188, 145
+40, 52
+254, 292
+270, 287
+238, 216
+299, 184
+141, 264
+117, 129
diff --git a/problems/day06.html b/problems/day06.html
new file mode 100644
index 0000000..390a26a
--- /dev/null
+++ b/problems/day06.html
@@ -0,0 +1,186 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 6 - 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?17"/>
+<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">12*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap"><y></span><a href="/2018">2018</a><span class="title-event-wrap"></y></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://rainway.io/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Rainway</a> - Play all your favorite PC games anytime, anywhere, across a variety of different devices.</div></div>
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 6: Chronal Coordinates ---</h2><p>The device on your wrist beeps several times, and once again you feel like you're falling.</p>
+<p>"<span title="Why is the situation always critical? Why can't the situation just be boring for once?">Situation critical</span>," the device announces. "Destination indeterminate. Chronal interference detected. Please specify new target coordinates."</p>
+<p>The device then produces a list of coordinates (your puzzle input). Are they places it thinks are safe or dangerous? It recommends you check manual page 729. The Elves did not give you a manual.</p>
+<p><em>If they're dangerous,</em> maybe you can minimize the danger by finding the coordinate that gives the largest distance from the other points.</p>
+<p>Using only the <a href="https://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan distance</a>, determine the <em>area</em> around each coordinate by counting the number of <a href="https://en.wikipedia.org/wiki/Integer">integer</a> X,Y locations that are <em>closest</em> to that coordinate (and aren't <em>tied in distance</em> to any other coordinate).</p>
+<p>Your goal is to find the size of the <em>largest area</em> that isn't infinite. For example, consider the following list of coordinates:</p>
+<pre><code>1, 1
+1, 6
+8, 3
+3, 4
+5, 5
+8, 9
+</code></pre>
+<p>If we name these coordinates <code>A</code> through <code>F</code>, we can draw them on a grid, putting <code>0,0</code> at the top left:</p>
+<pre><code>..........
+.A........
+..........
+........C.
+...D......
+.....E....
+.B........
+..........
+..........
+........F.
+</code></pre>
+<p>This view is partial - the actual grid extends infinitely in all directions. Using the Manhattan distance, each location's closest coordinate can be determined, shown here in lowercase:</p>
+<pre><code>aaaaa.cccc
+a<em>A</em>aaa.cccc
+aaaddecccc
+aadddecc<em>C</em>c
+..d<em>D</em>deeccc
+bb.de<em>E</em>eecc
+b<em>B</em>b.eeee..
+bbb.eeefff
+bbb.eeffff
+bbb.ffff<em>F</em>f
+</code></pre>
+<p>Locations shown as <code>.</code> are equally far from two or more coordinates, and so they don't count as being closest to any.</p>
+<p>In this example, the areas of coordinates A, B, C, and F are infinite - while not shown here, their areas extend forever outside the visible grid. However, the areas of coordinates D and E are finite: D is closest to 9 locations, and E is closest to 17 (both including the coordinate's location itself). Therefore, in this example, the size of the largest area is <em>17</em>.</p>
+<p><em>What is the size of the largest area</em> that isn't infinite?</p>
+</article>
+<p>Your puzzle answer was <code>3006</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>On the other hand, <em>if the coordinates are safe</em>, maybe the best you can do is try to find a <em>region</em> near as many coordinates as possible.</p>
+<p>For example, suppose you want the sum of the <a href="https://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan distance</a> to all of the coordinates to be <em>less than 32</em>. For each location, add up the distances to all of the given coordinates; if the total of those distances is less than 32, that location is within the desired region. Using the same coordinates as above, the resulting region looks like this:</p>
+<pre><code>..........
+.A........
+..........
+...#<em>#</em>#..C.
+..#D###...
+..###E#...
+.B.###....
+..........
+..........
+........F.
+</code></pre>
+<p>In particular, consider the highlighted location <code>4,3</code> located at the top middle of the region. Its calculation is as follows, where <code>abs()</code> is the <a href="https://en.wikipedia.org/wiki/Absolute_value">absolute value</a> function:</p>
+<ul>
+<li>Distance to coordinate A: <code>abs(4-1) + abs(3-1) = 5</code></li>
+<li>Distance to coordinate B: <code>abs(4-1) + abs(3-6) = 6</code></li>
+<li>Distance to coordinate C: <code>abs(4-8) + abs(3-3) = 4</code></li>
+<li>Distance to coordinate D: <code>abs(4-3) + abs(3-4) = 2</code></li>
+<li>Distance to coordinate E: <code>abs(4-5) + abs(3-5) = 3</code></li>
+<li>Distance to coordinate F: <code>abs(4-8) + abs(3-9) = 10</code></li>
+<li>Total distance: <code>5 + 6 + 4 + 2 + 3 + 10 = 30</code></li>
+</ul>
+<p>Because the total distance to all coordinates (<code>30</code>) is less than 32, the location is <em>within</em> the region.</p>
+<p>This region, which also includes coordinates D and E, has a total size of <em>16</em>.</p>
+<p>Your actual region will need to be much larger than this example, though, instead including all locations with a total distance of less than <em>10000</em>.</p>
+<p><em>What is the size of the region containing all locations which have a total distance to all given coordinates of less than 10000?</em></p>
+</article>
+<p>Your puzzle answer was <code>42998</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>If you still want to see it, you can <a href="6/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+%22Chronal+Coordinates%22+%2D+Day+6+%2D+Advent+of+Code+2018&url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F6&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F6&title=I%27ve+completed+%22Chronal+Coordinates%22+%2D+Day+6+%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/advent06/advent06.hs b/src/advent06/advent06.hs
new file mode 100644
index 0000000..2ff18f5
--- /dev/null
+++ b/src/advent06/advent06.hs
@@ -0,0 +1,119 @@
+{-# LANGUAGE OverloadedStrings #-}
+
+import Data.List
+
+import Data.Text (Text)
+import qualified Data.Text.IO as TIO
+
+import Data.Void (Void)
+
+import Text.Megaparsec
+import Text.Megaparsec.Char
+import qualified Text.Megaparsec.Char.Lexer as L
+import qualified Control.Applicative as CA
+
+import qualified Data.Map.Strict as M
+
+type Coord = (Integer, Integer) -- x, y
+type Bounds = (Integer, Integer, Integer, Integer)
+type Region = M.Map Coord Int
+
+main :: IO ()
+main = do
+ text <- TIO.readFile "data/advent06.txt"
+ let coords = successfulParse text
+ let boundingBox = findBounds coords
+ print $ length coords
+ print boundingBox
+ print $ part1 coords boundingBox
+ print $ part2 coords boundingBox
+ -- print $ part1 activity
+ -- print $ part2 activity
+
+
+part1 coords bounds = largestRegion $ regionSizes $ finite edgeLabels regions
+ where regions = findRegions coords bounds
+ edgeLabels = infinite regions bounds
+
+part2 coords bounds = M.size $ M.filter (< 10000) $ safeCells coords bounds
+
+findRegions :: [Coord] -> Bounds -> Region
+findRegions coords (minX, maxX, minY, maxY) = M.fromList labelledCells
+ where cells = [(x, y) | x <- [minX .. maxX], y <- [minY .. maxY] ]
+ starts = zip [1..] coords
+ labelledCells = map (\c -> (c, nearestStart 0 c starts)) cells
+
+nearestStart :: Int -> Coord -> [(Int, Coord)] -> Int
+nearestStart tieLabel cell starts = nearestLabel
+ where distances = sort $ map (\(l, s) -> (distance s cell , l)) starts
+ nearestLabel = if fst (distances!!0) == fst (distances!!1)
+ then tieLabel
+ else snd (distances!!0)
+
+
+safeCells :: [Coord] -> Bounds -> Region
+safeCells coords (minX, maxX, minY, maxY) = M.fromList distanceCells
+ where cells = [(x, y) | x <- [minX .. maxX], y <- [minY .. maxY] ]
+ distanceCells = map (\c -> (c, fromIntegral $ sumDistance c coords) ) cells
+
+
+sumDistance :: Coord -> [Coord] -> Integer
+sumDistance here others = sum $ map (\c -> distance here c) others
+
+
+infinite :: Region -> Bounds -> [Int]
+infinite regions (minX, maxX, minY, maxY) = nub $ sort $ M.elems $ M.filterWithKey onEdge regions
+ where onEdge (x, y) _ = (x == minX) || (x == maxX) || (y == minY) || (y == maxY)
+
+finite :: [Int] -> Region -> Region
+finite excluded regions = M.filter (\r -> r `notElem` excludedTied) regions
+ where excludedTied = (0:excluded)
+
+
+regionSizes :: Region -> [(Int, Int)]
+regionSizes regions = map (\g -> (g!!0, length g)) $ group $ sort $ M.elems regions
+
+
+largestRegion :: [(Int, Int)] -> Int
+largestRegion = maximum . map snd
+
+
+findBounds :: [Coord] -> (Integer, Integer, Integer, Integer)
+findBounds coords = ( minX - (maxY - minY) -- small x edge
+ , maxX + (maxY - minY) -- large x edge
+ , minY - (maxX - minX) -- small x edge
+ , maxY + (maxX - minX) -- large y edge
+ )
+ where maxX = maximum $ map fst coords
+ minX = minimum $ map fst coords
+ maxY = maximum $ map snd coords
+ minY = minimum $ map snd coords
+
+-- Manhattan distance
+distance :: Coord -> Coord -> Integer
+distance (x1, y1) (x2, y2) = (abs (x1 - x2)) + (abs (y1 - y2))
+
+
+-- Parse the input file
+
+type Parser = Parsec Void Text
+
+sc :: Parser ()
+sc = L.space (skipSome spaceChar) CA.empty CA.empty
+-- sc = L.space (skipSome (char ' ')) CA.empty CA.empty
+
+lexeme = L.lexeme sc
+integer = lexeme L.decimal
+symb = L.symbol sc
+
+commaP = symb ","
+
+
+coordFileP = many coordP
+coordP = (,) <$> integer <* commaP <*> integer
+
+successfulParse :: Text -> [Coord]
+successfulParse input =
+ case parse coordFileP "input" input of
+ Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
+ Right coords -> coords
\ No newline at end of file
--
2.43.0