排他的論理和で作る三角形

awkネタ

有名な「パスカルの三角形」は「右上の数と左上の数の和」を配置していきますが、今回は「排他的論理和」を使います。
01段目：1
02段目：11
03段目：101
04段目：1111
05段目：10001
06段目：110011
07段目：1010101
08段目：11111111
09段目：100000001
10段目：1100000011
11段目：10100000101
12段目：111100001111

上から順番に配置していった時、2014番目の「０」が出力されるのは何段目？

gawk では、xor関数があります。

xor(v1,v2)
引数のビットごとのXOR値を返す

#!/usr/bin/gawk -f

BEGIN{
    count = 0;      # 0が出現した回数
    line = 1;       # 現在の行数
    row[1] = 1;     # 現在の行の値
    next_row[1] = 1;

    while(count < 2014){
        for(i = 1; i <= length(row) - 1; i++){
            cell = xor(row[i] , row[i + 1]);
            next_row[i + 1] = cell;
            if (cell == 0){ # 0の場合にカウント
                count++;
            }
        }
        next_row[length(next_row) + 1] = 1;
        line++;         # 行数を増やして次の行へ
        for(j = 1; j <= length(next_row); j++){
            row[j] = next_row[j];
        }
    }
    print line;         # 2014個カウントした行を出力
}

実行してみます。

gawk -f q21.awk 
75