知恵袋で見つけた判断推理の出勤簿の問題をPythonで解いてみた。(3)

　以前、判断推理の出勤簿の問題を解くプログラムをPythonで作りましたが、同じものを含む順列set(itertools.permutations())を直接ループに用いたら遅くなってしまったので、itertools.product()を用いて作りました。(^_^;
　ひょんなことから、同じものを含む順列を用いて解いているプログラムをネットで発見しましたが、同じものを含む順列を使っても速いものができるようなので、それを参考にさせてもらって作り直しみました。(^_^;
　直接ループに用いるより、順列パターンを作成しておいてから用いる方が良いのかな。(^_^;

● AttendanceBook3.py

# coding: UTF-8
# AttendanceBook3.py

from time import time
import itertools

# 出勤者数のチェック
def chechAttendance(la, ls):
    for i in range(len(ls)):
        t = 0
        for j in range(len(la)):
            t+=1 if la[j][i]=='o' else 0
        if t!=ls[i]: return False
    return True

# aの出勤表laからc曜日に働いたか調べる
# 'UMTWRFS': '日月火水木金土'
def hasWorked(la, c):
    WD = 'UMTWRFS'
    return la[WD.index(c)]=='o'

# 一緒に出勤した日数を調べる
def numOfDaysTog(la,lb):
    c = 0
    for i in range(len(la)):
        if la[i]=='o' and lb[i]=='o': c+=1
    return c

# 結果を表示
def PrintResult(lst):
    n = len(lst)
    NAME = u'ＡＢＣＤＥ'
    print(u'　日月火水木金土')
    for i in range(n):
        s = NAME[i]+''.join(lst[i])
        print(s.replace('o',u'○').replace('x',u'×'))
    print('')

def main():
    tm=time()  # Timer Start
    S = [3,4,1,3,1,4,3]

    # 3日出勤パターン作成
    pattern3 = set(itertools.permutations('oooxxxx'))
    # 4日出勤パターン作成
    pattern4 = set(itertools.permutations('ooooxxx'))
    # 5日出勤パターン作成
    pattern5 = set(itertools.permutations('oooooxx'))

    ch = [True]*5
    cnt = 0
    for a in pattern3:
        sa = ''.join(a)                     # Aの出勤表を文字列で得る
        if 'xx' in sa: continue                             # 条件ア
        for b in pattern5:
            for c in pattern4:
                for d in pattern3:
                    if numOfDaysTog(c,d)!=0: continue       # 条件イ
                    for e in pattern4:
                        se = ''.join(e)     # Eの出勤表を文字列で得る
                        if numOfDaysTog(d,e)!=0: continue   # 条件ウ
                        if 'xxx' not in se: continue        # 条件エ
                        li = [a,b,c,d,e]
                        if not chechAttendance(li,S): continue
                        # チェックを潜り抜けたものだけを表示
                        cnt+=1
                        print("[%d]"%cnt)
                        PrintResult(li)
                        # 選択肢のチェック
                        ch[0] &= not hasWorked(c,'S')
                        ch[1] &= not hasWorked(a,'M')
                        ch[2] &=     hasWorked(d,'T')
                        ch[3] &= not hasWorked(b,'W')
                        ch[4] &=     hasWorked(e,'R')

    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]
　日月火水木金土
Ａ×○×○×○×
Ｂ○○×○×○○
Ｃ○○×××○○
Ｄ××○○○××
Ｅ○○×××○○

∴ 3
Runtime : 0.172 [sec]

※参考URL
●出勤簿の判断推理 - メモ
●判断推理の出勤簿の問題をJavaで解いてみた。
●知恵袋で見つけた判断推理の出勤簿の問題をPythonで解いてみた。
●知恵袋で見つけた判断推理の出勤簿の問題をPythonで解いてみた。(2)