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.