== The Golden Gate (Programming 400pts) ==
ユニバーサル基板上にゲートICを10個と，スイッチとLEDを8個ずつ配置して実際に製作されたエンコーダーの写真が与えられた。

ゲートICは調べてみるとNANDゲートが4つ入っていることがわかる。
裏表の写真を行き来しながら接続を確認して回路図に落とした。
スイッチは押すと0になるものと1になる物両方存在している。

{{attachment:circuit.jpg}}

この回路図を元にプログラムを作成して動作をシミュレーションした。
結論から言えば，依存関係順に並べれば一度に計算を終わらせることも可能であったが，
フリップフロップが含まれていて順序回路になっている可能性もあったため結果が安定するまで繰り返し計算するように実装した。
どちらが上位ビットなのかわからなかったため，切り替えられるようにしてある。
また，与えられたのはエンコーダであるから，結果を逆引きして平文を求めている。
{{{#!highlight c
#include <stdio.h>

#define UPPER 0

int nand(int x, int y) {
    return !(x && y);
}

int gate[10][5];
unsigned char f(unsigned char x) {
    int i;
    int plus = 1;
#if UPPER
    int sw1 =  !(x & 0x80);
    int sw2 =  !(x & 0x40);
    int sw3 = !!(x & 0x20);
    int sw4 = !!(x & 0x10);
    int sw5 =  !(x & 0x08);
    int sw6 = !!(x & 0x04);
    int sw7 =  !(x & 0x02);
    int sw8 = !!(x & 0x01);
#else
    int sw1 =  !(x & 0x01);
    int sw2 =  !(x & 0x02);
    int sw3 = !!(x & 0x04);
    int sw4 = !!(x & 0x08);
    int sw5 =  !(x & 0x10);
    int sw6 = !!(x & 0x20);
    int sw7 =  !(x & 0x40);
    int sw8 = !!(x & 0x80);
#endif
    for (i = 0; i < 100; i++) {
    gate[1][1] = nand(sw1, gate[8][2]);
    gate[1][2] = nand(gate[1][1], gate[8][2]);
    gate[1][3] = nand(gate[1][1], sw1);
    gate[1][4] = nand(gate[1][2], gate[1][3]);
    gate[2][1] = nand(plus, gate[3][1]);
    gate[2][2] = nand(gate[2][1], gate[3][2]);
    gate[2][3] = nand(gate[2][2], gate[3][3]);
    gate[2][4] = nand(gate[2][3], gate[3][4]);
    gate[3][1] = nand(plus, sw3);
    gate[3][2] = nand(sw3, gate[3][1]);
    gate[3][3] = nand(gate[2][2], gate[6][2]);
    gate[3][4] = nand(gate[3][3], gate[6][2]);
    gate[4][1] = nand(sw2, gate[5][1]);
    gate[4][2] = nand(gate[4][1], gate[5][2]);
    gate[4][3] = nand(gate[8][2], gate[5][3]);
    gate[4][4] = nand(gate[4][3], gate[5][4]);
    gate[5][1] = nand(sw2, sw4);
    gate[5][2] = nand(gate[5][1], sw4);
    gate[5][3] = nand(gate[8][2], gate[6][2]);
    gate[5][4] = nand(gate[5][3], gate[6][2]);
    gate[6][1] = nand(sw2, gate[7][1]);
    gate[6][2] = nand(gate[6][1], gate[7][2]);
    gate[6][3] = nand(gate[4][2], gate[7][3]);
    gate[6][4] = nand(gate[6][3], gate[7][4]);
    gate[7][1] = nand(sw2, sw3);
    gate[7][2] = nand(gate[7][1], sw3);
    gate[7][3] = nand(sw6, gate[4][2]);
    gate[7][4] = nand(gate[7][3], sw6);
    gate[8][1] = nand(sw6, gate[9][1]);
    gate[8][2] = nand(gate[8][1], gate[9][2]);
    gate[8][3] = nand(gate[6][2], gate[9][3]);
    gate[8][4] = nand(gate[8][3], gate[9][4]);
    gate[9][1] = nand(sw6, sw8);
    gate[9][2] = nand(gate[9][1], sw8);
    gate[9][3] = nand(gate[6][2], sw5);
    gate[9][4] = nand(gate[9][3], sw5);
    gate[0][1] = nand(sw7, sw2);
    gate[0][2] = nand(gate[0][1], sw2);
    gate[0][3] = nand(sw7, gate[0][1]);
    gate[0][4] = nand(gate[0][2], gate[0][3]);
    }
    int out1 = gate[1][4];
    int out2 = gate[2][4];
    int out3 = gate[2][2];
    int out4 = gate[4][4];
    int out5 = gate[0][4];
    int out6 = gate[6][4];
    int out7 = gate[4][2];
    int out8 = gate[8][4];
    x = 0;
#if UPPER
    x |= out1 << 7;
    x |= out2 << 6;
    x |= out3 << 5;
    x |= out4 << 4;
    x |= out5 << 3;
    x |= out6 << 2;
    x |= out7 << 1;
    x |= out8 << 0;
#else
    x |= out1 << 0;
    x |= out2 << 1;
    x |= out3 << 2;
    x |= out4 << 3;
    x |= out5 << 4;
    x |= out6 << 5;
    x |= out7 << 6;
    x |= out8 << 7;
#endif
        x ^= 0xff;
    return x;
}


unsigned char table[256];
void maketable() {
    int c;
    for (c = 0; c < 256; c++) {
        int c2 = f(c);
        table[c2] = c;
    }
/*
    for (c = 0; c < 256; c++) {
        fprintf(stderr, "%02x ", table[c]);
        if (c % 16 == 15) 
            fprintf(stderr, "\n");
    }
    fprintf(stderr, "\n");
//*/
}

int main(int argc, char **argv) {
    int i, j;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 5; j++) {
            gate[i][j] = 0;
        }
    }
    maketable();
    while (1) {
        int c = getchar();
        if (c == -1) break;
        if (*argv[1] == 'd')
            putchar(table[c]);
        else
            putchar(f(c));
    }
}
}}}

これによりgzip圧縮されたフラグが得られた。
{{{
% make solve && ./solve d < ct | file -
cc     solve.c   -o solve
/dev/stdin: gzip compressed data, from Unix, last modified: Tue Nov 25 00:13:06 2014

% ./solve d < ct > result.gz 

% gzip -dc result.gz 
The flag is SECCON{Hlvd0toiXgloBhTM}
}}}


LEDが点灯するのは回路の出力が0になった時であることになかなか気づけなかった。