Rings in the Squareの問題をPythonで解いてみた。(2)

Python

　前回作ったプログラムをNumPyを使って書き直してみました。(^_^;
　4点が同一円周上にある条件は、4次の行列式の方を使ってみました。(^_^;
　組み込み関数int()を使ったのは、np.linalg.det()の計算結果が実数なので誤差が出るためです。行列の要素が全部整数なので行列式の計算結果は整数になるはずなのでint()を使って整数化しました。

※参考URL
●numpy.linalg.det - NumPy v1.8 Manual
●Rings in the Squareの問題をPythonで解いてみた。
●行列式の値を計算するプログラムをPythonで作ってみた。(2)

● RingsInTheSquare1.py

# coding: UTF-8
# RingsInTheSquare1.py

import itertools
from time import time
import numpy as np

def main():
    tm=time()  # Timer Start

    Points = range(9)
    cnt = 0
    for p in itertools.combinations(Points,4):
        x = [n%3  for n in p]
        y = [n//3 for n in p]
        m = [[x[i]**2+y[i]**2,x[i],y[i],1] for i in range(4)]
        a = np.array(m)
        if int(np.linalg.det(a))!=0 : continue
        # チェックを潜り抜けたものだけを出力
        cnt+=1
        print("%2d : %s"%(cnt,p))

    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

 1 : (0, 1, 3, 4)
 2 : (0, 1, 5, 8)
 3 : (0, 1, 6, 7)
 4 : (0, 2, 3, 5)
 5 : (0, 2, 6, 8)
 6 : (0, 3, 7, 8)
 7 : (1, 2, 3, 6)
 8 : (1, 2, 4, 5)
 9 : (1, 2, 7, 8)
10 : (1, 3, 5, 7)
11 : (2, 5, 6, 7)
12 : (3, 4, 6, 7)
13 : (3, 5, 6, 8)
14 : (4, 5, 7, 8)
Runtime : 0.025 [sec]

※参考図

 6---7---8
 |   |   |
 3---4---5
 |   |   |
 0---1---2

P.S.
　ちなみに、4次の行列式計算に拙作のdet4()関数を使えば次のようになります。行列を変換しなくていいのと整数だけだから元のよりちょっと速いようです。o(^-^)o

● RingsInTheSquare2.py

# coding: UTF-8
# RingsInTheSquare2.py

import itertools
from time import time

def det4(m):
    r = (m[0][0]*m[1][1]-m[0][1]*m[1][0])*(m[2][2]*m[3][3]-m[2][3]*m[3][2])
    r-= (m[0][0]*m[1][2]-m[0][2]*m[1][0])*(m[2][1]*m[3][3]-m[2][3]*m[3][1])
    r+= (m[0][0]*m[1][3]-m[0][3]*m[1][0])*(m[2][1]*m[3][2]-m[2][2]*m[3][1])
    r+= (m[0][1]*m[1][2]-m[0][2]*m[1][1])*(m[2][0]*m[3][3]-m[2][3]*m[3][0])
    r-= (m[0][1]*m[1][3]-m[0][3]*m[1][1])*(m[2][0]*m[3][2]-m[2][2]*m[3][0])
    r+= (m[0][2]*m[1][3]-m[0][3]*m[1][2])*(m[2][0]*m[3][1]-m[2][1]*m[3][0])
    return r

def main():
    tm = time()     # Timer Start

    Points = range(9)
    cnt = 0
    for p in itertools.combinations(Points,4):
        x = [p[i]% 3 for i in range(4)]
        y = [p[i]//3 for i in range(4)]
        m = [[x[i]**2+y[i]**2,x[i],y[i],1] for i in range(4)]
        if det4(m)!=0: continue
        # チェックを潜り抜けたものだけを出力
        cnt+=1
        print("%2d : %s"%(cnt,p))

    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

Python入門[2&3対応]

Python入門[2&3対応]