Mercurial > repos > other > SevenLanguagesInSevenWeeks

comparison 7-Haskell/day3-maze.hs @ 102:d3e35dfc6f84

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Do some "have we been here via another route" filtering This (combined with simplified maze) means we solve the maze in under 10s!
author IBBoard <dev@ibboard.co.uk>
date Sun, 14 Jul 2019 13:43:22 +0100
parents 830140560f70
children
comparison
equal deleted inserted replaced
101:1fae0cca1ef8 102:d3e35dfc6f84
1 module Day3Maze where 1 module Day3Maze where
2 import System.IO 2 import System.IO
3 import Data.Set (empty, fromList, union, notMember)
3 4
4 -- This is a "type" alias, because they're just naming pre-existing types with specific patterns 5 -- This is a "type" alias, because they're just naming pre-existing types with specific patterns
5 -- Note: Nested lists with indexes will be inefficient compared to Vectors, but I'm working with what I know! 6 -- Note: Nested lists with indexes will be inefficient compared to Vectors, but I'm working with what I know!
6 type Maze = [[Node]] 7 type Maze = [[Node]]
7 type Coords = (Int, Int) 8 type Coords = (Int, Int)
82 -- This doubles up the corners, but we'll make an assumption that the corner is always filled in! 83 -- This doubles up the corners, but we'll make an assumption that the corner is always filled in!
83 findExits' maze = let candidates = (map last maze) ++ (map head maze) ++ (head maze) ++ (last maze) 84 findExits' maze = let candidates = (map last maze) ++ (map head maze) ++ (head maze) ++ (last maze)
84 in filter (\node -> (snd node) /= []) candidates 85 in filter (\node -> (snd node) /= []) candidates
85 86
86 step :: Maze -> [[Coords]] -> [[Coords]] 87 step :: Maze -> [[Coords]] -> [[Coords]]
87 step maze routes = filter (\(hd:lst) -> hd `notElem` lst) (concatMap (\route -> map (: route) (nextSteps maze route)) routes) 88 -- Map out all of the next steps, but remove ones that go back on themselves (head is in its own tail) or that we've been to before
89 -- (head is in previous points, meaning we've found a shorter route)
90 step maze routes = filter (\(hd:lst) -> (hd `notElem` lst) && (hd `notMember` all_previous_points)) (concatMap (\route -> map (: route) (nextSteps maze route)) routes)
91 where all_previous_points = foldl union empty (map fromList routes)
88 92
89 nextSteps :: Maze -> [Coords] -> [Coords] 93 nextSteps :: Maze -> [Coords] -> [Coords]
90 nextSteps maze route = map (fst . getRelativeNode maze pos) exits 94 nextSteps maze route = map (fst . getRelativeNode maze pos) exits
91 where { 95 where {
92 pos:prior_steps = route ; 96 pos:prior_steps = route ;