めめめめうめうを最適化

プログラミング

大分昔のツイートではあるが、朝から流れてきたので頭の体操がてらに最適化。あ、ちょっとプログラマーっぽい。
友人から「これってどういうこと？」と聞かれたので彼のために解説を書く。

設問

「"め"と"う"をランダムに出力するプログラムを書き、その文字列の最後が偶然「めめめめうめうめめめめうめう」となった時、「ぺったんぺったんぺったんぺったん大好き」という文字を出力して終了せよ。

回答
public class Main{
    public static void main(String[] args)
    {
        int M=0;while((M&16383)!=15738){M=(M<<1)|(int)(Math.random()*2);System.out.print((M&1)>0?"め":"う");}
        System.out.println("ぺったんぺったんぺったんぺったん大好き");
    }
}

正直 Java とかよくわかってないが、元ツイートが Java だったので Java で書いた。C++だともう数文字短い。

解説

基本的には"め"と"う"をランダムに出力しながら文字を記録していき、その記録のラスト14文字が特定の文字列になったら終了する、という考え方。

さて、どうして記録したものかと考えると、文字がランダム50音ならともかく、今回は"め"と"う"の二文字しかないことに注目する。例えば、それぞれを 1 と 0 に置き換えると、「めめめめうめうめめめめうめう」は 11110101111010 となる。二進数だ。

"め"を出力した場合は1、"う"を出力した場合は0を記録していけばいいのだが、配列のようなもので領域を使い回す場合、いちいち頭から最後までを 1 ずつズラす処理をしたり、LIFO*1方式のリスト構造を用いる必要が出てくる。
が、二進数の場合はシフト演算子というものでカンタンに数をひとつ左へズラすことができる。10101 <<= 1 は 101010 。ズレて現れた一番右に、新たな文字の情報を記録してあげればいい。

while(true)
{
    m <<= 1;    // ひとつ左へズラす

    int next = (int)(Math.random()*2);    // 次の数字は 1 か 0
    m |= next;                            // 空いた一桁目にビット演算子で入れる
    System.out.print( next == 1 ? "め" : "う" );   // 数字によって文字を出力
}

で、二進数を使った場合、めうめうチェックはとても楽チンだ。最後の14桁が 11110101111010 になればいいのである。最後の14桁、というのも & 演算子を使えばさっくり抽出することができる。

if ( ( m & 0b11111111111111 ) == 0b11110101111010 ) System.out.print( "めうめう！" );
// 0b〜〜は二進数を表す書き方。

以上である。
なので、最初に挙げた回答は簡略的な書き方をしなければ、

public class Main{
    public static void main(String[] args)
    {
        int M=0;
        while( true )
        {
            M <<=1;
            int next = (int)(Math.random()*2);
            m |= next;
            System.out.print( next == 1 ? "め" : "う" );

            if ( ( m & 0b11111111111111 ) == 0b11110101111010 ) break;
        }
        System.out.println("ぺったんぺったんぺったんぺったん大好き");
    }
}

という感じになる。

短縮

ここからはただの趣味。コードの短縮は見た目が面白くなるだけで基本的に最適化にはならないし難読化するしで良いことは特にない。

まず、二進数は10進数に変換しても同じ処理になる。フラグ管理等では16進数化することが多いが、今回は文字を1文字でも削るために「0x」も惜しんで10進数にする。

while((M&16383)!=15738){ meumeu; }

ついでに while と if は機能が重複していたのでカット。これだけで大分わけわからん度が上がってきた。

次に、文字の処理は4行も使わなくとも1行で可能。ただ、ビット演算子は優先度がややこしいのでカッコの位置には気を付けること。

M=(M<<1)|(int)(Math.random()*2);
System.out.print((M&1)>0?"め":"う");

Mを1シフトしたものにrandomの結果をそのままOR挿入している。"め":"う"の選り分けを >0 で行っているのは単純に ==1 より短いから。*2

あとはスペース無くしてぎゅっと縮めよう。

int M=0;while((M&16383)!=15738){M=(M<<1)|(int)(Math.random()*2);System.out.print((M&1)>0?"め":"う");}
System.out.println("ぺったんぺったんぺったんぺったん大好き");

恐らく「ぺったん」周りも文字コード弄ったり繰り返し処理したりすると更に縮まるのだが、日本語を消してしまうとコードの面白味がなくなってしまうのでそのまま残した。


以上。
大昔に流行った1行テトリスも、大体似たような感じ。

*1:Last In, First Out.後入れ先出し

*2:あとで気付いたのだが、<< は | より優先度が高いので、(M<<1)のカッコはいらなかったっぽい。