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
    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!

  2. Pingback: Competitive programming in Haskell: BFS, part 2 (alternative APIs) | blog :: Brent -> [String]

  3. Pingback: Competitive programming in Haskell: BFS, part 3 (implementation via HashMap) | blog :: Brent -> [String]

  4. Pingback: Competitive programming in Haskell: Enumeration | blog :: Brent -> [String]

  5. Pingback: Competitive programming in Haskell: BFS, part 4 (implementation via STUArray) | blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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