解説
解法2はNANDが少なく低遅延な構成(実績あり)。ORで2つ、ANDで2つNANDを経由していたのに比べて、3つのNANDを経由するだけで出力できるので、遅延が少ない。

解説
XORのXORをとればよい。表にするとわかりやすい。

0000 -> 00 -> 0 0001 -> 01 -> 1 0010 -> 01 -> 1 0011 -> 00 -> 0 ...

解説
さっきの奇数判別の回路を流用できる。
・1の位は奇数判定の回路と同じ。
・2の位は、1,2と3,4の両方のXORがONのとき、1,2と3,4のうち片方のANDがONのとき、の2パターン考えられるので、それをORでつなげばいい。

確認できるパターン
2個がON: 1010, 1001, 0110, 0101 -> XORを2つとANDで確認
2個がON: 1100, 0011 -> ANDを2つとXORで確認
3個がON: 1110, 1101, 1011, 0111 -> ANDを2つとXORで確認

・4の位はすべてがONのときにONを出力するようにAND回路を組めばいい。

解説
1bitずらせば、1が2に、2が4に、4が8に...という具合にすべての桁を2倍にできる。

解説
1の位は片方がONのときにONになるのでXOR、2の位は両方がONのときにONになるのでANDを使うといい。表にするとわかりやすい。

00 -> 0,0 01 -> 1,0 10 -> 1,0 11 -> 0,1

解説
半加算器を2つ組み合わせて実現する。2つの数字を半加算器に入れて2桁の出力を出した後、下の桁と3つめの数字をさらに半加算器に入れる。

最初の加算では00・01・10のパターンしかないので、繰り上がりが両方1になることはない。そのため、どちらかの加算で繰り上がりが出ていれば繰り上がりを1にすればいい。つまりORで繋ぐ。

0 0 0 -> 00 0 -> 00 0 0 1 -> 00 1 -> 01 0 1 0 -> 01 0 -> 01 0 1 1 -> 01 1 -> 10 1 0 0 -> 01 0 -> 01 1 0 1 -> 01 1 -> 10 1 1 0 -> 10 0 -> 10 1 1 1 -> 10 1 -> 11

解説
0,1の信号を、0のときに1になる線と、1のときに1になる線に分ける回路。
これを作るの自体は簡単だが、のちに大きい回路を作るときに役に立つ。

解説
3つの端子を持つANDを使って力押してで解ける。さっきのDemuxを使って、各bitが0と1それぞれのときに別の線に出力させて、000のとき、001のとき、010のとき...と計8種類、各場合をAND回路で拾っていけば簡単だ。

解説
Byte ANDがなかっため、byte NOTとbyte ORを組み合わせてANDを作っている。NOR・NANDはOR・ANDにそれぞれNOTを通したもの。

解説
自己参照・循環参照を起こすと信号が高速で切り替わって回路が焼ききれてしまう場合があるので、通常のステージでは禁止されている。
上の例で言うと、NOTの手前がOFFなのでONを出力する、すると手前もONになるのでOFFを出力する、すると...と瞬間的に高速にON・OFFが切り替わって破損する。

解説
CPUを作ると聞くと厳ついイメージがあるが、やることは割と単純。レジストリ(1byteのメモリ)のSave・Loadを操作して、レジストリどうしや入出力端子の間を数値を移動させる。
まずは各入力と出力をぐるっと繋ぐ。次に命令コードを1bitの信号に分解、各レジストリのSaveとLoad・入出力のONとOFFに繋げばそれで完成。配線もシンプル。

解説
ALU(上の「4-2-1. Arithmetic Engine」で作った計算回路)に1byteの命令とREG1とREG2の常時出力を常に繋いでおき、Compute命令が出たときに結果をREG3に流し、REG3にSaveさせる。信号が混戦しないように注意しよう。

解説
デコーダーで分解した8つの信号ごとに、ANDゲートで条件を満たすか確認し、それをORゲートでまとめている。Valueの入力から「=0」「!=0」「Negative(<0)」「Positive(>=0)」の情報を引き出し、その組み合わせで判定するかたち。

000 Never --- 接続しない
001 If value = 0 --- =0
010 If value < 0 --- Netagtive
011 If value <= 0 --- Netative or =0
100 Always --- そのままORに接続
101 If value != 0 --- !=0
110 If value >= 0 --- Positive
111 If value > 0 --- Positive and !=0

解説
入力に5を足すプログラム。上の5行で処理できる。上で設計したように、Immediate命令の数値はREG0に格納され、Compute命令はREG1とREG2の数値の演算結果をREG3に格納する。うまくCopy命令をつかって数値を移動させよう。

解説
Condition命令のお試し問題と言ってもいい内容。上で設計した通り、ConditionはReg3の数値を判定して、成立していればReg0の値をプログラムカウンタにコピーするので、Immediate命令で予めReg0にジャンプ先の行数を入れておくとよい。

また、Outputに直接好きな数字を送ることができないため、一旦Immediate命令でReg0に数字を入れ、Reg0からOutputにCopyしている。

インベーダー宇宙ネズミどもを倒すのに今回取った手順だが、
1. 最初に目の前の壁をぶち壊して一歩前に出る
2. 目の前を探索して入力を得て、0(なにもない)ならその場でループする
3. 0でないならレーザーを4回撃つ
こういう作戦だ。

解説
パスワードを解析するプログラムを作る問題。手法はシンプル、正解が見つかるまで0～9999のすべての数字を出力すればよい。簡単なループで解ける。
今回は「label」を使っている。行番号にラベル名をつけると、そのラベル名は行番号と同じ扱いがされる。

解説
入力を4で割った余りを出力する問題。このCPUに除算は実装されていないが、AND演算をすることで目的を達成できる。

