The Rows of cakes (Alice In Wonderland) - ケーキの列を数えよ

どんな問題？

The Rows of cakes
http://www.checkio.org/mission/cakes-rows/

多数のケーキが床に置かれている。3つ以上のケーキが一直線上に並んでいれば、1列(row)と数える。全部で何列あるかを数えよ。
4つ以上が1直線上に並んでいる場合も1列と数える。

3個以上のケーキが1直線上に並んでいるパターンを見つける問題。
ケーキって言うから、クリスマスケーキみたいなのをイメージしていたけど、カップケーキだと思えば状況がわかりやすい。

引数は、各ケーキの座標[x,y]のlistが渡される。
戻り値は、列の数を返す。

ケーキの数は1以上20未満、ケーキの座標は、0≦x,y≦10

例題：

checkio([[3, 3], [5, 5], [8, 8], [2, 8], [8, 2]]) == 2
checkio([[2, 2], [2, 5], [2, 8], [5, 2], [7, 2], [8, 2], [9, 2], [4, 5], [4, 8], [7, 5], [5, 8], [9, 8]]) == 6

どうやって解く？

問題文通りに素直に考えてみる。

• 全ケーキから3つを選び出す。（組み合わせ）
• 3つが同一直線上にあるかどうかをチェックする。
• 同一線上にあれば、その直線上にある他のケーキも探す。
• 重複した直線を除いて、直線の数を返す。

まず、3点が一直線上にあるかどうかを判定するのはどうしたらいいんだろう？ググってみた。

数学的には、(X1,Y1) (X2,Y2) (X3,Y3) の３点が同一線上にある場合
Y1 (X2 - X3) + Y2 (X3 - X1) + Y3 (X1 - X2) = 0
となります
http://studio-jo.net/cad/lisp_memo/equal2.htm

そのまま使わせていただこう。

def on_same_line(p1, p2, p3):
    # 点p1,p2,p3が同一線上にあればTrue
    (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3
    return y1 * (x2 - x3) + y2 * (x3 - x1) + y3 * (x1 - x2) == 0

重複した直線を除外するには、直線をsetとして定義すれば簡単かな。ただし、listやsetはunhashableなので、setの要素として使うことができない。setの要素として使うためには、listはtupleに、setはfrozensetに変換する必要がある。
引数の座標[x,y]は(x,y)に変換しておく。直線は set of tuple(x,y)として作成し、frozensetにキャストしてからlinesに追加する。

「3つが同一線上にあれば、その直線上にある他のケーキも探す。」という部分はこのように書いた。

line = {a, b, c} | {p for p in cakes - {a, b, c} if on_same_line(a, b, p)}

3つ(a,b,c)以外で、a,bと同じ直線上にあるケーキがあれば「|」で追加している。

まとめ

def checkio(cakes):
    # list of list から set of tuple に変換
    cakes = {(x, y) for x, y in cakes}
    lines = set()
    for a, b, c in itertools.combinations(cakes, 3):
        if on_same_line(a, b, c):
            # a,b,c以外で同一線上にあるケーキを追加
            line = {a, b, c} | {p for p in cakes - {a, b, c} if on_same_line(a, b, p)}
            lines.add(frozenset(line))
    return len(lines)

http://www.checkio.org/mission/cakes-rows/publications/natsuki/python-3/first/

他の人の答え

itertools.combinations(cakes, 2)

としている人が多かった。
たしかに、

• 3つが同一直線上にあるかどうかをチェックする。
• 同一線上にあれば、その直線上にある他のケーキも探す。

という部分は、１つにまとめられる。

上のコードを直すとしたら、こんな感じかな。

    for a, b in itertools.combinations(cakes, 2):
        line = {p for p in cakes if on_same_line(a, b, p)}
        if len(line) >= 3:
            lines.add(frozenset(line))

さて、これでAlice In Wonderland も終了。なぜかこのステーションだけ終了バッジがもらえた。
Ice Base や Mine は難しそうなので、次は O'Reillyに行こう。