Shortest Path (BFS) through a maze

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:

• Find shortest distance between (1,1) and (31,39).

• 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 = xx+3x+2xy+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 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) $

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:

• Turn mkEdges into a parameter to the search function.

• 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)

StackExchange Code Review Q#149757, answer score: 2