Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年24日目です。
※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目、20日目、21日目、22日目、23日目。
Day 24「Crossed Wires」
タイトルは「交差するワイヤー」。ん？2日連続グラフ理論的な問題？？
ストーリー的には、故障したデバイスを修理する、というものです。
デバイスは、論理回路で数値を生成しようとしています。各ゲートは２つの入力があり、出力は１つです。ゲートはすべてTrueもしくはFalseの値を取り、操作します。ここでは論理計算は省略します。
例えば、以下のようなインプットがあります。
x00: 1
x01: 1
x02: 1
y00: 0
y01: 1
y02: 0
x00 AND y00 -> z00
x01 XOR y01 -> z01
x02 OR y02 -> z02これは、頭のx00などはワイヤを示し、x00というワイヤが初期値として１という値を取っている、という意味です。次のセクションは、各ゲートとどのワイヤがつながっているか、というリストです。最初の１行目であれば、このゲートは、AND計算を行うゲートで、x00、y00というワイヤとつながっており、出力はz00ワイヤに流れていくということになります。これは非常に単純な例で、入力からすぐに最終出力のzシリーズのワイヤにつながっています。しかし、本番の入力は、様々なところを経由し、zシリーズのワイヤに到達します。
Part1では、上の論理回路とその初期値に基づきzシリーズの出力に出てくるビットを10進数に直したものがパズルの答えです。
Part2では、上の回路が一部テレコになっている場所があり、各論理回路の出力のワイヤが一部入れ替わっています。今回は４セット（８個）のワイヤを交換すれば正しい回路となります。なお、この回路は、xシリーズの入力に入力した２進数の値とyシリーズの入力に入力した２進数の値の足し算（AND）を行い、zシリーズの出力に計算した値を出す、という回路のようです。パズルの答えは、入れ替えた８個のワイヤの名前をアルファベット順に並べ替えてカンマで結合した文字列です。
・ネ
・
・タ
・
・バ
・
・レ
Part1を解いてみる
これは、zシリーズのワイヤに値が全部入るまでひたすら結合していくだけです。
論理回路は順番に値が更新されていくので、値の入ったワイヤの値を使って、各ゲートの入力に入れていきます。このとき、２つの入力に値が入ったときだけ各ゲートの演算をしていけば、そのゲートの出力先のワイヤに値が入ります。さらに、その値を使って、さらに繰り返す、ということをすると、最終的にすべてのワイヤに値が入力されます。そのための繰り返しマクロは以下のとおりです。終了条件がちょっとめんどくさかったです。
Part1部分のワークフローは以下のとおりです。
Part2を解いてみる
Base Aといいつつ、このPart2はExcelで結果を眺めながらやっています。ワイヤの入れ替えは手動です・・・。
回路として、xシリーズ、yシリーズに値をいれるとzシリーズが出てくる、とのことなので、xとyに値を入れればzに何かが出てくるはずです。足し算なので、xとyにわかりやすい値を入れればzに予測された値が出てこなければなにかおかしい、ということになります。ということで、x01~x44、y01~y44に頭のビットから順に1を入れてみます。つまり、以下のように値を入れていきます。
0000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000010
0000000000000000000000000000000000000000000100
0000000000000000000000000000000000000000001000
0000000000000000000000000000000000000000010000
0000000000000000000000000000000000000000100000
・
・
・これの答えとしては、当然一桁桁上りするので、以下のような出力になります。
00000000000000000000000000000000000000000000010
00000000000000000000000000000000000000000000100
00000000000000000000000000000000000000000001000
00000000000000000000000000000000000000000010000
00000000000000000000000000000000000000000100000
00000000000000000000000000000000000000001000000
・
・
・これが思ったところにビットが出ていないところが壊れています。実際は以下のようになっていました。
これによると、4、5、22、38あたりがおかしいことがわかります。
次に、各ワイヤを見てみましょう。各ワイヤがどのインプット、アウトプットに絡んでいるかというのがわかりにくいのですが、簡単に可視化するとなると、どのビットを立てた時に1が立つか、というのである程度どのあたりにあるかの検討はつきます。それにより、以下のような可視化を行いました。
基本的に、２本のワイヤがセットで1となるようになっています。これで、だいたいの内部のワイヤがどこらへんに絡んでいるかがわかります。
ここまでの結果を使って、実際の回路を見ていくことになります。
例えば、3ビット目は正しそうなので、そこを正しいパターンとしてみていきましょう。
まず、z03の出力のゲートは
fph XOR vmr z03です（色々と見ていると、出力のzシリーズに接続しているゲートはすべてXORのようです）。インプットのfph、vmrがどうなっているのか気になります。調べると、以下のように論理式がANDになっていて同じインプットを持つものがあります。
fph AND vmr fnfさらに上位を見てみましょう。fphとvmrはどこから生成されているのでしょうか？
vmrは、以下のようになっていました。つまり、論理式がORのゲートから生まれています。
cdr OR hjh vmrさらに、このhjhの生成元の方を見てみると、一つ上のx、yシリーズにたどり着きます。
y02 AND x02 hjhさらに、z03と同じインプットを持つfnfのワイヤを見てみましょう。これはどこに入力していくのでしょうか？以下のようにOR回路につながっています。さらにこの出力bbhを見てみましょう。
fnf OR wpn bbhこんどは、bbhはz04の入力になっていました。
jth AND bbh csc
jth XOR bbh z04少し戻りましょう。z03の入力の「fph」を覚えていますか？これがどこで生成されているのか見てみましょう。なんと、
x03 XOR y03 fphx03とy03から生成されていました。
基本的にこれらの回路の構成をベースに、おかしなところを調査していくと見つかるようになっています。
まとめると、以下のような構成です。
y02 AND x02 hjh ※以下の片方の生成元は一つ前のx,yシリーズから生成
cdr OR hjh vmr ※zの片方の入力を生成しているゲートはOR
x03 XOR y03 fph ※x,yシリーズからANDゲートを挟んでzシリーズのXORにつながる
fph AND vmr fnf ※zシリーズと同じインプットを持つANDゲート
fph XOR vmr z03 ※必ずzシリーズの時はXORゲート
x03 AND y03 wpn
fnf OR wpn bbh
y04 XOR x04 jth
jth AND bbh csc
jth XOR bbh z04このパターンを他にも当てはめていきましょう（といっても、わけわからなくなりますが）。
あとは、この入力を修正し、再度各ワイヤの並びを見ていくと、最終的にはキレイに入力に対して期待されたものが出力されるようになります。
ワークフローとしては、x,yシリーズのインプットを下位ビットから一つずつ1にするパターンを作って、それをバッチマクロで回してどのあたりがおかしそうかを判別するためのワークフローがメインです。あとは、あやしいところを入れ替えて試す、をトライ＆エラーを繰り返しました。
おかしいところを探るためのバッチマクロです。
まとめ
- Part2ははたしてBase Aなのか、という疑問は残りますが、Alteryxがないと解けないのでまぁいいのでは？といった感じです。去年のDay25もネットワーク解析ツールで見て終わらせたので、これもきっとBaseAでしょう！
- Private LeaderboardではPart1は6位、Part2は4位でした。
コメント