Google code jam 2008 round 1 Bの問題A. crop trianglesに挑戦する.
$x$-$y$平面上の点のうち,$x$座標も$y$座標も整数値となっている点を整数格子点という.
この問題を入力と出力で定義すると,
である.
ただし,この問題では3点が異なっていれば(その3点が一直線上にのっていたとしても)三角形と見なす. 一方で,3点のうち重複があったら三角形ではないと見なす.
なお,この問題では,入力の$n$点の座標値が直接与えられるわけではなく,点の座標値を$n$個生成するための関数(正確には関数のパラメータ)が与えられる.
予備知識だが,この点の座標値を生成する方法は「線形合同法」とよばれる. これは,擬似乱数を生成する最も単純な方法として用いられるものである.
入力と,それに対する正しい出力の例は,残念ながら陽には与えられていない.
まず,問題のページの説明に従って,入力の点座標を生成する関数を以下にgenarate_pointsとして定義する.
def generate_points(n, a, b, c, d, x_0, y_0, m):
x = x_0
y = y_0
point = [(x, y)]
for i in range(1, n):
x = ((a * x) + b) % m
y = ((c * y) + d) % m
point += [(x, y)]
return point
早速サンプルの1つ目の4点を生成してみる.
point4 = generate_points(4, 10, 7, 1, 2, 0, 1, 20)
point4
[(0, 1), (7, 3), (17, 5), (17, 7)]
座標だけではイメージがわかないかもしれないので,実際に点をプロットして様子を見てみる.
なお,直下のコードは描画用のコードなので気にしないでほしい.
# このコードは描画用
import numpy as np
import matplotlib.pyplot as plt
% matplotlib inline
plt.figure(figsize=(19/2, 8/2))
plt.axis([-1, 18, 0, 8])
z = plt.plot([0, 7, 17, 0], [1, 3, 5, 1], 'r-')
z = plt.plot([8], [3], 'ro', ms=16)
z = plt.plot(np.array(point4)[:,0], np.array(point4)[:,1], 'o')
plt.grid(True)
z = plt.xticks(np.arange(-1, 19, 1))
上図の青い点が入力の点である.
手計算で確認すると,上記の赤い三角形の重心(赤丸)だけが整数格子点である.
次にサンプルの2つ目の6点を生成してみる.
point6 = generate_points(6, 2, 0, 2, 1, 1, 2, 11)
point6
[(1, 2), (2, 5), (4, 0), (8, 1), (5, 3), (10, 7)]
こちらもプロットしてイメージを掴むことにする.
# このコードは描画用
% matplotlib inline
plt.figure(figsize=(11/2, 9/2))
plt.axis([0, 11, -1, 8])
z = plt.plot([1, 4, 10, 1], [2, 0, 7, 2], 'r-')
z = plt.plot([5], [3], 'ro', ms=16)
z = plt.plot([2, 8, 5, 2], [5, 1, 3, 5], 'r-')
z = plt.plot(np.array(point6)[:,0], np.array(point6)[:,1], 'o')
plt.grid(True)
z = plt.xticks(np.arange(0, 12, 1))
上図の青い点が入力の点である.
手計算で確認すると,今度は2つの三角形(上図の赤い三角形)の重心が整数格子点である. 三角形の1つは,3点が一直線上にのっているため,潰れている. この問題ではこれも三角形とみなす. このサンプルでは,たまたま赤い2つの三角形の重心が同じ点である.
$n$点から三角形の頂点を3つ選ぶ組み合わせは$_n\text{C}_3$通りなので,そのそれぞれに関して重心を計算してその座標値が整数となるものの数を数える.
この方針で出力される答えは正しいはずであるが……実際に解けるであろうか?
Small datasetならば間違いなく解けるはずなので,small datasetだけでも解いて欲しい.
今回も説明なしに丸括弧()を使ってしまったので,そろそろPythonにおける丸括弧()の役割を説明する.
Pythonではリストに似て非なるデータ構造であるタプルの表現に丸括弧を用いる. 以下に使用例を示す.
x = (3, 1, 'a', 2.22)
x
(3, 1, 'a', 2.22)
for i in range(4):
print(x[i])
3 1 a 2.22
これだけ見るとリストと何も変わらないようにみえる.
しかしリストと同様に要素を変更しようと試みると,
x[2] = 5
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-11-ec1532708085> in <module>() ----> 1 x[2] = 5 TypeError: 'tuple' object does not support item assignment
エラーとなる.
タプルはリストと異なり,一度作ったら,内容の変更はできない. 要素の並べ替えなどもできない.
これだけだとリストの劣化版という感じがする.
しかし,内容の変更をできないからこそ,使える場面がある. 以下に例を示す.
x = (3, 2)
y = [3, 2]
dicx = {x: 4}
dicx
{(3, 2): 4}
dicy = {y: 4}
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-15-3efb4a153881> in <module>() ----> 1 dicy = {y: 4} TypeError: unhashable type: 'list'
リストは辞書のキーには使えないが,タプルは辞書のキーに使えるのである.
詳しく説明するためには「ハッシュ」というデータ構造をまず説明しないといけないのだが,すごく簡単に言うと
「辞書のキーは値を格納する住所みたいなものだから『変更可能なデータ』は使えない(住所が変わっては困る)」
ということである.
他にも,プログラムの実行中に変化しては困るデータをタプルとして格納することによって,(人間の不注意による)ミスを防ぐという使い所もある.