2013年11月10日日曜日

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

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

問84「モノポリーの確率」 
モノポリーの標準的な盤面は以下である:

GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL
H2   C1
T2   U1
H1   C2
CH3   C3
R4   R2
G3   D1
CC3   CC2
G2   D2
G1   D3
G2J F3 U2 F2 F1 R3 E3 E2 CH2 E1 FP

各プレイヤーはGOのマスから開始し, 2個の6面サイコロを用いて時計回りに進む. 
他のルールが無いとすれば, 各マスに止まる確率は全て等しく, 2.5%である. 
しかし, G2J (Go To Jail), CC (Community Chest, 共同基金), CH (Chance, チャンス) のマスによってこの確率は変えられてしまう.

G2Jに止まる, または, CCやCHのマスに止まると引くカードのうちそれぞれ1枚によって, プレイヤーはJAILのマスに飛ばされる.
またプレイヤーが連続して3回ゾロ目を出すと, 3投目の結果のマスに進むのではなく, 直接JAILのマスに飛ばされる.
(筆者注:ぞろ目が連続して出る場合、連続が3回以内続く分の目の合計を進むのではなく、さいころを振る都度止まるマスの指示に従う)

ゲーム開始前にCCカードとCHカードはシャッフルされる.
プレイヤーがCCまたはCHマスに止まった場合, プレイヤーはCCカードまたはCHカードの山の一番上からカードを1枚引く. 
カードの指示に従ったのち, そのカードは山の一番下に戻される.
それぞれのカードは16枚あるが, 今回は問題を進み方に限定するので, 移動の指示があるカードのみを考える.
移動の指示が無いカードに関しては何もせずカードをそのまま山の下に戻す.
プレイヤーはそのままCC/CHマスに残るものとする.

Community Chest (16枚中2枚が移動カード) 
GOへ進め 
JAILへ進め
Chance (16枚中10枚が移動カード) 
GOへ進め 
JAILへ進め 
C1へ進め 
E3へ進め 
H2へ進め 
R1へ進め 
次のRへ進め (Rはrailway company, 鉄道会社の意) 
次のRへ進め 
次のUへ進め (Uはutility company, 公共事業会社の意) 
3マス戻れ
今回考えるのは, どのマスに止まりやすいかである. 
即ち, サイコロを投げた後に止まる確率である. 
より正確には, サイコロを1回振ってカードやマスによる移動を終えた後に各マスに止まる確率を求めたい. 
従って, G2Jに止まる確率は0であり, CHマスに止まる確率はその次に少ない(16枚中10枚が移動カードなので).
またJAILマスにたまたま止まることとJAILマスに送られることを区別しない.
またJAILマスから抜けるルール (自分のターンにゾロ目を2回出す) を無視する.
つまり必ず保釈金を払ってJAILマスから進むものとする.

GOマスを00とし番号を00-39と順番に振る. これにより各マスを2桁の数で表すことが出来る.
統計的には, 3つのマスに止まりやすいことを示せる.
JAIL (6.24%) = 10番目, E3 (3.18%) = 24番目, GO (3.09%) = 00番目である.
従ってもっとも止まりやすいマスを6桁で表せて102400となる.

2つの6面サイコロではなくて, 2つの4面サイコロを用いた場合の, もっとも止まりやすいマスを6桁で表せ.





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






私の回答例は以下の通りです。
def f(n, d):
	import random
	#Board List
	BL = "GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL C1 U1 C2 C3 R2 D1 CC2 D2 D3 \
		FP E1 CH2 E2 E3 R3 F1 F2 U2 F3 G2J G1 G2 CC3 G3 R4 CH3 H1 T2 H2".split()
	BD = dict([(s, i) for i,s in enumerate(BL)])

	#Next Railway company
	L = [i for i,s in enumerate(BL) if s[0]=="R" and s[1:].isdigit()]
	NxR = [i for i,j in zip(L, [0]+L[:-1]) for k in xrange(i-j)]
	NxR += [NxR[0]]*(len(BL)-len(NxR))

	#Next Utility company
	L = [i for i,s in enumerate(BL) if s[0]=="U" and s[1:].isdigit()]
	NxU = [i for i,j in zip(L, [0]+L[:-1]) for k in xrange(i-j)]
	NxU += [NxU[0]]*(len(BL)-len(NxU))

	#community chest
	cc = [i for i,s in enumerate(BL) if s[:2]=="CC" and s[-1].isdigit()]
	ccL = [BD["GO"], BD["JAIL"]]+[""]*14
	random.shuffle(ccL)

	#chance
	ch = [i for i,s in enumerate(BL) if s[:2]=="CH" and s[-1].isdigit()]
	chL = [BD["GO"], BD["JAIL"], BD["C1"], BD["E3"], BD["H2"], BD["R1"], \
			"NxR", "NxR", "NxU", "bk3"]+[""]*6
	random.shuffle(chL)

	iCD = cntcc = cntch = p = 0
	B = dict([i, 0] for i in xrange(len(BL)))
	for i in xrange(n):
		d1, d2 = random.randrange(1, d+1), random.randrange(1, d+1)
		p = (p+d1+d2)%len(BL)

		#consecutive dobles
		if d1==d2:
			iCD += 1
			if iCD>=3: iCD, p = 0, BD["JAIL"]
		else: iCD = 0

		while True:
			#G2J
			if p==BD["G2J"]: p = BD["JAIL"]; break
			#JAIL
			elif p==BD["JAIL"]: break
			#comunity chest
			elif p in cc:
				t = ccL[cntcc]
				p = {True:t, False:p}[isinstance(t, int)]
				cntcc = (cntcc+1)%len(ccL)
				if p not in ch: break
			#chance
			elif p in ch:
				t = chL[cntch]
				t = {"NxR":NxR[p], "NxU":NxU[p], "bk3":p-3}.get(t,t)
				if isinstance(t, int): p = t
				cntch = (cntch+1)%len(chL)
				if p not in cc: break
			#etc.
			else: break

		B[p] += 1

	L = [t for t in sorted(B.items(), key=lambda x:x[1], reverse=True)]
	r = "".join([str(L[i][0]).zfill(2) for i in xrange(3)])
	P = [str(L[i][1]*100.0/n)[:4] for i in xrange(3)]
	return L, r, P

L, r, (p0, p1, p2) = f(1000000, 4)
print r, str(p0)+"%", str(p1)+"%", str(p2)+"%"


共同基金やチャンスカードがあるので数学的に確率を求めるのは難しいと思い、
PC上で十分に多い回数を試行することにしました。
6面さいころで試行したところ、さいころを100万回振ると、結果として、問題文中の値との差異が0.05%程度以内に収まりました。
そこで、4面さいころを100万回振ることで解を求めました。

1.関数f(n,d)
・モノポリーでd面さいころをn回振ることを試行し、止まった回数の多いマスのベスト3を6桁表示した値とそのマスに止まった割合を返します。

・最初に固定データをリストや辞書にします。
 盤面位置リストBL、マス名称から盤面位置を取得できる辞書BD、
 各マスごとに「次の鉄道会社」の位置のリストNxR、
 各マスごとに「次の公共事業会社」の位置のリストNxU、
 共同基金の位置リストcc、共同基金カードリストccL、
 チャンスの位置リストch、チャンスカードリストchL

・import random
 pythonにある乱数に関するいろいろな関数を使えるようにしておきます。

・ramdom.shuffle(ccL)
 共同基金カードリストccLをシャッフルします。最初にカードをよく切り混ぜるイメージです。チャンスカードも同様によく切り混ぜます。

・カウンタなどを初期設定しておきます。
 ぞろ目(consecusive doubles)の連続回数iCD、共同基金カードの現在使用位置cntcc、チャンスカードの現在使用位置cntch、盤面の現在位置pはゼロクリアしておきます。
 マス位置別に止まった回数カウンターを用意し辞書Bとし、各カウンタはゼロクリアしておきます。

・for i in xrange(n):
 さいころを振る回数iのループです。n回振ります。

・d1, d2 = random.randrange(1, d+1), random.randrange(1, d+1)
 d1とd2それぞれがさいころの目です。
 randrange関数で1からdまで整数を乱数発生させ、さいころの目とします。

・ぞろ目判定では、ぞろ目のときにぞろ目連続回数iCDをカウントアップし、ぞろ目以外の場合必ずゼロクリアすることで連続3回か判定しています

・共同基金とチャンスでは、出るカードによって進む先が再び共同基金やチャンスのことがあるので、連続してカードを引けるように無限ループに入れます。
どちらもこれ以外が出ればループから抜けます。

・共同基金カードは使用した位置をcntchで保持して1つずつ加算することで、カードの山の上から順番に使って使用後はカードの山の一番下に戻すイメージを実現しました。チャンスカードも同様です。

・L = [t for t in sorted(B.items(), key=lambda x:x[1], reverse=True)]
 sorted関数で並び替えた値を取り出して内包表記でリストLにします。
 sorted関数の引数は以下のとおりです。
・B.items()は、マス位置別に止まった回数カウンター辞書Bから、キー(マス位置)と値(止まった回数)の組のタプルを要素として取り出したリストです。
・key=lambda x:x[1]
 lambdaは無名関数で引数xを受け取り、x[1]、配列位置1つまり2番目の要素を返します。ここでは辞書Bをリスト化したデータを受け取り、止まった回数を返します。これがsorted関数での並び替えるキーとなります。
・reverse=Trueでsorted関数での並び順は降順、ここでは止まった回数の多い順となります。

・r = "".join([str(L[i][0]).zfill(2) for i in xrange(3)])
 止まった回数の多いベスト3の6桁表示値を求めます。
 止まった回数順に並び替えたリストLから、ループiで配列位置0から2番目の要素を取得します。ここでは止まった回数の多いベスト3の要素が取得されます。
 L[i][0]は対象のマス位置の数字なので、str関数で文字列にして、zfill関数で0埋めで2桁でします。
 さらに、このベスト3のマス位置の2桁値を、join関数で区切り文字なしで文字列連結します。

・P = [str(L[i][1]*100.0/n)[:4] for i in xrange(3)]
 止まった回数の多い方からベスト3の回数のパーセントを求めて、順に格納したリストです。


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

101524 7.04%% 3.65% 3.29% ※ベスト3の割合はたまたま実行したときの値です。


0 件のコメント:

コメントを投稿