From 663bcffc837d286c63abf8060dce053b18e42275 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sun, 22 Dec 2019 16:16:26 +0000 Subject: [PATCH] Done part 1 --- advent17/advent17grid.txt | 62 +++++++++++++++++++ advent17/package.yaml | 60 +++++++++++++++++++ advent17/src/advent17.hs | 123 ++++++++++++++++++++++++++++++++++++++ data/advent17.txt | 1 + stack.yaml | 1 + 5 files changed, 247 insertions(+) create mode 100644 advent17/advent17grid.txt create mode 100644 advent17/package.yaml create mode 100644 advent17/src/advent17.hs create mode 100644 data/advent17.txt diff --git a/advent17/advent17grid.txt b/advent17/advent17grid.txt new file mode 100644 index 0000000..e5b8ce4 --- /dev/null +++ b/advent17/advent17grid.txt @@ -0,0 +1,62 @@ +........................#############........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...#############.................... +........................#...#.......#...#.................... +........................#...#.......#...#.................... +........................#...#.......#...#.................... +........................#...#.......#######.................. +........................#...#...........#.#.................. +......................#######...........#######.............. +......................#.#.................#...#.............. +................#########.................#...#.............. +................#.....#...................#...#.............. +................#.....#...................#...#.............. +................#.....#...................#...#.............. +................#.....#...................#######............ +................#.....#.......................#.#............ +................#.....#.......................#############.. +................#.....#.........................#.........#.. +................#.....#.........................#.........#.. +................#.....#.........................#.........#.. +..............#########.........................#.........#.. +..............#.#...............................#.........#.. +........#########...............................############^ +........#.....#...........................................#.. +........#.....#...........................................#.. +........#.....#...........................................#.. +........#.....#...........................................#.. +........#.....#...........................................#.. +#########.....#...................................#########.. +#.............#...................................#.......... +#.............#...................................#.......... +#.............#...................................#.......... +#.............#############.......................#.......... +#.........................#.......................#.......... +#############.............#.......................#.......... +............#.............#.......................#.......... +............#.............#.......................#.......... +............#.............#.......................#.......... +............#.............#.......................#.......... +............#.............#.......................#.......... +............#.............#.................#######.......... +............#...............................#................ +............#######.........................#................ +..................#.........................#................ +..................#.........................#................ +..................#.........................#................ +..................#.................#########................ +..................#.................#........................ +..................#.................#........................ +..................#.................#........................ +..................#######...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#...........#........................ +........................#############........................ + diff --git a/advent17/package.yaml b/advent17/package.yaml new file mode 100644 index 0000000..2271e6a --- /dev/null +++ b/advent17/package.yaml @@ -0,0 +1,60 @@ +# This YAML file describes your package. Stack will automatically generate a +# Cabal file when you run `stack build`. See the hpack website for help with +# this file: . + +name: advent17 +synopsis: Advent of Code +version: '0.0.1' + +default-extensions: +- AllowAmbiguousTypes +- ApplicativeDo +- BangPatterns +- BlockArguments +- DataKinds +- DeriveFoldable +- DeriveFunctor +- DeriveGeneric +- DeriveTraversable +- EmptyCase +- FlexibleContexts +- FlexibleInstances +- FunctionalDependencies +- GADTs +- GeneralizedNewtypeDeriving +- ImplicitParams +- KindSignatures +- LambdaCase +- MonadComprehensions +- MonoLocalBinds +- MultiParamTypeClasses +- MultiWayIf +- NegativeLiterals +- NumDecimals +- OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeInType +- TypeOperators +- ViewPatterns + + +executables: + advent17: + main: advent17.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - containers + - intcode diff --git a/advent17/src/advent17.hs b/advent17/src/advent17.hs new file mode 100644 index 0000000..bef9ddf --- /dev/null +++ b/advent17/src/advent17.hs @@ -0,0 +1,123 @@ +import Debug.Trace + +import Intcode + +import qualified Data.Text.IO as TIO + +import qualified Data.Map.Strict as M +import Data.Map.Strict ((!)) +import Data.List +import qualified Data.Set as S +-- import Data.Char +import Data.List + +type Position = (Integer, Integer) -- x, y +type Boundary = [Position] +data Direction = North | East | South | West deriving (Show, Eq, Ord) +data ReturnValue = Static | Moved | Goal deriving (Show, Eq, Ord) + +data Droid = Droid + { _machine :: Machine + , _executionState :: ExecutionState + , _currentInput :: [Integer] + , _machineOutput :: [Integer] + } deriving (Eq) + +instance Show Droid where + show d = "Droid {, _executionState = " ++ show (_executionState d) ++ + ", _currentInput = " ++ show (_currentInput d) ++ + ", _machineOutput = " ++ show (_machineOutput d) ++ + " }" + +type Scaffold = S.Set Position + +data ScaffoldBuilder = ScaffoldBuilder { _scaffold :: Scaffold + , _r :: Integer + , _c :: Integer + , _droidPos :: Position + , _droidDirection :: Direction + } deriving (Show, Eq) + + +main :: IO () +main = do + text <- TIO.readFile "data/advent17.txt" + let mem = parseMachineMemory text + -- print mem + let sb = buildScaffold mem + print $ part1 sb + -- print $ part2 mem + + +part1 sb = S.foldl (+) 0 $ S.map alignmentParam intersections + where scaffold = _scaffold sb + intersections = S.filter (isIntersection scaffold) scaffold + + +buildScaffold mem = foldl' addGridChar emptyScaffoldBuilder output + where (_, _, output) = runProgram [] mem + emptyScaffoldBuilder = ScaffoldBuilder {_scaffold = S.empty, _r = 0, _c = 0, + _droidPos = (0, 0), _droidDirection = North } + + +addGridChar sb 10 = sb { _r = _r sb + 1, _c = 0 } +addGridChar sb 46 = sb { _c = _c sb + 1 } +addGridChar sb 35 = sb { _scaffold = S.insert (_r sb, _c sb) $ _scaffold sb, + _c = _c sb + 1 } +addGridChar sb 94 = sb { _scaffold = S.insert (_r sb, _c sb) $ _scaffold sb, + _c = _c sb + 1, + _droidPos = (_r sb, _c sb), _droidDirection = North } +addGridChar sb 118 = sb { _scaffold = S.insert (_r sb, _c sb) $ _scaffold sb, + _c = _c sb + 1, + _droidPos = (_r sb, _c sb), _droidDirection = South } +addGridChar sb 60 = sb { _scaffold = S.insert (_r sb, _c sb) $ _scaffold sb, + _c = _c sb + 1, + _droidPos = (_r sb, _c sb), _droidDirection = West } +addGridChar sb 61 = sb { _scaffold = S.insert (_r sb, _c sb) $ _scaffold sb, + _c = _c sb + 1, + _droidPos = (_r sb, _c sb), _droidDirection = East } + + +isIntersection :: Scaffold -> Position -> Bool +isIntersection scaffold (r, c) = neighbours `S.isSubsetOf` scaffold + where neighbours = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] + +alignmentParam :: Position -> Integer +alignmentParam (r, c) = r * c + + +-- runDroid :: Droid -> Direction -> (Droid, ReturnValue) +-- runDroid droid direction = (droid', found) +-- where ci = _currentInput droid +-- droid' = runDroidMachine (droid {_currentInput = ci ++ [commandOf direction]}) +-- found = returnValue $ last $ _machineOutput droid' + + +-- runDroidMachine :: Droid -> Droid +-- runDroidMachine d = d { _machine = machine' +-- , _executionState = halted +-- , _machineOutput = output +-- } +-- where machine = _machine d +-- input = _currentInput d +-- (halted, machine', output) = runMachine input machine + + +showHull :: Hull -> String +showHull screen = unlines rows + where minX = minimum $ map fst $ M.keys screen + minY = minimum $ map snd $ M.keys screen + maxX = maximum $ map fst $ M.keys screen + maxY = maximum $ map snd $ M.keys screen + rows = [showHullRow screen minX maxX y | y <- [minY..maxY]] + +showHullRow :: Hull -> Integer -> Integer -> Integer -> String +showHullRow screen minX maxX y = [showHullCell screen x y | x <- [minX..maxX]] + +showHullCell :: Hull -> Integer -> Integer -> Char +showHullCell screen x y = + case (M.findWithDefault Unknown (x, y) screen) of + Empty _ _ True -> 'O' + Empty _ _ _ -> '.' + Wall -> '\x2588' + Unknown -> ' ' diff --git a/data/advent17.txt b/data/advent17.txt new file mode 100644 index 0000000..cbc603f --- /dev/null +++ b/data/advent17.txt @@ -0,0 +1 @@ +1,330,331,332,109,5242,1101,1182,0,16,1102,1521,1,24,102,1,0,570,1006,570,36,102,1,571,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,16,1,16,1008,16,1521,570,1006,570,14,21101,0,58,0,1105,1,786,1006,332,62,99,21102,333,1,1,21101,73,0,0,1106,0,579,1101,0,0,572,1102,0,1,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,101,0,574,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1105,1,81,21102,340,1,1,1106,0,177,21101,0,477,1,1106,0,177,21102,1,514,1,21102,176,1,0,1105,1,579,99,21102,184,1,0,1106,0,579,4,574,104,10,99,1007,573,22,570,1006,570,165,102,1,572,1182,21101,375,0,1,21101,0,211,0,1105,1,579,21101,1182,11,1,21102,222,1,0,1106,0,979,21102,1,388,1,21102,1,233,0,1106,0,579,21101,1182,22,1,21101,244,0,0,1106,0,979,21101,0,401,1,21102,255,1,0,1105,1,579,21101,1182,33,1,21101,0,266,0,1106,0,979,21102,1,414,1,21102,277,1,0,1106,0,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21101,1182,0,1,21101,313,0,0,1105,1,622,1005,575,327,1101,1,0,575,21102,327,1,0,1106,0,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,60,24,0,109,4,2101,0,-3,586,21002,0,1,-1,22101,1,-3,-3,21102,1,0,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1105,1,597,109,-4,2105,1,0,109,5,2101,0,-4,629,21002,0,1,-2,22101,1,-4,-4,21102,1,0,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,653,20101,0,0,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21102,1,702,0,1106,0,786,21201,-1,-1,-1,1106,0,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21101,731,0,0,1106,0,786,1105,1,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,756,0,0,1105,1,786,1106,0,774,21202,-1,-11,1,22101,1182,1,1,21102,774,1,0,1106,0,622,21201,-3,1,-3,1106,0,640,109,-5,2105,1,0,109,7,1005,575,802,20101,0,576,-6,21002,577,1,-5,1105,1,814,21101,0,0,-1,21101,0,0,-5,21102,0,1,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,61,-3,22201,-6,-3,-3,22101,1521,-3,-3,2101,0,-3,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21102,1,1,-1,1106,0,924,1205,-2,873,21102,35,1,-4,1106,0,924,2102,1,-3,878,1008,0,1,570,1006,570,916,1001,374,1,374,2101,0,-3,895,1101,2,0,0,2101,0,-3,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,922,20101,0,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,61,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,61,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1101,0,1,575,21102,1,973,0,1106,0,786,99,109,-7,2105,1,0,109,6,21101,0,0,-4,21102,0,1,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1106,0,1041,21101,-4,0,-2,1106,0,1041,21101,-5,0,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,2101,0,-2,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,1201,-2,0,0,1105,1,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1106,0,989,21101,439,0,1,1105,1,1150,21102,1,477,1,1106,0,1150,21102,1,514,1,21101,1149,0,0,1106,0,579,99,21101,1157,0,0,1105,1,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,2101,0,-5,1176,1202,-4,1,0,109,-6,2105,1,0,24,13,48,1,11,1,48,1,11,1,48,1,11,1,48,1,3,13,44,1,3,1,7,1,3,1,44,1,3,1,7,1,3,1,44,1,3,1,7,1,3,1,44,1,3,1,7,7,42,1,3,1,11,1,1,1,40,7,11,7,36,1,1,1,17,1,3,1,30,9,17,1,3,1,30,1,5,1,19,1,3,1,30,1,5,1,19,1,3,1,30,1,5,1,19,1,3,1,30,1,5,1,19,7,28,1,5,1,23,1,1,1,28,1,5,1,23,13,18,1,5,1,25,1,9,1,18,1,5,1,25,1,9,1,18,1,5,1,25,1,9,1,16,9,25,1,9,1,16,1,1,1,31,1,9,1,10,9,31,13,8,1,5,1,43,1,10,1,5,1,43,1,10,1,5,1,43,1,10,1,5,1,43,1,10,1,5,1,43,1,2,9,5,1,35,9,2,1,13,1,35,1,10,1,13,1,35,1,10,1,13,1,35,1,10,1,13,13,23,1,10,1,25,1,23,1,10,13,13,1,23,1,22,1,13,1,23,1,22,1,13,1,23,1,22,1,13,1,23,1,22,1,13,1,23,1,22,1,13,1,23,1,22,1,13,1,17,7,22,1,31,1,28,7,25,1,34,1,25,1,34,1,25,1,34,1,25,1,34,1,17,9,34,1,17,1,42,1,17,1,42,1,17,1,42,7,11,1,48,1,11,1,48,1,11,1,48,1,11,1,48,1,11,1,48,1,11,1,48,1,11,1,48,1,11,1,48,13,24 diff --git a/stack.yaml b/stack.yaml index e9556a5..de5b5af 100644 --- a/stack.yaml +++ b/stack.yaml @@ -54,6 +54,7 @@ packages: - advent14 - advent15 - advent16 +- advent17 # Dependency packages to be pulled from upstream that are not in the resolver. -- 2.34.1