※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、1日目、2日目、3日目、4日目、5日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目
13日目です。画像は13日目を解いた時点のものに差し替えています。
タイトルは、「Distress Signal」、つまり「救難信号」です。どちらかというと、我々が助けてほしい感じでした・・・。
今回の問題は受信した信号をデコードするという問題ですが、中身は鉤括弧の入れ子構造の解析です。
サンプルの入力データとしては、以下のようになっています。
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[9]
[[8,7,6]]
[[4,4],4,4]
[[4,4],4,4,4]
[7,7,7,7]
[7,7,7]
[]
[3]
[[[]]]
[[]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]
各2行がセットになっていて、上の列を左側、下の列を右側、といった感じで扱います。つまり、最初の2行だと、以下のようにしてこのデータを破棄するか、採用するかという判定を行っていきます。
[1,1,3,1,1] | [1,1,5,1,1] |
先頭から1列ずつ比較し、左側の数値の方が小さければOK。そうでなければNGという判定を行います。一つでもNGがあればこのセットのデータは破棄、という形になります。
また、各データは列数が異なるケースがあり、左側が少ない場合は残りのデータは破棄してかまわないのですが、そうではない場合はNGとして判定されます。
しかし、様々なパターンがあり、以下のような組み合わせの場合、
[9]
[[8,7,6]]
以下のようになりますが、
[9] | [[8,7,6]] |
これの外側の鉤括弧をはずすと、左側が整数値、右側がリストになります。
9 | [8,7,6] |
このような場合は、整数値を一旦リストに変換してから比較することになります。つまり以下のような形にして比較します。
[9] | [8,7,6] |
最終的に、採用して問題ない組み合わせの番号(上から1、2、3と番号が付きます)を合計したものを出すのがPart1です。
Part2はPart1よりも遥かに簡単で、すべてのパケットを並べ替える問題です。その際、[[2]]と[[6]]のパケットを加えて、先頭から見たときの位置を取得しかけ合わせます。
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
今のところ未解決問題になっているので、解けたら更新します。
まさか一番最後まで残る問題とは思いませんでしたが、とにかく解けました・・・。
サンプルだと、非常にシンプルですが、本番データは、例えば以下のような形です。
[[[[2],9,1,[2,2,4,8]],[1,8,8],9,[7,2,[7,0,1],0,[10,9,10,3]]]]
[[1,6,[[0,0,10,9]],[[10,6,0,2],[7,4],[2]],[[],3]],[[2,7,2],5,[[7,0,5],[8],1,[],3],2]]
リストが入れ子構造になっていて手動でやっても非常にわかりにくいです。
Part1は、整数に着目し、リストと比較する必要があるものがあれば、まずリスト化します。これをリスト化する必要なくなるまで再帰的(繰り返し)に行っています。このとき、リスト化する必要のある整数が見つかった場合、それよりあとのものは何も行いません。
リスト化する必要のあるものがなければ、実際の比較を行います。条件は以下のようにしました(1は正しくない順番としています)
- 左側が小さければFlagを-1として比較終了(一つ前のFlagが-1であればそれを持ってくるようにし、それ以上の比較を行わないようにしています)
- 右側が大きければFlagを1として比較終了
- 数値が同じであればFlag0として引き続き比較します
- 左が]で右が数値なら比較終了します(左がEmptyなので比較終了)
- 左が数値で右が数値でないなら右がEmptyでFlagを1で比較終了
- 左が]で右が[であれば、Flag-1にして比較終了
- 左が[で右が]であれば、Flag1にして比較終了(右がEmptyなので比較終了)
- 上記に当てはまらない場合はNullとして何もしません
正直、すべてをコントロールするというより、問題文で提示された条件でパケットを処理するだけの問題です。サンプルデータはかなりシンプルなので、本番データが複雑すぎて条件の作り方がきっちりいかなかったです。
深さを見ながら当初やろうとしていましたが、うまくいきませんでした・・・。
最終的なPart1のワークフローは以下のとおりです。
Part2は、完全にPart1無視で、与えられたパケットをソートするだけの問題でした。空パケット([])は、0に変換し、一番左の数字を抽出し、並べ替えました。ただ、[[2]]と[[6]]は頭が2もしくは6で始まるパケットの中でも一番最初に持ってこないといけないので、カッコを削除して2,9,1,1・・・といった形にしたもので並べ替えを行っています。
Part2含めたワークフローは以下のとおりです。
まとめ
- 13日目も、Advent of Codeによくある問題で、データ解析の問題です。
- 当時完走した人は5名でした。もうタイムより解けるかどうか、というレベルの問題です。
- 個人タイム:時間をかけてじっくりやりました。
コメント