Grundy数を使って1次元ドミノ置きゲームを解く（その２）

その１はこちら

#####【問題】1次元のマス目（1xN）に交互にドミノ（1x2）を置いて行って置けなくなった方が負けというゲームで、先手が必ず負けになるN<100をリストせよ。

この問題をGrundy数を使ってN＝7までの結果の再び表にします。

N	mex	Grundy数
N=0		0
N=1		0
N=2	$mex(G(0))$	1
N=3	$mex(G(1))$	1
N=4	$mex(G(1),G(2))=mex(0,1)$	2
N=5	$mex(G(3),G(1)\oplus G(2))=mex(1,1)$	0
N=6	$mex(G(4),G(1)\oplus G(3),G(2)\oplus G(2))=mex(2,1,0)$	3
N=7	$mex(G(5),G(1)\oplus G(4),G(2)\oplus G(3))=mex(0,2,0)$	1

これから推測されるように、任意のNの時のGrundy数は以下の式で表せます。

• $G(N) = mex(\\ G(0)\oplus G(N-2),\\ G(1)\oplus G(N-2-1),\\ ...\\ G(k)\oplus G(N-2-k))$

ここで$0\leqq k \leqq floor(N/2)$

これをそのままPythonのプログラムにします。まずmex関数を定義します。単純に0からリストの最大値まで見ていって、ない数があったらそれを返し、もし全部あった場合は最大値+1を返します。

def mex(gl):
  for i in range(max(gl)+2):
    if i not in gl: return i
  return ("error")

これを使って$G(N)$の計算を行います。2つ前までのGrundy数のリストを逆順にしてXORを取り、mexを見つけてGrundy数のリストに加えるのを繰り返せばOKです。
(XORを取るのは半分までで良いのですがコードを簡単にするために全部取っています)

import numpy as np
n = 100

GL = np.array([0, 0])  # G(0), G(1)
for i in range(2, n+1):
  GL = np.append(GL, mex(GL[:-1]^GL[-2::-1]))

print(list(*np.where(GL==0)))
# [0, 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63, 73, 77, 89, 93, 97]

これでオンライン整数列大辞典に掲載されていた数列のN<100が計算できました。