※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、１０日目、１１日目、１２日目、１３日目、１４日目
１５日目です。トップの画像は２５日まで完走したものを使っています・・・。
タイトルは、「Beacon Exclusion Zone」。ビーコン除外領域、でしょうか。
今回の問題は、センサーでビーコンの位置を特定する問題です。
サンプルの入力データとしては、以下のようになっています。
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3これは、センサーの場所（x、y座標）と、最も近いビーコンの位置が記載されています。この「近い」というのは、マンハッタン距離とのことで、つまり斜めに行くのに直接行けず、縦、横を辿る必要があるので、斜め方向は距離２となります。また、最も近いビーコンの位置なので、これより近い位置にビーコンはありません。
例えば、x=8, y=7のセンサーに着目すると、以下の＃の範囲内には指定されたビーコンのみしかないということになります。
1 1 2 2
0 5 0 5 0 5
-2 ..........#.................
-1 .........###................
0 ....S...#####...............
1 .......#######........S.....
2 ......#########S............
3 .....###########SB..........
4 ....#############...........
5 ...###############..........
6 ..#################.........
7 .#########S#######S#........
8 ..#################.........
9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....Part1としては、y=2000000の行に、ビーコンが存在できないポイント（つまり、＃になるポイント）が何ポイントあるかを算出します。
Part2は、遭難ビーコンを見つけます。つまり、入力データのセンサーには遭難しているビーコンはないため、センサーが届いていないポイントを探す必要があります。その範囲は、x、y座標ともに0から4000000の範囲内にあるとのことです。場所が見つかると、周波数を設定する必要があるとのことです。x座標×4000000にy座標を足すことで必要な周波数が得られます。
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
センサー位置とビーコン位置からビーコンが存在できない場所を各センサーについて作り出します。その結果を集計するだけで答えが特定できます。単にx、y座標に対して処理を行っていくだけですので、１４日目の問題が解けるようであればそれほど苦労しないと思います。
Part1では必要ないですが、Part2では今回は特にマクロを使っていませんが、ちょっとしたトリックを使っています。
今回x、y座標と2つのパラメータを同時に操作しないといけないので、通常であれば反復マクロを使うのですが、複数行フォーミュラの中にテキスト形式で２つのパラメータを押しこみ、内部で計算を無理やり行っています。これによりかなりの高速化が図れ、ワークフロー自体がシンプルになります。
ところで、今回の問題は可視化した際に非常に広い領域になるため、なかなか可視化も現実的ではありません。ただ、サンプルデータでしっかりロジックが組み立てられれば、単に数量との戦いになるだけなので、あとはどう絞り込むか、というだけの問題になります。
Part1については、特定の行に対しての実行なので、ある程度絞り込むことも可能かと思いますが、そのままやっても十分処理しきれる量です。ちなみに、ユニオンツールの手前までがベーシックなデータ準備です。
Part2については、ある程度範囲が決められているので、その範囲に絞り込んで実行する必要があります。Part1とは出力するものが異なり、存在しないものを出す必要があります。この場合、すべての点を作って比較する方法もありますし（ポイント数が多すぎると処理しきれない可能性があります）、ちょっとしたロジックを作る方法があります。ちなみに今回は、x座標ごとにy座標を検査し、途切れているポイントがあるかどうか、という観点で見ていくようなロジックを構築し、全ポイントを検査しないようにしました。ただ、得られているデータがy1からy2へのラインのデータで、重なり合うような形だったので、複数行フォーミュラでちょっとしたロジックを組む必要がありました（おかげで、3分40秒くらいで実行できています）。
まとめ
- １５日目も、図形的な問題です。今回はそこまで複雑な問題ではないので、うまくセンサーの範囲を作れれば問題ありません。ただ、パッと見でわかりにくい問題です・・・（とっつきにくいというか・・・）。
- といいつつも、クリアされている方はそれなりですが、時間的にはそれなりにかかっているようです。膨大なデータをどう絞るか、、、知恵を問われる問題です。
- 個人タイム：数日にかけて解きました（Private Leaderboardで3位）
コメント