Tidying
[advent-of-code-19.git] / advent03 / src / advent03part1.hs
1 import Data.Text (Text)
2 import qualified Data.Text.IO as TIO
3
4 import Data.Void (Void)
5
6 import Text.Megaparsec hiding (State)
7 import Text.Megaparsec.Char
8 import qualified Text.Megaparsec.Char.Lexer as L
9 import qualified Control.Applicative as CA
10
11 import Data.List (foldl', foldl1')
12 import qualified Data.Set as S
13
14 import Linear (V2(..), (^+^), (^-^), (*^), (*^))
15
16 data Direction = East | South | West | North deriving (Show, Eq)
17
18 type Location = V2 Int -- x, y
19
20 type Visited = S.Set Location
21
22 data Path = Path { _visited :: Visited
23 , _tip :: Location
24 }
25 deriving (Show, Eq)
26
27 data Segment = Segment { _direction :: Direction
28 , _steps :: Int
29 } deriving (Show, Eq)
30
31
32 main :: IO ()
33 main = do
34 text <- TIO.readFile "data/advent03.txt"
35 let segmentss = successfulParse text
36 -- print segmentss
37 -- print $ travelPath $ head segmentss
38 print $ part1 segmentss
39 -- print $ part2 machine
40
41 part1 :: [[Segment]] -> Int
42 part1 segmentss = closest $ crossovers $ travelAllPaths segmentss
43
44 closest :: Visited -> Int
45 closest points = S.findMin $ S.map manhattan points
46
47 crossovers :: [Path] -> Visited
48 crossovers travelledPaths =
49 foldl1' S.intersection $ map _visited travelledPaths
50
51 travelAllPaths :: [[Segment]] -> [Path]
52 travelAllPaths = map travelPath
53
54 travelPath :: [Segment] -> Path
55 travelPath segments = foldl' travelSegment path0 segments
56 where path0 = Path { _visited = S.empty, _tip = V2 0 0 }
57
58 travelSegment :: Path -> Segment -> Path
59 travelSegment path segment = path { _tip = tip', _visited = visited' }
60 where delta = facing $ _direction segment
61 distance = _steps segment
62 start = _tip path
63 visited = _visited path
64 visited' = foldl' (flip S.insert) visited $ take distance $ drop 1 $ iterate (^+^ delta) start
65 tip' = start ^+^ distance *^ delta
66
67 facing :: Direction -> Location
68 facing East = V2 1 0
69 facing South = V2 0 (-1)
70 facing West = V2 (-1) 0
71 facing North = V2 0 1
72
73
74 manhattan (V2 x y) = (abs x) + (abs y)
75
76 -- Parse the input file
77 type Parser = Parsec Void Text
78
79 sc :: Parser ()
80 sc = L.space (skipSome spaceChar) CA.empty CA.empty
81 -- sc = L.space (skipSome (char ' ')) CA.empty CA.empty
82
83 lexeme = L.lexeme sc
84 integer = lexeme L.decimal
85 -- signedInteger = L.signed sc integer
86 symb = L.symbol sc
87 comma = symb ","
88
89 wiresP = many pathP
90 pathP = segmentP `sepBy1` comma
91
92 segmentP = segmentify <$> directionP <*> integer
93 where segmentify direction steps =
94 Segment { _direction = direction, _steps = steps }
95
96
97 directionP = eP <|> sP <|> wP <|> nP
98 eP = (symb "R" *> pure East)
99 sP = (symb "D" *> pure South)
100 wP = (symb "L" *> pure West)
101 nP = (symb "U" *> pure North)
102
103
104 successfulParse :: Text -> [[Segment]]
105 successfulParse input =
106 case parse wiresP "input" input of
107 Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
108 Right wires -> wires