## Competitive programming in Haskell: BFS, part 1

In a previous post, I challenged you to solve Modulo Solitaire. In this problem, we are given a starting number $s_0$ and are trying to reach $0$ in as few moves as possible. At each move, we may pick one of up to 10 different rules $(a_i,b_i)$ that say we can transform $s$ into $(a_i s + b_i) \bmod m$.

In one sense, this is a straightforward search problem. Conceptually, the numbers $0$ through $m-1$ form the vertices of a graph, with a directed edge from $s$ to $t$ whenever there is some allowed $(a_i, b_i)$ such that $t = (a_i s + b_i) \bmod m$; we want to do a breadth first search in this graph to find the length of a shortest path from $s_0$ to $0$. However, $m$ can be up to $10^6$ and there can be up to $10$ rules, giving a total of up to $10^7$ edges. In the case that $0$ is unreachable, we may have to explore every single edge. So we are going to need a pretty fast implementation; we’ll come back to that later.

Haskell actually has a nice advantage here. This is exactly the kind of problem in which we want to represent the graph implicitly. There is no reason to actually reify the graph in memory as a data structure; it would only waste memory and time. Instead, we can specify the graph implicitly using a function that gives the neighbors of each vertex, which means BFS itself will be a higher-order function. Higher-order functions are very awkward to represent in a language like Java or C++, so when I solve problems like this in Java, I tend to just write the whole BFS from scratch every single time, and I doubt I’m the only one. However, in Haskell we can easily make an abstract interface to BFS which takes a function as input specifying an implicit graph, allowing us to nicely separate out the graph search logic from the task of specifying the graph itself.

What would be my ideal API for BFS in Haskell? I think it might look something like this (but I’m happy to hear suggestions as to how it could be made more useful or general):

``````data BFSResult v =
BFSR { level :: v -> Maybe Int, parent :: v -> Maybe v }

bfs ::
(Ord v, Hashable v) =>
[v] ->                      -- Starting vertices
(v -> [v]) ->               -- Neighbors
(v -> Bool) ->              -- Goal predicate
BFSResult v``````

`bfs` takes a list of vertices to search from (which could be a singleton if there is a single specific starting vertex), a function specifying the out-neighbors of each vertex, and a predicate specifying which vertices are “goal” vertices (so we can stop early if we reach one), and returns a `BFSResult` record, which tells us the level at which each vertex was encountered, if at all (i.e. how many steps were required to reach it), and the parent of each vertex in the search. If we just want to know whether a vertex was reachable at all, we can see if `level` returns `Just`; if we want to know the shortest path to a vertex, we can just iterate `parent`. Vertices must be `Ord` and `Hashable` to facilitate storing them in data structures.

Using this API, the solution is pretty short.

``````main = C.interact \$ runScanner tc >>> solve >>> format

data Move = Move { a :: !Int, b :: !Int } deriving (Eq, Show)
data TC = TC { m :: Int, s0 :: Int, moves :: [Move] } deriving (Eq, Show)

tc :: Scanner TC
tc = do
m <- int
n <- int
TC m <\$> int <*> n >< (Move <\$> int <*> int)

format :: Maybe Int -> ByteString
format = maybe "-1" showB

solve :: TC -> Maybe Int
solve TC{..} = level res 0
where
res = bfs [s0] (\v -> map (step v) moves) (==0)
step v (Move a b) = (a*v + b) `mod` m``````

We run a BFS from $s_0$, stopping when we reach $0$, and then look up the `level` of 0 to see the minimum number of steps needed to reach it.

In part 2, I’ll talk about how to implement this API. There are many viable implementation strategies, but the trick is getting it to run fast enough.

## About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in competitive programming, haskell and tagged , , , , . Bookmark the permalink.

### 5 Responses to Competitive programming in Haskell: BFS, part 1

1. Andrey Mokhov says:

Just to share a couple of alternative APIs for breadth-first search, here are two from the algebraic-graphs library:

bfsForest :: Ord a => [a] -> AdjacencyMap a -> Forest a
bfs :: Ord a => [a] -> AdjacencyMap a -> [[a]]

where AdjacencyMap a = Map a (Set a), so it’s not really a good representation for this problem :)

With the second one (bfs), the solution is going to be pretty short too: findIndex (elem 0) res.

Curious to see how you’ll implement your BFS!

This site uses Akismet to reduce spam. Learn how your comment data is processed.