美しすぎるプログラムを解読せよの巻

program 
#include <iostream>
#include <cstring>
using namespace std;

long long dp[18][4][4][4][4][4][4][4][4][4][4];

#define FORN( n ) for ( int i##n = 0; i##n < 4; i##n ++ )

int main()
{
    memset( dp, 0, sizeof( dp ) );
    
    FORN( 0 ) FORN( 1 ) FORN( 2 ) FORN( 3 ) FORN( 4 ) FORN( 5 ) FORN( 6 ) FORN( 7 ) FORN( 8 ) FORN( 9 )
        dp[0][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] = 1;
    
    for ( int r = 1; r <= 17; r ++ )
    {
        FORN( 0 ) FORN( 1 ) FORN( 2 ) FORN( 3 ) FORN( 4 ) FORN( 5 ) FORN( 6 ) FORN( 7 ) FORN( 8 ) FORN( 9 )
        {
            if ( i0 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0+1][i1][i2][i3][i4][i5][i6][i7][i8][i9];
            if ( i1 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1+1][i2][i3][i4][i5][i6][i7][i8][i9];
            if ( i2 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2+1][i3][i4][i5][i6][i7][i8][i9];
            if ( i3 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3+1][i4][i5][i6][i7][i8][i9];
            if ( i4 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4+1][i5][i6][i7][i8][i9];
            if ( i5 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4][i5+1][i6][i7][i8][i9];
            if ( i6 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4][i5][i6+1][i7][i8][i9];
            if ( i7 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4][i5][i6][i7+1][i8][i9];
            if ( i8 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4][i5][i6][i7][i8+1][i9];
            if ( i9 < 3 ) dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9] += dp[r-1][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9+1];
        }
    }
    
    long long res = 0;
    res += dp[17][0][1][0][0][0][0][0][0][0][0];
    res += dp[17][0][0][1][0][0][0][0][0][0][0];
    res += dp[17][0][0][0][1][0][0][0][0][0][0];
    res += dp[17][0][0][0][0][1][0][0][0][0][0];
    res += dp[17][0][0][0][0][0][1][0][0][0][0];
    res += dp[17][0][0][0][0][0][0][1][0][0][0];
    res += dp[17][0][0][0][0][0][0][0][1][0][0];
    res += dp[17][0][0][0][0][0][0][0][0][1][0];
    res += dp[17][0][0][0][0][0][0][0][0][0][1];
    
    cout << res << endl;

    return 0;
}

これは確かに美しい…。このプログラムは、棚瀬将棋の棚瀬さんが書いたプログラムだ。

前に私が書いたプログラムです。
これはある問題に対する解答なんですが、ネタ狙いじゃなくて真面目に考えてこのコードに辿りつきました。
視覚的にこれ以上美しいプログラムはそうそうないんではないかと自負していますがいかがでしょう。
メイン部分はなんと11重ループです。
これが何を求めるプログラムか分かった人には・・何もあげませんがすごいです。
あるウェブサイトで出されている問題の一つなので知ってる人は知ってるかもしれないですが。


美しすぎるプログラム
http://d.hatena.ne.jp/tanase_yasushi/20101012

見た瞬間、何をするプログラムか私には想像がついた。プログラマの方は是非考えてみていただきたい。


以下、解答。









yaneurao 2010/10/12 20:37
何のプログラムかは知りませんが、dp[r]...がrにおけるなんかの回数でそれがr-1に依存して決まるのだから典型的なDP(Dynamic Programming)ですね。FORNが0から9まであることから、10進数であることも確定。じゃあrは桁数でしょう。dp[18]だから18桁ですね。18桁の10進数表記において、各桁を見たときに、同じ数字の出現回数が3回以内である数は何通りあるかだとかそんなところだと予想します。dp配列の正確な意味はもうちょっと考えないとよくわかんないです。よければ解説など希望。


tanase_yasushi 2010/10/12 23:41
さすがにすごいですね。正解です。早すぎますね。
いやあもうちょっと待って欲しかったというのが正直なところですｗ
正解されてしまうと解説も必要ないでしょうが、DPも知らない人多いでしょうし（僕も３０過ぎて初めて実装しましたし）そのうちまた。


http://d.hatena.ne.jp/tanase_yasushi/20101012/1286874490#c

さすがにやねうらおはすごかったようだ…。(自分で言ってりゃ世話ねーけどな)


まあ、冗談はさておき、C/C++のプログラムだと逆アセンブルして解読するのとは異なり、変数名として意味のある名前がついていることが多いのでそれを手がかりに解読できることが多々ある。上のプログラムで言うとforループで(r=0ではなく)r=1から始まっていて、dp[r]がdp[r-1]に依存して決定するので、ああ、DPっぽいな、変数名もよく見たらdpって書いてあるしな、とかそういうのを手がかりにすればすぐに解読できる…はず。


それはそれとして、現実的に意味のあるプログラムが、なかなかここまで対称的で美しいプログラムにはならないので、そういう意味では久しぶりにいいものを見させていただきました。