From ebb8c78c3e4bf2d4f95b93bd065384680e40600a Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 13 Dec 2017 09:49:13 +0000 Subject: [PATCH] Day 13 --- advent-of-code.cabal | 8 + data/advent13.txt | 43 ++++ problems/day13.html | 393 ++++++++++++++++++++++++++++++++++++ src/advent13/advent13.hs | 66 ++++++ src/advent13/advent13.ipynb | 377 ++++++++++++++++++++++++++++++++++ 5 files changed, 887 insertions(+) create mode 100644 data/advent13.txt create mode 100644 problems/day13.html create mode 100644 src/advent13/advent13.hs create mode 100644 src/advent13/advent13.ipynb diff --git a/advent-of-code.cabal b/advent-of-code.cabal index 6e57c34..0461d0b 100644 --- a/advent-of-code.cabal +++ b/advent-of-code.cabal @@ -118,3 +118,11 @@ executable advent12 , text , megaparsec +executable advent13 + hs-source-dirs: src/advent13 + main-is: advent13.hs + default-language: Haskell2010 + build-depends: base >= 4.7 && < 5 + , text + , megaparsec + diff --git a/data/advent13.txt b/data/advent13.txt new file mode 100644 index 0000000..0d2d8dd --- /dev/null +++ b/data/advent13.txt @@ -0,0 +1,43 @@ +0: 4 +1: 2 +2: 3 +4: 5 +6: 8 +8: 4 +10: 6 +12: 6 +14: 6 +16: 10 +18: 6 +20: 12 +22: 8 +24: 9 +26: 8 +28: 8 +30: 8 +32: 12 +34: 12 +36: 12 +38: 8 +40: 10 +42: 14 +44: 12 +46: 14 +48: 12 +50: 12 +52: 12 +54: 14 +56: 14 +58: 14 +60: 12 +62: 14 +64: 14 +68: 12 +70: 14 +74: 14 +76: 14 +78: 14 +80: 17 +82: 28 +84: 18 +86: 14 \ No newline at end of file diff --git a/problems/day13.html b/problems/day13.html new file mode 100644 index 0000000..a6ff13b --- /dev/null +++ b/problems/day13.html @@ -0,0 +1,393 @@ + + + + +Day 13 - Advent of Code 2017 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 26*

       Î»y.2017

+ + + +
+

--- Day 13: Packet Scanners ---

You need to cross a vast firewall. The firewall consists of several layers, each with a security scanner that moves back and forth across the layer. To succeed, you must not be detected by a scanner.

+

By studying the firewall briefly, you are able to record (in your puzzle input) the depth of each layer and the range of the scanning area for the scanner within it, written as depth: range. Each layer has a thickness of exactly 1. A layer at depth 0 begins immediately inside the firewall; a layer at depth 1 would start immediately after that.

+

For example, suppose you've recorded the following:

+
0: 3
+1: 2
+4: 4
+6: 4
+
+

This means that there is a layer immediately inside the firewall (with range 3), a second layer immediately after that (with range 2), a third layer which begins at depth 4 (with range 4), and a fourth layer which begins at depth 6 (also with range 4). Visually, it might look like this:

+
 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+

Within each layer, a security scanner moves back and forth within its range. Each security scanner starts at the top and moves down until it reaches the bottom, then moves up until it reaches the top, and repeats. A security scanner takes one picosecond to move one step. Drawing scanners as S, the first few picoseconds look like this:

+

+Picosecond 0:
+ 0   1   2   3   4   5   6
+[S] [S] ... ... [S] ... [S]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+Picosecond 1:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+Picosecond 2:
+ 0   1   2   3   4   5   6
+[ ] [S] ... ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+Picosecond 3:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] ... [ ]
+[S] [S]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [S]     [S]
+
+

