From ae3315403a3d303f4f1ea73147fc16f3568781f3 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 22 Dec 2017 13:30:46 +0000 Subject: [PATCH] Day 22 --- advent-of-code.cabal | 21 ++ data/advent22.txt | 25 +++ problems/day22.html | 286 +++++++++++++++++++++++++++ src/advent22/advent22a.hs | 75 +++++++ src/advent22/advent22a.ipynb | 320 ++++++++++++++++++++++++++++++ src/advent22/advent22b.hs | 87 ++++++++ src/advent22/advent22b.ipynb | 373 +++++++++++++++++++++++++++++++++++ src/advent22/advent22bh.hs | 90 +++++++++ 8 files changed, 1277 insertions(+) create mode 100644 data/advent22.txt create mode 100644 problems/day22.html create mode 100644 src/advent22/advent22a.hs create mode 100644 src/advent22/advent22a.ipynb create mode 100644 src/advent22/advent22b.hs create mode 100644 src/advent22/advent22b.ipynb create mode 100644 src/advent22/advent22bh.hs diff --git a/advent-of-code.cabal b/advent-of-code.cabal index f2d723c..39e555b 100644 --- a/advent-of-code.cabal +++ b/advent-of-code.cabal @@ -238,3 +238,24 @@ executable advent21parallel , 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 diff --git a/data/advent22.txt b/data/advent22.txt new file mode 100644 index 0000000..1252674 --- /dev/null +++ b/data/advent22.txt @@ -0,0 +1,25 @@ +##########..#.###...##..# +##....#...#....#..####.#. +#..#.##..#..##.###..#.### +.#.#.......####.....#.#.. +...######....#.########## +##.#.....#.#####.#....### +#.####.#..#.#.#...#.#..## +#.##..#####..###..###.##. +#.####.#.##.##...#.#.#.## +#.#.#......##.##..###.#.# +#...#.#..#.##....#.##..## +.#.....##.##..#.####..##. +.#......#.#.########..### +##....###.#.#.###...##..# +..##.###....#.....#...#.# +....##...##...##.##.#..## +..#.#.#..#######..###..## +......#####.#####..#.#..# +.####.#......#..###..#.## +#....####.#..#.##.###.##. +####.#...##....###...#.#. +#####.#......#.#..###.##. +#.##.#..#..#..#.....#.#.# +#...#.#.##.#.####.#.#..#. +.##.##..#..###.##.....### \ No newline at end of file diff --git a/problems/day22.html b/problems/day22.html new file mode 100644 index 0000000..a5e2c0f --- /dev/null +++ b/problems/day22.html @@ -0,0 +1,286 @@ + + + + +Day 22 - Advent of Code 2017 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 44*

   0xffff&2017

+ + + +
+

--- Day 22: Sporifica Virus ---

Diagnostics indicate that the local grid computing cluster has been contaminated with the Sporifica Virus. The grid computing cluster is a seemingly-infinite two-dimensional grid of compute nodes. Each node is either clean or infected by the virus.

+

To prevent overloading the nodes (which would render them useless to the virus) or detection by system administrators, exactly one virus carrier 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 current node) and keeps track of the direction it is facing.

+

To avoid detection, the virus carrier works in bursts; in each burst, it wakes up, does some work, and goes back to sleep. The following steps are all executed in order one time each burst:

+
    +
  • If the current node is infected, it turns to its right. Otherwise, it turns to its left. (Turning is done in-place; the current node does not change.)
  • +
  • If the current node is clean, it becomes infected. Otherwise, it becomes cleaned. (This is done after the node is considered for the purposes of changing direction.)
  • +
  • The virus carrier moves forward one node in the direction it is facing.
  • +
+

Diagnostics have also provided a map of the node infection status (your puzzle input). Clean nodes are shown as .; infected nodes are shown as #. This map only shows the center of the grid; there are many more nodes beyond those shown, but none of them are currently infected.

+

The virus carrier begins in the middle of the map facing up.

+

For example, suppose you are given a map like this:

+
..#
+#..
+...
+
+

Then, the middle of the infinite grid looks like this, with the virus carrier's position marked with [ ]:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . . #[.]. . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

