, text
, megaparsec
, parallel
+
+executable advent22a
+ hs-source-dirs: src/advent22
+ main-is: advent22a.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , containers
+
+executable advent22b
+ hs-source-dirs: src/advent22
+ main-is: advent22b.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , containers
+
+executable advent22bh
+ hs-source-dirs: src/advent22
+ main-is: advent22bh.hs
+ default-language: Haskell2010
+ build-depends: base >= 4.7 && < 5
+ , unordered-containers
--- /dev/null
+##########..#.###...##..#
+##....#...#....#..####.#.
+#..#.##..#..##.###..#.###
+.#.#.......####.....#.#..
+...######....#.##########
+##.#.....#.#####.#....###
+#.####.#..#.#.#...#.#..##
+#.##..#####..###..###.##.
+#.####.#.##.##...#.#.#.##
+#.#.#......##.##..###.#.#
+#...#.#..#.##....#.##..##
+.#.....##.##..#.####..##.
+.#......#.#.########..###
+##....###.#.#.###...##..#
+..##.###....#.....#...#.#
+....##...##...##.##.#..##
+..#.#.#..#######..###..##
+......#####.#####..#.#..#
+.####.#......#..###..#.##
+#....####.#..#.##.###.##.
+####.#...##....###...#.#.
+#####.#......#.#..###.##.
+#.##.#..#..#..#.....#.#.#
+#...#.#.##.#.####.#.#..#.
+.##.##..#..###.##.....###
\ No newline at end of file
--- /dev/null
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 22 - Advent of Code 2017</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?12"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<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 took an hour or two
+each, but the harder ones took 4-5 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="/2017/about">[About]</a></li><li><a href="/2017/support">[AoC++]</a></li><li><a href="/2017/events">[Events]</a></li><li><a href="/2017/settings">[Settings]</a></li><li><a href="/2017/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">44*</span></div></div><div><h1 class="title-event"> <span class="title-event-wrap">0xffff&</span><a href="/2017">2017</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2017">[Calendar]</a></li><li><a href="/2017/leaderboard">[Leaderboard]</a></li><li><a href="/2017/stats">[Stats]</a></li><li><a href="/2017/sponsors">[Sponsors]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2017/sponsors">sponsors</a> help make Advent of Code possible:</div><p><a href="http://www.novetta.com/careers?utm_campaign=Advent%20of%20Code%202017&utm_source=www.adventofcode.com&utm_medium=ad" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Novetta</a> - Unleash your imagination. Innovate at Novetta.</p></div>
+<p class="quiet">By popular demand, there are now AoC-themed objects available (until Jan. 3rd)! Get them shipped <a href="https://teespring.com/advent-of-code" target="_blank">from the US</a> or <a href="https://teespring.com/advent-of-code-eu" target="_blank">from Europe</a>.</p>
+
+</div><!--/sidebar-->
+
+<main>
+<article class="day-desc"><h2>--- Day 22: Sporifica Virus ---</h2><p>Diagnostics indicate that the local <em>grid computing cluster</em> has been contaminated with the <em>Sporifica Virus</em>. The grid computing cluster is a seemingly-<span title="The infinite is possible at AdventOfCodeCom.">infinite</span> two-dimensional grid of compute nodes. Each node is either <em>clean</em> or <em>infected</em> by the virus.<p>
+<p>To <a href="https://en.wikipedia.org/wiki/Morris_worm#The_mistake">prevent overloading</a> the nodes (which would render them useless to the virus) or detection by system administrators, exactly one <em>virus carrier</em> moves through the network, infecting or cleaning nodes as it moves. The virus carrier is always located on a single node in the network (the <em>current node</em>) and keeps track of the <em>direction</em> it is facing.</p>
+<p>To avoid detection, the virus carrier works in bursts; in each burst, it <em>wakes up</em>, does some <em>work</em>, and goes back to <em>sleep</em>. The following steps are all executed <em>in order</em> one time each burst:</p>
+<ul>
+<li>If the <em>current node</em> is <em>infected</em>, it turns to its <em>right</em>. Otherwise, it turns to its <em>left</em>. (Turning is done in-place; the <em>current node</em> does not change.)</li>
+<li>If the <em>current node</em> is <em>clean</em>, it becomes <em>infected</em>. Otherwise, it becomes <em>cleaned</em>. (This is done <em>after</em> the node is considered for the purposes of changing direction.)</li>
+<li>The virus carrier <a href="https://www.youtube.com/watch?v=2vj37yeQQHg">moves</a> <em>forward</em> one node in the direction it is facing.</li>
+</ul>
+<p>Diagnostics have also provided a <em>map of the node infection status</em> (your puzzle input). <em>Clean</em> nodes are shown as <code>.</code>; <em>infected</em> nodes are shown as <code>#</code>. This map only shows the center of the grid; there are many more nodes beyond those shown, but none of them are currently infected.</p>
+<p>The virus carrier begins in the middle of the map facing <em>up</em>.</p>
+<p>For example, suppose you are given a map like this:</p>
+<pre><code>..#
+#..
+...
+</code></pre>
+<p>Then, the middle of the infinite grid looks like this, with the virus carrier's position marked with <code>[ ]</code>:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . . #[.]. . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>The virus carrier is on a <em>clean</em> node, so it turns <em>left</em>, <em>infects</em> the node, and moves left:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . .[#]# . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>The virus carrier is on an <em>infected</em> node, so it turns <em>right</em>, <em>cleans</em> the node, and moves up:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . .[.]. # . . .
+. . . . # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>Four times in a row, the virus carrier finds a <em>clean</em>, <em>infects</em> it, turns <em>left</em>, and moves forward, ending in the same place and still facing up:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . #[#]. # . . .
+. . # # # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>Now on the same node as before, it sees an infection, which causes it to turn <em>right</em>, <em>clean</em> the node, and move forward:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . # .[.]# . . .
+. . # # # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>After the above actions, a total of <code>7</code> bursts of activity had taken place. Of them, <code>5</code> bursts of activity caused an infection.</p>
+<p>After a total of <code>70</code>, the grid looks like this, with the virus carrier facing up:</p>
+<pre><code>. . . . . # # . .
+. . . . # . . # .
+. . . # . . . . #
+. . # . #[.]. . #
+. . # . # . . # .
+. . . . . # # . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>By this time, <code>41</code> bursts of activity caused an infection (though most of those nodes have since been cleaned).</p>
+<p>After a total of <code>10000</code> bursts of activity, <code>5587</code> bursts will have caused an infection.</p>
+<p>Given your actual map, after <code>10000</code> bursts of activity, <em>how many bursts cause a node to become infected</em>? (Do not count nodes that begin infected.)</p>
+</article>
+<p>Your puzzle answer was <code>5182</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>As you go to remove the virus from the infected nodes, it <em>evolves</em> to resist your attempt.</p>
+<p>Now, before it infects a clean node, it will <em>weaken</em> it to disable your defenses. If it encounters an infected node, it will instead <em>flag</em> the node to be cleaned in the future. So:</p>
+<ul>
+<li><em>Clean</em> nodes become <em>weakened</em>.</li>
+<li><em>Weakened</em> nodes become <em>infected</em>.</li>
+<li><em>Infected</em> nodes become <em>flagged</em>.</li>
+<li><em>Flagged</em> nodes become <em>clean</em>.</li>
+</ul>
+<p>Every node is always in exactly one of the above states.</p>
+<p>The virus carrier still functions in a similar way, but now uses the following logic during its bursts of action:</p>
+<ul>
+<li>Decide which way to turn based on the <em>current node</em>:
+ <ul>
+ <li>If it is <em>clean</em>, it turns <em>left</em>.</li>
+ <li>If it is <em>weakened</em>, it does <em>not</em> turn, and will continue moving in the same direction.</li>
+ <li>If it is <em>infected</em>, it turns <em>right</em>.</li>
+ <li>If it is <em>flagged</em>, it <em>reverses</em> direction, and will go back the way it came.</li>
+ </ul>
+</li>
+<li>Modify the state of the <em>current node</em>, as described above.</li>
+<li>The virus carrier moves <em>forward</em> one node in the direction it is facing.</li>
+</ul>
+<p>Start with the same map (still using <code>.</code> for <em>clean</em> and <code>#</code> for infected) and still with the virus carrier starting in the middle and facing <em>up</em>.</p>
+<p>Using the same initial state as the previous example, and drawing <em>weakened</em> as <code>W</code> and <em>flagged</em> as <code>F</code>, the middle of the infinite grid looks like this, with the virus carrier's position again marked with <code>[ ]</code>:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . . #[.]. . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>This is the same as before, since no initial nodes are <em>weakened</em> or <em>flagged</em>. The virus carrier is on a clean node, so it still turns left, instead <em>weakens</em> the node, and moves left:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . .[#]W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>The virus carrier is on an infected node, so it still turns right, instead <em>flags</em> the node, and moves up:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . .[.]. # . . .
+. . . F W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>This process repeats three more times, ending on the previously-flagged node and facing right:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+. . W[F]W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>Finding a flagged node, it reverses direction and <em>cleans</em> the node:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+. .[W]. W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>The <em>weakened</em> node becomes infected, and it continues in the same direction:</p>
+<pre><code>. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+.[.]# . W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+</code></pre>
+<p>Of the first <code>100</code> bursts, <code>26</code> will result in <em>infection</em>. Unfortunately, another feature of this evolved virus is <em>speed</em>; of the first <code>10000000</code> bursts, <code>2511944</code> will result in <em>infection</em>.</p>
+<p>Given your actual map, after <code>10000000</code> bursts of activity, <em>how many bursts cause a node to become infected</em>? (Do not count nodes that begin infected.)</p>
+</article>
+<p>Your puzzle answer was <code>2512008</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="/2017">return to your advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="22/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+%22Sporifica+Virus%22+%2D+Day+22+%2D+Advent+of+Code+2017&url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F22&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
+ <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F22" target="_blank">Google+</a>
+ <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F22&title=I%27ve+completed+%22Sporifica+Virus%22+%2D+Day+22+%2D+Advent+of+Code+2017" 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
--- /dev/null
+{-# LANGUAGE NegativeLiterals #-}
+{-# LANGUAGE FlexibleContexts #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE TypeFamilies #-}
+{-# LANGUAGE BangPatterns #-}
+
+import Prelude hiding (Left, Right)
+import Data.List
+import qualified Data.Set as S
+
+type Point = (Int, Int)
+type Infection = S.Set Point
+
+data Direction = Up | Right | Down | Left deriving (Show, Eq, Enum)
+
+leftOf Up = Left
+leftOf x = pred x
+
+rightOf Left = Up
+rightOf x = succ x
+
+delta :: Direction -> Point
+delta Up = (-1, 0)
+delta Right = (0, 1)
+delta Down = (1, 0)
+delta Left = (0, -1)
+
+(+:) :: Point -> Point -> Point
+(+:) (r, c) (dr, dc) = (r + dr, c + dc)
+
+data World = World { infected :: Infection
+ , position :: Point
+ , direction :: Direction
+ , infectionCount :: Int
+ } deriving (Eq, Show)
+
+
+main :: IO ()
+main = do
+ text <- readFile "data/advent22.txt"
+ let grid = lines text
+ print $ infectionCount $ progress 10000 $ initialWorld grid
+
+initialWorld :: [String] -> World
+initialWorld grid = World
+ { infected = initialInfected grid
+ , position = initialPosition grid
+ , direction = Up
+ , infectionCount = 0
+ }
+
+initialInfected :: [String] -> Infection
+initialInfected g = S.fromList [(r, c) | r <- [0..(length g - 1)]
+ , c <- [0..((length . head) g - 1)]
+ , g!!r!!c == '#']
+
+initialPosition :: [String] -> Point
+initialPosition g = (length g `div` 2, (length . head) g `div` 2)
+
+
+progress :: Int -> World -> World
+progress n = (!! n) . iterate step
+
+step :: World -> World
+step world = World { infected = inf', position = pos', direction = dir'
+ , infectionCount = ic'}
+ where here = position world
+ infectedHere = here `S.member` infected world
+ dir' = if infectedHere then rightOf (direction world)
+ else leftOf (direction world)
+ inf' = if infectedHere then S.delete here $ infected world
+ else S.insert here $ infected world
+ ic' = if infectedHere then infectionCount world
+ else infectionCount world + 1
+ pos' = here +: delta dir'
\ No newline at end of file
--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "{-# LANGUAGE NegativeLiterals #-}\n",
+ "{-# LANGUAGE FlexibleContexts #-}\n",
+ "{-# LANGUAGE OverloadedStrings #-}\n",
+ "{-# LANGUAGE TypeFamilies #-}\n",
+ "{-# LANGUAGE BangPatterns #-}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import Prelude hiding (Left, Right)\n",
+ "import Data.List\n",
+ "import qualified Data.Set as S"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type Point = (Int, Int)\n",
+ "type Infection = S.Set Point\n",
+ "\n",
+ "data Direction = Up | Right | Down | Left deriving (Show, Eq, Enum)\n",
+ "\n",
+ "data World = World { infected :: Infection\n",
+ " , position :: Point\n",
+ " , direction :: Direction\n",
+ " , infectionCount :: Int\n",
+ " } deriving (Eq, Show)\n",
+ " "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "text <- readFile \"../../data/advent22.txt\"\n",
+ "grid = lines text"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "sampleGrid = lines \"..#\\n#..\\n...\\n\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialInfected g = S.fromList [(r, c) | r <- [0..(length g - 1)], c <- [0..((length . head) g - 1)],\n",
+ " g!!r!!c == '#']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [(0,2),(1,0)]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialInfected sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialPosition g = (length g `div` 2, (length . head) g `div` 2)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(1,1)"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialPosition sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "leftOf Up = Left\n",
+ "leftOf x = pred x\n",
+ "\n",
+ "rightOf Left = Up\n",
+ "rightOf x = succ x"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Down"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "leftOf Left"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "delta :: Direction -> Point\n",
+ "delta Up = (-1, 0)\n",
+ "delta Right = (0, 1)\n",
+ "delta Down = (1, 0)\n",
+ "delta Left = (0, -1)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "(+:) (r, c) (dr, dc) = (r + dr, c + dc)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialWorld grid = World \n",
+ " { infected = initialInfected grid\n",
+ " , position = initialPosition grid\n",
+ " , direction = Up\n",
+ " , infectionCount = 0\n",
+ " }"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "World {infected = fromList [(0,2),(1,0)], position = (1,1), direction = Up, infectionCount = 0}"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "step world = World {infected = inf', position = pos', direction = dir', infectionCount = ic'}\n",
+ " where here = position world\n",
+ " infectedHere = here `S.member` infected world\n",
+ " dir' = if infectedHere then rightOf (direction world)\n",
+ " else leftOf (direction world)\n",
+ " inf' = if infectedHere then S.delete here $ infected world\n",
+ " else S.insert here $ infected world\n",
+ " ic' = if infectedHere then infectionCount world\n",
+ " else infectionCount world + 1\n",
+ " pos' = here +: delta dir'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "World {infected = fromList [(0,2),(1,1)], position = (0,0), direction = Up, infectionCount = 1}"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "step $ step $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "progress n = (!! n) . iterate step "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "5587"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "infectionCount $ progress 10000 $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "5182"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "infectionCount $ progress 10000 $ initialWorld grid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Haskell",
+ "language": "haskell",
+ "name": "haskell"
+ },
+ "language_info": {
+ "codemirror_mode": "ihaskell",
+ "file_extension": ".hs",
+ "name": "haskell",
+ "version": "8.0.2"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
--- /dev/null
+{-# LANGUAGE NegativeLiterals #-}
+{-# LANGUAGE FlexibleContexts #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE TypeFamilies #-}
+{-# LANGUAGE BangPatterns #-}
+
+import Prelude hiding (Left, Right)
+import Data.List
+import qualified Data.Map.Strict as M
+
+type Point = (Int, Int)
+
+data Flag = Clean | Weakened | Infected | Flagged deriving (Show, Eq)
+
+type Infection = M.Map Point Flag
+
+data Direction = Up | Right | Down | Left deriving (Show, Eq, Enum)
+
+leftOf Up = Left
+leftOf x = pred x
+
+rightOf Left = Up
+rightOf x = succ x
+
+delta :: Direction -> Point
+delta Up = (-1, 0)
+delta Right = (0, 1)
+delta Down = (1, 0)
+delta Left = (0, -1)
+
+(+:) :: Point -> Point -> Point
+(+:) (r, c) (dr, dc) = (r + dr, c + dc)
+
+data World = World { infected :: Infection
+ , position :: Point
+ , direction :: Direction
+ , infectionCount :: Int
+ } deriving (Eq, Show)
+
+
+main :: IO ()
+main = do
+ text <- readFile "data/advent22.txt"
+ let grid = lines text
+ print $ infectionCount $ progress 10000000 $ initialWorld grid
+
+initialWorld :: [String] -> World
+initialWorld grid = World
+ { infected = initialInfected grid
+ , position = initialPosition grid
+ , direction = Up
+ , infectionCount = 0
+ }
+
+initialInfected :: [String] -> Infection
+initialInfected g = M.fromList [ ((r, c), Infected)
+ | r <- [0..(length g - 1)]
+ , c <- [0..((length . head) g - 1)]
+ , g!!r!!c == '#']
+
+initialPosition :: [String] -> Point
+initialPosition g = (length g `div` 2, (length . head) g `div` 2)
+
+
+progress :: Int -> World -> World
+progress n = (!! n) . iterate step
+
+
+step :: World -> World
+step world = World { infected = inf', position = pos', direction = dir'
+ , infectionCount = ic'}
+ where !here = position world
+ !stateHere = M.findWithDefault Clean here (infected world)
+ !dir' = case stateHere of
+ Clean -> leftOf (direction world)
+ Weakened -> direction world
+ Infected -> rightOf (direction world)
+ Flagged -> rightOf (rightOf (direction world))
+ !stateHere' = case stateHere of
+ Clean -> Weakened
+ Weakened -> Infected
+ Infected -> Flagged
+ Flagged -> Clean
+ !inf' = M.insert here stateHere' (infected world)
+ !ic' = if stateHere' == Infected then infectionCount world + 1
+ else infectionCount world
+ !pos' = here +: delta dir'
\ No newline at end of file
--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "{-# LANGUAGE NegativeLiterals #-}\n",
+ "{-# LANGUAGE FlexibleContexts #-}\n",
+ "{-# LANGUAGE OverloadedStrings #-}\n",
+ "{-# LANGUAGE TypeFamilies #-}\n",
+ "{-# LANGUAGE BangPatterns #-}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import Prelude hiding (Left, Right)\n",
+ "import Data.List\n",
+ "import qualified Data.Map as M"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type Point = (Int, Int)\n",
+ "\n",
+ "data Flag = Clean | Weakened | Infected | Flagged deriving (Show, Eq)\n",
+ "\n",
+ "type Infection = M.Map Point Flag\n",
+ "\n",
+ "data Direction = Up | Right | Down | Left deriving (Show, Eq, Enum)\n",
+ "\n",
+ "data World = World { infected :: Infection\n",
+ " , position :: Point\n",
+ " , direction :: Direction\n",
+ " , infectionCount :: Int\n",
+ " } deriving (Eq, Show)\n",
+ " "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "text <- readFile \"../../data/advent22.txt\"\n",
+ "grid = lines text"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "sampleGrid = lines \"..#\\n#..\\n...\\n\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialInfected g = M.fromList [((r, c), Infected) | r <- [0..(length g - 1)], c <- [0..((length . head) g - 1)],\n",
+ " g!!r!!c == '#']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "fromList [((0,2),Infected),((1,0),Infected)]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialInfected sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialPosition g = (length g `div` 2, (length . head) g `div` 2)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(1,1)"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialPosition sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "leftOf Up = Left\n",
+ "leftOf x = pred x\n",
+ "\n",
+ "rightOf Left = Up\n",
+ "rightOf x = succ x"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "Down"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "leftOf Left"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "delta :: Direction -> Point\n",
+ "delta Up = (-1, 0)\n",
+ "delta Right = (0, 1)\n",
+ "delta Down = (1, 0)\n",
+ "delta Left = (0, -1)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "(+:) (r, c) (dr, dc) = (r + dr, c + dc)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "initialWorld grid = World \n",
+ " { infected = initialInfected grid\n",
+ " , position = initialPosition grid\n",
+ " , direction = Up\n",
+ " , infectionCount = 0\n",
+ " }"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "World {infected = fromList [((0,2),Infected),((1,0),Infected)], position = (1,1), direction = Up, infectionCount = 0}"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "step world = World {infected = inf', position = pos', direction = dir', infectionCount = ic'}\n",
+ " where here = position world\n",
+ " stateHere = M.findWithDefault Clean here (infected world)\n",
+ " dir' = case stateHere of \n",
+ " Clean -> leftOf (direction world)\n",
+ " Weakened -> direction world\n",
+ " Infected -> rightOf (direction world)\n",
+ " Flagged -> rightOf (rightOf (direction world))\n",
+ " stateHere' = case stateHere of \n",
+ " Clean -> Weakened\n",
+ " Weakened -> Infected\n",
+ " Infected -> Flagged\n",
+ " Flagged -> Clean\n",
+ " inf' = M.insert here stateHere' (infected world)\n",
+ " \n",
+ " ic' = if stateHere' == Infected then infectionCount world + 1\n",
+ " else infectionCount world\n",
+ " pos' = here +: delta dir'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "World {infected = fromList [((0,2),Infected),((1,0),Flagged),((1,1),Weakened)], position = (0,0), direction = Up, infectionCount = 0}"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "step $ step $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "progress n = (!! n) . iterate step "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "World {infected = fromList [((0,-1),Weakened),((0,0),Weakened),((0,2),Infected),((1,-1),Infected),((1,0),Clean),((1,1),Weakened)], position = (1,-2), direction = Left, infectionCount = 1}"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "progress 7 $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "26"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "infectionCount $ progress 100 $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2511944"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "infectionCount $ progress 10000000 $ initialWorld sampleGrid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2512008"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "infectionCount $ progress 10000000 $ initialWorld grid"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Haskell",
+ "language": "haskell",
+ "name": "haskell"
+ },
+ "language_info": {
+ "codemirror_mode": "ihaskell",
+ "file_extension": ".hs",
+ "name": "haskell",
+ "version": "8.0.2"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
--- /dev/null
+{-# LANGUAGE NegativeLiterals #-}
+{-# LANGUAGE FlexibleContexts #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE TypeFamilies #-}
+{-# LANGUAGE BangPatterns #-}
+
+import Prelude hiding (Left, Right)
+import Data.List
+import qualified Data.HashMap.Strict as M
+
+type Point = (Int, Int)
+
+data Flag = Clean | Weakened | Infected | Flagged deriving (Show, Eq)
+
+type Infection = M.HashMap Point Flag
+
+data Direction = Up | Right | Down | Left deriving (Show, Eq, Enum)
+
+leftOf Up = Left
+leftOf x = pred x
+
+rightOf Left = Up
+rightOf x = succ x
+
+delta :: Direction -> Point
+delta Up = (-1, 0)
+delta Right = (0, 1)
+delta Down = (1, 0)
+delta Left = (0, -1)
+
+(+:) :: Point -> Point -> Point
+(+:) (r, c) (dr, dc) = (r + dr, c + dc)
+
+data World = World { infected :: Infection
+ , position :: Point
+ , direction :: Direction
+ , infectionCount :: Int
+ } deriving (Eq, Show)
+
+
+main :: IO ()
+main = do
+ text <- readFile "data/advent22.txt"
+ let grid = lines text
+ print $ infectionCount $ progress 10000000 $ initialWorld grid
+
+initialWorld :: [String] -> World
+initialWorld grid = World
+ { infected = initialInfected grid
+ , position = initialPosition grid
+ , direction = Up
+ , infectionCount = 0
+ }
+
+initialInfected :: [String] -> Infection
+initialInfected g = M.fromList [ ((r, c), Infected)
+ | r <- [0..(length g - 1)]
+ , c <- [0..((length . head) g - 1)]
+ , g!!r!!c == '#']
+
+initialPosition :: [String] -> Point
+initialPosition g = (length g `div` 2, (length . head) g `div` 2)
+
+
+progress :: Int -> World -> World
+-- progress n = (!! n) . iterate step
+progress 0 world = world
+progress n world = progress (n - 1) world'
+ where !world' = step world
+
+
+step :: World -> World
+step world = World { infected = inf', position = pos', direction = dir'
+ , infectionCount = ic'}
+ where !here = position world
+ !stateHere = M.lookupDefault Clean here (infected world)
+ !dir' = case stateHere of
+ Clean -> leftOf (direction world)
+ Weakened -> direction world
+ Infected -> rightOf (direction world)
+ Flagged -> rightOf (rightOf (direction world))
+ !stateHere' = case stateHere of
+ Clean -> Weakened
+ Weakened -> Infected
+ Infected -> Flagged
+ Flagged -> Clean
+ !inf' = M.insert here stateHere' (infected world)
+ !ic' = if stateHere' == Infected then infectionCount world + 1
+ else infectionCount world
+ !pos' = here +: delta dir'
\ No newline at end of file
projects / advent-of-code-17.git / commitdiff