# 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:

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.

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)