If you’re only interested in seeing or playing the game, you can find it on my GitHub.

The occasion

The Haskell Tiny Game Jam is a game jam which challenges participants to write a video game in Haskell using 10 lines of 80 characters. I happen to love Haskell and code golf (abusing a programming language to produce disgustingly short code for fun) so I decided to enter the Feb ‘23 jam.

My journey

My game is called Call-by-push-block. It’s a Sokoban, or block-pushing game, where you take a lambda code golfing (“golfing” here is meant a little more literally).

I started with an initial game that had player movement, pushing a single block, and a single test level. I already had employed a few code golfing tricks, but the code stood at 40 lines and was reasonably legible.

Many ugly hacks later, I ended up with a game that also included a level and score counter, undoing, resetting, pushing arbitrarily many blocks, 14 levels, and some other features to be discovered by the player. It stands at exactly 10 lines of 80 characters. It is disgusting and I’m fiercely proud of it.

n="噞㋪㛃䚬摣ۜ㝜ቲ㜑昫⫛㍋勓ㅋ⩞䤤㱪㳃䊩㓛⤤㳝ᙪ㛅Ⳝ㩛㚙㛦䥢㔬㜞㋖⛍㣛戛㙉ኛ㙎ኛ孶抭安Ჭ㱉㚛㛛ᰛ⯙瞎㤅⛛牶䢯㛛㣠⭤㳳㑌䜜㚿㛛䜓缣㛚≣㶳ㅬ㛜㛛䛚㛛暛㛣⛛䤤䣤"
e('λ':c)|(a,b)<-span(>'n')c=u(u a#m 1 b)%e(y b);e(c:d)=c:e d;e l=l;k="λ.";m=take
v(x:_)=c x`mod`7;v _=0;l=print;s=[]:s;c=fromEnum;i="\no .#_λ+";y=drop 1;(%)=(++)
e&0=u.t;f&_=f;p=putStr;(1?f)x=z x;(5?f)x=y x%z x%z x;(i?f)x=(f&i$r e$f$head x):x
r=map;main=print=<<(mapM g.zip[1..].r(pure.words).lines$r(i!!).m 5.w=<<r c(n%x))
g(k,o)|any(elem '_')$head o=do{k!o;p b;i<-v<$>d;g(k,i?([t.u,t,id,t,t,t,r u]!!i)$
o)};g(k,x)=a x<$k!x<*p"↩"<*d;t=foldr(zipWith(:))s;z=m 1.u;w n=n`mod`8:w(n`div`8)
n!x@(s:_)=p"\^[cLvl "*>l n*>l(a x)*>p(unlines s);d=getLine;(_:r)#""=r%k;_#""="."
n#"."=n%k;(_:r)#"+"='.':r%k;_#"+"="..";('o':r)#"_"='O':r%k;l#x=x%l%"λ";u=reverse
a=length;b="λ:wasd 🔄:x 🔙:u\n";x="ᴔ翉䕿䤤䜣㛚㣛㢛䛳۳四⛛竛⛛笛⛛禣✤ባ⦉档✌䡣✌ቴ✙䤣✴㛛ۣ廛⛟盻⟛㛛⛛䌜⣡㞛⛳㣣✜幜⣏㛜ࣛ"

In this post, I’ll give you several tips that you can use to reduce your own Sokoban game to a mess of letters and operators like the one above.

(Update 03/10/23: This code is now out of date, but some of the hacks refer to it so I’m leaving it as-is. The submitted version of can be found on my GitHub or the jam page)

Forgo any and all style

Do you like descriptive function names?

resolveMove index modifyGrid = undoMove modifyGrid index . map move . head $ gameGrid

Too bad, it’s too many characters.

r i f = u f i . o m . head $ x

Think Haskell has too many arcane operators? Sorry, it’s shorter.

i?f = (f&i) . o m . head $ x

Does this disgust you yet? It should, because we have to put parens around i&f to prevent GHC from getting confused by operator precedence. And someone left in spaces!!

i?f=f&i$o m$head$x

Much better. Now slap a semicolon on it and jam it in somewhere.

(My challenge to you for this tip and the other ones that have code: see if you can find the actual source code corresponding to its example. Just like with the Tiny Game Jam, there is no prize other than your self-satisfaction.)

Think like a C Programmer

My game has 6 controls: wasd for directional movement, x for resetting, and u for undoing. The way I would properly approach handling inputs would be something like

data Input = Up | Left -- ...

charToInput c = case c of
  'w' -> Up
  'a' -> Left
  -- ...
  'u' -> Undo

gameLoop gameGrid = do
  c <- getChar
  handleInput (charToInput c) gameGrid

We’re already over 10 lines and I’m trying to be terse in my example. Not only that, the case keyword and each -> takes up so much space.

Instead, we can think like C programmers and use the Enum instance for Char, for which fromEnum produces a char code. Then we just need to find a modulus where wasdxu are unique and we can use fromEnum c in that modulus to index into a list of commands. Luckily for us, 7 gives unique values.

charToInput c = fromEnum c `mod` 7

gameLoop gameGrid = do
  c <- getChar
  let command = [moveRight, moveLeft, ...] !! charToInput c
  command gameGrid

“Hold on,” you might stop me, “What about the other index mod 7 that none of wasdxu map to?” Good question, just put the smallest variable you can get to type check there. All keys will do something, but we will only tell the players what 6 of them do.

(Update 03/10/23: I ended up using that last character to implement a cheat code.)

Abuse loopholes

There are 610 characters used across all the levels in Call-by-push-block. A careful reader will observe that there are not 610 characters worth of strings in my code. So where do they live? In the horrifying Unicode strings on the first and last lines.

I need 8 unique characters for my levels: 6 for tiles and 2 for separators. A limited tileset like this allows you to smush 5¹ tiles into a single Unicode character. The relevant loophole here is that the judges count characters, not bytes², so this cuts the levels’ footprint by a factor of 5.

Here’s how you can encode your levels. Start with the characters list. First, map each tile to a number between 0 and 7. Now you have a list of digits in base 8. Next, take 5 digits at a time, interpret them as a number in base 8, and convert to decimal. Now you have a list of decimal numbers that is 1/5 the size of the original. Interpret the decimal numbers as Unicode characters and you’re done.

One small wrinkle: GHC doesn’t allow raw strings and requires strings to contain printable Unicode. To work around this, I simply iterated over every possible permutation of digits to assign my tiles, encoded my levels, and checked the characters in each encoding against GHC.Unicode.isPrint. There were a bunch of printable encodings so I picked one that had funny emoji in it.

With this trick, you can go from half of a single level

x="oλoo.... ooλλ_____ oλooλ____ λooooλ... ........."

to a little over two much bigger levels

x="ᴔ翉䕿䤤䜣㛚㣛㢛䛳۳四⛛竛⛛笛⛛禣✤ባ⦉档✌䡣✌ቴ✙䤣✴㛛ۣ廛⛟盻⟛㛛⛛䌜⣡㞛⛳㣣✜幜⣏㛜ࣛ"

Even though it doesn’t look it, the latter is fewer characters, too.

If this tip would actually be helpful to your own tiny game, then you can check out the code I wrote for it (warning: it is gross and uncommented) and refer to the decoding function in my golfed code, which of writing is named w (I shouldn’t need to warn you about this one).

Solve NP-Hard problems by hand

A Haskell file is basically just a bunch of variable declarations. The same is true for a very golfed one, it’s just harder to make them out. I count about 30 variables in my game.

Often when golfing you can reduce the overall character count by moving around some logic, resulting in one line being 2 characters over and another 5 under, for a net gain of 3 characters.

What do you do after this? Rearrange the variables so that all of the lines are within the character limit.

Sound hard? That’s because it’s NP-Hard.³ It’s an instance of the Bin packing problem where the items are variables, sizes are their lengths, and bins are each of the 10 lines. Have fun and don’t forget that you need semicolons to separate your variables!⁴

Only move right

The grid of tiles in my game is just a list of of list of Chars. An unfortunate downside of Haskell lists being linked lists is that it is much harder to move vertically in the grid than it is to move horizontally. Should you encode your grid the same way, there is good news! All you need to do is write code that moves the player to the right.

moveRight :: [[Char]] -> [[Char]]

Need to move to the left? Reverse all of the rows first, move right, then unreverse them.

moveLeft = map reverse . moveRight . map reverse

Need to move down? Transpose the grid, move right, then untranspose it.

moveDown = transpose . moveRight . transpose

Barring moving up (which I have conveniently omitted), we can abstract a pattern out:

move dir = transformation . moveRight . transformation
  where
    -- 0 = right, 1 = left, 2 = down, 3 = up??? >:(
    transformation = [id, map reverse, transpose, undefined] !! dir

Maybe smart math people can figure out a way to do upward movement that doesn’t require annoying special casing. If you figure it out, don’t tell me since it means I’ll have to make more levels. With the special casing for moving up, you’ll end up with something like

move dir = undo dir transformation . moveRight . transformation
  where
    -- 0 = right, 1 = left, 2 = down, 3 = up
    transformation = [id, map reverse, transpose, transpose . reverse] !! dir

undo 3 _ = reverse . transpose -- special case for undoing 'transpose . reverse'
undo _ f = f                   -- everything else undoes itself

Ask HLS

The Haskell Language Server is a helpful tool for doing proper Haskell development. It can also help with improper development if it’s not busy freaking out about all of your missing type signatures.

Throughout the course of golfing, you might end up with code like

(l!!x)$y

Spot the mistake? You don’t need to! HLS will helpfully report

Redundant $ found,
  Found: (l !! x) $ y
  Why not: (l !! x) y

Make sure to ignore the spaces in its suggestions though, those are for proper developers.

Look how hard at work HLS is. Does proper code even need type signatures?

Forget what you know

It’s often said that authors have difficulty finding flaws in their own works because they know them so well. Empty your mind and let inscrutable code be your superpower.

Ignore all but the single function you need to update. Once it’s done and your code now has a bug, you’ll likely find spots you missed as you mentally trace the haphazard path your code follows when it executes. These spots might be things like

• A short alias for a function that in fact makes your code longer
• A completely unused function (I guess HLS was too busy trying to fill in type signatures to inform me)
• Two of the same function written with different names

Proof that the method works: I shaved three characters off while trying to understand code I refer to in this blog post.

Kill many birds with one stone

Originally, my game did not have an undo. Adding undo was the number two request⁵ from my playtesters. I also wanted to add a move counter to give some replayability since my game didn’t utilize randomness.

I initially dismissed my playtesters’ requests as unreasonable and my own as unnecessary. Then I forgot how to solve a level I was pretty sure was solvable and decided adding an undo was a good idea. Unfortunately I was already at the character cap. What allowed me to add both undoing and move tracking was refactoring how I reset the game grid.

My game loop took a tuple containing the current grid and the initial grid. Resetting replaced the grid with the initial grid.

handleInput (grid, initialGrid) Reset = (initialGrid, initialGrid)
handleInput (grid, initialGrid) input = (move grid input, initialGrid)

Let’s forget about resetting for a second and change this to just support undoing. Instead of keeping track of the initialGrid, we can keep a list of every past grid. Then if we want to undo, we just replace the current grid with the grid that came before it. When we make any other move, we now we have to add the current grid to the list of past grids.

handleInput (grid, (pastGrid:olderGrids)) Undo = (pastGrids, olderGrids)
handleInput (grid, pastGrids) input            = (move grid input, grid:pastGrids)

This works well, but there’s way too many parens and other stuff going on. It’s fewer characters if we put the current grid onto the front of the list.

handleInput (grid:pastGrids) Undo  = pastGrids
handleInput (grid:pastGrids) input = move grid input : grid : pastGrids

Now for resetting. The cruel game dev would just say “reset = undo many times.” I like to think I’m not that cruel. Fortunately, we can reset without too much trouble by removing everything except the last element.

handleInput grids Reset = [last grids]

Remember how I said I wanted to add a move counter? Before, this would require threading the counter through my game loop, which would take a bunch more characters. Now with the new list-based format, the number of moves is just the length of grids. Well, technically the length of grids minus one since the initial grid doesn’t count toward a move.⁶

The astute reader will observe that there are few issues with this implementation. The first is that this function is partial and will crash the game if you try to undo from the initial state. The second is that the move score counter doesn’t count undos because undoing decreases the length of the list. We can fix both of these by just throwing some copies⁷ of the initial grid onto the end of the grids list whenever we undo.

handleInput grids Undo     = tail grids ++ initialGrid grids ++ initialGrid grids
handleInput grids Reset    = initialGrid grids
handleInput (grid:pastGrids) input = move grid input : grid : pastGrids

initialGrid grids = [last grids]

It’s still technically partial but who cares other than HLS?

Motivate yourself

I spent a lot of time staring at the garbled mess that is 809 characters of the tersest possible Haskell you can write using Prelude. It takes willpower to keep searching for more ways to cut another characters off. Here are three possible motivations.

Create levels with reckless abandon

A thoughtful tiny game jam developer might design levels with a character count in mind. I just sort of made levels until I felt I couldn’t come up with any more interesting ideas. At that point, I ended up about 20 characters in the red. So I golfed 20 characters off.

The tile calculus

I’m used to golfing 30-character programs where removing a single character is a pretty big accomplishment. In an 809-character program, the value of a single character can be harder to appreciate. That is, until I implemented tile compression.

If you compress your tiles, suddenly the two ’e’s in the word “Level” represent a quarter of a level. The four characters you save by replacing “Reset” with “🔄” are another half.

With this mindset, even a cutting a single character could result in a small level that teaches how a new mechanic works.

Rick Roll the judges

Did you happen to read the first column of my game’s source?

As I was writing up this post, I noticed that almost every single line began with a variable. At a first glance, “never gonna” wouldn’t work because variables need to be unique. I realized, however, that I was very close to being able to rearrange some infix function definitions so that the variable bound was at the beginning of the line. This would allow me to shadow an existing variable and therefore duplicate a letter.

To do this would require me rearranging lines and golfing at least one character off of an infix function. So, well, I set out to do that and in the process I actually discovered some more tricks to cut off three characters total.

Never underestimate the creativity born out of desire to make a stupid joke.

In conclusion

Although code golfing is an ultimately frivilous endeavor, I had a lot of fun trying to fit as much as I could into my game and I’m pleased with how it turned out. I especially enjoyed asking my friends, “Hey, do you want to play this game I made?” and just sending them 10 lines of nonsense that somehow spits out a video game when fed into GHC. While I don’t expect you to ever make (serious) use of these tips, I hope you liked them.

Call-by-push-block can be found as a submission on the Feb ‘23 Haskell Tiny Game Jam. And if you enjoyed this content, be sure to check out the other tiny games there too!

Detailed instructions on running Call-by-push-block (including in your browser) can be found on my GitHub.

Addendum 1

After writing this blog post, I got some interesting comments that inspired the responses below.

Comments

My website is janky and doesn’t support commenting (sorry!). If you’d like to leave a comment, feel free to do so on Reddit or Lobste.rs.

Being able to undo past resets

In a comment on Lobste.rs, hwayne suggested making undos work across resets. For example, reset then undo should bring you back to the state you were in originally. I replied with a 2 character change to my code to support it. In that reply, I challenge you to find where I made the change, but here I’ll explain what the change is.

I described in Kill many birds with one stone how resetting replaces the grid list with the initial grid.

handleInput grids Reset = [last grids]

In order to support undos across resets, we can instead put the initial grid at the front of the list.

handleInput grids Reset = last grids : grids

It’s really that easy.

Unfortunately, it does have a cost: resets no longer reset the score. Instead, they’re counted the same as any other move. This goes against my game developer philosophy, but I might end up changing my mind and implementing this feature in my submission. Thanks, hwayne!

(Ab)use obscure typeclass instances

In a comment on Reddit, LSLeary suggested an alternate method for dealing with the edge case in Only move right. We both weren’t able to figure out a way to golf it shorter than what I had, but the mention of abstract algebra and function composition got me thinking of the Semigroup instance on functions.

First, what’s a semigroup? Basically if a type a has a Semigroup instance, that means there’s an operation that combines two as and gives you another a

(<>) :: a -> a -> a

It also has to be associative, but it’s fine if you don’t know what that means; this isn’t math class. Nor do you need to know why we care about semigroups.

One semigroup is the list type [a]. Any guesses as to what its operation of type [a] -> [a] -> [a] is?

There aren’t a lot, so hopefully you guessed concatenation.⁸ For lists, <> and ++ are the same thing. It turns out there are a bunch of Semigroup instances, but since its inclusion in Prelude people basically just use it as a cooler-looking concatenation.⁹

So let’s talk about an instance people don’t (and frankly shouldn’t) use it for: the instance on functions. The type we care about is a -> [b] so I’m going to simplify it to that

instance Semigroup (a -> [b]) where
  f <> g = \x -> f x <> g x

So we can combine two functions f and g into a new function that feeds its input to both f and g and then concatenates the lists they make. Now if you struggle to see the utility of this, you aren’t alone. Why does it exist? I would say because it can? I mean it’s a lawful Semigroup. I won’t complain too much since it lets me write shorter code.

I lied a bit when I described how handleInput works. The actual code incorporates the “only move right” technique like so, where t is the transformation

handleInput Reset t grids = initialGrid grids
handleInput Undo  t grids = tail grids ++ initialGrid grids ++ initialGrid grids
handleInput input t (grid:pastGrids) = (undo input t . moveRight . t $ grid) : pastGrids

initialGrid grids = [last grids]

I would really like to remove a variable here (remember, infix is shorter), and grids is an especially good candidate since it’s used a lot. Let’s start with the lowest hanging fruit.

handleInput Reset t = initialGrid

We just remove the grids variable because defining f x = initialGrid x is the same thing as f = initialGrid.¹⁰ In the Undo case, we can now exploit the aforementioned Semigroup instance no one in their right mind should use

handleInput Undo t = tail <> initialGrid <> initialGrid

For the final case, let’s start by trying something that won’t type check:

handleInput input t  = undo input t . moveRight . t . head <> id

id is the identity function, which means the right side of the <> becomes grids. We have to add head on the left side because we no longer can pattern match on grids to extract the first grid. This doesn’t type check, though, because the left side produces a [[Char]] (our grid type) and the right side produces a [[[Char]]] (our grids type). For <> to work, the types on either side have to be the same Semigroup.

One more obscure instance to the rescue: the Applicative instance on lists.¹¹ I won’t explain this one in-depth since the only part you need to know is that for this instance

pure :: a -> [a]
pure a = [a]

So we can fix the type error by throwing in a pure and if it type checks it must therefore work.

handleInput input f  = pure . undo input f . moveRight . f . head <> id

In sum, this removes nine whole characters. While I did explicitly ask that people not help me golf more, I’ll make an exception here because LSLeary was so polite and I like using typeclass instances that no one should really should.

Addendum 2: Post-submission

This addendum was added in an update on 03/10/23.

There were a few other things that changed between the code I wrote and the code I submitted. As I was getting things ready to submit, I ended up golfing another 20+ characters (I lost count) and of course I had to not waste them. So now I have some more tips and comments.

Keep track of your requirements

Several big golfs I made at the end were due to assumptions I made that forced me to not write code in a shorter way.

An example would be parentheses. Sometimes I had parentheses around an expression because of operator precedence, but I then removed the operator and forgot about the parentheses. HLS can often help with that, but there still are instances where I would discover unnecessary parens left in.

If I were to do this again, I would write down whatever assumptions are causing me to not take easy golfs. To a degree, though, there are just so many decisions and moving pieces that if you are satisfied with anything less than perfection it ought to be much more sufficient to reread your code every so often.

Adding a cheat code

Let me set a scene for you. It’s the night before the jam ends and you’re sitting in front of code you’ve lovingly hacked to fit into 809 characters. Except, there’s a problem. It’s not perfectly 809 characters, it’s actually shorter than that. If you’re me, the thought running through your head can be appropriately summarized as

aaaaaaaaaaaaaaaaaaaaaaaaaaaa.¹²

I had put together a fifteenth level despite telling myself I would never design another sokoban level for - well - at least longer than two days. I had fit it in just right and kept my Rick Roll. But that stupid golfy part of my brain had to find another significant reduction.

Fortunately, I did not have to subject myself to making a sixteenth level. You see, my playtesters, lovely people that they were, were rightly a little peeved if I asked them to just replay all of the levels when I made a new version. So in the versions I sent them, I would add a cheat code to skip a level. And because I was adding it to horribly-golfed code, it ended up being a very small change. Funny how that works.

By this point I’ve talked enough about the implementation details that you hopefully know what’s going on, so I’ll be brief on the recap: what you need to recall is that the main game loop takes a lists of grids as the game state.

The way that I decide if a level is incomplete is to check for any holes (_) in the current (front) grid. When a block is pushed into a it, a hole becomes a O, so we can just do a search for the hole character. Here’s a simplified version of the gameLoop¹³:

gameLoop grids | any (elem '_') $ head grids = getAndHandleInput grids
               | 0<3 = returnScore grids

Note that we call the gameLoop separately on each starting grid and collect the scores from each, so in the second case we don’t need any logic to advance to the next level.

Can you think of any particularly hacky ways to transform grids in handleInput to skip to the next level? Here’s mine.

handleInput SkipLevel _f = pure [[]]

You are probably rightfully scratching your head so let’s unpack this.

handleInput, as you may recall from the previous addendum, returns a function that modifies grids. For this case we can ignore its second argument.

pure [[]] is a function. It’s a one-character shorter way of writing const [[]], which is a function that ignores its argument and returns [[]] (see footnote 11).

So in plain English, when we want to skip a level, we change grids to be [[]]. What happens when we pass [[]] to gameLoop? We evaluate

  any (elem '_') $ head [[]]
= any (elem '_') []
= False

and therefore skip the first branch and reach the goToNextLevel branch. You might have been curious as to why it was pure [[]] and not pure [], and the answer to this now should be clear (hint: what is head []?).

This is great and - importantly - short, so we’re done right?

Well, no. Because there are two problems. One, this means that score is pointless because you can get as low of a score as you want with no penalty by skipping. Two, [[]] is two characters more than [] and it really feels like we should just be able to return the empty list.

Fortunately, this is solvable without adding too many more characters. We’ll recover two characters from handleInput by defining it now as

handleInput SkipLevel _f = pure []

and at the cost of a few extra characters,¹⁴ we’ll punish those dirty cheaters.

gameLoop grids | head grids == [] = pure 0
               | any (elem '_') $ head grids = getAndHandleInput grids
               | 0<3 = returnScore grids

Since gameLoop returns the score (in IO), we just hardcode it as as pure 0.

An observant reader might ask, “Why 0 if a lower score is better?” Because of technical limitations, the score starts at 1, so a score of 0 is impossible in legitimate play and therefore indicative of cheating.¹⁵

Now that we’re done, we need to pick a key to represent our skip level command. I was relieved that I actually had a leftover command in my input mappings because mod 6 didn’t work.

I had been lucky that after mapping wasd to movement, I could map reset to x and undo to u. I was not about to add more characters to change the modulus or otherwise shift the mappings, so let’s take a look at what I had at my disposal for the skip level key, which needs to be equal to 4 mod 7.

  [char | code <- [32..127], code `mod` 7 == 4, let char = toEnum code :: Char]
= " '.5<CJQX_fmt{"

Not exactly the greatest selection. So I chose to again do what should be its own tip by now: lie to the player.

I instruct players to type verbatim

Cheat Code

to skip the level. This works because I have to read an entire line to take inputs (there’s no way I know of to take inputs unbuffered in Prelude). So I just take the first character of the line and use that as the input. And C is one of the characters that maps to level skip.