※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目、20日目、21日目。
第弐拾弐話「Sand Slabs」
タイトルは、「砂の平板」。
前回庭を暇つぶしに歩いているだけでしたが、砂がレンガとして落ちてきているようです。水をろ過するために砂を使う必要があるのですが、レンガを一部崩す必要があるそうです。
落ちてくるレンガはまるで3Dのテトリスのように降ってきます（が、テトリスのようにレンガの回転はできません）。エルフが落ちてくる途中のレンガのスナップショットを撮影しました。
1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9これは、例えば１行目の（1,0,1）は、x軸、y軸、z軸を示しており、x軸は1～1の立方体、y軸は0～3の直方体（長さは3）、z軸は1～1の立方体、といった形に読み解きます。つまり、x軸、z軸は長さ1、y軸は長さ3の直方体、ということです。まずこれを自由落下させて積み上げる必要があります。テトリスのように着地するとバランスを崩さずくっついてしまいます。
Part1では、積み上がったレンガについて、崩さずに破壊できるレンガを探すことです。テトリスのようにくっつくので、例えば以下のようになっているとします。
66
445
233
111を壊すと、全部崩れるのでNGです。2を壊しても4は3が支えます。3を壊すと、5が落下します（が、6は落下しません）。4を壊しても6は5が支えます。このようなケースでは、2,3,4を破壊してもオッケーということになります（まぁ、全部壊すと支え合っているものがなくなるのでNGなのですが）。あくまで、壊せる可能性があるものを見つける、ということになります。クイズの解答は、壊せるレンガの数です。
Part2は、確実に破壊したときに上から落ちてくる個数を数えます。例えば、上の例だと、1はすべて崩れるのでカウントとしては、２，３，４，５，６の５。2は何も落ちてきませんが、３は５が落ちてくるので１。合計６となります。※サンプルよりもう少し突っ込んだ例にしています
・ネ
・
・タ
・
・バ
・
・レ
Part1、2を解いてみる
Part1は、二段階で構成します。1段階目は、安全に落とすことです。
データは以下のようにしています。これをマクロでぐるぐるまわします。
上のRecordID＝0は床です。データ量を減らすため、マクロ内部で個別のブロックに分解しています。１ブロック＝１レコードとしています。
マクロ内では、各ブロックを一つずつ落としていきます。落とすブロックのZ軸を１マイナス後、各レコードを展開してバラバラの立方体に分解し、マッチングをかけます。ここで設置ポイントも取得できます（これをPart2で使います）。マッチしなかったら反復をかけていきますが、Z軸を１マイナスしてから反復します。
基本的に全データをぐるぐる回していきます。ブロックをばらすのは各反復の内部で行うため、データ量がめちゃくちゃ増えたりはしないのですが、落としていったブロックが増えると、結果的にばらすブロックが増えるのでどんどん時間がかかるような形になっています（うまく抑制できればよかったのですが・・・）。
3Dテトリスを落とすマクロ。
このマクロにより、各ブロックの関係性（どこに設置されているか）が入ったデータが得られます。
例えば、１は２と３を支えています。２は４と５を支えていますが、３も４と５を支えています。これを使っていきます。Part1でほしいのは、複数のブロックを支えるブロックの数です。なくなったときに、もう一方のブロックで支えられればオッケーということになります。ただ、注意するポイントは、上の表で複数のブロックから支えられているかどうかは、CurrentPosのカウントを取ればわかりますが、支えているブロックが別のブロックを単独で支えていた時、そのブロックは破壊できない、ということです。
以下の例だと、4は２カウントでてくるので配下の２と３はいずれか破壊しても落ちませんが、３を破壊すると５が落ちてくるので３は対象外となってしまいます。
66
445
233
11ここに気づくのに時間がかかり、かなりの時間を無駄にしたような気がします。ワークフローとしては以下の通り。
なお、今回の問題用にビジュアライズしています。これがないとデバッグ難しいですね。若干雑に作っています（本来は空白部分もちゃんと補完してあげるほうがいいのですが、しなくてもデバッグには影響ありません）。3D表示の場合は、テーブルツールを使って、Z軸を別の表にするという表現を使っています（高さで輪切りして水平面を見ている感じです）。
Part2も、Part1のマクロで得られた設置ポイントを使っていきます。Part2は破壊したときの数を取っていきます。Part1で、単独で支えているリストができているので、これをベースに１ブロックずつ親子関係を見ていきます。１ブロックずつ見るために、反復マクロをバッチマクロで呼び出し、反復マクロ自体は一つのレンガを破壊したときに落ちる数をカウントし、バッチマクロで全体を回しています。
バッチマクロ：
反復マクロ：
結論として、反復マクロ内では、落ちていったブロックの履歴を取り、落としている最中のブロック全体で共有するようなことをしています。
Part2部分のワークフローです。Part1の途中のリストを再利用しています。ワークフロー自体にはたったの３ツールしか追加していません（マクロの中はそれなりのツール数です）。
全体：
まとめ
- タフな問題です。最初インプットデータの意味がわかりませんでした（笑）※去年も似たようなデータを扱っていた気がしますが・・・。落とすマクロでも、バグが多く、最初指定したID以降すべてのブロックを落としていたため、ブロックがめり込んでいました・・・。これは、やはりちゃんと可視化してちゃんと動いているかどうか見ないとだめですね・・・。
- また、落とすマクロ以降のところ、どのブロックを選択すべきか、非常に時間がかかりました。サンプルでうまくいっていても実際のリストだとうまく動かないというAoCの罠にまんまとハマっていました。だいたい後半の問題は条件が複雑になるためサンプルデータでは気づけ無い、網羅していない問題を見つけていかないといけない、というのはなかなかしんどいですね。仕事なら要件定義がクソ甘い、って言ってやりたい感じです。
- Private Leaderボードでは、Part1は8位。Part2では5位でした。Part2解けてる人が少ないのでそれで巻き返した感じです・・・。これでもPart1を1時間程度で解いている人がいるのは驚きです。
コメント