Mercurial > repos > other > SevenLanguagesInSevenWeeks
changeset 102:d3e35dfc6f84
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 | 1fae0cca1ef8 |
| children | 98be775c533c |
| files | 7-Haskell/day3-maze.hs |
| diffstat | 1 files changed, 5 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/7-Haskell/day3-maze.hs Sun Jul 14 13:42:24 2019 +0100 +++ b/7-Haskell/day3-maze.hs Sun Jul 14 13:43:22 2019 +0100 @@ -1,5 +1,6 @@ module Day3Maze where import System.IO + import Data.Set (empty, fromList, union, notMember) -- This is a "type" alias, because they're just naming pre-existing types with specific patterns -- Note: Nested lists with indexes will be inefficient compared to Vectors, but I'm working with what I know! @@ -84,7 +85,10 @@ in filter (\node -> (snd node) /= []) candidates step :: Maze -> [[Coords]] -> [[Coords]] - step maze routes = filter (\(hd:lst) -> hd `notElem` lst) (concatMap (\route -> map (: route) (nextSteps maze route)) routes) + -- 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 + -- (head is in previous points, meaning we've found a shorter route) + step maze routes = filter (\(hd:lst) -> (hd `notElem` lst) && (hd `notMember` all_previous_points)) (concatMap (\route -> map (: route) (nextSteps maze route)) routes) + where all_previous_points = foldl union empty (map fromList routes) nextSteps :: Maze -> [Coords] -> [Coords] nextSteps maze route = map (fst . getRelativeNode maze pos) exits