ShaFuck is not unbeatable

When I found ShaFuck, I really loved this idea and I thought it's indeed impossible to write code in this language.

However, I found a way to write code in ShaFuck and I could write a script which translates Brainfuck code into ShaFuck code.

http://shinh.skr.jp/obf/bf2sf.rb

Here is a few evidence:

• http://shinh.skr.jp/obf/hello.sf
• http://shinh.skr.jp/obf/cal.sf.gz

> ./shafuck hello.sf
Hello, world!
> ./shafuck cal.sf
2012 03
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 

The idea was very simple. We cannot find a 1024 byte characters which will be translated into a fully meaningful 20 BF commands (1/32^20 if SHA1 is random), but we can find a code chunk which will become 3 bytes of BF sequence and 17 bytes of junks. As the existence of BF comments (i.e., any characters which aren't the eight BF commands) are allowed as long as they aren't executed, we need to skip the junks. Luckily, I could find a translation:

+ => +>[ (17B)  (18B) ]<
- => ->[ (17B)  (18B) ]<
> => >[  (18B)  (18B) ]>
< => <[  (18B)  (18B) ]<
. => .>[ (17B)  (18B) ]<
, => ,>[ (17B)  (18B) ]<
[ => >[  (18B)  (17B) ]<[
] => >[  (18B)  (17B) ]<]

With my translation, all BF commands will be translated into 2 ShaFuck code junks (i.e., 2048 bytes of code). The trick was that we will never modify the contents of odd address and they always have zero. We can use them to skip junks. Note that > and < moves the pointers twice.

I found code chunks which will be translated into the above sequences by

http://shinh.skr.jp/obf/sf_find_ops.cc

I used sha1.c and sha1.h in shafuck's reference implementation. It took about 3 minutes to find code chunks we need.

I used shafuck-0.2 for this entry. The feature versions may not have this vulnerability. I think the simplest "fix" for this issue is validating code after calculating SHA1 and before running code.

ICFP Programming Contest 2012

The problem was to write a program which automatically solves Boulder Dash efficiently (the less turn you consume, the better).

As usual, I joined the lightning division (the first 24 hours of this 72 hours long contest) with C++. However, I decided to do something different this year because I was getting a bit bored of this kind of topcoder marathon match style problems. So, I wrote the boulder dash solver in Befunge:

http://shinh.skr.jp/dat_dir/bd.b98

I guess this is one of the biggest hand-written Befunge code. Technically, this isn't Befunge-93 code because it uses address space bigger than 80x25, so this code requires Funge-98 implementation like cfunge. However, I think it would be OK to claim this is a Befunge code because I only used Befunge-93 operations. Anyway, it wasn't easy to write this code, although I think I'm fairly good at Befunge (I've ever won a Befunge contest at codeforces). Like other participants, I didn't do almost nothing except for writing this code, but it was just 6 hours before the end of contest when I finished my simulator in Befunge...

The following is the full package I submitted. This includes a Befunge interpreter implementation written by me during this contest, some Makefile and README stuff, code for lightning division, etc.

http://shinh.skr.jp/dat_dir/icfp12.tgz

This is an attempt to describe something about my code. You can see a visualized image of dungeon around the bottom right of this image. This is just a memory dump. Befunge has 2D address space so we need no external visualizer.

BTW, I forgot to write something about ICFP programming contest 2011. It was great. The problem was better than all other contest problems I've ever seen and the organizers prepared a fairly stable duel server where participants can fight each other. I took 6th place. It seemed the 5th place team was also 1 person team and he got the judge's prize because of he was a one person team. So, I was the 2nd place one person team, yay.

The 20th IOCCC

I won the 20th IOCCC! http://ioccc.org/2011/whowon.html My code was a paint by number solver which looks like a paint by number problem. I think my code is decent. It is fairly obfuscated due to the size limit, bit operations, and the difficulty of paint by numbers itself. But obviously, akari.c is much better than mine...