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.

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.

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 51 tiles into a single Unicode character. The relevant loophole here is that the judges count characters, not bytes2, 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 helptful 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.3 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!4

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 request5 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 : grids

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.6

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 copies7 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 : grids

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.

If you’d like to give it a try, you can find Call-by-push-block on my GitHub.

Addendum

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!