Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Squeezing a Sokoban game into 10 lines of Haskell (cole-k.com)
169 points by ufo on Feb 24, 2023 | hide | past | favorite | 31 comments


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

Don't read this, then (from a 2048 game instead of Sokoban, but same principle): https://github.com/darius/cant/blob/master/examples/games/20...

As long as I'm commenting, here are some links to other Sokobans I thought were fun (listed in the source code to mine). The sed one is nuts -- I had no idea it could do that: https://github.com/darius/cant/blob/master/examples/games/so...


I couldn't resist and clicked your link, but thankfully it is early and I couldn't quite understand how to port it to the `f . moveRight . f` format.

So really it is a shame that nothing can be done about golfing this further and I will be content knowing that... is what I'd like to say if not for the several [1] characters [2] I have at my disposal for a last level.

Thank you for sharing though, I also was amazed by the sed one. And just to make it clear since sometimes these things don't communicate well over the internet, I'm being a little facetious here: if you actually want to spell it out for me I'm not going to be upset (but if you don't, I'm also not going to be upset :) ).

[1] https://news.ycombinator.com/item?id=34924577

[2] https://reddit.com/r/haskell/comments/11953ov/squeezing_a_so...


Yeah, I wanted to stay with your jokey tone.

I was thinking along the same line as the parent comment at your link [2] -- really, I was too eager to play know-it-all.

Just to explain the difference that may be unclear because of the language: the move functions I linked to call an `each` function which is like Haskell's `map`, only because these move functions all return a list of board states, for the sake of animating the moves in the 2048 game.

These all work in terms of `left` in my code, vs. `moveRight` in yours. So the function that'd cause trouble is `down` instead of `moveUp`, if I'd tried to organize it exactly the way you did, versus just generally basing it on conjugation. I didn't try to golf this version, and I sure wouldn't bet on being able to as much as you did. Respect.


I thought of group theory when I read this. The faf' pattern comes up quite a lot and is called conjugation. https://en.wikipedia.org/wiki/Conjugacy_class#Conjugacy_as_g...


Your second link is the same as the first.


Thanks, oops, fixed.


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

This is less of a challenge for IOCCC entries like my [1] where I wanted the variables & constants to spell out the language it interprets:

       Int L[A],m,b,*D=A,
        *c,*a=L,C,*U=L,u;s
as C doesn't care about capitalization, whereas Haskell reserves upper case for types and constructors.

[1] https://www.ioccc.org/2012/tromp/tromp.c


I thought your name looked familiar! I recall being very impressed with your 1989[1] entry when I came across the ioccc in the mid 90s.

[1] https://www.ioccc.org/years.html#1989_tromp


That one was co-authored with Freek Wiedijk, who curiously also went on to win a "Most Functional" award [1].

[1] https://www.ioccc.org/years.html#2014_wiedijk


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

This made my morning.


The title of the paragraph, "Think like a C Programmer", is absolutely fitting too


> It stands at exactly 10 lines of 80 characters.

Awesome! Sometimes people allow themselves to use unlimited length lines when shortening the number of lines. But this is good, 80 chars max per line is how it should be when talking about obfuscated code which has been crammed into a low number of lines.


It would've certainly been nice to avoid playing Bin Packing, but alas this is just the rules of the game jam.


So this is a fun read and probably also lots of fun to write.

One fact that does not get enough mention though is that, regardless of the code golfing results, Haskell programs have the habit of being exceptionally concise even if you don't try to write short code.


Part of it (but certainly not all of it) is because of all the funny instances hanging around. I'm able to exploit the Semigroup b => (a -> Semigroup b) instance in a WIP version for example. And using (<*>) on the Applicative instance of (-> r) is a favorite of mine.


... To be super ridiculously over-the-top pedantic... That Applicative instance is on ((->) r). If you could actually do type-level sections, that'd be (r ->). But type-level sections are the same as type-level lambdas, and they would break a lot about Haskell's type system so they don't exist.

All of which is to say, great work.


Right you are, I never remember the proper name for the instance. I only use it to spaghettify code.


I am curious if there are languages that would be able to use the same techniques but beat the number of chars. Code golfers often use Ruby due to what the syntax allows.

Also, a shameless plug, but if you are interested in a Sokoban like game, you might enjoy Pathology (formerly called Psychopath built in 2005). It is a 2d block pushing game where the goal is to go from Point A to Point B in shortest amount of steps. There's a level editor (thousands of levels) multiplayer, and active community (Many folks from the Sokoban online community play too)

https://pathology.gg


At least on the Code Golf Stack Exchange, I see a lot of people using esolangs for golfing (two random examples: Jelly [1] and O5AB1E [2]). I expect that it could be a line or two shorter at least with a change of language. As I recall some of the golfing langs also have pretty sophisticated compression techniques for strings, although they might be optimized for dictionary words. Careful distinction: they are all optimizing for bytes used, not characters used.

I don't want to neglect your shameless plug, but I struggle enough to find a solution to some of the puzzles I wrote (hence the undo), so finding the shortest path is a little daunting.

[1] https://github.com/DennisMitchell/jellylanguage

[2] https://github.com/Adriandmen/05AB1E


Having only started using ruby professionally recently, I have a vague idea of what you mean about "what the syntax allows". But I'm curious if you have specific details?

Are there good references for how I can make my coworkers hate me?



this post put a smile upon my face. a good example how someone becomes creative when limited


Is there a haskell transpiler that converts well formed well formatted code to this obfuscation format?


I don't personally know of one. It's not that I particularly intended this to be obfuscated, either, I just wanted it to be short. OK, I did rearrange it to spell out a rick roll but the impact to readability on that point was probably minimal. I guess what I'm saying is that the obfuscation is a side effect of the minification (side effects, in Haskell??).

The best I know of are some tools people developed for the tiny game jam to help you minify your code, which you can find here https://github.com/haskell-game/tiny-games-hs#minifying.


Is there a haskell compiler that does this obfuscation from well formatted well labeled code?


Or a transpiler


I think another 4 chars can be removed by replacing `head` with `!!0`.


You know I'm in too deep when the first thing I thought when reading this was "Oh no, not my Rick Rolll!" because now `g` wraps around to `}` instead of a variable.

Initial readers noted that the code blocks were unreadable for those without dark mode extensions due to black-on-black text. Perhaps I should've kept them that way.

Jokes aside, thank you!


It'd be 2 characters no? `head x` vs `x!!0`.


head is used twice in the program


Amazing




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: