2014年11月24日月曜日

プロジェクトオイラー 問97

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問97「大きな非メルセンヌ素数」
100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 26972593-1 である. 実際, 2,098,960桁ある. 
それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている.

しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. 
これは2,357,207桁の数であり, 28433×27830457+1である.

この素数の末尾10桁を答えよ.






注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。
def f(a, n, p, b, m):
	k, t, c = n, 10**m, 1
	for s in str(p)[::-1]:
		c *= k**(int(s))%t
		k = k**10%t
	return (a*c+b)%t

def f2(a, p, b, m): return ((a<<p)+b)%(10**m)

#(a×(nのp乗)+b)の末尾m桁を返す
a, n, p ,b ,m =28433, 2, 7830457, 1,10
s = f(a, n, p ,b ,m)
print s

#(a×(2のp乗)+b)の末尾m桁を返す
a, p ,b ,m =28433, 7830457, 1,10
s = f2(a, p ,b ,m)
print s


1.関数f(a, n, p, b, m)
・a×np+b の末尾m桁を返します。

・for s in str(p)[::-1]:
 数値pをstr関数で文字型にして、文字のスライス機能の[開始:終了:刻み]での刻みを-1にすることで右から1文字ずつ、つまり1の位の数字から順に1つずつ取り出し、ループ変数sに設定します。

・c *= k**(int(s))%t
 k = k**10%t
 変数kは、ループ変数sの桁位置に相当するnの累乗値を設定します。
 初期値はnで、ループが回るにつれ、nの10回累乗、100回累乗、...と直前の累乗値を10回ずつ累乗していきます。
 変数cに、kのs乗をかけて、ためていきます。
 例えば、
 2の345乗ならば、(2の5乗) x ((2の10乗))の4乗) x ((2の100乗)の3乗)です。
 このときの「2の10乗」「2の100乗」が変数kで、各桁の数字が変数sです。

2.(別解)関数f2(a, p ,b ,m)
・a×2p+b の末尾m桁を返します。
 関数の中の累乗計算を、2の累乗に固定します。

・a<<p
 数値aをpビット左にシフトすることで、2進数でp桁繰り上がります。
 これは、数値aに対して2をp回かけることと同じです。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
8739992577

2014年11月4日火曜日

プロジェクトオイラー 問96

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問96「数独」
"数独"(日本語で数字を配置するという意味)とは人気があるパズルの名前である.
起源は不明だが, その評判はラテン語で"Squares"と呼ばれる同様な, 
そしてはるかに難しいパズルを考案したレオンハルト・オイラーの貢献によるものに違いない. 
しかしながら, "数独"パズルの目的はそれぞれの行, 列が3×3の枠を含む9×9の格子の空白(もしくは0)をそれぞれ1から9の数字で置き換えることである. 
下に, 一般的なパズルの開始状態とその解答の例がある.



うまく作られている"数独"パズルは, 選択肢を消去するために"仮定とテスト"方式を用いる必要があるかもしれないが, ただ一つの解を持ち, 論理によって解くことができる(これについては様々な意見がある).

探索の複雑さがパズルの難易度を決定する; 上に挙げた例は, 単純で直接的な推論によって解く事ができるため, 簡単であると考えられる.

6kバイトのテキストファイルsudoku.txt(右クリックで,"名前をつけてリンク先を保存") にはただ一つの解を持つ, 様々な難易度の50の"数独"パズルが含まれている(上の例題はこのファイルにおける最初のパズルである).

50すべてのパズルを解き, それぞれの解答の左上隅にある3桁の数の合計が求めよ; 
例えば483は上の解答例の左上隅の3桁の数である.






注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。







私の回答例は以下の通りです。
def d0(d):
	for x,y in Lxy():
		if not d[x,y]: d[x,y] = list(xrange(1,10))
	return d

def d1(d):
	for x,y in Lt(d):
		d[x, y] = sorted(set(d[x, y])-set(Ka(d,x,y)))
	return d

def d2(d):
	for x,y in Lt(d):
		for L in [Ltx(d,y), Lty(d,x), Ltm(d,x,y)]:
			M = [s for i,j in L for s in d[i,j]]
			N = [s for s in d[x,y] if M.count(s)==1]
			if N: d[x,y] = N
	return d

