/**************************************************/
/* NAND素子による最少段数(=5)最少素子数の全加算器 */
/* 　　　　　Computer & Puzzle 2001/02 by takaken */
/**************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int  VAL[20];
int  DAN[20];

int  DMX[256];
int  USE[256];
int  COUNT;
int  DEPTH;
clock_t StartTime;

/**************************************************/
/* 解の表示　　　　　　　　　　　　　　　　　　　 */
/**************************************************/
void Result(void)
{
    int  i, j, k, val_a, val_b, val_c, dan_a, dan_b, dan_c;

    /* 解の個数と探索時間 */
    printf("\n[%d] time = %f sec\n",++COUNT,((float)(clock() - StartTime)) / CLK_TCK);

    /* 外部入力 */
    printf(" 0: %02x(0)\n", 0x0f);
    printf(" 0: %02x(0)\n", 0x33);
    printf(" 0: %02x(0)\n", 0x55);

    /* NAND素子 */
    for (i=3; i<DEPTH; i++) {
        /* 自分の両親を探す */
        val_a = dan_a = val_b = dan_b = -1;
        for (j=0; j<i; j++) {
            val_a = VAL[j];
            dan_a = DAN[j];
            for (k=j; k<i; k++) {
                val_b = VAL[k];
                val_c = (val_a & val_b) ^ 0xff;
                if (val_c != VAL[i]) continue;
                dan_b = DAN[k];
                dan_c = ((dan_a > dan_b)? dan_a: dan_b) + 1;
                if (dan_c == DAN[i]) break;
            }
            if (k < i) break;
        }
        /* 表示 */
        printf("%2d: %02x(%d) <- %02x(%d), %02x(%d)\n"
            ,i-2, VAL[i], DAN[i], val_a, dan_a, val_b, dan_b);
    }
}
/**************************************************/
/* バッックトラッキング(IDA*)　　　　　　　　　　 */
/**************************************************/
void BackTrack(int index)
{
    int  i, j, val_a, val_b, val_c, val_x, dan_a, dan_b, dan_c, dan_x, lower_bound;
    int  dan_new[256];

    /* 以後最低限必要な要素数 */
    lower_bound = 2 - USE[0x17] - USE[0x69];

    if (lower_bound == 0) { /* 解を発見した */
        Result();
    } else {
        /* (枝刈1)下限値による枝刈り */
        if (index + lower_bound > DEPTH) return;

        /* 準備(添え字の値が次の要素になれない場合を99とする) */
        for (i=0; i<256; i++) dan_new[i] = 99;
        val_x = VAL[index - 1]; /* 直前の要素 */
        dan_x = DAN[index - 1];

        /* 次の要素と成り得る候補を列挙する */
        for (i=0; i<index; i++) {
            val_a = VAL[i];
            dan_a = DAN[i];
            for (j=i; j<index; j++) {
                val_b = VAL[j];
                val_c = (val_a & val_b) ^ 0xff;

                /* (枝刈2)同じ出力の素子は作らない */
                if (USE[val_c]) continue;

                dan_b = DAN[j];
                dan_c = ((dan_a > dan_b)? dan_a: dan_b) + 1;

                /* (枝刈3)子の大小関係ルールを守り重複探索を防止 */
                if (dan_c < dan_x) {
                    continue;
                } else if (dan_c == dan_x) {
                    if (val_c < val_x) continue;
                }

                /* (枝刈4)自己の最大段数を超えた */
                /*「このチェックを外すと単なる最少素子数の解が求まる」*/
                if (dan_c > DMX[val_c]) continue;

                /* (枝刈5)得策段数の更新 */
                if (dan_c < dan_new[val_c]) dan_new[val_c] = dan_c;
            }
        }

        /* 新しい要素を付加して再帰呼出し */
        for (val_c=0; val_c<256; val_c++) {
            if (dan_new[val_c] != 99) {
                VAL[index] = val_c;
                DAN[index] = dan_new[val_c];
                USE[val_c] = 1;
                BackTrack(index + 1);
                USE[val_c] = 0;
            }
        }
    }
}
/**************************************************/
/* 初期処理　　　　　　　　　　　　　　　　　　　 */
/**************************************************/
void Initialize(void)
{
    int  i, a, b, c, dan;

    /* 逆解きで最大限界段数のテーブルを作る */
    for (i=0; i<256; i++) DMX[i] = 0;
    DMX[0x17] = DMX[0x69] = 5;
    for (dan=4; dan>=0; dan--) {
        for (i=0; i<256; i++) {
            if (DMX[i] != dan + 1) continue;
            for (a=0; a<256; a++)
            for (b=0; b<256; b++) {
                c = (a & b) ^ 0xff;
                if (c != i) continue;
                if (DMX[a] < dan) DMX[a] = dan;
                if (DMX[b] < dan) DMX[b] = dan;
            }
        }
    }
    DMX[0x0f] = DMX[0x33] = DMX[0x55] = 0;

    /* 同じ出力の素子を作らない為のテーブル初期化 */
    for (i=0; i<256; i++) USE[i] =  0;
    USE[0x0f] = USE[0x33] = USE[0x55] = 1;

    /* 外部入力を設定 */
    VAL[0] = 0x0f; VAL[1] = 0x33; VAL[2] = 0x55;
    DAN[0] = 0;    DAN[1] = 0;    DAN[2] = 0;
}
/**************************************************/
/* 反復深化の制御　　　　　　　　　　　　　　　　 */
/**************************************************/
int main(void)
{
    StartTime = clock();
    Initialize();
    for (DEPTH=3; !COUNT; DEPTH++)
        BackTrack(3);

    return 0;
}