ネットで見つけた判断推理の座席の位置関係の問題をPythonで解いてみました。(^_^;
図のように机が配置されている教室で、黒板に向かって座っているA～Lの12人の生徒の席順について、次のア～キのことが分かっている。
ア Aの両隣にはBとCが座っている。
イ Bのすぐ後ろにはDが座っている。
ウ Cのすぐ前にはEが座っている。
エ Dの隣にはLが座っている。
オ Fの隣にはKが座っている。
カ Gのすぐ後ろにはJが座っている。
キ Hの両隣にはGとIが座っている。
以上から判断して、確実にいえるのはどれか。
１ Aのすぐ後ろにはFが座っている。
２ Eの隣にはGが座っている。
３ Hのすぐ後ろにはAが座っている。
４ Kの隣にはBが座っている。
５ Lのすぐ前にはJが座っている。+------------------+ | ============== | | 黒板 | | [ 0][ 1][ 2][ 3] | | ◎ ◎ ◎ ◎ | | [ 4][ 5][ 6][ 7] | | ◎ ◎ ◎ ◎ | | [ 8][ 9][10][11] | | ◎ ◎ ◎ ◎ | +------------------+（注）◎は各生徒の座席位置を示す
ただし、各座席に0～11の通し番号を付けました。
12個の順列は時間がかかるので枝が早く刈れそうなA～Eのグループと残りのグループに分け、A～Eのグループだけのマップを先に作成して、残りを順列で回してみました。(^_^;
前半のA～Eのグループだけのマップを作成する場合、同じものを含む順列を使ってもいいですが、「set(itertools.permutations())」は、
全要素数が大きいと遅くなってしまうようなので、結果の出力数が少ないと速くなる拙ブログのPermSame1.pyで用いた「genPerm()」を使うとよいです。(^_^;
ちなみに、subStr()関数は、Perlのsubstr()関数を参考にして作りました。ただし、Perlと違って、文字列 s は変更せずに、置換後の文字列を戻り値として返します。(^_^;
● seating4.py
# coding: UTF-8 # seating4c.py import itertools from time import time RM, CM = 3+2, 4+2 # 行・列の最大数 # マップの初期状態(固定) MAP = ''' ###### #0123# #4567# #89ab# ###### ''' MAP = MAP.replace('\n','') MAP1 = '#'*CM+'#....#'*3+'#'*CM ##print(MAP); print(MAP1); exit() # 通し番号n番目の行数を得る（0スタート） def getRow(n): return n//CM # 通し番号n番目の列数を得る（0スタート） def getCol(n): return n%CM # r行c列の通し番号を得る（0スタート） def getN(r,c): if not(0<=r< RM): return -1 # ドメインエラーは-1を返す if not(0<=c< CM): return -1 return r*CM+c # map上の人 c のすぐ前の人を文字で得る def getFrontOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r-1,c)] # map上の人 c のすぐ後ろの人を文字で得る def getBackOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r+1,c)] # 作成途中のマップ m と順列 p から新しいマップを作る def mkNewMap(m,p): r = m li = LookUp('.',r) for i,n in enumerate(li): r = subStr(r,n,1,p[i]) return r # リストla中の要素xに対応するリストlb中の要素をリストですべて返す # lbを省略すると、インデックスのリストを返す def LookUp(x,la,lb=[]): if lb==[]: return [i for i,a in enumerate(la) if a==x] return [lb[i] for i,a in enumerate(la) if a==x] # 文字列 s の m 番目(0スタート)から n 文字分を文字列 t で置換する # t を省略すると、文字列 s の m 番目から n 文字分を取り出す def subStr(s,m,n,t=None): if t is None: return s[m:m+n] return f'{s[:m]}{t}{s[m+n:]}' # 結果の表示 def PrintResult(c,m): print(f"[{c:2d}]") print(f"{m[ :CM ]}") print(f"{m[CM :CM*2]}") print(f"{m[CM*2:CM*3]}") print(f"{m[CM*3:CM*4]}") print(f"{m[CM*4: ]}") # 確実にいえる選択肢を得る def getAns(ch,lb='12345'): return ','.join([lb[i] for i,c in enumerate(ch) if c]) def main(): tm = time() # Timer Start choices = [True]*5 PLACE = '0123456789ab' P = 'ABCDE' # 人(グループ1) Q = 'FGHIJKL' # 人(グループ2) count = 0 Maps = [] for i in range(12): a = MAP.index(PLACE[i]) # AのMAP上の通し番号 for b,c in [(a-1,a+1),(a+1,a-1)]: # B,CのMAP上の通し番号 if '#' in (MAP[b], MAP[c]): continue # 条件ア d = getN(getRow(b)+1,getCol(b)) # DのMAP上の通し番号 if MAP[d]=='#': continue # 条件イ e = getN(getRow(c)-1,getCol(c)) # EのMAP上の通し番号 if MAP[e]=='#': continue # 条件ウ pass # チェックを潜り抜けたものを追加 m = MAP1 # A~Eだけのマップを作成 for i,n in enumerate([a,b,c,d,e]): m = subStr(m,n,1,P[i]) Maps.append(m) ## print(Maps); exit() for p in Maps: for q in itertools.permutations(Q): m = mkNewMap(p,q) if not ('DL' in m or 'LD' in m): continue # 条件エ if not ('FK' in m or 'KF' in m): continue # 条件オ if not getBackOf('G',m)=='J': continue # 条件カ if not ('GHI' in m or 'IHG' in m): continue # 条件キ pass # チェックを潜り抜けたものを表示 count+=1 PrintResult(count,m) # 選択肢のチェック choices[0] &= getBackOf('A',m)=='F' choices[1] &= ('EG' in m or 'GE' in m) choices[2] &= getBackOf('H',m)=='A' choices[3] &= ('KB' in m or 'BK' in m) choices[4] &= getFrontOf('L',m)=='J' print("∴%s"%getAns(choices)) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[ 1] ###### #EIHG# #CABJ# #FKDL# ###### [ 2] ###### #EIHG# #CABJ# #KFDL# ###### [ 3] ###### #GHIE# #JBAC# #LDFK# ###### [ 4] ###### #GHIE# #JBAC# #LDKF# ###### ∴5 Runtime : 0.551 [sec]
※参考URL
●質問の座席の問題をPythonで解いてみた。 - rscのブログ
●知恵袋の判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ
●判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ
