Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年20日目です。
※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目。
Day 20「Race Condition」
タイトルは、「レースコンディション」。
ストーリとしては、なぜかレースに参加させられることになったそうです（なんだこの強制イベントは、、、結構クソゲーぽいですね）。毎度おなじみのMAPが与えられます（Sがスタート、Eがゴール、「.」は通れる道、#は壁）。
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############レースなのに、移動は上下左右に動くと1ピコ秒かかる、ということで、さらには一本道なので競争にもなんにもならないのですが、チート（不正行為）を行えるようになったようです。2ピコ秒だけ壁を通過できるのですが、チート終了時は通常のルートに戻る必要があります。
Part1では、チートすることで節約できる時間を出力し、100ピコ秒節約できるチートがいくつあるかを探します。
Part2では、チートできる時間が20ピコ秒に延長されました。
・ネ
・
・タ
・
・バ
・
・レ
Part1、2を解いてみる
とにかく、スタートからゴールまでのルートを取得する必要があります。一本道なのでなんちゃらアルゴリズムは不要で、まぁ、単純な反復マクロです。
楽をしたくなってきたので、次のポイントを探す時のポイント作成マクロを作りました・・・。そして、なんと今回のマクロはこれだけです！あとは素のワークフローで勝負できます。
あとから気づいたのですが、Part2の考え方はPart1でも適用できます。
Part1では、できあがったルートに対して、隣接ポイントを作成し、さらにその直線の先のポイントを作成しました。これを歩行（？）ルートとがっちゃんこしました。これで、チートポイントが確定しますが、巻き戻るチートもでてきてしまうので、歩行ルートの経過秒数を比較して、がっちゃんこできたポイントがチート前のポイントよりあとのポイントだけ抽出しています。しかしこれでは壁を通過しているかどうかわからないため、元のルートの隣接ポイントが壁かどうか、さらに壁のデータとがっちゃんこして、できたところが最終的なチートポイントです。
これ、Part2ではPart1のアルゴリズムは使えないので、別のアルゴリズムになっています。
Part2では、各歩行ポイントに対してマンハッタン距離が20以内のルートがチートの候補ポイントとなります（20ステップ以内に元のルートに戻ってこないといけないため）。単純に歩行ルートをデカルト結合し、マンハッタン距離が20以内で、結合先が各ポイントより時系列的にあとのポイントを抽出します。あとは節約できる秒数ですが、時間の差分からさらにマンハッタン距離を引いたものです。
Part2の20を2にすれば、Part1にも適合します。
まとめ
- チートをどうやって実現するかの発想がでないと非常に難しいですね
- 発想さえ出れば実装は難しくない問題でした
- 完全に後追いでやってるので、Private Leaderboardのことは忘れましょう。
コメント