page =
url = https://byorgey.wordpress.com
blog :: brent -> [string]
In a previous post , I challenged you to solve Modulo Solitaire . In this problem, we are given a starting number and are trying to reach in as few moves as possible. At each move, we may pick one of up to 10 different rules that say we can transform into .
In one sense, this is a straightforward search problem. Conceptually, the numbers through form the vertices of a graph, with a directed edge from to whenever there is some allowed such that ; we want to do a breadth first search in this graph to find the length of a shortest path from to . However, can be up to and there can be up to rules, giving a total of up to edges. In the case that 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
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 , stopping when we reach , and then look up the
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.
Posted in competitive programming , haskell | Tagged BFS , graph , haskell , Kattis , search | Leave a comment
graph