Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2025年3日目です。
※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目。
Day 3「Lobby」
タイトルは「ロビー」。
Day2からは階段で降りてきたのですが、さらに下に下るには、エレベータがオフラインになっているとのことです。オフラインの原因は、バッテリーにあるようで、バッテリーを治す必要があります。
インプットは以下のような感じです。
987654321111111
811111111111119
234234234234278
818181911112111横を一列としたときに、Part1では2つのバッテリをオンにする必要があります。2つのバッテリをオンにしたときに、左側が10の桁、右側が1の桁になるのですが、この一列の中で、左と右を組み合わせて最大になるバッテリをオンにする必要があります。例えば、１行目なら98が最大。次は、最初と最後で89・・・。最終的にはこの例では、98+89+78+89で357が求める答えです。
Part2では、12個のバッテリをオンにする必要があります。サンプルのインプットだと3つ破棄すれば良いだけではありますが・・・。実際の問題では100桁もあります。
・ネ
・
・タ
・
・バ
・
・レ
Part1、2を解いてみる
難しいのは、どのようなアルゴリズムで残していけば良いのか、というところかと思います。Part1はたった2つ取るだけなので、比較的シンプルなアルゴリズムで対応できます。
１文字目は左から見た時に一番大きな文字を取ります。２文字目は右から見た時に一番大きな文字を取ります。このとき、１文字目を取る時に、一番右の文字を取ると桁が１つになってしまうので、文字列の長さ-1までで一番大きい数字を探す、ということになります。２文字目を取る時は、取った一文字目より右の数字の中で一番大きなものを取る、というアルゴリズムでクリアできます。
818181911112111であれば、赤文字の中で最大の数字を取ります（今回は、9ですね）。
２文字目は、9より右の文字が検索範囲です。
818181911112111つまり、2です。この列は92となります。
Part2はこの考え方は使えません。最初、右の数字の方が大きければ、消す、みたいな感じでやれば良いかな、と組んでみたのですが、全然うまく行かず、、、サンプルだと全部で15文字あるから単に３文字消さばいいだけでしょ？とやると、本番が100文字あってそもそも考え方ぜんぜん違うじゃん、とやって時間が取られ、、、結局全パターン検査する方向のが正解、ということになりました。この方向性の転換で今回時間が取られたのですが、AoCについてはさっさと変なアルゴリズム組むより、全パターン検査を考えて、そこからどう絞れるか、の方が近道ではないかと思います。
全パターン検査の場合は、一文字消す、というのを全パターンやってみて、１文字消した時に一番大きい数値を残して、さらに一文字消して一番大きなものを残す、、、とやればオッケーです。一気に全パターンを作るとおそらくデータ量が爆発するように思います。
つまり、これは、、、繰り返しマクロってことになります。
三日目で繰り返しマクロとは、、、さすが12日に短縮されただけのことはあります。
ということで今回のワークフローは以下のとおりです。
マクロ：
結論としては、これ同じマクロ使えばPart1も2もできますね・・・（今回はPart2のマクロは12文字まで実施するようにハードコーディングしています）。
まとめ
- コミュニティで他の方のSolutionを見ると、結構いろんなやり方している人が多くてびっくりです。
- P1の延長線上の方法やろうとして失敗した上で、P2を頭リセットしてゼロから考え直したので途中時間をロスしました。
- 私のP2のやり方は異端ぽい・・・。
コメント