The virus carrier is on a clean node, so it turns left, infects the node, and moves left:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . .[#]# . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

The virus carrier is on an infected node, so it turns right, cleans the node, and moves up:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . .[.]. # . . .
+. . . . # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

Four times in a row, the virus carrier finds a clean, infects it, turns left, and moves forward, ending in the same place and still facing up:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . #[#]. # . . .
+. . # # # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

Now on the same node as before, it sees an infection, which causes it to turn right, clean the node, and move forward:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . # .[.]# . . .
+. . # # # . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

After the above actions, a total of 7 bursts of activity had taken place. Of them, 5 bursts of activity caused an infection.

+

After a total of 70, the grid looks like this, with the virus carrier facing up:

+
. . . . . # # . .
+. . . . # . . # .
+. . . # . . . . #
+. . # . #[.]. . #
+. . # . # . . # .
+. . . . . # # . .
+. . . . . . . . .
+. . . . . . . . .
+
+

By this time, 41 bursts of activity caused an infection (though most of those nodes have since been cleaned).

+

After a total of 10000 bursts of activity, 5587 bursts will have caused an infection.

+

Given your actual map, after 10000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.)

+
+

Your puzzle answer was 5182.

--- Part Two ---

As you go to remove the virus from the infected nodes, it evolves to resist your attempt.

+

Now, before it infects a clean node, it will weaken it to disable your defenses. If it encounters an infected node, it will instead flag the node to be cleaned in the future. So:

+
    +
  • Clean nodes become weakened.
  • +
  • Weakened nodes become infected.
  • +
  • Infected nodes become flagged.
  • +
  • Flagged nodes become clean.
  • +
+

Every node is always in exactly one of the above states.

+

The virus carrier still functions in a similar way, but now uses the following logic during its bursts of action:

+
    +
  • Decide which way to turn based on the current node: +
      +
    • If it is clean, it turns left.
    • +
    • If it is weakened, it does not turn, and will continue moving in the same direction.
    • +
    • If it is infected, it turns right.
    • +
    • If it is flagged, it reverses direction, and will go back the way it came.
    • +
    +
  • +
  • Modify the state of the current node, as described above.
  • +
  • The virus carrier moves forward one node in the direction it is facing.
  • +
+

Start with the same map (still using . for clean and # for infected) and still with the virus carrier starting in the middle and facing up.

+

Using the same initial state as the previous example, and drawing weakened as W and flagged as F, the middle of the infinite grid looks like this, with the virus carrier's position again marked with [ ]:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . . #[.]. . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

This is the same as before, since no initial nodes are weakened or flagged. The virus carrier is on a clean node, so it still turns left, instead weakens the node, and moves left:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . # . . .
+. . .[#]W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

The virus carrier is on an infected node, so it still turns right, instead flags the node, and moves up:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . .[.]. # . . .
+. . . F W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

This process repeats three more times, ending on the previously-flagged node and facing right:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+. . W[F]W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

Finding a flagged node, it reverses direction and cleans the node:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+. .[W]. W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

The weakened node becomes infected, and it continues in the same direction:

+
. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . W W . # . . .
+.[.]# . W . . . .
+. . . . . . . . .
+. . . . . . . . .
+. . . . . . . . .
+
+

Of the first 100 bursts, 26 will result in infection. Unfortunately, another feature of this evolved virus is speed; of the first 10000000 bursts, 2511944 will result in infection.

+

Given your actual map, after 10000000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.)

+
+

Your puzzle answer was 2512008.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/src/advent22/advent22a.hs b/src/advent22/advent22a.hs new file mode 100644 index 0000000..1e25cfb --- /dev/null +++ b/src/advent22/advent22a.hs @@ -0,0 +1,75 @@ +{-# 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 diff --git a/src/advent22/advent22a.ipynb b/src/advent22/advent22a.ipynb new file mode 100644 index 0000000..83f6876 --- /dev/null +++ b/src/advent22/advent22a.ipynb @@ -0,0 +1,320 @@ +{ + "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 +} diff --git a/src/advent22/advent22b.hs b/src/advent22/advent22b.hs new file mode 100644 index 0000000..6529e5a --- /dev/null +++ b/src/advent22/advent22b.hs @@ -0,0 +1,87 @@ +{-# 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 diff --git a/src/advent22/advent22b.ipynb b/src/advent22/advent22b.ipynb new file mode 100644 index 0000000..d752b20 --- /dev/null +++ b/src/advent22/advent22b.ipynb @@ -0,0 +1,373 @@ +{ + "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 +} diff --git a/src/advent22/advent22bh.hs b/src/advent22/advent22bh.hs new file mode 100644 index 0000000..e52ee55 --- /dev/null +++ b/src/advent22/advent22bh.hs @@ -0,0 +1,90 @@ +{-# 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 -- 2.34.1