Your plan is to hitch a ride on a packet about to move through the firewall. The packet will travel along the top of each layer, and it moves at one layer per picosecond. Each picosecond, the packet moves one layer forward (its first move takes it into layer 0), and then the scanners move one step. If there is a scanner at the top of the layer as your packet enters it, you are caught. (If a scanner moves into the top of its layer while you are there, you are not caught: it doesn't have time to notice you before you leave.) If you were to do this in the configuration above, marking your current position with parentheses, your passage through the firewall would look like this:

+
Initial state:
+ 0   1   2   3   4   5   6
+[S] [S] ... ... [S] ... [S]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+Picosecond 0:
+ 0   1   2   3   4   5   6
+(S) [S] ... ... [S] ... [S]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+( ) [ ] ... ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 1:
+ 0   1   2   3   4   5   6
+[ ] ( ) ... ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] (S) ... ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+
+Picosecond 2:
+ 0   1   2   3   4   5   6
+[ ] [S] (.) ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] (.) ... [ ] ... [ ]
+[S] [S]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [S]     [S]
+
+
+Picosecond 3:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... (.) [ ] ... [ ]
+[S] [S]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [S]     [S]
+
+ 0   1   2   3   4   5   6
+[S] [S] ... (.) [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[ ]             [S]     [S]
+                [ ]     [ ]
+
+
+Picosecond 4:
+ 0   1   2   3   4   5   6
+[S] [S] ... ... ( ) ... [ ]
+[ ] [ ]         [ ]     [ ]
+[ ]             [S]     [S]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... ( ) ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 5:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] (.) [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [S] ... ... [S] (.) [S]
+[ ] [ ]         [ ]     [ ]
+[S]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 6:
+ 0   1   2   3   4   5   6
+[ ] [S] ... ... [S] ... (S)
+[ ] [ ]         [ ]     [ ]
+[S]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] ... ( )
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+

In this situation, you are caught in layers 0 and 6, because your packet entered the layer when its scanner was at the top when you entered it. You are not caught in layer 1, since the scanner moved into the top of the layer once you were already there.

+

The severity of getting caught on a layer is equal to its depth multiplied by its range. (Ignore layers in which you do not get caught.) The severity of the whole trip is the sum of these values. In the example above, the trip severity is 0*3 + 6*4 = 24.

+

Given the details of the firewall you've recorded, if you leave immediately, what is the severity of your whole trip?

+
+

Your puzzle answer was 1904.

--- Part Two ---

Now, you need to pass through the firewall without being caught - easier said than done.

+

You can't control the speed of the packet, but you can delay it any number of picoseconds. For each picosecond you delay the packet before beginning your trip, all security scanners move one step. You're not in the firewall during this time; you don't enter layer 0 until you stop delaying the packet.

+

In the example above, if you delay 10 picoseconds (picoseconds 0 - 9), you won't get caught:

+
State after delaying:
+ 0   1   2   3   4   5   6
+[ ] [S] ... ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+Picosecond 10:
+ 0   1   2   3   4   5   6
+( ) [S] ... ... [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+( ) [ ] ... ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 11:
+ 0   1   2   3   4   5   6
+[ ] ( ) ... ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[S] (S) ... ... [S] ... [S]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 12:
+ 0   1   2   3   4   5   6
+[S] [S] (.) ... [S] ... [S]
+[ ] [ ]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] (.) ... [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+
+Picosecond 13:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... (.) [ ] ... [ ]
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [S] ... (.) [ ] ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+
+Picosecond 14:
+ 0   1   2   3   4   5   6
+[ ] [S] ... ... ( ) ... [ ]
+[ ] [ ]         [ ]     [ ]
+[S]             [S]     [S]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... ( ) ... [ ]
+[S] [S]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [S]     [S]
+
+
+Picosecond 15:
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] (.) [ ]
+[S] [S]         [ ]     [ ]
+[ ]             [ ]     [ ]
+                [S]     [S]
+
+ 0   1   2   3   4   5   6
+[S] [S] ... ... [ ] (.) [ ]
+[ ] [ ]         [ ]     [ ]
+[ ]             [S]     [S]
+                [ ]     [ ]
+
+
+Picosecond 16:
+ 0   1   2   3   4   5   6
+[S] [S] ... ... [ ] ... ( )
+[ ] [ ]         [ ]     [ ]
+[ ]             [S]     [S]
+                [ ]     [ ]
+
+ 0   1   2   3   4   5   6
+[ ] [ ] ... ... [ ] ... ( )
+[S] [S]         [S]     [S]
+[ ]             [ ]     [ ]
+                [ ]     [ ]
+
+