解説
この手の問題ではおなじみの、左手伝いに辿ればゴールに辿り着く法則を使う。
1. 前方を調べて、壁ならば、その場で右に方向転換して1.を繰り返す
2. 壁でなければ前進して左に方向転換
3. 1に戻る
この手順で実行できる。

解説
空いているOPCODEにRAM_SAVEとRAM_LOADを割り当てる。今回は、問題文で示唆されているとおり、アドレス指定レジスタとして、REG5の値を参照するようにした。

また、RAM_LOADのときにレジスタへの書き込みが発生しないように、回路左上に書き込みを制限する回路を追加している。今後も同様のことが起こらないように、特定のOPCODEでのみレジスタへの書き込みを許可するようにしてみた。

解説
NAND SCOREとDELAY SCOREの解説のためのステージ。適当に配置して繋ぐだけでいい。
NAND SCOREは使用したNANDの数。DELAY SCOREは、コンポーネントごとの遅延を評価するためのもの。通過したNAND1つにつき2増える。

解説
被除数から除数を1回ずつ引いていき、引いた回数を出力する単純なプログラム。商が大きくなると計算に時間がかかる。

解説
このステージでは関数...というかサブルーチンの呼び出し「CALL」と、呼び出し元のアドレスに戻る「RET」の実装をする。関数からさらに関数を呼び出す際に、呼び出し元のアドレスを上書きしないように専用のスタックを使って戻り先アドレスを記録する。

「CALL」命令では引数を1つとり、専用スタックにプログラムカウンタの値を保存し、引数で指定されたアドレスでプログラムカウンタを上書きする。
「RET」命令では引数をとらず、専用スタックに保存されたカウンタの値+4でプログラムカウンタを上書きする。

今回は専用スタックの追加だけでなく、プログラムカウンタを上書きするための回路も追加している。

レジスタ
00000000 REG0
00000001 REG1
00000010 REG2
00000011 REG3
00000100 REG4
00000101 RAM_ADDRESS
00000110 P_COUNTER
00000111 INPUT
00000111 OUTPUT

OPCODE
00000000 ADD (reg reg reg)
01000000 ADDi (reg value reg)
11000000 ADDii (value value reg)
00000001 SUB (reg reg reg)
01000001 SUBi (reg value reg)
11000001 SUBii (value value reg)
00000010 AND (reg reg reg)
01000010 ANDi (reg value reg)
00000011 OR (reg reg reg)
01000011 ORi (reg value reg)
00000100 NOT (reg _ reg)
00000101 XOR (reg reg reg)
01000101 XORi (reg value reg)
00000110 SHL (reg reg reg)
01000110 SHLi (reg value reg)
00000111 SHR (reg reg reg)
01000111 SHRi (reg value reg)

00100000 IF_EQUAL (reg reg address)
01100000 IF_EQUALi (reg value address)
00100001 IF_NOT_EQ (reg reg address)
01100001 IF_NOT_EQi (reg value address)
00100010 IF_LESS (reg reg address)
01100010 IF_LESSi (reg value address)
00100011 IF_LESS_EQ (reg reg address)
01100011 IF_LESS_EQi (reg value address)
00100100 IF_GT (reg reg address)
01100100 IF_GTi (reg value address)
00100101 IF_GT_EQ (reg reg address)
01100101 IF_GT_EQi (reg value address)

00101000 RAM_LOAD (_ _ reg)
00101001 RAM_SAVE (reg _ _)
00101010 POP (_ _ reg)
00101011 PUSH (reg _ _)

00101101 CALL (label _ _)
00101100 RET (_ _ _)

解説
よく考えるととても単純な計算式で対応できる。

引くカードの数 = (残りのカードの数 - 1) mod 4

理屈を説明すると、
1) 相手が1枚引いたときに3枚・2枚引いたときに2枚・3枚引いたときに1枚引くようにすると、1巡ごとに4枚のカードが減るように調整できる
2) 相手に最後の1枚を引かせるためには、相手のターンに「4の倍数+1」のカードが残るようにすればいい
3) 自分の手番で引くカードは、「残りのカードの数 - (4の倍数 + 1)」枚
4) 整理すると、「(残りのカードの数 - 1) を4で割った余り」の枚数を引けばよい

例えば12枚なら3枚引いて9枚に、ここから相手が3枚引いて6枚になれば、1枚引いて5枚にする。これを繰り返せば、相手は確実に最後の1枚を引くことになる。カードの枚数が4の倍数+1枚でない限り先手が勝つゲームとも言える。

解説
反復するパターンが掴みにくい問題。この迷路はフラクタルな空間充填曲線であるヒルベルト曲線と呼ばれるもの。正方形をコの字型に4つの領域に分割し、それぞれの領域をさらにコの字型に分割していくことで作られる。再帰的に処理することで、短いプログラムで移動指示を出すことができる。

再帰的に処理する際にコの字の向きと裏表を変える必要があるのだが、XORを重ねて使うことでうまく処理できる。

別解:
クリアするだけなら、すべての行動をプログラム上に書きあげるハードコーディングの力技でも解決できる。

解説
RAMを活用する練習問題。流れてきたフルーツのIDをRAMに記録し、記録されたフルーツと比較して同じものがあれば報告する。

解説
基本的な選択ソートで実装してみた。ソートアルゴリズムはネット上の各所に解説があるので割愛。

解説
擬似乱数生成器を組む問題。問題文に書かれている通りのアルゴリズムを実装するだけなので、特に難しい問題ではない。擬似乱数の生成についても深堀りすると楽しいはず。

解説
再帰関数を使う問題。「7-5. Functions」で実装したcallとretを活用する。この解法では、元の階層の変数の値を汎用スタックに詰め込んでみた。