Advent of Code 2023 Day 18 Lavaduct Lagoon ですが、回答にあたって、個人的にたいへん苦労したので、解き方や考え方のメモを残しておきたいと思います。
この問題はPart1、Part2ともに、次のように言い換えることができます。
「ある多角形が与えられるので、その辺上の格子点の数と、内部にある格子点の数を合計した数を求めなさい。」
① 辺上の格子点の数
これは問題文を正しく解釈すれば簡単に求めることができます。
② 内部にある格子点の数
難しいのはこちら。これを求めるにあたってはピックの定理を利用します。
\displaylines{
多角形の面積 = 内部にある格子点 + 辺上にある格子点 \div 2 - 1 \\
\Leftrightarrow 内部にある格子点 = 多角形の面積 - 辺上にある格子点 \div2 + 1
}
先述したとおり、辺上にある格子点の数は計算済み。では多角形の面積はどのように求めればよいのかというと、shoelace formulaを利用します。多角形の頂点の座標が$(x1,y1),(x2,y2)\ldots(x_n,y_n)$とすると、その面積は以下の式により求めることができます。
Area = \frac{1}{2}\left| \sum\limits_{i=1}^n (x_iy_{i+1} - x_{i+1}y_i) \right|
なお多角形の頂点の座標については、問題の入力を正しく解釈すれば簡単に求めることができるはずです。
解答(Python)
参考文献