Sokoban 14

[Dorothy Gouldie]

Twoyears ago, I held the CIS194 minicourse on Haskell at the University of Pennsylvania. In that installment of the course, I changed the first four weeks to teach the basics of Haskell using the online Haskell environment CodeWorld, and lead the students towards implementing the game Sokoban.

As it is customary for CIS194, I put my lecture notes and exercises online, and this has been used as a learning resources by people from all over the world. But since I have left the University of Pennsylvania, I lost the ability to update the text, and as the CodeWorld API has evolved, some of the examples and exercises no longer work.

So if you feel like learning Haskell without worrying about local installation, and while creating a reasonably fun game, head over to -via-sokoban.nomeata.de/ and get started! Improvements can now also be contributed at -via-sokoban.

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, butthe code stood at 40 lines and was reasonably legible.

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

Instead, we can think like C programmers and use theEnuminstance for Char, for which fromEnum produces a char code. Then we justneed to find a modulus where wasdxu are unique and we can use fromEnum c inthat modulus to index into a list of commands. Luckily for us, 7 gives uniquevalues.

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

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

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

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

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

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

An example would be parentheses. Sometimes I had parentheses around anexpression because of operator precedence, but I then removed the operator andforgot about the parentheses. HLS can often help with that, butthere 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 causingme to not take easy golfs. To a degree, though, there are just so many decisionsand moving pieces that if you are satisfied with anything less than perfectionit ought to be much more sufficient to reread your code every sooften.

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

Fortunately, I did not have to subject myself to making a sixteenth level. Yousee, my playtesters, lovely people that they were, were rightly a little peevedif I asked them to just replay all of the levels when I made a new version. Soin the versions I sent them, I would add a cheat code to skip a level. Andbecause I was adding it to horribly-golfed code, it ended up being a very smallchange. Funny how that works.

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

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

The classic sokoban rules are generalized to allow multiple sokaban. Squares containing sokoban may be proceded by an integer sokoban number. If multiple sokoban appear but are unnumbered, then they are assumed to be numbered in the order they appear. The range of numbered sokoban must not have gaps. Boxes may be likewise preceded by an integer box number and are otherwise numbered in the order in which they appear.

The visualizer also accepts an alternative puzzle format where the file begins with the number of rows, a comma, the number of columns, a comma, and then a series of strings each surrounded by double quotes and separated by white space that represent the rows.

Locations are specifed by row and column for the m command and by cell number for the M command. Row, column, and cell numbers start at 0. Cells are numbered from location [0,0] right to left and top to bottom, so that row = floor(cell / number columns)

column = cell mod number columns Note the final comma that appears after the last argument to m or M. Steps may be proceeded by an integer identifying the sokoban. If no integer appears sokoban 1 is selected.

The b commands first sends the sokoban on the shortest path to the appropriate side of the box and then pushes it in the specified direction. The m and M commands send the sokoban on the shortest path to the appropriate side of the box that is in the indicated location and then pushes the box to the new location.

Adding new example puzzles and solutions: Suppose the name of the new example is MyBigPuzzle. Add the puzzle file named MyBigPuzzle.txt to the Examples/ directory. Add the solution file named MyBigPuzzle-sol.txt to t he Examples/ directory. Edit the file exampleFiles.txt and insert the string MyBigPuzzle at the end of the file.

3a8082e126