2012年9月12日水曜日

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

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

問59「XOR暗号化された暗号文を解読できるか?」
各文字はそれぞれ一意のコードに割り当てられている.よく使われる標準としてASCII (American Standard Code for Information Interchange) がある.ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.

モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある.
XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である.
65 XOR 42 = 107であり, 107 XOR 42 = 65である.

破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない.ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある.また, もし一方が失われると, 暗号文を復号することは不可能になる.
悲しいかな, この手法はほとんどのユーザーにとって非現実的である.

そこで, 鍵の変わりにパスワードを用いる手法が用いられる.パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる.
この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.

この問題での課題は簡単になっている.
暗号化鍵は3文字の小文字である.
cipher1.txtは暗号化されたASCIIのコードを含んでいる.
また, 平文はよく用いられる英単語を含んでいる.

この暗号文を復号し, 平文のASCIIでの値の和を求めよ.

-----


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






私の解答例は以下です。畳んでいます。
def g(s, n):
	import itertools
	for t in itertools.product(s, repeat=n): yield "".join(t)

def f(sIn, a, n):
	L = [int(t) for t in open(sIn).read().split(",")]
	for s in g(a, n):
		M = ([ord(t) for t in s]*len(L))[:len(L)]
		N = [i^j for i,j in zip(L, M)]
		R = [chr(i) for i in N]
		t = "".join(R)
		if " the " in t: return sum(N), s, t

import os
sIn = os.path.join(os.path.dirname(__file__), "cipher1.txt")
a = "abcdefghijklmnopqrstuvwxyz"
n = 3
print f(sIn, a, n)


2つの関数を使っています。

1.関数g(s, n)
・文字列sからn個選んだ直積を連結した文字列を返します。
 直積とは、重複を許し順番が違えば別のものとして扱う組み合わせです。
 例えば、abcから2つ選んだ直積は、aa,ab,ac,ba,bb,bc,ca,cb,ccです。

・import itertools
 標準モジュールitertoolsを使えるようにしておきます。

・for t in itertools.product(s, repeat=n): yield "".join(t)
 標準モジュールitertoolsにあるproduct関数で、文字列sからをn個選んだ直積の構成要素のタプルを生成し、for文のループ変数tに設定します。
 forループの中で、タプルtを区切り文字無しで連結し、yield文で返します。
 yield文で返すと、返した時点で処理内容が一旦凍結され、再度呼び出されたときに処理を再開して続きの処理による値を返します。
 このような動きをするyield文で返す関数をジェネレータ関数といいます。
 なお、単発呼び出しで終了するreturn文で返す関数はイテレータ関数といいます。
 また、product関数はpython2.6以上です。
 python2.5にもitertoolsモジュールはありますが、product関数が含まれていません。

2.関数f(sIn, a, n)
・主処理です。
・入力ファイルsInの中の文字列を、指定した文字列aからn個選んだ秘密鍵sによって順にxor演算で復号した数値列N、及びこれをasciiコード扱いして得られる復号文字列tがあるとき、数値列Nの合計値、キー文字列s、復号文字列tを返します。

・引数sInは入力ファイルのフルパス、文字列aは秘密鍵の構成文字候補の文字列、nは秘密鍵の桁数です。

・L = [int(t) for t in open(sIn).read().split(",")]
 暗号文の各数値をもつリストLを作成します。
 入力ファイルsInを開き、その内容をすべて読み込んで、カンマで区切った文字列を
 ループ変数tに設定します。
 このtをfor文の前に送り、int関数で数値化してリストLとします。
 なお、開いたファイルオブジェクトはpythonがタイミングをみて閉じくれます。

・for s in g(a, n):
 関数gで文字列aからn個選んだ秘密鍵候補をループ変数sとします。

・M = ([ord(t) for t in s]*len(L))[:len(L)]
 Mは、秘密鍵候補sの構成要素の数値を暗号文の長さまで繰り返した復号用鍵のタプルです。
 内包表記のループ変数tとして秘密鍵候補sの文字1つずつを、for文の前に送り、ord関数でasciiコードとして対応する数値にしてリスト化します。
 このリストをlen(L)倍、つまり暗号文の長さ倍して、秘密鍵を順に繰り返し連結した状態にしてから、[:len(L)]で暗号文の長さの分だけ取り出しておきます。
 
