Advent of CodeをAlteryxでやってみる2024_21日目

Advent of code
2024.12.29

Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年21日目です。

※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目、20日目。

Day 21「Keypad Conundrum」

タイトルは「キーパッドの難問」。確かに難問でした・・・。難易度は今年一番かな、、、

ストーリー的には歴史家が今度は宇宙船で行方不明になったようです。

場所はわかっていますが、入るのにドアにあるテンキーに4桁のコードを入力する必要があります。以下のような配置です。

+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    | 0 | A |
    +---+---+

ここは減圧されているところにあるので、直接押すことができないため、ロボットを使う必要があるようです。ロボットは直接数字のキーパッドを押すように指示できず、別の場所にある方向キーパッドを使ってロボットアームを動かし、上の数字のキーパッドを押すことができます。

    +---+---+
    | ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+

ちなみに、このキーパッドのある場所も放射線で汚染されており、人間が行くことができないため、ここにロボットを送り込み、また別のキーパッドからこのロボットに指示を行う必要があります。さらに悪いことにそのキーパッドの場所も-40°なので人間は近づけません。同様にロボットを送り込み、別の場所のキーパッドを押す必要があります。

ロボットは、自動的にAキー（入力キー）を認識して、最初はここにアームを持ってきます。また、空白の部分はなにもないと認識してロボットがエラーになるようなので、常にキーのある場所しか移動できません。

例えば、029Aを押すためには、以下のように押す必要があります。

<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
v<<A>>^A<A>AvA<^AA>A<vAAA>^A
<A^A>^^AvvvA
029A

一番上は人間が押すものです。次の段は-40°の場所、次は放射線の場所、最後が数字のキーパッドです。

ドアのロックを解除するためには、5つのコードを入力する必要があります（これはサンプルインプットです）。

029A
980A
179A
456A
379A

これを押すためには、以下のようになります。

029A: <vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
980A: <v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A
179A: <v<A>>^A<vA<A>>^AAvAA<^A>A<v<A>>^AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A
456A: <v<A>>^AA<vA<A>>^AAvAA<^A>A<vA>^A<A>A<vA>^A<A>A<v<A>A>^AAvA<^A>A
379A: <v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A

パズルの答えは、それぞれの長さと、それぞれのキーコードの数字部分、例えば980Aなら「980」を掛け算したものを合計したものとなります。

Part2では、別の場所にもう一人行方不明者がいたらしく（そのまま消えてください）、25台のロボットの先にあるそうです。

・ネ

・

・タ

・

・バ

・

・レ

Part1を解いてみる

今年のAoCチャレンジャーのブロッカーとなっている問題です。

結局、ルートの問題（組み合わせ問題）的なイメージで捉えればよいかと思います。

テンキーと方向キーパッドでそれぞれあるボタンから別のボタンに移動する際にいくつかのルートがあります。どれが最適なのか？というのが一番のポイントです。いずれも一意に決まります。例えば、Aから2に移動するのに、「^<」「<^」の二通りがあります。Aから4なら「^^<<」「^<<^」「^<^<」「<^^<」「<^<^」の４通りなど。数字だけならどれでもボタンのクリック数は同じですが、これに方向キーが絡むと、明らかに変わってきます。例えば、「^<^<」であれば、なんども^と<を往復しなければなりません。なので、基本的に同じキーを叩きたい、ということになります。ただ、どれか一つのパターンに絞っても、テンキーで移動する方向が異なると、方向キーでの最適なルートが変化します。なので、一旦Part1では明らかに非効率なパターン以外で進むことになります。

  • ^<^<など、同じキーパッドを叩けるのに異なるキーパッドを互い違いに押すパターンは削除（「>^>」「<v<」を削除しました）

これにより、

方向パッド：31パターン、テンキー：158　で17秒程度でRun

方向パッド：29パターン、テンキー：158　で1秒程度でRun

実は方向パッドの最適化が非常に速度に影響するようです。

Part1のワークフローは以下のとおりです。

マクロはいくつか作っていますが、以下は実際にキーパッドを叩く部分です。

