Competitive programming in Haskell: Infinite 2D array

If you like number theory, combinatorics, and/or optimizing Haskell code, I challenge you to solve Infinite 2D Array using Haskell.

• Level 1: can you come up with a general formula to compute $F_{x,y}$?
• Level 2: In general, how can you efficiently compute $F_{x,y} \pmod {10^9 + 7}$?
• Level 3: Now implement the above ideas in Haskell so your solution actually fits within the 1 second time limit.

I have solved it but it was definitely challenging. In a subsequent blog post I’ll talk about my solution and ask for other optimization ideas.

Posted in competitive programming, haskell | Tagged , , | 2 Comments

Types for top-level definitions

I’ve come up with idea for a type system for first-class (global) definitions, which can serve as a very lightweight alternative to a proper module system. I’m posting it here in the hopes of getting some feedback and pointers to related work.

Commands and expressions

The programming language of Swarm (for lack of a better term I will hereafter refer to it as Swarmlang) has a bunch of imperative commands, and standard monadic sequencing constructs. For example,

move; move

does two move commands in sequence, and

thing <- grab; give friend thing

first executes grab, binding the variable thing to the result, then executes give friend thing. Of course, there is also a rich language of pure expressions, with things like arithmetic, strings, lambdas and function application, pairs, sums, and so on.

Some languages make a syntactic distinction between statements and expressions, but Swarmlang does not: everything is an expression, and some expressions happen to have a command type. If t is a type, then cmd t is the type of an imperative command which, when executed, can have some effects and then returns a result of type t. (Of course this should feel very familiar to Haskell programmers; cmd has many similarities to IO.) This approach makes many things simpler and means that commands are first-class values.

Typechecking definitions

Swarmlang has definitions, which are just expressions with a command type. If e is an expression, then

def x = e end

has type cmd (). When executed, it should have the effect of binding the name x to the expression e, and bringing x into scope for all subsequent commands. Thus, it is valid to sequence this first definition with a second definition that mentions x, like so:

def x = e end;
def y = foo bar x end

Of course, this means that while typechecking the definition of y, we must be able to look up the type of x. However, the type of the first def command is simply cmd (), which does not tell us anything about x or its type. Normally, the typing rule for sequencing of commands would be something like

$\displaystyle \frac{\Gamma \vdash c_1 : \mathrm{cmd}\; \tau_1 \qquad \Gamma \vdash c_2 : \mathrm{cmd}\; \tau_2}{\Gamma \vdash c_1 ; c_2 : \mathrm{cmd}\;\tau_2}$

but this does not work for def commands, since it does not take into account the new names brought into scope. Up until now, I have dealt with this in a somewhat ad-hoc manner, with some special typechecking rules for def and some ad-hoc restrictions to ensure that def can only syntactically show up at the top level. However, I would really like to put everything on a more solid theoretical basis (which will hopefully simplify the code as well).

Decorating command types

The basic idea is to decorate the $\mathrm{cmd}$ type with extra information about names bound by definitions. As usual, let $\Gamma$ denote a generic context, that is, a finite mapping from variable names to their types. Then we extend the cmd type by adding a context to it:

$\mathrm{cmd}\; \tau \Rightarrow \Gamma$

is the type of a command which yields a result of type $\tau$ and produces global bindings for some names whose types are recorded in $\Gamma$. (Of course, we can continue to use $\mathrm{cmd}\; \tau$ as an abbreviation for $\mathrm{cmd}\; \tau \Rightarrow \varnothing$.) So, for example, def x = 3 end no longer has type $\mathrm{cmd}\; ()$, but rather something like $\mathrm{cmd}\; () \Rightarrow \{x : \mathrm{int}\}$, representing the fact that although def x = 3 end does not result in an interesting value, it does bind a name, x, whose type is int.

This is slightly unusual in the fact that types and contexts are now mutually recursive, but that doesn’t seem like a big problem. We can now write down a proper typing rule for sequencing that takes definitions into account, something like this:

$\displaystyle \frac{\Gamma \vdash c_1 : \mathrm{cmd} \; \tau_1 \Rightarrow \Gamma_1 \qquad \Gamma, \Gamma_1 \vdash c_2 : \mathrm{cmd} \; \tau_2 \Rightarrow \Gamma_2}{\Gamma \vdash c_1 ; c_2 : \mathrm{cmd} \; \tau_2 \Rightarrow \Gamma, \Gamma_1, \Gamma_2}$