・N = [i^j for i,j in zip(L, M)]
 Nは復号化した数値のリストです。
 zip関数で上記のリストLとリストMから1つずつ組み合わせて取り出し、ループ変数i,jとし、内包表記のfor文の前に送り、^演算子で数値j,jのxorを計算しリストにため、リストNとします。

・R = [chr(i) for i in N]
 復号数値リストNから1つずと取り出しchr関数でascii文字化してリストにため、リストRとします。
 
・t = "".join(R)
 上記の文字列リストRの要素を区切り文字無しで連結し、復号文tとします。

・if " the " in t: return sum(N), s, t
 復号が正しいか判定します。
 判定は「よく用いられる英単語」があるという問題文に従い、半角空白ではさんだ「 the 」としてみました。結果的にこれで判定できました。
「 the 」があれば、復号化した数値リストNの要素の合計、秘密鍵、復号文tを返します。

3.関数の外
・import os
 ファイルを扱うので、標準モジュールosを使えるように取り込んでおきます。

・sIn = os.path.join(os.path.dirname(__file__), "cipher1.txt")
 暗号文のフルパスです。
 「__file__」は実行するpythonファイルのフルパスです。
 os.path.dirname関数で親フォルダまで取得し、ファイル名とともに、
 os.path.joinでパス表示を連結しました。
 つまり、暗号文は実行するpythonファイルと同じフォルダに置いて実行するように記述しています。
 
・a = "abcdefghijklmnopqrstuvwxyz"
 秘密鍵の候補です。問題文から小文字のアルファベットです。

・n = 3
 秘密鍵の桁数です。問題文から3としました。

 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
107359
秘密鍵はgod。平文の内容は、聖書ヨハネによる福音書の第1章第1節から第14節。

(追記)
・20130129 ネタバレ注意の追記など

2012年9月9日日曜日

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

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

問58「渦巻きに配置された格子の対角線上にある素数の数を調べ上げよ」
1から始めて, 以下のように反時計回りに数字を並べていくと,
辺の長さが7の渦巻きが形成される.


37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49


面白いことに, 奇平方数が右下の対角線上に出現する.
もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である.
ここで割合は8/13 ≒ 62%である.


渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る.
以下, この操作を繰り返していく.


対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

-----


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





私の解答例は以下です。畳んでいます。
def h(n):
	if n<2 or (not n%2): return False
	for i in xrange(3, n, 2):
		if i*i>n: break
		if not n%i: return False
	return True

def g(n):
	if n<1 or (not n%2): return []
	elif n==1: return [1]
	s, t = n-1, n-2
	u = t*t+s
	return [u, u+s, u+s*2, u+s*3]

