Shortest Path (BFS) through a maze

Question

Background

I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I produce is not the most readable and possibly has inefficiencies. Any suggestions on how to improve readability and performance would be much appreciated.

Problem

The problem is Day 13 of AoC. It consists of a maze where each cell (x,y) is either a wall or an empty space, dictated by the population count of the following equation:

x*x + 3*x + 2*x*y + y + y*y + key (where key is some arbitrary integer)

The cell is a wall if the population count is odd. The problem then comes in two parts:

1. Find shortest distance between (1,1) and (31,39).
2. Find number of cells that can be visited in 50 or less steps (from (1,1)).

Code

The code uses BFS for both parts. I am aware that A* may quicker for Part1.

import Data.Bits (popCount)
import qualified Data.Map as Map 
import Debug.Trace 
-- Define all types 
type Index = (Int, Int) -- (x,y)
type Edges = [Index] -- list of connecting edges
type Prob = (Int, Int, Int) -- (key, width, height)
type State = (Index, Int, Map.Map Index Bool) -- (current, steps, visited)
-- Determine if a specific cell index represents a wall
isWall :: Int -> Index -> Bool 
isWall key (x,y) = odd $ popCount num 
 where num = x*x+3*x+2*x*y+y+y*y+key
-- Generate all edges of a specific cell
mkEdges :: Int -> Index -> Edges 
mkEdges key (x,y) = filter (not.isWall key) adjs
 where adjs = wB [(x, y-1), (x+1, y), (x,y+1), (x-1,y)]
 wB = filter (\(a,b) -> not (a<0 || b<0))
-- Find the shortest path length 
bfsPathLength :: Int -> Index -> [State] -> Int 
bfsPathLength key goal t@((curr, steps, visited):rest) | goal==curr = steps
 | otherwise = bfsPathLength key goal newStates
 where newStates = (filter (not.isQueued) $ filter (not.isVisited) $ map mkStates $ mkEdges key curr) ++ rest 
 mkStates s = (s, steps+1, Map.insert curr True visited)
 isVisited (s,_,_) = Map.member s visited
 isQueued (s,_,_) = elem s $ map (\(x,_,_) -> x) t
-- Calculate the number of reachable nodes from a starting position
bfsReachableLocations :: Int -> [(Int, Index)] -> [Index] -> Int 
bfsReachableLocations key a@((lim,curr):rest) visited | lim < 0 = 0 
 | otherwise = 1 + bfsReachableLocations key newNodes (visited++[curr])
 where neighbours = filter (not.isQueued) $ filter (not.(\x -> elem x visited)) $ mkEdges key curr
 isQueued n = elem n $ map (\(_,x) -> x) a
 newNodes = rest ++ map (\x -> (lim-1, x)) neighbours
main = do 
 print $ bfsPathLength 1362 (31,39) [((1,1), 0, Map.empty)]
 print $ bfsReachableLocations 1362 [(50, (1,1))] [] 

The code is not as readable as I'd like. There are probably easier ways of performing some of the steps that I have no yet encountered on my short Haskell journey. Any recommendations would be appreciated.

Answer 1

General Comments

mkEdges

I would probably just call this function edges. mk (which I assume is short for make) has an imperative ring to it.

bfsPathLength :: Int -> Index -> [State] -> Int

You are forcing users of bfsPathLength to pass an initial state. This forces them to be aware of the internal details of the algorithm, which is not a good design. You could get rid of the [State] parameter and have bfsPathLength delegate to a helper function that takes the initial state. Public interfaces should never expose details that aren't necessary.

bfsReachableLocations :: Int -> [(Int, Index)] -> [Index] -> Int 

• What's the purpose of this function? It doesn't appear to be used for computation of the actual answer to the riddle. If it's for debugging purposes, you should add a comment that says so (be sure to include what it actually does, and why it's useful for debugging as well).
• Also, once again you force users to incorporate knowledge about the internal state of the algorithm.

Performance

You perform a linear search for nodes in the queue and the visited set. You should use a more appropriate datastructure, such as a set, that can do the search in \$O(\log{n})\,ドル or even \$O(1)\,ドル time.

Abstraction

• Consider separating the graph generation from the search algorithm. This will allow you to use BFS search to solve other problems. You have some options here, including:

  1. Turn mkEdges into a parameter to the search function.
  2. Use a typeclass.

  For example, if you turn mkEdges into a parameter (and remove the internal state parameter), bfsPathLength might have the following type signature:

  bfsPathLength :: (a -> [a]) -> a -> Int 
  bfsPathLength edgeGenerator goalLocation = ...
  

• You should parameterize the start location:

  bfsPathLength :: (a -> [a]) -> a -> a -> Int
  bfsPathLength edgeGnerator startLocation goalLocation = ...
  

• It seems like it would be useful to be able to find the actual path in most cases, rather than just the length:

  bfsPath :: (a -> [a]) -> a -> [a]
  

  Then you can write bfsPathLength as follows:

  bfsPathLength :: (a -> [a]) -> a -> a-> Int
  bfsPathLength edgeGenerator startLocation = length . (bfsPath edgeGenerator startLocation)