5 ms·

Squeezing a Sokoban game into 10 lines of Haskell

169 points by ufo 4y ago

noloblo 4y ago
Is there a haskell compiler that does this obfuscation from well formatted well labeled code?
- noloblo 4y ago
  Or a transpiler
codetrotter 4y ago
> 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.
- cole-k 4y ago
  It would've certainly been nice to avoid playing Bin Packing, but alas this is just the rules of the game jam.
BWStearns 4y ago
> “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.
- isoprophlex 4y ago
  The title of the paragraph, "Think like a C Programmer", is absolutely fitting too
k2xl 4y ago
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 https://pathology.gg
- mabbo 4y ago
  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?
  - k2xl 4y ago
    https://codegolf.stackexchange.com/questions/363/tips-for-golfing-in-ruby https://codegolf.stackexchange.com/questions/363/tips-for-go... Enjoy!
- cole-k 4y ago
  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 https://github.com/DennisMitchell/jellylanguage [2] https://github.com/Adriandmen/05AB1E https://github.com/Adriandmen/05AB1E
sambalbadjak 4y ago
this post put a smile upon my face. a good example how someone becomes creative when limited
theK 4y ago
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.
- cole-k 4y ago
  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.
  - chowells 4y ago
    ... 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.
    - cole-k 4y ago
      Right you are, I never remember the proper name for the instance. I only use it to spaghettify code.
tromp 4y ago
> 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 https://www.ioccc.org/2012/tromp/tromp.c
- User23 4y ago
  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 https://www.ioccc.org/years.html#1989_tromp
  - tromp 4y ago
    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 https://www.ioccc.org/years.html#2014_wiedijk
quchen 4y ago
I think another 4 chars can be removed by replacing `head` with `!!0`.
- paradoja 4y ago
  It'd be 2 characters no? `head x` vs `x!!0`.
  - ginnungagap 4y ago
    head is used twice in the program
- cole-k 4y ago
  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!
kevinwang 4y ago
Amazing
abecedarius 4y ago
> 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/2048.cant#L135-L137 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/sokoban.cant#L20-L24 https://github.com/darius/cant/blob/master/examples/games/so...
- mzs 4y ago
  Your second link is the same as the first.
  - abecedarius 4y ago
    Thanks, oops, fixed.
- cole-k 4y ago
  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 https://news.ycombinator.com/item?id=34924577 [2] https://reddit.com/r/haskell/comments/11953ov/squeezing_a_sokoban_game_into_10_lines_of_code/j9nyk15/ https://reddit.com/r/haskell/comments/11953ov/squeezing_a_so...
  - gdprrrr 4y ago
noloblo 4y ago
Is there a haskell transpiler that converts well formed well formatted code to this obfuscation format?
- cole-k 4y ago
  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 https://github.com/haskell-game/tiny-games-hs#minifying.

169 points by ufo 4y ago

noloblo 4y ago

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

noloblo 4y ago
Or a transpiler

codetrotter 4y ago

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

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

BWStearns 4y ago

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

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

k2xl 4y ago

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 https://pathology.gg

mabbo 4y ago
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?
- k2xl 4y ago
  https://codegolf.stackexchange.com/questions/363/tips-for-golfing-in-ruby https://codegolf.stackexchange.com/questions/363/tips-for-go... Enjoy!
cole-k 4y ago
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 https://github.com/DennisMitchell/jellylanguage [2] https://github.com/Adriandmen/05AB1E https://github.com/Adriandmen/05AB1E

sambalbadjak 4y ago

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

theK 4y ago

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.

cole-k 4y ago
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.
- chowells 4y ago
  ... 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.
  - cole-k 4y ago
    Right you are, I never remember the proper name for the instance. I only use it to spaghettify code.

tromp 4y ago

> 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 https://www.ioccc.org/2012/tromp/tromp.c

User23 4y ago
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 https://www.ioccc.org/years.html#1989_tromp
- tromp 4y ago
  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 https://www.ioccc.org/years.html#2014_wiedijk

quchen 4y ago

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

paradoja 4y ago
It'd be 2 characters no? `head x` vs `x!!0`.
- ginnungagap 4y ago
  head is used twice in the program
cole-k 4y ago
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!

kevinwang 4y ago

Amazing

abecedarius 4y ago

> 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/2048.cant#L135-L137 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/sokoban.cant#L20-L24 https://github.com/darius/cant/blob/master/examples/games/so...

mzs 4y ago
Your second link is the same as the first.
- abecedarius 4y ago
  Thanks, oops, fixed.
cole-k 4y ago
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 https://news.ycombinator.com/item?id=34924577 [2] https://reddit.com/r/haskell/comments/11953ov/squeezing_a_sokoban_game_into_10_lines_of_code/j9nyk15/ https://reddit.com/r/haskell/comments/11953ov/squeezing_a_so...
- gdprrrr 4y ago

noloblo 4y ago

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

cole-k 4y ago
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 https://github.com/haskell-game/tiny-games-hs#minifying.