def f(p):
	i, u = 1, 0
	while not (0<float(u)/(4*(i//2)+1)<p):
		i += 2
		u += len([j for j in g(i) if h(j)])
	return i

p = 0.1
print f(p)


3つの関数を使っています。

1.関数h(n)
・素数判定です。2と、3以上の奇数で割り切れるか判定します。

・if n<2 or (not n%2): return False
 2以下、または2で割り切れる場合、素数ではありません。
 %演算子は割り算の余り、余り0は論理的にFalseです。

・for i in xrange(3, n, 2):
 素因数候補として、3以上の奇数を順にループ変数iに設定します。
 割り切り判定の割る数として使用します。
 終了値をnにしていますが、後続ロジックでnになる前に必ずループを終了します。

・if i*i>n: break
 引数nを構成する素因数の限界値は√nです。これを超える素因数はあり得ません。そこで、素因数候補がこの限界値まで達したら、ループを抜けます。

・if not n%i: return False
 割り切り判定です。割り切れたら、素数でないのでFalseを返します。
 %演算子は割り算の余り、余り0は論理的にFalseです。

・return True
 割り切れる素因数候補が無く、素数なのでTrueを返します。

2.関数g(n)
 問28では同じ渦巻きの四隅和を返す関数を作りましたので、
 これの返り値を四隅和から四隅値のリストに修正しました。

3.関数f(n)
・問題文の渦巻きについて、対角線上の値のうち素数の割合が引数p未満になる最初の辺の長さを返します。

・i, u = 1, 0
 初期設定です。iは渦巻きの辺の長さ、uは対角線上の素数の個数です。

・while not (0<float(u)/(4*(i//2)+1)<p):
 「float(u)/(4*(i//2)+1)」は、対角線上の素数の割合です。
 この値が0と引数pの間に入ったら、ループ終了です。
 uは対角線上の素数の個数で、割り算で小数点以下まで求めるので、float関数で浮動小数点型にしています。
 「(4*(i//2)+1)」は対角線上の値の個数です。辺の長さiにより決まります。

・i += 2
 辺の長さは渦巻きを1つ巻くごとに、2ずつ増えます。

・u += len([j for j in g(i) if h(j)])
 内包表記です。
 for文で関数g(i)にて取得した辺の長さiの四隅値の1つひとつをループ変数jに設定し、後ろのif文に渡し、関数h(j)にて素数判定し素数だけをfor文の前に渡します。
 for文の前はjをリスト化し、len関数でその要素数を数えて、uに累積します。

・return i
 whileループ終了時点の辺の長さiを呼び出し元に返します。

4.関数の外
・p = 0.1
 print f(p)
 問題に合うように10%=0.1を関数fに渡し、その返り値を表示します。
 
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
26241

(追記)
・20130129 ネタバレ注意の追記など

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

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

問57「2の平方根の連分数展開を調べあげよ」
2の平方根は無限に続く連分数で表すことができる.
 √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

次の3つの項は99/70, 239/169, 577/408である.
第8項は1393/985である.
これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?


-----


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






私の解答例は以下です。畳んでいます。
def g(n):
	if n<1: return 1, 1
	a, b = g(n-1)
	return a+b*2, a+b

def f(n):
	import sys
	sys.setrecursionlimit(n+10)
	u = 0
	for i in xrange(n+1):
		a, b = g(i)
		if len(str(a))>len(str(b)): u += 1
	return u

n =1000
print f(n)


2つの関数を使っています。

1.関数g(n)
・問題文の第n項の値を、分子と分母で返します。
・問題文から、
 L1 = 1 + 1/2
 L2 = 1 + 1/(2 + 1/2)
 L3 = 1 + 1/(2 + 1/(2 + 1/2))
 L4 = 1 + 1/(2 + 1/(2 + 1/(2 + 1/2)))
 ・・・

「1+(1/x)」のxの部分に1世代前の値が入るようにして再帰関数を作ります。
 L0 = 1
 L1 = 1 + 1/2 ... (A)
   = 1 + 1/(1 + L0)
  
 L2 = 1 + 1/(2      + 1/2)
   = 1 + 1/(1 + (1 + 1/2)) ...(B)
   = 1 + 1/(1 +  L1)
  
 L3 = 1 + 1/(2      + 1/(2      + 1/2))
   = 1 + 1/(1 + (1 + 1/(1 + (1 + 1/2))))...(C)
   = 1 + 1/(1 + L2)

・・・というようになります。
ポイントは、各世代の第1項が1なので入れ子になる「1+(1/x)」のx自身も第1項は1からはじめることです。
問題文ではこの部分は2なので1+1に分けて式変形します。
(B)全体を「1+(1/x)」と見ると、そのxの部分が「1+(A)」です。
(C)全体を「1+(1/x)」と見ると、そのxの部分が「1+(B)」です。

次に、1世代前の値の分母子から、当世代の値の分母子を求めておきます。
1世代前の値がa/b、つまり分子a、分母bだとすると、当世代の値は、
  1 + 1 / (1 + a/b)  かっこ内を分母bで通分して、
 = 1 + 1 / ((a+b) / b) 第2項の分母子をb倍して、
 = 1 + (b / (a+b))   全体を分母(a+b)で通分して、
 = ((a+b) + b) / (a+b) 整理して
 = (a+b*2) / (a+b)   以上より、分子a+b*2、分母a+b になります。
 
以上をふまえて、
・if n<1: return 1, 1
 g(n)は1世代前の自分自身を呼び出す再帰関数なので、
 世代さかのぼりの終了条件として、nが1より小さくなったら、
 L0 = 1/1 で、分子1、分母1を返し、さかのぼりは終了します。

・a, b = g(n-1)
 1世代前の分子a、分母bを受け取ります。
 
・return a+b*2, a+b
 当世代の分子a+b*2、分母a+bを返します。

2.関数f(n)
・問題文に合う最初のn項までのうち、
 分子の桁数が分母の桁数を超える場合の件数を返します。

・import sys
 sys.setrecursionlimit(n+10)
 再帰呼び出しの深さの限界値を設定します。
 初期値は1000なので当問題では足りません。
 限界を超えたときのエラーメッセージは以下のとおりです。
 「RuntimeError: maximum recursion depth exceeded」
 ここでは上記エラーが発生しないように、
 引数nに余裕をもたせた値を再帰呼び出し深さ限界値として設定しています。
 
・u = 0
 求める件数のカウンターです。0クリアしておきます。

・for i in xrange(n+1):
 問題文にある項番号をループ変数iとして設定します。

・a, b = g(i)
 当世代の分子、分母をそれぞれa、bとして取得します。

・if len(str(a))>len(str(b)): u += 1
 分子a、分母bをそれぞれstr関数で文字型にしてlen関数で文字列長(桁数)を取得し、
 分子の桁数が分母の桁数を超える場合に、カウントアップします。

3.関数の外
・n =1000
 print f(n)
 問題に合うように引数1000を関数fに渡し、戻り値を表示します。
 

なお、関数g(n)の返り値の分子分母はその桁数違いを判定するので、
公約数が存在すのであれば約分して最も簡単な分数にしておく必要があります。
そこでこの分子分母に公約数が無いことを確認をしておきます。

まず、第1項のa=3,b=2には明らかに公約数が存在しません。
次に、
第n-1項の分子分母a,bに公約数が存在しない条件のもと、
第n項の分子分母a+b*2, a+bに公約数pが存在すると仮定すると、
公約数pを使用して、それぞれ以下のように表せます。
a+b*2 = pm ...(1)
a+b = pn ...(2)
ここで、
(1)-(2)より、
(a+b*2) - (a+b) = pm - pn
 b = p(m-n) ...(3)
(2)*2-(1)より、
(a+b)*2 - (a+b*2) = 2*pn - pm
 a = p(2*n-m) ...(4)
となって、(3)(4)よりa,bにも公約数pが存在することになり、
a,bに公約数が存在しないという条件と矛盾します。
以上より、a+b*2,a+bには公約数が存在しません。

なので、関数g(n)の返り値はそのまま桁数判定に使っています。


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

(追記)
・20130129 ネタバレ注意の追記など

2012年9月2日日曜日

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

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

問56「aのb乗の形の自然数について桁の和の最大値を求めよ」
Googol (10100)は非常に大きな数である: 1の後に0が100個続く.
100100は想像を絶する. 1の後に0が200回続く.
その大きさにも関わらず, 両者とも桁の和は1である.

a, b < 100について自然数abを考える. 桁の和の最大を答えよ.

-----


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






私の解答例は以下です。畳んでいます。
def f(n):
	L = [0, 0, 0]
	for i in xrange(n):
		for j in xrange(n):
			s = sum([int(k) for k in list(str(i**j))])
			if L[2]<s: L = [i, j, s]
	return L

n = 100
i,j,t = f(n)
print t," = ", i, "**",j


1.関数f(n):
・n未満の整数i,jについて、iのj乗の各桁の合計値が最大になるときの
 i,j,およびiのj乗の各桁の合計値を返します。

・for i in xrange(n):
  for j in xrange(n):
 ループ変数i,jにはn未満の整数を1つずつ設定します。

・s = sum([int(k) for k in list(str(i**j))])
 sはiのj乗の各桁の合計値です。
 **演算子は累乗です。i**jでiのj乗です。
 これをstr関数で各桁ごとの文字のリストにします。
 内包表記で、このリストから1つずつループ変数kに設定しint関数で数値に変換した値のリストを作ります。
 そしてsum関数でこのリストの合計値を計算します。

・if L[2]<s: L = [i, j, s]
 iのj乗とその桁和値sについて、リストLにこの順でとっておきます。
 L[2]は桁和値です。
 この桁和値についてリストL保存値よりも計算値sが大きい場合、
 その計算値sとこのときのi,jをリストLに保存します。

2.関数の外
・n = 100
 i,j,t = f(n)
 print t," = ", i, "**",j
 問題に合うように100未満の数値を対象にして、
 関数fで問題に合う数値のリストを取得し、表示します。
 
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
972  =  99 ** 95


(追記)
・20130129 ネタバレ注意の追記など

Project Euler - Problem 55

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 55
47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.

全ての数が素早く回文数になるわけではない. 349を考えよう,
 1.349 + 943 = 1292
 2.1292 + 2921 = 4213
 3.4213 + 3124 = 7337
349は 3回の操作を経て回文数になる.

まだ証明はされていないが,

196のようないくつかの数字は回文数にならないと考えられている.
反転したものを足すという操作を経ても回文数にならないものを

Lychrel数と呼ぶ.
先のような数の理論的な性質により, またこの問題の目的のために,
Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

更に, 10000未満の数については,常に以下のどちらか一方が成り立つと仮定してよい.
 1.50回未満の操作で回文数になる
 2.まだ誰も回文数まで到達していない

実際, 10677が50回以上の操作を必要とする最初の数である:
4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).

驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.
10000未満のLychrel数の個数を答えよ.

注: 2007/04/24にLychrel数の理論的な性質を強調するために文面が修正された.


-----


私の解答例は以下です。畳んでいます。
def g(n):
	s = str(n)
	for i in xrange(len(s)//2):
		if s[i]!=s[-(i+1)]: return False
	return True

def f(n):
	L = []
	for i in xrange(n):
		s = i
		for j in xrange(50):
			s += int("".join(list(str(s))[::-1]))
			if g(s): break
		else: L.append(i)
	return L

n = 10000
L = f(n)
print len(L)


2つの関数を使っています。

1.関数g(n):
・回文数かどうかチェックします。
・s = str(n)
 引数nを文字型に変換し、文字列sとします。

・for i in xrange(len(s)//2):
 ループ変数iは、文字列sの真ん中まで、位置番号を1つずつ設定します。
 文字列sが奇数桁の場合、真ん中の文字はチェック対象外です。
 len関数で文字列sの長さを取得し、//演算子で割り算の商を求めています。

・if s[i]!=s[-(i+1)]: return False
 文字列sの前からi番目の文字と後ろからi番目の文字を比べ、
 違っていたらFalseを返し、同じならば位置iを1つ進めます。

・return True
 上記でFalseでループを抜けなかったので、前からと後ろからの同じ位置の文字がすべて同じで回文数なので、Trueを返します。

2.関数f(n)
 n未満のLychrel数のリストを返します。
・for i in xrange(n):
 ループ変数iには0から引数nまでの値を1つずつ設定します。

・for j in xrange(50):
 50回を限度に、以下の反転数累積とその回文数チェックをします。

・s += int("".join(list(str(s))[::-1]))
 数値sをstr関数で文字型にして、list関数で1文字ずつのリストにして、[::-1]で反転します。
 "".joinでその反転リストを結合して反転数文字列にして、int関数で数値に直して元の反転前の値に累積していきます。
リスト[開始位置:終了位置:刻み]なので、リスト[::-1]で反転リストになります。
・if g(s): break
 上記で計算した反転数累積値について、関数gにて回文数チェックをします。
 回文数ならば、問題に合わないのでループ変数iを次に進めます。

・else: L.append(i)
 for文のelse節は、forループが途中抜けせず最後まで回って要素が尽きた場合に処理します。
 ここでelse節に入るには、反転数累積を50回やっても1つも回文数にならなかったということで、まさにLychrel数なので、このようなiはリストLに追加します。

3.関数の外
・n=10000
 L = f(n)
 print len(L)
 問題に合うように10000未満の数値を対象にして、
 関数fで問題に合う数値のリストを取得し、len関数でその件数を取得し、表示します。
 

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

Project Euler - Problem 54

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 54
カードゲームのポーカーでは, 手札は5枚のカードからなりランク付けされている.
役を低い方から高い方へ順に並べると以下である.

0.役無し: 一番値が大きいカード
1.ワン・ペア: 同じ値のカードが2枚
2.ツー・ペア: 2つの異なる値のペア
3.スリーカード: 同じ値のカードが3枚
4.ストレート: 5枚の連続する値のカード
5.フラッシュ: 全てのカードが同じスート
 (注: スートとはダイヤ・ハート・クラブ/スペードというカードの絵柄のこと)
6.フルハウス: スリーカードとペア
7.フォーカード: 同じ値のカードが4枚
8.ストレートフラッシュ: ストレートかつフラッシュ
9.ロイヤルフラッシュ: 同じスートの10, J, Q, K, A

ここでカードの値は小さい方から
2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, Aである.
(訳注:データ中で10は'T'と表される)

もし2人のプレイヤーが同じ役の場合には, 役を構成する中で値が最も大きいカードによってランクが決まる:
例えば, 8のペアは5のペアより強い (下の例1を見よ).
それでも同じランクの場合には (例えば, 両者ともQのペアの場合),
一番値が大きいカードによってランクが決まる (下の例4を見よ).
一番値が大きいカードが同じ場合には, 次に値が大きいカードが比べれられ, 以下同様にランクを決定する.

例:
プレイヤー1プレイヤー2勝者
15H 5C 6S 7S KD
(5のペア)
2C 3S 8S 8D TD
(8のペア)
プレイヤー2
25D 8C 9S JS AC
(役無し, A)
2C 5C 7D 8S QH
(役無し, Q)
プレイヤー1
32D 9C AS AH AC
(Aのスリーカード)
3D 6D 7D TD QD
(ダイヤのフラッシュ)
プレイヤー2
44D 6S 9H QH QC
(Qのペア, 9)
3D 6D 7H QD QS
(Qのペア, 7)
プレイヤー1
52H 2D 4C 4D 4S
(4-2のフルハウス)
3C 3D 3S 9S 9D
(3-9のフルハウス)
プレイヤー1

poker.txtには1000個のランダムな手札の組が含まれている.
各行は10枚のカードからなる(スペースで区切られている):
最初の5枚がプレイヤー1の手札であり, 残りの5枚がプレイヤー2の手札である.
以下のことを仮定してよい

  • 全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)
  • 各プレイヤーの手札は特に決まった順に並んでいるわけではない
  • 各勝負で勝敗は必ず決まる
1000回中プレイヤー1が勝つのは何回か?

-----

私の解答例は以下です。畳んでいます。
def L2dic(L):
	d = {"T":10,"J":11,"Q":12,"K":13,"A":14}
	dN, dM = {}, {}
	for s in L:
		if s[0]>"9": t = d[s[0]]
		else: t = int(s[0])
		dN[t] = dN.get(t, 0)+1
		dM[s[1]] = dM.get(s[1], 0)+1
	return dN, dM

def g(L):
	dN, dM = L2dic(L)
	maxN, minN, nN, maxNV = max(dN), min(dN), len(dN), max(dN.values())
	nM = len(dM)
	difN = maxN-minN
	if nN==5:
		if difN>4:
			if nM>1: t = 0	#0:High Card
			else: t = 5		#5:Flush
		elif nM>1: t = 4		#4:Straight
		elif minN<10: t = 8	#8:Straight Flush
		else: t = 9			#9:Royal Straight Flush
	elif nN==4: t = 1		#1:One Pair
	elif nN==3:
		if maxNV==3: t = 3	#3:Three cards
		else: t = 2			#2:Two pairs
	elif nN==2:
		if maxNV==4: t = 7	#7:Four in a kind
		else: t = 6			#6:Full House

	s = str(t)
	for k,v in sorted(dN.items(), key=lambda (k,v):(v,k), reverse=True):
		s += str(k).zfill(2) * v
	return s

def f(sIn):
	t = 0
	for s in open(sIn).readlines():
		L = s.split()
		p1, p2 = g(L[:5]), g(L[5:])
		t += int(p1>p2)
	return t

import os, sys
sIn = os.path.join(os.path.dirname(sys.argv[0]), "poker.txt")
print f(sIn)


3つの関数を使っています。

1.関数L2dic(L):
・カードのリストから、番号辞書とマーク辞書を返します。
 番号辞書dNは、カードの番号をキーにその枚数を値に持つ辞書です。
 マーク辞書dMは、カードのマークをキーにその枚数を値に持つ辞書です。
・9を超える番号でも並べ替え可能にするため、
 T,J,Q,K,Aを順に10から14までの連番に置き換えます。

・d = {"T":10,"J":11,"Q":12,"K":13,"A":14}
 10以上の値のための変換辞書です。

・for s in L:
 カードのリストから1枚ずつ取り出し、ループ変数sとします。
 sは2桁の文字列で、位置0の値s[0]が番号で、位置1の値s[1]が絵柄です。

・if s[0]>"9": t = d[s[0]]
 else: t = int(s[0])
 番号が9を超える場合、変換辞書で数値にします。
 番号が9を超えない場合、int関数でそのまま数値にします。

・dN[t] = dN.get(t, 0)+1
 番号辞書では、上記で数値化した値tをキーにカウントアップします。
 辞書[キー]ではキー未設定の場合エラーになるので、
 get関数を使い、引数1未設定の場合に引数2、この場合0を返すようにします。
 こうして得た値に、+1します。

・dM[s[1]] = dM.get(s[1], 0)+1
 マーク辞書は、マークのアルファベット値をキーに件数カウントアップします。

2.関数g(L)
・カードの強さ(役+すべての番号)の文字列を返します。
 ただし、すべての番号の並び順は、
 役を構成している番号群を優先し、番号の大きい順です。

・dN, dM = L2dic(L)
 番号辞書dN、マーク辞書dMを取得しておきます。

・maxN, minN, nN, maxNV = max(dN), min(dN), len(dN), max(dN.values())
 nM = len(dM)
 difN = maxN-minN
 役の判定で必要な情報を以下のように前もって準備しておきます。
 最大番号maxN、最小番号minN、番号の種類数nN、番号別件数の最大値maxNV、
 マークの種類数nM、最大番号と最小番号の差difN。
 difNは連番判定で使います。
 
・if nN==5:
 数字が5種類の場合の判定です。

・if difN>4:
  if nM>1: t = 0 #0:High Card
  else: t = 5  #5:Flush
 数字が5種類で、連番以外の場合のチェックです。
 最大番号と最小番号の差が4より大きいということが連番ではないということです。
 この場合はさらにマークの種類がいくつあるかみて、
 マークが複数あれば、役無しで、強さtは0です。
 マークが1種類であれば、フラッシュで、強さtは5です。
 
・elif nM>1: t = 4 #4:Straight
 数字が5種類で、連番の場合、
 マークが複数であれば、ストレートで、強さt=4です。

・elif minN<10: t = 8 #8:Straight Flush
 数字が5種類で、連番で、マークが1種類の場合、
 最小番号が10未満の場合、ストレートフラッシュで、強さt=8です。

・else: t = 9   #9:Royal Straight Flush
 数字が5種類で、連番で、マークが1種類で、最小番号が10以上の場合、
 ストレートフラッシュで、強さt=8です。

・elif nN==4: t = 1  #1:One Pair
 数字が4種類の場合はワンペアしかなく、強さt=1。

・elif nN==3:
  if maxNV==3: t = 3 #3:Three cards
  else: t = 2   #2:Two pairs
 数字が3種類の場合、番号別の件数は(3,1,1)(2,2,1)のどちらかです。
 そこで番号別件数の最大値maxNVが3の場合、スリーカードで、強さt=3です。
 それ以外はツーペアで、強さt=2です。

・elif nN==2:
  if maxNV==4: t = 7 #7:Four in a kind
  else: t = 6   #6:Full House
 数字が2種類の場合、番号別の件数は(4,1)(3,2)のどちらかです。
 そこで番号別件数の最大値maxNVが4の場合、フォーカードで、強さt=7です。
 それ以外はフルハウスで、強さt=6

・s = str(t)
 上記で判定した役の強さをstr関数で文字列にしてsとします。

・for k,v in sorted(dN.items(), key=lambda (k,v):(v,k), reverse=True):
 ループ処理で1ずつ値を取り出せるものをイテレータといいます。
 sorted関数は並べ替えたイテレータを返します。
 最初の引数は並べ替え対象のイテレータです。
 dN.items()は、番号辞書dNのキーと値の組のタプルを返すイテレータです。
 つまり番号8が2枚のときに(8,2)のように組み合わせて返すイテレータです。
 これが並べ替え元です。

 引数keyは並べ替えキーの指定関数です。
 lambda関数で指定しています。lambda関数は無名関数といって、
 関数名を付けられないだけで通常の関数と同様に数式を指定できます。
 これはdef文による名前付き関数を別途定義して、その関数名を指定しても同じです。
 書式は「lambda 引数:数式」です。
 ここでは「lambda (k,v):(v,k)」なので、引数として
 番号辞書dNのキーと値の組み合わせタプル(k,v)を受け取って、(v,k)を返します。
 役を構成する番号はフラッシュ以外すべて複数枚であり、
 しかもその枚数の多い方が判定で優先使用されるため、
 ここでは番号辞書dNの(枚数, 番号)の順に並べ替えます。
 なおフラッシュは番号順に優先使用なのでこの並べ替え優先順位はそのまま使えます。

 引数reverseは逆順指定です。
 初期値はFalseで小さい順です。ここでは大きい順にしたいのでTrueとします。

・s += str(k).zfill(2) * v
 zfillプロパティは文字列を頭0埋めして指定桁数にした値を返します。
 上記で並べ替えた順に番号kと枚数vが設定されるので、
 頭0埋め文字列に変換して枚数の分だけ、順に連結します。

・return s
 上記で設定した、カードの強さ、つまり役+すべての番号の文字列sを呼び出し元に返します。
 例えば、カードが「TC TD QC 6D TS」の場合、10のスリーカードで、
 s=031010101206となります。

3.関数f(sIn)
・問題にあるポーカー用テキストファイルのフルパスを受け取り、プレーヤー1が勝つ回数を返します。

・for s in open(sIn).readlines():
 入力テキストファイルの全行を読み込んで、1行ずつループ変数sとします。

・L = s.split()
 半角空白区切りでリストにします。

・p1, p2 = g(L[:5]), g(L[5:])
 p1,p2はプレーヤー1,2の手札、前半5枚と後半5枚を関数gで変換した強さ文字列です。

・t += int(p1>p2)
 プレーヤー1の方が強い場合、カウンターtを1つカウントアップします。

4.関数の外
・import os, sys
 pythonの標準モジュールであるosモジュールとsysモジュールを使えるように準備します。

・sIn = os.path.join(os.path.dirname(sys.argv[0]), "poker.txt")
 ポーカー用テキストファイルのフルパスです。
 当pyソースと同じフォルダに置いていることを想定しています。
 sys.argv[0]は当pyソースのフルパスです。
 os.path.dirnameでその親フォルダ名を取得し、
 os.path.joinで親フォルダ名とファイル名を結合します。
 
・print f(sIn)
 上記関数fにポーカー用テキストファイルのフルパスを渡し、戻り値を表示します。
 

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