X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=advent03%2Fsrc%2Fadvent03.hs;h=a863ffef9ca2a09ac081a321c6bbc8f1f2c539a1;hb=52bfc1a213695ffc0a5107a0b1b7e094b5841423;hp=a541f23b926d4c26edb315041ebf226db60c7473;hpb=9ae9e4b2751996170400ddea8503a3b0313e724c;p=advent-of-code-19.git

diff --git a/advent03/src/advent03.hs b/advent03/src/advent03.hs
index a541f23..a863ffe 100644
--- a/advent03/src/advent03.hs
+++ b/advent03/src/advent03.hs
@@ -1,6 +1,3 @@
--- Some code taken from [AoC 2017 day 5](https://adventofcode.com/2017/day/5), 
---    and some from [AoC 2018 day 21](https://adventofcode.com/2018/day/21)
-
 import Data.Text (Text)
 import qualified Data.Text.IO as TIO
 
@@ -11,8 +8,9 @@ import Text.Megaparsec.Char
 import qualified Text.Megaparsec.Char.Lexer as L
 import qualified Control.Applicative as CA
 
-import Data.List (foldl')
-import qualified Data.Set as S
+import Data.List (foldl', foldl1')
+import qualified Data.Map as M
+import Data.Map ((!))
 
 import Linear (V2(..), (^+^), (^-^), (*^), (*^))
 
@@ -20,10 +18,11 @@ data Direction = East | South | West | North deriving (Show, Eq)
 
 type Location = V2 Int -- x, y
 
-type Visited = S.Set Location
+type Visited = M.Map Location Int
 
 data Path = Path { _visited :: Visited
                  , _tip :: Location
+                 , _currentLength :: Int
                  } 
                deriving (Show, Eq)
 
@@ -36,38 +35,49 @@ main :: IO ()
 main = do 
         text <- TIO.readFile "data/advent03.txt"
         let segmentss = successfulParse text
-        print segmentss
+        let paths = travelAllPaths segmentss
         -- print $ travelPath $ head segmentss
-        print $ part1 segmentss
-        -- print $ part2 machine
+        print $ part1 paths
+        print $ part2 paths
+
+part1 :: [Path] -> Int
+part1 paths = closest $ crossovers paths
+
+part2 :: [Path] -> Int
+part2 paths = shortestPaths $ crossovers paths
 
-part1 :: [[Segment]] -> Int
-part1 segmentss = closest $ crossovers $ travelAllPaths segmentss
 
 closest :: Visited -> Int
-closest points = S.findMin $ S.map manhattan points
+closest points = snd $ M.findMin $ M.mapWithKey (\k _ -> manhattan k) points
+
+shortestPaths :: Visited -> Int
+shortestPaths crossings = minimum $ M.elems  crossings
+
 
 crossovers :: [Path] -> Visited
 crossovers travelledPaths = 
-      foldl' S.intersection
-             (_visited $ head travelledPaths)
-             (map _visited $ drop 1 travelledPaths)
+      foldl1' (M.intersectionWith (+)) $ map _visited travelledPaths
 
 travelAllPaths :: [[Segment]] -> [Path]
 travelAllPaths = map travelPath
 
 travelPath :: [Segment] -> Path
 travelPath segments = foldl' travelSegment path0 segments
-    where   path0 = Path { _visited = S.empty, _tip = V2 0 0 }
+    where   path0 = Path { _visited = M.empty, _tip = V2 0 0, _currentLength = 0 }
 
 travelSegment :: Path -> Segment -> Path
-travelSegment path segment = path { _tip = tip', _visited = visited' }
+travelSegment path segment = path { _tip = tip', _visited = visited', _currentLength = len'}
     where   delta = facing $ _direction segment
             distance = _steps segment
             start = _tip path
+            len = _currentLength path
+            len' = len + distance
             visited = _visited path
-            visited' = foldl' (flip S.insert) visited $ take distance $ drop 1 $ iterate (^+^ delta) start
+            visited' = foldl' insertStep visited $ take distance $ drop 1 $ zip [len, (len + 1) ..] $ iterate (^+^ delta) start
             tip' = start ^+^ distance *^ delta
+            insertStep visits (dist, loc) = if loc `M.member` visits
+                                            then visits
+                                            else M.insert loc dist visits
 
 facing :: Direction -> Location
 facing East = V2 1 0