And of course the typing rule for def looks like this:

$\displaystyle \frac{\Gamma \vdash e : \tau}{\Gamma \vdash \texttt{def}\; x = e\; \texttt{end} : \mathrm{cmd}\; () \Rightarrow \{x : \tau\}}$

These rules together can now correctly typecheck an expression like

def x = 3 end;
def y = 2 + x end

where the second definition refers to the name defined by the first. The whole thing would end up having type $\mathrm{cmd}\; () \Rightarrow \{ x : \mathrm{int}, y : \mathrm{int} \}$.

…with polymorphism?

All this seems straightforward with only first-order types, as in my example typing rules above. But once you add parametric polymorphism my brain starts to hurt. Clearly, the context associated to a command type could bind variables to polytypes. For example, def id = \x.x end has type $\mathrm{cmd}\; () \Rightarrow \{id : \forall \alpha. \alpha \to \alpha\}$. But should the context associated to a command type always contain polytypes, or only when the command type is itself a polytype? In other words, how do we deal with the associated contexts in the monotypes that show up during type inference? And what would it mean to unify two command types with their contexts (and would that ever even be necessary)? I hope it’s actually simple and I just need to think about it some more, but I haven’t wrapped my brain around it yet.

Ideas and pointers welcome!

I’d be very happy to hear anyone’s ideas, or (especially) pointers to published work that seems related or relevant! Feel free to comment either here, or on the relevant github issue.

Posted in projects | Tagged , , | 7 Comments

Swarm: status report

Swarm is a 2D programming and resource gathering game, written in Haskell. I announced it last September and gave an update one week after that, but haven’t written anything since then. However, that doesn’t mean development has stopped! Since last October, the repo has grown by an additional 4K lines of Haskell code (to 12K). Notable changes since then include:

• Many UI improvements, like a main menu, ASCII art recipes, and mouse support
• Many new entities and recipes (multiple types of motors, drills, and mines; new materials like iron, silver, quartz, and glass; new devices like circuits, clocks, cameras, comparators, compasses, …)
• The game now supports scenarios, generically describing how to initialize the game and what the winning conditions should be: scenarios can be used to describe open-world games, tutorials, tricky programming challenges, … etc.
• Improvements to the programming language, like a new dedicated robot type, and a “delay” type for things that should be evaluated lazily
• Increased emphasis on exploration, with the ability to scan unknown entities in the world