def d3(d):
	for n in xrange(1, 10):
		setn = set([n])
		for x,y in Lm3():
			N = [(i,j) for i,j in Ltm(d,x,y) if (n in d[i,j])]
			if len(N)!=2: continue
			if N[0][0]==N[1][0]:
				for i,j in Lty(d, N[0][0]):
					if (i,j) not in N: d[i,j] = sorted(set(d[i,j])-setn)
			if N[0][1]==N[1][1]:
				for i,j in Ltx(d, N[0][1]):
					if (i,j) not in N: d[i,j] = sorted(set(d[i,j])-setn)
	return d

def d4(d):
	for n in xrange(1, 10):
		setn = set([n])
		for s in xrange(9):
			L = [j for i,j in Lty(d,s) if (n in d[i,j])]
			if len(L)!=2: continue
			for i in sorted(set(xrange(9))-set([s])):
				N = [j for i,j in Lty(d,i) if (n in d[i,j])]
				if len(N)!=2: continue
				if sorted(L)!=sorted(N): continue
				for j in L:
					for k,j in Ltx(d,j):
						if k not in [s,i]: d[k,j] = sorted(set(d[k,j])-setn)
					
		for s in xrange(9):
			L = [i for i,j in Ltx(d,s) if (n in d[i,j])]
			if len(L)!=2: continue
			for j in sorted(set(xrange(9))-set([s])):
				N = [i for i,j in Ltx(d,j) if (n in d[i,j])]
				if len(N)!=2: continue
				if sorted(L)!=sorted(N): continue
				for i in L:
					for i,k in Lty(d,i):
						if k not in [s, j]: d[i,k] = sorted(set(d[i,k])-setn)
						
	return d

def d5(d):
	for x in xrange(9): d = f5(d, Lty(d, x), Vty(d, x))
	for y in xrange(9): d = f5(d, Ltx(d, y), Vtx(d, y))
	for x,y in Lm3(): d = f5(d, Ltm(d, x, y), Vtm(d, x, y))
	return d

def f5(d, Li, Lv):
	L = [s for s in Lv if len(s)==2]
	M = sorted(set([tuple(s) for s in L if Lv.count(s)==2]))
	M = [list(s) for s in M]
	for L in M:
		for n in L:
			setn = set([n])
			for i, j in Li:
				if d[i, j]!=L: d[i, j] = sorted(set(d[i, j])-setn)
	return d

