※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、1日目、2日目、3日目、4日目、5日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目。
第拾肆話 「Parabolic Reflector Dish」
タイトルは「パラボラ反射板」。タイトルだけ聞くと不穏な感じがします。
前回鏡を抜けたあと、鏡の向いていた場所に到着したようです。そこには巨大なパラボナアンテナのようなものがある場所に来ました。小さい鏡が大量にあり、それが全体としてパラボナアンテナのようなものを形成しているようなのですが、それぞれの鏡の向きはバラバラのようです。
今回は、その焦点を合わせるために、プラットフォームを操作するようです。そのプラットフォームはいずれかの方向(東西南北)に傾けることができ、傾けるとそちらの方向に◯がよっていきます。#は岩のため、動きません。鏡の◯は#で止まってしまいます。「.」(ドット)は何もない空間です。
現在の状況は以下のとおりです(パズルのインプット)。
O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....
北に向けると、
OOOO.#.O..
OO..#....#
OO..O##..O
O..#.OO...
........#.
..#....#.#
..O..#.O.O
..O.......
#....###..
#....#....
となります。それぞれの◯は上側に寄っていきます。何もなければ一番上からたまっていきますし、#があれば#で止まります。
さて、ゴールは荷重を数えることです。それぞれの◯は、下側からの距離の分だけ重さを持ちます。すなわち、1列目は、「7+8+9+10」=34、2列目は、「8+9+10」=27、3列目は、「3+4+10」=17、4列目は「10」、5列目は「8」、6列目は「7」、7列目は「7」、8列目は「4+10」=14、9列目は「0」、10列目は「4+8」=12。合計すると136です。
Part2は、北→西→南→東と傾けた結果を1サイクルとし、1000000000サイクルのときの荷重を数える、ということになります。
・ネ
・
・タ
・
・バ
・
・レ
Part1、2を解いてみる
Part1は色々な手法で解くことができるかと思います。ぱっと思いつくのは、列ごとにデータを持ち替えて、置換検索で「.◯」があれば「◯.」に置換するのを繰り返す、というところでしょうか。
今回は、行生成ツールをForループ代わりに使いました。これによりマクロなしでいけます。
例えばこのようなインプットがあります。
これに対して、行生成ツールで以下のように展開できます。これは、設定として、「Concat_Input」フィールドに対してアップデートをかけるのですが、初期は「Concat_Input」とし、Loop式に
REGEX_Replace([Concat_Input], "\.O", "O\.")
として置換をしてしまいます。その結果、判定式は
REGEX_Match([Concat_Input], ".*\.O.*")
とし、つまり「.O」があるうちは実行する、という形にします。
ただし、この場合最後の一回が実行されないので(正確には実行後に結果を捨てているように思います)、再度フォーミュラツールで一度実行してあげる必要があります。
いずれにしても、上のデータのうち、一番下に来るものが最終の結果なので、サンプリングツールで最後の一つを取ります。
この一連の動きは以下のようになります。
最終的なPart1のワークフローは以下のとおりです。
Part2は2022年のAoCのDay17の俗に言う「テトリス」で使ったテクニックが必要です。問題文では1000000000回(10億回)ループをしなさい、とありますが、いつ終わるかわかりません。ボールの動きを見ていると、何度も同じような動きをするように見えると思います。つまり、このような動きがパターン化して収束するものは、その結果からパターンを見つける必要があります。
まず、1サイクルを処理しましょう。これができないと始まりません。今回は反復マクロにしました。とはいえ、Part1でやった北の処理をデータの持ち方を変えて、置換条件を少し変えたものを並べればすぐにできます。
次に出てくる結果を見てみましょう。最初の方は収束していないので、ある程度たったところを見る必要があります。以下によると、443行目~449行目をパターンとしてこれを繰り返しています。
頭から1000000000レコードのところでどうなるか、計算で求めるだけです。基本的にはMOD関数を使います(と、簡単に言ってますが、目視でパターンを見つけて手計算した方が正直早いです。Designerでループを見つけるアルゴリズムを組むのは結構骨が折れます)。
ちなみにループ自体の長さを見つけ(loop lengthのところ)、ループの開始地点を特定するのに以下のワークフローが必要でした。特に、ループを見つけるのにどれくらいのデータが必要になるかは、ループの長さによって変更する必要があるかもしれません。本番データでは44個でループしていたので、ループのサンプルは50個でたまたまうまくきました(サンプルデータの場合はもっと短くて、ループ長はたったの7です)。
最終的には、以下の関数で所定の答えがあるレコードを見つけました。
MOD(1000000000-[RepeatPoint],[NextCount])+[RepeatPoint]-1
※NextCountがループ長、RepeatPointはループ開始地点(データのどこのループでもいいです)
最終的なワークフローは以下のとおりです。
まとめ
- テトリス再来!(2022年のAoCのDay17)
- Private Leaderボードで、Part1は22分で解けて3位でしたが、Part2で手間取って総合7位でした。しかも、最初は手計算でクリアだけして、あとから帳尻合わせでポジション合わせ部分を作りました。最速の方でも1時間40分かかっていますね・・・。
- 正直繰り返しパターンを読むのは目検の方が早いです・・・。初見だと迷宮入りしてもおかしくない問題かと思います。
コメント