ネットで見つけた判断推理の家の位置関係の問題をPythonで解いてみました。(^_^;
次の図のような十字路の道路に面して(1)~(8)の家が並んでおり、A~Hの8人が一人ずつ住んでいる。今、次のア~カのことがわかっているとき、確実にいえるのはどれか。
ア Aの家は、2つの道路に面している。
イ AとBの家は、道路を挟んで真向かいにある。
ウ Cの家の隣にはDの家があり、BとDの家は、道路を挟んで真向かいにある。
エ CとHの家は、道路を挟んで真向かいにある。
オ Eの家の道路を挟んだ真向かいに家はない。
カ Fの家の隣の家とAの家は、道路を挟んで真向かいにある。1 Aの家は、(6)である。
2 Bの家は、(2)である。
3 Cの家の隣は、Eの家である。
4 Dの家の隣は、Fの家である。
5 Eの家の隣は、Gの家である。
ただし、「店」を「家」に、丸数字を括弧数字に修正しました。(^_^;
|道| +--+--+路+--+ |1|2| |3| -------+--+--+ +--+------- 道路 ----+--+--+--+ +--+--+---- |4|5|6| |7|8| +--+--+--+ +--+--+ | |
拙ブログのプログラムBoardPuz1.pyを雛形にしました。
条件ウは、「Cの家の隣にはDの家がある。」と「BとDの家は、道路を挟んで真向かいにある。」に分割しました。
条件カは、隣接する家と道路真向かいの家がそれぞれ2つある場合のことを考えて、setを使ってみました。ちなみに、Pythonで空集合は、「set()」です。
● House2.py
# coding: UTF-8 # House2.py from time import time import itertools RM, CM = 5, 8 # 行・列の最大数 # マップの初期状態 MAP = ''' +------+ | 12#3 | |######| |456#78| +------+ ''' ##print(MAP) MAP = MAP.replace('\n','') # 通し番号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 # A~Hの家の順列pを加えて新しいマップを作る PLACE = '12345678' def mkNewMap(p): r = MAP for n in range(len(p)): r = r.replace(PLACE[n],p[n]) return r # map上の通し番号n番目のとこの上下左右の文字のリストを得る def getSurroundings(n, map): li = [] if n< 0 or RM*CM-1< n: return [] # ドメインエラーなら[]を返す r,c = getRow(n),getCol(n) for i,j in [(-1,0),(1,0),(0,-1),(0,1)]: m = getN(r+i,c+j) if m!=-1: li.append(map[m]) return li # map上でA~Hの家hが面する道路の数を得る def getNumOfFacingRoad(h, map): n = map.find(h) li = getSurroundings(n, map) return li.count('#') # map上でA~Hの家hの隣の家のリストを得る def getNeighborsOf(h, map): n = map.find(h) li = getSurroundings(n, map) return [x for x in li if x.isalpha()] # map上でA~Hの家hの道路を挟んで真向かいの家のリストを得る def getHousesAcrossTheRoadFrom(h, map): n = map.find(h) li = getSurroundings(n, map) if li.count('#')==0: return [] r,c = getRow(n),getCol(n) lr = [] for i in range(len(li)): if li[i]=='#': if i==0: m = getN(r-2,c ) elif i==1: m = getN(r+2,c ) elif i==2: m = getN(r ,c-2) elif i==3: m = getN(r ,c+2) lr.append(map[m]) return lr # 結果を表示 def PrintMap(m): for i in range(RM): print(m[i*CM:(i+1)*CM]) ## print('') # 確実にいえる選択肢を得る def getAns(cho,lbl='12345'): return ','.join([lbl[i] for i in range(len(cho)) if cho[i]]) def main(): tm = time() # Timer Start HOUSE = 'ABCDEFGH' choices = [True]*5 cnt = 0 for p in itertools.permutations(HOUSE): map = mkNewMap(p) if not getNumOfFacingRoad('A',map)==2: continue # 条件ア if not 'B' in getHousesAcrossTheRoadFrom('A', map): continue # 条件イ if not 'D' in getNeighborsOf('C', map): continue # 条件ウ if not 'D' in getHousesAcrossTheRoadFrom('B', map): continue # 条件ウ if not 'H' in getHousesAcrossTheRoadFrom('C', map): continue # 条件エ if not ' ' in getHousesAcrossTheRoadFrom('E', map): continue # 条件オ s1 = set(getNeighborsOf('F',map)) s2 = set(getHousesAcrossTheRoadFrom('A',map)) if s1&s2==set(): continue # 条件カ ## if s1.isdisjoint(s2): continue pass # チェックを潜り抜けたものだけを表示 cnt+=1 print(cnt) PrintMap(map) pass # 選択肢のチェック choices[0] &= (map.find('A')==MAP.find('6')) choices[1] &= (map.find('B')==MAP.find('2')) choices[2] &= ('E' in getNeighborsOf('C', map)) choices[3] &= ('F' in getNeighborsOf('D', map)) choices[4] &= ('G' in getNeighborsOf('E', map)) print("∴%s"%getAns(choices)) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
1 +------+ | HB#A | |######| |ECD#GF| +------+ 2 +------+ | HG#A | |######| |ECD#BF| +------+ ∴3 Runtime : 0.953 [sec]
※参考URL
●Python, set型で集合演算(和集合、積集合や部分集合の判定など) | note.nkmk.me
●判断推理の家の位置関係の問題をPythonで解いてみた。 - rscのブログ
●判断推理のロッカーの位置関係の問題をPythonで解いてみた。 - rscのブログ
●日能研のマインスイーパーに似たボードパズルの問題をPythonで解いてみた。 - rscのブログ