これ、テンキー、カーソルキーそれぞれ全組み合わせ作成して、さらにテンキーに対してカーソルキーを適用していくとか結構重たいですね・・・。

Part 2を解いてみる

さて、Part2をどうするかです。25回カーソルキーを適用しようとするとものすごいことになりそうです。少なくとも初期の17秒のワークフローで回る気がしません。しかしながら、最適化したパターンでも15回くらいが限界です。

カーソルキーの動きでかなり短縮できたので、まずはそこの絞り込みが必要でしょう。さて、いろいろなところでヒントを得ると、どうやら一意に決まってしまうようです。

  • 左に動く場合は、先に左に動いてから上下に動く
  • 左に動かない場合は、先に上下に動く

実際に、左右と上下をどちらにするか、という検証を行っています。１と２、３と４、５と６、７と８で比較できます。

３と４、７と８については一意に決まっています。ただ、１，２が決まっていません。まぁ、なんとなく１と２だと１の方が良さそうですし、５と６だと、５の方が良さそうなことはわかります（ここまではなんとなくノーヒントですが、どっちがほんとに良いの？は懐疑的な感じでした。最終的にはヒントで確定した感じです）。

このルールを用いて、すべてのテンキーとカーソルの移動パターンから不要なパターンを取り除きます。これは目で見てリスト化しています（テンキーからは47パターン、カーソルキーからは４パターンを取り除いています）。このあたりはいわゆる「貪欲法」と呼ばれる手法になります。

さて、ルートが一意に決まってももう１仕事残っています。２５回回さなくてはいけません。これを普通にやると、文字列が長くなりすぎて回りきりません。

ここで考慮する必要があるのは、各カーソルキーは、ボタンを押すためにAに戻るということです。これはAに一度戻るため、それまでどんなルートを通ってきたかを無視して良い（Aでリセットされる）、ということになります（流れが切れるため）。その性質を使っていきましょう（いわゆる分割統治法的な考え方になると思います）。

各カーソルキーの適用の際に、A～Aで区切ります。このパターンを１回目～３回目まで適用した時にA～Aで区切れるパターンを抽出し、元のパターンから適用後にできるパターンのリストを作成します。このリストを使って、A～Aで区切ったパターンを置換検索し、その後さらにA～Aに分割する、というのを繰り返します。A～Aで区切るのは、他の流れを気にしなくて良いので、A～Aで区切ったパターンをグループ化して集計することが可能です。これにより、反復するレコード数を大幅に削減することができ、あっというまに結果を出すことが可能です（この方法は、他でも使いましたよね・・・）。つまり、以下のようなリストを作っています。パターン的には21パターンに集約されます。

これを作るためには、Part1で回していたカーソルのパターンの１，２も使います。それだけでは足りない３回目を回して、作っています。

これらを使って最後に２５回回しましょう。マクロは非常にシンプルです。

内部では常に60グループに集約されます。

Part2自体は前準備を除くと、以下のような感じです。

すべての全景は以下のとおりです。

まとめ

  • 最初、とりあえず、キーパッドの移動１パターンだけ作ってPart1に挑戦したところ、一旦テストデータは通りましたが、本番データで玉砕。ここで１０キーの通り方で最適解が変わる、ということをまず理解しました。
  • 一旦初期状態でPart1は解けましたが、Part2を解くのにPart1を最適化しました。ある程度絞り込めましたが、どーにもならず（そりゃまぁ２５回回すところの実装にミスってるのでどうにもならなかったわけです）。結局、Redditのヒントで一意にまで絞り込みます。
  • 一意に絞り込んだのに２５回回らないということで、試行錯誤し、A～Aで区切ってパターンを作成、それでも回らなくて、いつものループで集計でようやく解決（これに早く気づくべきでした）。
  • もしかしたら一意で絞り込まなくても、ループで集計法を使えばいけたのかもしれません。
  • おかげで1秒でPart1/2回ります。
  • 最後に、、、Part2で発見された行方不明者はどうなったのでしょうか？ボタンを押す回数は4416億回です。1秒に1回ボタンを押せたとしても、42万年かかります。SAYONARA！

コメント

タイトルとURLをコピーしました