def Lxy(): return [(x, y) for x in xrange(9) for y in xrange(9)]
def Lm(x, y): return [(x//3*3+i, y//3*3+j) for j in xrange(3) for i in xrange(3)]
def Lm3(): return [(x, y) for x in xrange(0,9,3) for y in xrange(0,9,3)]

def Lt(d): return [(x, y) for x,y in Lxy() if isinstance(d[x,y], list)]
def Ltx(d,y): return [(x, y) for x in xrange(9) if isinstance(d[x,y], list)]
def Lty(d,x): return [(x, y) for y in xrange(9) if isinstance(d[x,y], list)]
def Ltm(d,x,y): return [(x, y) for x, y in Lm(x,y) if isinstance(d[x,y], list)]

def Vx(d, y): return [d[x, y] for x in xrange(9)]
def Vy(d, x): return [d[x, y] for y in xrange(9)]
def Vm(d, x, y): return [d[x, y] for x,y in Lm(x, y)]
def Va(d, x, y): return Vx(d, y)+Vy(d, x)+Vm(d, x, y)

def Vtx(d, y): return [s for s in Vx(d, y) if isinstance(s, list)]
def Vty(d, x): return [s for s in Vy(d, x) if isinstance(s, list)]
def Vtm(d, x, y): return [s for s in Vm(d, x, y) if isinstance(s, list)]

def Kx(d, y): return [s for s in Vx(d, y) if isinstance(s, int)]
def Ky(d, x): return [s for s in Vy(d, x) if isinstance(s, int)]
def Km(d, x, y): return [s for s in Vm(d, x, y) if isinstance(s, int)]
def Ka(d, x, y): return sorted(set(Kx(d, y)+Ky(d, x)+Km(d, x, y)))

def chk(d):
	N = list(xrange(1, 10))
	for i in xrange(9):
		if sorted(Vx(d,i))!=N: return False
		if sorted(Vy(d,i))!=N: return False
	for x,y in Lm3():
		if sorted(Vm(d,x,y))!=N: return False
	return True

def f(sIn):
	pIn = open(sIn)
	L = pIn.read().split("\n")
	c = 0
	for i in xrange(0, len(L), 10):
		print "-------\n",L[i]
		d = {}
		for x,y in Lxy(): d[x,y] = int(L[i+y+1][x])
		d = d0(d)
		while not chk(d):
			dd = d.copy()
			for i in xrange(1, 6):
				for x, y in Lt(d):
					if len(d[x,y])==1: d[x,y] = d[x,y][0]
				d = eval("d"+str(i)+"(d)")
				if dd!=d: break
				
		for y in xrange(9): print y,[d[(x,y)] for x in xrange(9)]
		c += d[0,0]*100+d[1,0]*10+d[2,0]
		
	pIn.close()
	pIn = None
	return c
	
if __name__=="__main__":
	import os, sys
	sIn = os.path.join(os.path.dirname(__file__), "problem096_sudoku.txt")
	s = f(sIn)
	print s
数独を辞書dに格納します。
辞書dのキーは(0,0)-(8,8)の81マスの位置を示す座標タプルで、
値は候補値の配列(リスト型)、または確定値(整数型)です。

1.関数f(sIn)
・問題ファイルのパスを受け取り、リストLに各行を要素として全部読み込みます。
・リストLをヘッダを含めた10行ごとに取り出し、
 左上(0,0)-右下(8,8)の81マスの位置を示す座標タプルをキーとする辞書d
 に、値を1つずつ格納しておきます。
・最初に関数d0()で未設定値0を候補リストまたは確定値に変換しておきます。
・次に、関数chk()で数独辞書dが完成したかチェックOKになるまで、関数d1()から関数d5()を順に行います。
 ただし、関数d1()から関数d5()はこの順に基本的な操作から順に並べているので、マスの値が1つでも変化した時点で、改めて関数d1()から再処理します。
・数独が完成したら、左上3マスの値を3桁の数値にして、変数cに累積します。

2.関数d0():
・数独辞書dの未設定値0のマスに[1~9]を候補リストとして設定します。

3.関数d1()
・数独全体の候補リストについて、候補リストから関係項目に存在する確定値を削除します。












4.関数d2()
・行内、列内、3x3メッシュ内もそれぞれで、その全候補値の中に1つだけ存在する値があれば確定値とします。











5.関数d3()
・3x3メッシュ内に2つだけある候補値の位置が一列に並んでいるとき、
どちらかが確定値(例の○か◎)なので、
その並んでいる行内、または列内の他の候補からその値(例の×)を削除します。






















6.関数d4()
・ある候補値が2つだけ存在する行が2つあり、しかもその列位置が同じ場合、
 これら4つの値のうち、いずれかの対角位置の候補値が確定値(例の○か◎)になるため、この2つの列内の候補リストから、この候補値(例の×)を削除します。
 列についても上記と同様に処理します。





















7.関数d5()
・行内に、候補値が2つだけの同一の候補リストが2つのマスにある場合、
どちらの候補値もどちらかのマスのそれぞれの確定値(下図の○か◎)になるため、このマスを含む、列内、また3x3メッシュがあればそれも含めた候補リストからこの2つの値(例の×)を削除します。
列内も同様です。















8.その他
部品となる関数を以下の通りです。
・Lxy():全マスの項目番号リスト
・Lm(x, y):数独辞書dのx列y行が含まれる3x3メッシュの項目番号リスト
・Lm3()   :3x3メッシュの左上マスの項目番号リスト

・Lt(d)   :数独辞書dの処理中の項目番号リスト
・Ltx(d,y):数独辞書dのy行目の処理中の項目番号リスト(横方向)
・Lty(d,x) :独辞書dのx列目の処理中の項目番号リスト(縦方向)
・Ltm(d,x,y):数独辞書dのx列y行が含まれる3x3メッシュの処理中の項目番号リスト

・Vx(d, y)  :数独辞書dのy行目の値リスト(横方向)
・Vy(d, x)  :数独辞書dのx列目の値リスト(縦方向)
・Vm(d, x, y):数独辞書dのx列y行目が含まれる3x3メッシュの値リスト
・Va(d, x, y):数独辞書dのx列y行に関係する値リスト

・Vtx(d, y)  :数独辞書dのy行目の値リスト(横方向)
・Vty(d, x)  :数独辞書dのx列目の値リスト(縦方向)
・Vtm(d, x, y):数独辞書dのx列y行目が含まれる3x3メッシュの値リスト

・Kx(d, y) :数独辞書dのy行目の確定値リスト(横方向)
・Ky(d, x) :数独辞書dのx列目の確定値リスト(縦方向)
・Km(d, x, y):数独辞書dのx列y行目が含まれる3x3メッシュの確定値リスト
・Ka(d, x, y):数独辞書dのx列y行に関係する確定値リスト

・chk(d):#数独辞書dの縦、横、3x3メッシュの全てが[1~9]であるかの最終チェック


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
24702