知恵袋で見つけた判断推理のトーナメントの問題をPythonで解いてみました。(^_^;
問題 A〜Hの8チームが綱引きの試合をトーナメント戦で行った。
ア〜オのことがすべて分かっているとき、確実にいえるのはどれか。
ア 1回戦でHチームに勝ったチームは、2回戦でEチームに負けた。
イ Dチームは全部で2試合試合を行った。
ウ 1回戦でBチームに勝ったチームは、3回戦まで進んだが、優勝はしなかった。
エ 1回戦でAチームに勝ったチームは、2回戦でFチームに勝った。
オ CチームはEチームに負けた。1 AチームはGチームと対戦した。
2 BチームはCチームと対戦した。
3 CチームはFチームと対戦した。
4 DチームはHチームと対戦した。
5 EチームはGチームと対戦した。
下図のようなトーナメント戦のそれぞれの位置に入るチーム名を、K,L,M,N,Q,R,S,T,X,Y,Z,O,U,V,Wとおいて、対称性からK
W
+-----+-----+ 3回戦
| |
U V
+--+--+ +--+--+ 2回戦
| | | |
X Y Z O
+-+-+ +-+-+ +-+-+ +-+-+ 1回戦
| | | | | | | |
K < L M < N Q < R S < T
K < M Q < S
K < Q● TournamentTugOfWar.py
# coding: UTF-8 # TournamentTugOfWar.py import itertools from time import time # cが何回戦まで出場したかを対戦データlstから求める def getRound(c, lst): if c not in lst: return 1 n = lst.index(c)+1 if n< 2: return 4 elif n< 4: return 3 else: return 2 # aとbの対戦が対戦リストlst内にあるか調べる def hasMatched(a, b, lst): if [a,b] in lst: return True if [b,a] in lst: return True return False # aがbと対戦して勝ったかを対戦データlstから調べる def hasWon(a, b, lst): if [a,b,a] in lst: return True if [b,a,a] in lst: return True return False # aの対戦者を対戦リストlstから求める def getOpponent(a,lst): for l in lst: if a in l: return l[l.index(a)^1] return '\0' # なければ、'\0'を返す # 次元を下げる def flatten(lst): return list(itertools.chain.from_iterable(lst)) def main(): tm = time() # Timer Start ch = [True]*5 #12345678 P = 'ABCDEFGH' cnt = 0 for p in itertools.permutations(P): k,l,m,n,q,r,s,t = p if k>=l or m>=n or k>=m or k>=q: continue if q>=r or s>=t or q>=s: continue lFst = [[k,l],[m,n],[q,r],[s,t]] for b in itertools.product([True,False],repeat=7): x,y = k if b[0] else l, m if b[1] else n z,o = q if b[2] else r, s if b[3] else t u,v = x if b[4] else y, z if b[5] else o w = u if b[6] else v lSnd = [[x,y],[z,o]] lTrd = [[u,v]] # [[{対戦者1},{対戦者2}],…] lAll = lFst+lSnd+lTrd # hasMatched用データ lgRd = [w]+flatten(lTrd+lSnd) # getRound用データ lhWF = [[k,l,x],[m,n,y],[q,r,z],[s,t,o]] lhWS = [[x,y,u],[z,o,v]] # [[{対戦者1},{対戦者2},{勝者}],…] lhWT = [[u,v,w]] lhWA = lhWF+lhWS+lhWT # hasWon用データ oH = getOpponent('H',lFst) # Hチームの1回戦の対戦相手 if not hasWon( oH,'H',lhWF): continue # 条件ア if not hasWon('E', oH,lhWS): continue # 条件ア if getRound('D',lgRd)!= 2: continue # 条件イ oB = getOpponent('B',lFst) # Bチームの1回戦の対戦相手 if getRound(oB,lgRd)!= 3: continue # 条件ウ oA = getOpponent('A',lFst) # Aチームの1回戦の対戦相手 if not hasWon( oA,'F',lhWS): continue # 条件エ if not hasWon('E','C',lhWA): continue # 条件オ # チェックを潜り抜けたものだけを表示 cnt+=1 print("[%2d] %c "%(cnt,w)) print(" +-----+-----+ ") print(" | | ") print(" %c %c "%(u,v)) print(" +--+--+ +--+--+ ") print(" | | | | ") print(" %c %c %c %c "%(x,y,z,o)) print(" +-+-+ +-+-+ +-+-+ +-+-+") print(" | | | | | | | |") print(" %c %c %c %c %c %c %c %c"%(k,l,m,n,q,r,s,t)) print("") # 選択肢のチェック ch[0] &= True if hasMatched('A','G',lAll) else False ch[1] &= True if hasMatched('B','C',lAll) else False ch[2] &= True if hasMatched('C','F',lAll) else False ch[3] &= True if hasMatched('D','H',lAll) else False ch[4] &= True if hasMatched('E','G',lAll) else False if cnt==0: ch = [False]*5 s = "" for c in ch: if c : s+=" %s"%(ch.index(c)+1) print(u"∴%s"%s) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[ 1] E
+-----+-----+
| |
E C
+--+--+ +--+--+
| | | |
E F C D
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | |
A E F H B C D G
∴ 2
Runtime : 0.580 [sec]P.S.
対戦データをリストのリストから文字列のリストに変更すると、対戦データが整理されて倍速とまではいきませんがちょっと高速化します。(^_^;
● TournamentTugOfWar2.py
# coding: UTF-8 # TournamentTugOfWar2.py import itertools from time import time # cが何回戦まで出場したかを対戦データlstから求める def getRound(c, lst): sl = ''.join(lst) if c not in sl: return 1 n = sl.index(c)+1 if n< 2: return 4 elif n< 4: return 3 else: return 2 # aとbが対戦したか対戦リストlstから調べる def hasMatched(a, b, lst): if a+b in lst: return True if b+a in lst: return True return False # aがbと対戦して勝ったかを対戦データll(下),lu(上)から調べる def hasWon(a, b, ll,lu): sl = ''.join(lu) if a+b in ll and sl[ll.index(a+b)]==a: return True if b+a in ll and sl[ll.index(b+a)]==a: return True return False # aの対戦者を対戦リストlstから求める def getOpponent(a,lst): for li in lst: if a in li: return li[li.index(a)^1] return '\0' # なければ、'\0'を返す def main(): tm = time() # Timer Start ch = [True]*5 #12345678 P = 'ABCDEFGH' cnt = 0 for p in itertools.permutations(P): k,l,m,n,q,r,s,t = p if k>=l or m>=n or k>=m or k>=q: continue if q>=r or s>=t or q>=s: continue lFst = [k+l,m+n,q+r,s+t] for b in itertools.product([True,False],repeat=7): x,y = k if b[0] else l, m if b[1] else n z,o = q if b[2] else r, s if b[3] else t u,v = x if b[4] else y, z if b[5] else o w = u if b[6] else v lSnd = [x+y,z+o] lTrd = [u+v] lAll = lTrd+lSnd+lFst lAlu = [w]+lTrd+lSnd # getRound用データ oH = getOpponent('H',lFst) # Hチームの1回戦の対戦相手 if not hasWon( oH,'H',lFst,lSnd): continue # 条件ア if not hasWon('E', oH,lSnd,lTrd): continue # 条件ア if getRound('D',lAlu)!= 2: continue # 条件イ oB = getOpponent('B',lFst) # Bチームの1回戦の対戦相手 if getRound(oB,lAlu)!= 3: continue # 条件ウ oA = getOpponent('A',lFst) # Aチームの1回戦の対戦相手 if not hasWon( oA,'F',lSnd,lTrd): continue # 条件エ if not hasWon('E','C',lAll,lAlu): continue # 条件オ # チェックを潜り抜けたものだけを表示 cnt+=1 print("[%3d] %c "%(cnt,w)) print(" +-----+-----+ ") print(" | | ") print(" %c %c "%(u,v)) print(" +--+--+ +--+--+ ") print(" | | | | ") print(" %c %c %c %c "%(x,y,z,o)) print(" +-+-+ +-+-+ +-+-+ +-+-+") print(" | | | | | | | |") print(" %c %c %c %c %c %c %c %c"%(k,l,m,n,q,r,s,t)) print # 選択肢のチェック ch[0] &= hasMatched('A','G',lAll) ch[1] &= hasMatched('B','C',lAll) ch[2] &= hasMatched('C','F',lAll) ch[3] &= hasMatched('D','H',lAll) ch[4] &= hasMatched('E','G',lAll) if cnt==0: ch = [False]*5 s = "" for c in ch: if c : s+=" %s"%(ch.index(c)+1) print(u"∴%s"%s) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[ 1] E
+-----+-----+
| |
E C
+--+--+ +--+--+
| | | |
E F C D
+-+-+ +-+-+ +-+-+ +-+-+
| | | | | | | |
A E F H B C D G
∴ 2
Runtime : 0.327 [sec]※参考URL
http://stackoverflow.com/questions/103844/how-do-i-merge-a-2d-array-in-python-into-one-string-with-list-comprehension
●Pythonでリストをflattenする方法まとめ - Soleil cou coupe
●知恵袋で見つけた判断推理のトーナメントの問題をPythonで解いてみた。
●知恵袋で見つけた判断推理のトーナメントの問題をPythonで解いてみた。(2)
