# HG changeset patch
# User IBBoard <dev@ibboard.co.uk>
# Date 1563108202 -3600
# Node ID d3e35dfc6f84b0cbf8a52d94cf3283f01f8302d5
# Parent  1fae0cca1ef8913726fd1fb2dcbeb40cb0635583
Do some "have we been here via another route" filtering

This (combined with simplified maze) means we solve the maze in under 10s!

diff -r 1fae0cca1ef8 -r d3e35dfc6f84 7-Haskell/day3-maze.hs
--- 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