当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Condition【NandGame編】

2023年12月16日

Conditionレベル

Conditionレベルのゴールは、条件判定回路を組むことです。

今回の条件判定は、ゼロと比べての大小比です。

組むべき回路の入出力は次のとおりです。

入力X:比較対象の16ビット値
lt:Less than zero
eq:Equasl to zero
gt:Greater than zero
出力Output:判定結果。1ビット。1を出力する条件は次の表を参照。
当該回路の入出力
lteqgt1を出力する条件
000Never
001x > 0
010x = 0
011x ≧ 0
100x < 0
101x ≠ 0
110x ≦ 0
111Always

Conditionレベルを解く

直列的アプローチで解いてみる

1:用意されているコンポーネントに注目します。

新たなコンポーネントとして、is negコンポーネントとis zeroコンポーネントが用意されています。

  • is negコンポーネント…入力値(16ビット)が負の数なら、1を出力する。
    • 最上位ビットが1かどうかで負の数かどうかを判定している。
  • is zeroコンポーネント…入力値(16ビット)の全桁が0なら、0を出力する。

正直なところ3ビットデコーダーがあれば簡単に回路を設計できますが、本レベルでは用意されていません。

2:gtフラグの処理を実装します。

Xピンをis negとis zeroに分岐させてからorでまとめることで、Xの値が「負の数 or ゼロ」であるときに1を出力します。

上記の回路において、orコンポーネントの出力値をinvコンポーネントに通すことで、Xの値が「0より大」のときに1になります。

そして、gtフラグがON(すなわちgt=1)であるときに、Xの値が「0より大」であることを一致回路(XOR回路+NOT回路)で識別できます。

しかしフラグはgt以外にもあります。gtフラグのみがONであることを識別しなければならないのです。

残りのltフラグとeqフラグが両方とも0のときに1を出力させるには、NOR(OR+NOT)を通すことで実現できます。

後は最終的に2つの出力値が一致することを識別すればよいわけです。

8パターンあるうちの1パターンを解く回路ができあがりました。

愚直なアプローチなので冗長な箇所が多数あります。

それだけではありません。レベルを解くには、残り7パターンの回路を組む必要があります。

カイロを配置するキャンバス全体を覆い尽くしかねないので、このアプローチで解くのは諦めます。

素朴に並列的アプローチで解く

「1つの条件に対する回路を組んでから、次の条件の回路を組む」という直列的アプローチは非現実的であることがわかりました。

そこで並列的アプローチを採用します。

  • 第1段:is negで負の数であること、is zeroでゼロであること
  • 第2段:invを使って、0より大であること、ゼロでないこと
    • ⇒この2つをANDで束ね、0なら負の数、1なら正の数と判定できる。

ポイントはフラグごとにANDを用意し、その出力をORでつないで集約していくのです。

※全フラグが0なら、Xの値に依存せずに常にOutputはゼロになります。

※逆に全フラグが1なら、どこかの判定処理で1になるはずなので、ANDの出力もどこか1になります。ORで集約されるということは、1つでも1があればORの出力は1です。よって、全フラグが1なら、常に出力は1になるわけです。

この回路は9つのコンポーネントを使っており、内部的には62個のNnadゲートを使っています。

ヒントによると、さらに最適化できるとあります。

Nandを使うように最適化する【別解】

「And⇒Nand」に置き換えて、後はつじつまが合うように調整すると次のようになります。

この回路は9つのコンポーネントを使っており、内部的には56個のNandゲートによって構成されます。

別バージョン【別解2】

この回路も56個のNandゲートで構成されます。

ネット上の攻略記事を参考にしただけであり、回路を導く考え方がまだトレースできていません。