Development has picked up considerably in the past few weeks, and we’re making good progress toward a planned alpha release (though no concrete plans in terms of a release date yet). If you’re interested in getting involved, check out our contribution guide, come join us on IRC (#swarm on Libera.Chat) and take a look at the list of issues marked “low-hanging fruit”—as of this writing there are 28 such issues, so plenty of tasks for everyone!

Competitive programming in Haskell: BFS, part 4 (implementation via STUArray)

In a previous post, we saw one way to implement our BFS API, but I claimed that it is not fast enough to solve Modulo Solitaire. Today, I want to demonstrate a faster implementation. (It’s almost certainly possible to make it faster still; I welcome suggestions!)

Once again, the idea is to replace the HashMaps from last time with mutable arrays, but in such a way that we get to keep the same pure API—almost. In order to allow arbitrary vertex types, while storing the vertices efficiently in a mutable array, we will require one extra argument to our bfs function, namely, an Enumeration specifying a way to map back and forth between vertices and array indices.

So why not instead just restrict vertices to some type that can be used as keys of a mutable array? That would work, but would unnecessarily restrict the API. For example, it is very common to see competitive programming problems that are “just” a standard graph algorithm, but on a non-obvious graph where the vertices are conceptually some more complex algebraic type, or on a graph where the vertices are specified as strings. Typically, competitive programmers just implement a mapping between vertices to integers on the fly—using either some math or some lookup data structures on the side—but wouldn’t it be nicer to be able to compositionally construct such a mapping and then have the graph search algorithm automatically handle the conversion back and forth? This is exactly what the Enumeration abstraction gives us.

This post is literate Haskell; you can obtain the source from the darcs repo. The source code (without accompanying blog post) can also be found in my comprog-hs repo.

{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE RecordWildCards     #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Graph where

import Enumeration

import           Control.Arrow       ((>>>))
import qualified Data.Array.IArray   as IA
import           Data.Array.ST
import           Data.Array.Unboxed  (UArray)
import qualified Data.Array.Unboxed  as U
import           Data.Array.Unsafe   (unsafeFreeze)
import           Data.Sequence       (Seq (..), ViewL (..), (<|), (|>))
import qualified Data.Sequence       as Seq

infixl 0 >$> (>$>) :: a -> (a -> b) -> b
(>$>) = flip ($)
{-# INLINE (>$>) #-} exhaustM is like exhaust from the last post, but in the context of an arbitrary Monad. Each step will now be able to have effects (namely, updating mutable arrays) so needs to be monadic. exhaustM :: Monad m => (a -> m (Maybe a)) -> a -> m a exhaustM f = go where go a = do ma <- f a maybe (return a) go ma The BFSResult type is the same as before. data BFSResult v = BFSR { getLevel :: v -> Maybe Int, getParent :: v -> Maybe v } Instead of using HashMaps in our BFSState as before, we will use STUArrays.1 These are unboxed, mutable arrays which we can use in the ST monad. Note we also define V as a synonym for Int, just as a mnemonic way to remind ourselves which Int values are supposed to represent vertices. type V = Int data BFSState s = BS { level :: STUArray s V Int, parent :: STUArray s V V, queue :: Seq V } To initialize a BFS state, we allocate new mutable level and parent arrays (initializing them to all $-1$ values), and fill in the level array and queue with the given start vertices. Notice how we need to be explicitly given the size of the arrays we should allocate; we will get this size from the Enumeration passed to bfs. initBFSState :: Int -> [V] -> ST s (BFSState s) initBFSState n vs = do l <- newArray (0,n-1) (-1) p <- newArray (0,n-1) (-1) forM_ vs$ \v -> writeArray l v 0
return $BS l p (Seq.fromList vs) The bfs' function implements the BFS algorithm itself. Notice that it is not polymorphic in the vertex type; we will fix that with a wrapper function later. If you squint, the implementation looks very similar to the implementation of bfs from my previous post, with the big difference that everything has to be in the ST monad now. bfs' :: Int -> [V] -> (V -> [V]) -> (V -> Bool) -> ST s (BFSState s) bfs' n vs next goal = do st <- initBFSState n vs exhaustM bfsStep st where bfsStep st@BS{..} = case Seq.viewl queue of EmptyL -> return Nothing v :< q' | goal v -> return Nothing | otherwise -> v >$> next >>> filterM (fmap not . visited st)
>=> foldM (upd v) (st{queue=q'}) >>> fmap Just

upd p b@BS{..} v = do
writeArray level v (lp + 1)
writeArray parent v p
return $b{queue = queue |> v} visited :: BFSState s -> V -> ST s Bool visited BS{..} v = (/= -1) <$> readArray level v
{-# INLINE visited #-}

The bfs function is a wrapper around bfs'. It presents the same API as before, with the exception that it requires an extra Enumeration v argument, and uses it to convert vertices to integers for the inner bfs' call, and then back to vertices for the final result. It also handles freezing the mutable arrays returned from bfs' and constructing level and parent lookup functions that index into them. Note, the use of unsafeFreeze seems unavoidable, since runSTUArray only allows us to work with a single mutable array; in any case, it is safe for the same reason the use of unsafeFreeze in the implementation of runSTUArray itself is safe: we can see from the type of toResult that the s parameter cannot escape, so the type system will not allow any further mutation to the arrays after it completes.

bfs :: forall v. Enumeration v -> [v] -> (v -> [v]) -> (v -> Bool) -> BFSResult v
bfs Enumeration{..} vs next goal
= toResult $bfs' card (map locate vs) (map locate . next . select) (goal . select) where toResult :: (forall s. ST s (BFSState s)) -> BFSResult v toResult m = runST$ do
st <- m
(level' :: UArray V Int) <- unsafeFreeze (level st)
(parent' :: UArray V V) <- unsafeFreeze (parent st)
return $BFSR ((\l -> guard (l /= -1) >> Just l) . (level' IA.!) . locate) ((\p -> guard (p /= -1) >> Just (select p)) . (parent' IA.!) . locate) Incidentally, instead of adding an Enumeration v argument, why don’t we just make a type class Enumerable, like this? class Enumerable v where enumeration :: Enumeration v bfs :: forall v. Enumerable v => [v] -> ... This would allow us to keep the same API for BFS, up to only different type class constraints on v. We could do this, but it doesn’t particularly seem worth it. It would typically require us to make a newtype for our vertex type (necessitating extra code to map in and out of the newtype) and to declare an Enumerable instance; in comparison, the current approach with an extra argument to bfs requires us to do nothing other than constructing the Enumeration itself. Using this implementation, bfs is finally fast enough to solve Modulo Solitaire, like this: 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)

type Output = Maybe Int

format :: Output -> ByteString
format = maybe "-1" showB

solve :: TC -> Output
solve TC{..} = getLevel res 0
where
res = bfs (finiteE m) [s0] (\v -> map (step m v) moves) (==0)

step :: Int -> Int -> Move -> Int
step m v (Move a b) = (a*v + b) mod m
{-# INLINE step #-}

It’s pretty much unchanged from before, except for the need to pass an Enumeration to bfs (in this case we just use finiteE m, which is the identity on the interval $[0 .. m)$).

Some remaining questions

This is definitely not the end of the story.

• Submitting all this code (BFS, Enumeration, and the above solution itself) as a single file gives a 2x speedup over submitting them as three separate modules. That’s annoying—why is that?

• Can we make this even faster? My solution to Modulo Solitaire runs in 0.57s. There are faster Haskell solutions (for example, Anurudh Peduri has a solution that runs in 0.32s), and there are Java solutions as fast as 0.18s, so it seems to me there ought to be ways to make it much faster. If you have an idea for optimizing this code I’d be very interested to hear it! I am far from an expert in Haskell optimization.

• Can we generalize this nicely to other kinds of graph search algorithms (at a minimum, DFS and Dijkstra)? I definitely plan to explore this question in the future.

Next time, I want to look at a few other applications of this BFS code (and perhaps see if we can improve it along the way); I challenge you to solve Breaking Bad.

1. Why not use Vector, you ask? It’s probably even a bit faster, but the vector library is not supported on as many platforms.↩︎

Posted in competitive programming, haskell | Tagged , , , , , , | 3 Comments

I’m in the middle of a multi-part series on implementing BFS in Haskell. In my last post, we saw one implementation, but I claimed that it is not fast enough to solve Modulo Solitaire, and I promised to show off a faster implementation in this post, but I lied; we have to take a small detour first.

The main idea to make a faster BFS implementation is to replace the HashMaps from last time with mutable arrays, but hopefully in such a way that we get to keep the same pure API. Using mutable arrays introduces a few wrinkles, though.

1. The API we have says we get to use any type v for our vertices, as long as it is an instance of Ord and Hashable. However, this is not going to work so well for mutable arrays. We still want the external API to allow us to use any type for our vertices, but we will need a way to convert vertices to and from Int values we can use to index the internal mutable array.

2. A data structre like HashMap is dynamically sized, but we don’t have this luxury with arrays. We will have to know the size of the array up front.

In other words, we need to provide a way to bijectively map vertices to a finite prefix of the natural numbers; that is, we need what I call invertible enumerations. This idea has come up for me multiple times: in 2016, I wrote about using such an abstraction to solve another competitive programming problem, and in 2019 I published a library for working with invertible enumerations. I’ve now put together a lightweight version of that library for use in competitive programming. I’ll walk through the code below, and you can also find the source code in my comprog-hs repository.

First, some extensions and imports.

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}

module Enumeration where

import qualified Data.List as L
import Data.Hashable
import qualified Data.Array as A
import qualified Data.HashMap.Strict as HM

An Enumeration a consists of a cardinality, and two functions, select and locate, which together form a bijection between (some subset of) values of type a and a finite prefix of the natural numbers. We can convert an Enumeration into a list just by mapping the select function over that finite prefix.

data Enumeration a = Enumeration
{ card   :: !Int
, select :: Int -> a
, locate :: a -> Int
}

enumerate :: Enumeration a -> [a]
enumerate e = map (select e) [0 .. card e-1]

Since a occurs both positively and negatively, Enumeration is not a Functor, but we can map over Enumerations as long as we provide both directions of a bijection a <-> b.

mapE :: (a -> b) -> (b -> a) -> Enumeration a -> Enumeration b
mapE f g (Enumeration c s l) = Enumeration c (f . s) (l . g)

We have various fundamental ways to build enumerations: empty and unit enumerations, and an identity enumeration on a finite prefix of natural numbers.

voidE :: Enumeration a
voidE = Enumeration 0 (error "select void") (error "locate void")

unitE :: Enumeration ()
unitE = singletonE ()

singletonE :: a -> Enumeration a
singletonE a = Enumeration 1 (const a) (const 0)

finiteE :: Int -> Enumeration Int
finiteE n = Enumeration n id id

We can automatically enumerate all the values of a Bounded Enum instance. This is useful, for example, when we have made a custom enumeration type.

boundedEnum :: forall a. (Enum a, Bounded a) => Enumeration a
boundedEnum = Enumeration
{ card   = hi - lo + 1
, select = toEnum . (+lo)
, locate = subtract lo . fromEnum
}
where
lo, hi :: Int
lo = fromIntegral (fromEnum (minBound @a))
hi = fromIntegral (fromEnum (maxBound @a))

We can also build an enumeration from an explicit list. We want to make sure this is efficient, since it is easy to imagine using this e.g. on a very large list of vertex values given as part of the input of a problem. So we build an array and a hashmap to allow fast lookups in both directions.

listE :: forall a. (Hashable a, Eq a) => [a] -> Enumeration a
listE as = Enumeration n (toA A.!) (fromA HM.!)
where
n = length as
toA :: A.Array Int a
toA = A.listArray (0,n-1) as
fromA :: HM.HashMap a Int
fromA = HM.fromList (zip as [0 :: Int ..])

Finally, we have a couple ways to combine enumerations into more complex ones, via sum and product.

(>+<) :: Enumeration a -> Enumeration b -> Enumeration (Either a b)
a >+< b = Enumeration
{ card   = card a + card b
, select = \k -> if k < card a then Left (select a k) else Right (select b (k - card a))
, locate = either (locate a) ((+card a) . locate b)
}

(>*<) :: Enumeration a -> Enumeration b -> Enumeration (a,b)
a >*< b = Enumeration
{ card = card a * card b
, select = \k -> let (i,j) = k divMod card b in (select a i, select b j)
, locate = \(x,y) -> card b * locate a x + locate b y
}

There are a few more combinators in the source code but I don’t know whether I’ll ever use them. You can read about them if you want. For now, let’s try using this to solve a problem!

…ah, who am I kidding, I can’t find any problems that can be directly solved using this framework. Invertibility is a double-edged sword—we absolutely need it for creating an efficient BFS with arbitrary vertices, and the combinators will come in quite handy if we want to use some complex type for vertices. However, requiring invertibility also limits the expressiveness of the library. For example, there is no Monad instance. This is why my simple-enumeration library has both invertible and non-invertible variants.

Posted in competitive programming, haskell | Tagged , , , , | 1 Comment

Competitive programming in Haskell: BFS, part 3 (implementation via HashMap)

In a previous post, I showed how we can solve Modulo Solitaire (and hopefully other BFS problems as well) using a certain API for BFS, and we also explored some alternatives. I had a very interesting discussion with Andrey Mokhov in the comments about potential designs for an even more general API; more on that in a future post, perhaps!

For today, though, I want to finally show one way to implement this API efficiently. Spoiler alert: this implementation ultimately won’t be fast enough for us, but it will be a helpful stepping stone on our way to a yet faster implementation (which will of course get its own post in due time).

This post is literate Haskell; you can obtain the source from the darcs repo. We begin with a few LANGUAGE pragmas and imports.

{-# LANGUAGE RecordWildCards            #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE TupleSections              #-}

module BFS where

import           Control.Arrow               ((>>>))
import           Data.Hashable               (Hashable)
import           Data.HashMap.Strict         (HashMap, (!))
import qualified Data.HashMap.Strict         as HM
import           Data.List                   (foldl')
import           Data.Sequence               (Seq (..), ViewL (..), (|>))
import qualified Data.Sequence               as Seq

Now a couple utility functions: (>$>) is just flipped function application, and exhaust iterates an (a -> Maybe a) function as many times as possible, returning the last non-Nothing value. infixl 0 >$>
(>$>) :: a -> (a -> b) -> b (>$>) = flip ($) {-# INLINE (>$>) #-}

exhaust :: (a -> Maybe a) -> a -> a
exhaust f = go
where
go a = maybe a go (f a)

Here is the BFSResult record that we ultimately want to produce; it should be familiar from previous posts.

data BFSResult v =
BFSR { getLevel :: v -> Maybe Int, getParent :: v -> Maybe v }

While running our BFS, we’ll keep track of three things: the level of each vertex that has been encountered; a mapping from each encountered vertex to its parent; and a queue of vertices that have been encountered but yet to be processed. We use a Seq from Data.Sequence to represent the queue, since it supports efficient (amortized constant-time) insertion and removal from either end of the sequence. There are certainly other potential ways to represent a queue in Haskell (and this probably deserves its own blog post) but Data.Sequence seems to give good performance for minimal effort (and in any case, as we’ll see, it’s not the performance bottleneck here). We use a pair of HashMaps to represent the level and parent maps.

data BFSState v =
BS { level :: HashMap v Int, parent :: HashMap v v, queue :: Seq v }

Given a list of starting vertices, we can create an initial state, with a queue containing the starting vertices and all of them set to level 0.

initBFSState :: (Eq v, Hashable v) => [v] -> BFSState v
initBFSState vs = BS (HM.fromList (map (,0) vs)) HM.empty (Seq.fromList vs)

Now, here is our imeplementation of BFS, using the API discussed previously: it takes a list of starting vertices, a function giving the neighbors of each vertex, and a function identifying “target vertices” (so we can stop early), and returns a BFSResult record. We create an initial state, run bfsStep as much as possible, and convert the end state into a result.

bfs :: forall v. (Eq v, Hashable v) => [v] -> (v -> [v]) -> (v -> Bool) -> BFSResult v
bfs vs next goal = toResult $exhaust bfsStep (initBFSState vs) where Converting the final BFSState into a BFSResult is easy: just return functions that do a lookup into the relevant map.  toResult BS{..} = BFSR (HM.lookup level) (HM.lookup parent) To do a single step of BFS, try to remove the next vertex v from the queue. If the queue is empty, or the next vertex is a goal vertex, return Nothing to signal that we are done.  bfsStep st@BS{..} = case Seq.viewl queue of EmptyL -> Nothing v :< q' | goal v -> Nothing Otherwise, use the next function to find the neighbors of v, keep only those we haven’t encountered before (i.e. those which are not keys in the level map), and use each one to update the BFS state (being sure to first set the queue to the new one with v removed).  | otherwise -> v >$> next >>> filter (not . (HM.member level)) >>>
foldl' (upd v) (st{queue=q'}) >>> Just

To update the BFS state based on a newly visited vertex, we record its parent, insert it into the level map with a level one greater than its parent, and add it to the end of the queue.

    upd p BS{..} v = BS
(HM.insert v l level)
(HM.insert v p parent)
(queue |> v)
where
l = level!p + 1

And that’s it! This is good enough to solve many BFS problems on Open Kattis, such as Breaking Bad, ARMPIT Computations, and Folding a Cube. (I will leave you the pleasure of solving these problems yourself; I am especially fond of my Haskell solution to Folding a Cube.)

Unfortunately, it is not fast enough to solve Modulo Solitaire, which I picked specifically because it seems to be one of the most computationally demanding BFS problems I’ve seen. My solution using this HashMap-based implementation solves a bunch of initial test cases, but exceeds the 2 second time limit on one of the later test cases. Next time, I’ll show how to adapt this into an even faster implementation which is actually fast enough to solve Modulo Solitaire.

Posted in competitive programming, haskell | Tagged , , , , , | 4 Comments

Competitive programming in Haskell: BFS, part 2 (alternative APIs)

In my last post, I showed how we can solve Modulo Solitaire (and hopefully other BFS problems as well) using a certain API for BFS, which returns two functions: one, level :: v -> Maybe Int, gives the level (i.e. length of a shortest path to) of each vertex, and parent :: v -> Maybe v gives the parent of each vertex in the BFS forest. Before showing an implementation, I wanted to talk a bit more about this API and why I chose it.

In particular, Andrey Mokhov left a comment on my previous post with some alternative APIs:

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

Of course, as Andrey notes, AdjacencyMap is actually a reified graph data structure, which we don’t want here, but that’s not essential; presumably the AdjacencyMap arguments in Andrey’s functions could easily be replaced by an implicit graph description instead. (Note that an API requiring an implicit representation is strictly more powerful, since if you have an explicit representation you can always just pass in a function which does lookups into your explicit representation.) However, Andrey raises a good point. Both these APIs return information which is not immediately available from my API.

• bfsForest returns an actual forest we can traverse, giving the children of each node. My API only returns a parent function which gives the parent of each node. These contain equivalent information, however, and we can convert back and forth efficiently (where by “efficiently” in this context I mean “in $O(n \lg n)$ time or better”) as long as we have a list of all vertices. To convert from a Forest to a parent function, just traverse the forest and remember all the parent-child pairs we see, building e.g. a Map that can be used for lookup. To convert back, first iterate over the list of all vertices, find the parent of each, and build an inverse mapping from parents to sets of children. If we want to proceed to building an actual Forest data structure, we can unfold one via repeated lookups into our child mapping.

However, I would argue that in typical applications, having the parent function is more useful than having a Forest. For example, the parent function allows us to efficiently answer common, classic queries such as “Is vertex v reachable from vertex s?” and “What is a shortest path from s to v?” Answering these questions with a Forest would require traversing the entire Forest to look for the target vertex v.

• bfs returns a list of levels: that is, the first list is the starting vertices, the next list is all vertices one step away from any starting vertex, the next list is all vertices two steps away, and so on. Again, given a list of all vertices, we can recover a list of levels from the level function: just traverse the list of all vertices, looking up the level of each and adding it to an appropriate mapping from levels to sets of vertices. Converting in the other direction is easy as well.

A level list lets us efficiently answer a queries such as “how many vertices are exactly 5 steps away from s”?, whereas with the level function we can efficiently answer queries such as “What is the length of a shortest path from s to v?” In practice, the latter form of query seems more common.

In the final version of this BFS API, I will probably include some functions to recover forests and level sets as described above. Some benchmarking will be needed to see whether it’s more efficient to recover them after the fact or to actually keep track of them along the way.

Posted in competitive programming, haskell | Tagged , , , , | 6 Comments

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.

Posted in competitive programming, haskell | Tagged , , , , | 5 Comments

Swarm: a lot can happen in a week

It’s been about a week since I put out an announcement and call for collaboration on a new game, Swarm. Since then, the response has been fantastic: lots of people have tried it out, a few have even streamed themselves playing it on Twitch, and there has been lots of development activity.

There’s still a long, long way to go before the game comes anywhere close to the vision for it, but we’ve made great progress! Some notable new features added since the initial announcement include:

• New scan, upload, and install commands

• Semicolons are no longer required beetween consecutive defs

• Basic help panel, and panel shortcut keys

• Dramatically reduced CPU usage when idle

• An overhaul of parsing and pretty-printing of constants (makes adding new constants easier, and an important prerequisite for saving definitions and games)

• Better handling of water (you can make curry now)!

A couple more exciting things in progress that should land very soon:

• ASCII art recipes

• Basic editor integration via LSP, so you can write Swarm programs in your favorite editor with automatically highlighted syntax and type errors.

And of course there are many other exciting things planned or in the works. Come join us!

Posted in haskell, projects | Tagged , , , , | 1 Comment

Swarm: preview and call for collaboration

For about a month now I have been working on building a game1, tentatively titled Swarm. It’s nowhere near finished, but it has at least reached a point where I’m not embarrassed to show it off. I would love to hear feedback, and I would especially love to have others contribute! Read on for more details.

Swarm is a 2D tile-based resource gathering game, but with a twist: the only way you can interact with the world is by building and programming robots. And there’s another twist: the kinds of commands your robots can execute, and the kinds of programming language features they can interpret, depends on what devices they have installed; and you can create new devices only by gathering resources. So you start out with only very basic capabilities and have to bootstrap your way into more sophisticated forms of exploration and resource collection.

I guess you could say it’s kind of like a cross between Minecraft, Factorio, and Karel the Robot, but with a much cooler programming language (lambda calculus + polymorphism + recursion + exceptions + a command monad for first-class imperative programs + a bunch of other stuff).

The game is far from complete, and especially needs a lot more depth in terms of the kinds of devices and levels of abstraction you can build. But for me at least, it has already crossed the line into something that is actually somewhat fun to play.

If it sounds interesting to you, give it a spin! Take a look at the README and the tutorial. If you’re interested in contributing to development, check out the CONTRIBUTING file and the GitHub issue tracker, which I have populated with a plethora of tasks of varying difficulty. This could be a great project to contribute to especially if you’re relatively new to Haskell; I try to keep everything well-organized and well-commented, and am happy to help guide new contributors.

1. Can you tell I am on sabbatical?↩︎

Posted in haskell, projects | Tagged , , , , | 7 Comments