トボガントラジェクトリーー
Advent of Code 2020 第3日目
シミュレーターを試してみてね！
タスク: Xを解いてみよう。ここでXは...
X = N個のトラジェクトリーそれぞれで当たる木の数
- N = 1
- N = 5
例の入力
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
これは以下を表しています:
- 林の範囲
- '.'は開けた地域、'#'は木
第1部
- 正しいメンタルモデルを見つける
- このモデルを実装するために
moduloを使う - 動作するアルゴリズムを書く
正しいメンタルモデルを見つける
- 指示によると、林の範囲は右へ無限に広がっている
- これはこのように表される:
..##.........##.........##.........##.........##.........##.......
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#
北西から南東への経路はこんな感じ:
-
-
-
-
-
-
-
-
-
-
-
-
でもコツはそのメンタルモデルをもっとスパイラル階段や円筒形に変えること:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
moduloを使ってこのモデルを実装する
- 例の入力で第1部の軌道に従って出た結果はこんな感じ:
O.##.......
#..O#...#..
.#....X..#.
..#.#...#O#
.X...##..#.
..#.X#.....
.#.#.#.O..#
.#........X
#.X#...#...
#...#X....#
.#..#...X.#
-
-
-
-
-
-
-
-
-
-
-
0
3
6
9
1
4
7
10
2
5
8
- 0から3、6、9へ行くのは簡単
- でも9から1へは？どうやればいい？
Moduloはある値を別の値で割った後の余りを計算する。
- 例の入力では1行に11文字がある
9 % 11 == 9(9 + 3) % 11 == 12 % 11 == 1
ほら！moduloを使って、行の長さ、現在のインデックスと適切なオフセットを加えると、各反復作業で正しい水平の位置が得られる。
動作するアルゴリズムを書く
入力を新しい行ごとに文字列の配列に分ける
各文字列を文字の配列に分ける
row, col, hitsの変数をセットする...すべて0から始める
処理済み入力のrowの位置が存在する限り
rowとcolの値が#ならhitsを1増やす
rowを1増やす
colを更新して、col と 3 の合計をネストされた配列の長さで割った余りと等しくする
hitsに入っている値を返す
第2部
- スコープの拡大を理解する
- 更新された動作するアルゴリズムを書く
- シミュレーターを作る
スコープの拡大を理解する
- 第1部には単一の軌道があった: (3,1)
- 第2部には5つの軌道がある
- 従って、私のアルゴリズムは今全ての5つの軌道に対する当たる木の数を生成して...それから全てを掛け合わせた積を計算しなくてはならない
更新された動作するアルゴリズムを書く
入力を新しい行ごとに文字列の配列に分ける
各文字列を文字の配列に分ける
5つの2要素配列を持つ配列をセットする各軌道を表すために
各軌道について
2要素配列を操作して以下の操作に従う当たる木の数の数に変える:
row, col, hitsの変数をセットする...すべて0から始める
処理済み入力のrowの位置が存在する限り
rowとcolの値が#ならhitsを1増やす
rowを元の2要素配列の1の位置の値だけ増やす
colを更新して、col と 元の2要素配列の2の位置の値の合計をネストされた配列の長さで割った余りと等しくする
それぞれの値を掛け合わせた後の積を返す
シミュレーターを作る
- 有効な入力について、各軌道の経路をレンダリングしたい
- トラジェクトリに応じたボタンを押すと、森の領域はリセットされ、それから逐次的に各XとOをレンダリングするべき
2021年の一部のパズルでこのらせん状のアルゴリズムに出会ったことはありがたいことだった。
そういうわけで、このパズルは特に解くのが簡単に感じた。
こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/rmion/toboggan-trajectory-2e2g