Because all smaller delays would get you caught, the fewest number of picoseconds you would need to delay to get through safely is 10.

+

What is the fewest number of picoseconds that you need to delay the packet to pass through the firewall without being caught?

+
+

Your puzzle answer was 3833504.

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/advent13/advent13.hs b/src/advent13/advent13.hs new file mode 100644 index 0000000..46f1d7a --- /dev/null +++ b/src/advent13/advent13.hs @@ -0,0 +1,66 @@ +{-# LANGUAGE NegativeLiterals #-} +{-# LANGUAGE FlexibleContexts #-} +{-# LANGUAGE OverloadedStrings #-} + +import Data.Text (Text) +import qualified Data.Text as T +import qualified Data.Text.IO as TIO + +import Text.Megaparsec +import qualified Text.Megaparsec.Lexer as L +import Text.Megaparsec.Text (Parser) + +import qualified Control.Applicative as CA + +type ScannerDef = (Integer, Integer) +type Scanner = Integer -> Integer + + +main :: IO () +main = do + text <- TIO.readFile "data/advent13.txt" + let scannerDefs = successfulParse text + print $ part1 scannerDefs + print $ part2 scannerDefs + + +part1 :: [ScannerDef] -> Integer +part1 = sum . map (uncurry (*)) . filter (\(d, r) -> scanner d r 0 == 0) + + +part2 :: [ScannerDef] -> Integer +part2 scannerDefs = head $ filter (canPass scanners) [0..] + where scanners = scanify scannerDefs + + +scanify :: [ScannerDef] -> [Scanner] +scanify = map (uncurry scanner) + +canPass :: [Scanner] -> Integer -> Bool +canPass scannersF t = all (\s -> s t /= 0) scannersF + + +scanner :: Integer -> Integer -> Integer -> Integer +scanner depth range t = + let t' = (t + depth) `mod` ((range - 1) * 2) + in if t' < range + then t' + else range - t' - 1 -- t' + (t' - range + 1) * -2 + + +sc :: Parser () +sc = L.space (skipSome spaceChar) CA.empty CA.empty + +lexeme = L.lexeme sc +integer = lexeme L.integer +symb = L.symbol sc + +scannersP = many scannerP + +scannerP = (,) <$> integer <*> (symb ":" *> integer) + +successfulParse :: Text -> [ScannerDef] +successfulParse input = + case parse scannersP "input" input of + Left err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right scanners -> scanners \ No newline at end of file diff --git a/src/advent13/advent13.ipynb b/src/advent13/advent13.ipynb new file mode 100644 index 0000000..cd129f3 --- /dev/null +++ b/src/advent13/advent13.ipynb @@ -0,0 +1,377 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "{-# LANGUAGE NegativeLiterals #-}\n", + "{-# LANGUAGE FlexibleContexts #-}\n", + "{-# LANGUAGE OverloadedStrings #-}" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": {}, + "outputs": [], + "source": [ + "import Data.Text (Text)\n", + "import qualified Data.Text as T\n", + "import qualified Data.Text.IO as TIO\n", + "\n", + "import Text.Megaparsec\n", + "import qualified Text.Megaparsec.Lexer as L\n", + "import Text.Megaparsec.Text (Parser)\n", + "\n", + "import qualified Data.Map.Strict as M\n", + "import Data.Map.Strict ((!))\n", + "\n", + "import qualified Data.Set as S\n", + "import qualified Control.Applicative as CA" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": {}, + "outputs": [], + "source": [ + "scanner :: Integer -> Integer -> Integer -> Integer\n", + "scanner depth range t = \n", + " let t' = (t + depth) `mod` ((range - 1) * 2)\n", + " in if t' < range\n", + " then t' \n", + " else t' + (t' - range + 1) * -2" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [], + "source": [ + "sc :: Parser ()\n", + "sc = L.space (skipSome spaceChar) CA.empty CA.empty\n", + "\n", + "lexeme = L.lexeme sc\n", + "integer = lexeme L.integer\n", + "symb = L.symbol sc\n", + "\n", + "scannersP = many scannerP\n", + "\n", + "scannerP = (,) <$> integer <*> (symb \":\" *> integer)\n", + "\n", + "successfulParse :: Text -> [(Integer, Integer)]\n", + "successfulParse input = \n", + " case parse scannersP \"input\" input of\n", + " Left err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err\n", + " Right scanners -> scanners" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "[0,1,2,3,4, 3, 2, 1,0,1,2,3] res = t' + x\n", + "[0,1,2,3,4, 5, 6, 7,0,1,2,3] t'\n", + "[ 0, 1, 2 t' - len\n", + " -2,-4,-6 x\n", + "\n", + "cycle is 5 + (5-2) = 8\n", + "\n", + "if t' <= 5 then t' else 5 - t' + 1\n", + "\n", + "\n", + "0 1 2 3 4 5 6 7 8 \n", + "S . . . . . . .\n", + ". S . . . . . .\n", + ". . S . . . . .\n", + ". . . S . . . .\n", + ". . . . S . . .\n", + ". . . . . S . .\n", + ". . . . . . S .\n", + ". . . . . . . S\n", + "\n" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0,1,2,3,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,4]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "s50 = scanner 0 5\n", + "map s50 [0..20]" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0,1,2,1,0,1,2,1,0,1,2,1,0,1,2,1,0,1,2,1,0]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "s30 = scanner 0 3\n", + "map s30 [0..20]" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[3,2,1,0,1,2,3,2,1,0,1,2,3,2,1,0,1,2,3,2,1]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "map (scanner 3 4) [0..20]" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0,1,2,0]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "[scanner 0 3 0, scanner 1 2 0, scanner 4 4 0, scanner 6 4 0]" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "metadata": {}, + "outputs": [], + "source": [ + "sample = [(0, 3), (1, 2), (4, 4), (6, 4)]" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "24" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "sum $ map (uncurry (*)) $ filter (\\(d, r) -> scanner d r 0 == 0) sample " + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "metadata": {}, + "outputs": [], + "source": [ + "part1 :: [(Integer, Integer)] -> Integer\n", + "part1 = sum . map (uncurry (*)) . filter (\\(d, r) -> scanner d r 0 == 0)" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "metadata": {}, + "outputs": [], + "source": [ + "main :: IO ()\n", + "main = do \n", + " text <- TIO.readFile \"../../data/advent13.txt\"\n", + " let instrs = successfulParse text\n", + " print $ part1 instrs" + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1904" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "main" + ] + }, + { + "cell_type": "code", + "execution_count": 68, + "metadata": {}, + "outputs": [], + "source": [ + "scanify = map (uncurry scanner)" + ] + }, + { + "cell_type": "code", + "execution_count": 76, + "metadata": {}, + "outputs": [], + "source": [ + "canPass scannersF t = all (\\s -> s t /= 0) scannersF" + ] + }, + { + "cell_type": "code", + "execution_count": 77, + "metadata": {}, + "outputs": [], + "source": [ + "scs = scanify sample" + ] + }, + { + "cell_type": "code", + "execution_count": 82, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "10" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "head $ filter (canPass scs) [0..]" + ] + }, + { + "cell_type": "code", + "execution_count": 81, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[2,1,2,2]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "map (\\s -> s 10) scs" + ] + }, + { + "cell_type": "code", + "execution_count": 83, + "metadata": {}, + "outputs": [], + "source": [ + "part2 scannerDefs = head $ filter (canPass scanners) [0..]\n", + " where scanners = scanify scannerDefs" + ] + }, + { + "cell_type": "code", + "execution_count": 84, + "metadata": {}, + "outputs": [], + "source": [ + "main :: IO ()\n", + "main = do \n", + " text <- TIO.readFile \"../../data/advent13.txt\"\n", + " let instrs = successfulParse text\n", + " print $ part1 instrs\n", + " print $ part2 instrs" + ] + }, + { + "cell_type": "code", + "execution_count": 85, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1904\n", + "3833504" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "main" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "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 +} -- 2.34.1