嘘つき族と正直族の問題

####はじめに
とあるところで、次のような「嘘つき族と正直族の問題」を見つけました。興味がわいたので自分なりにPythonでプログラムしてみました。

>
ある村に，Ａさん，Ｂさん，Ｃさん，Ｄさんの4人がいました．
このうち2人は嘘つき族であり，このうち2人は正直族であることが分かっています．
嘘つき族は必ずうそをつき，正直族は必ず正直に答えます．
彼らは，論理的であり，ミスはありません．
あなたの手元には， １，２，３，４と書かれた4枚のカードがあります．同じ数字が書かれたカードはありません．
そこからランダムに選んで，一人1枚ずつ，彼らに渡しました． 彼らは，以下のように発言しました．
Ａさん：私のカードは，偶数です．
Ｂさん：私のカードは，３か４のどちらかです．
Ｃさん：Ｂさんは，正直族です．
Ｄさん：私のカードは，１です．
彼らに配られた可能性のあるカードの数字と，誰が嘘つき族／正直族かを表示するプログラムを作成します．

#####どのように進めるか
Ａさん，Ｂさん，Ｃさん，Ｄさんの誰が嘘つき族か正直族か分からない（これが問題だから当然）ので、各人を嘘つき族か正直族かを仮定した全パターンで、全パターンのカードを配り各人の嘘つき族か正直族を判断します。
次に仮定したパターンと判断したパターンが一致した場合に求める解とすれば良いのではないかと思ったので、そのようにプログラムを作っていきます。

#####嘘つきか正直かの判定
以下のように、配られたカードでＡさん，Ｂさん，Ｃさん，Ｄさんが嘘つきか正直かを判定します。ただし、ＣさんはＢさんの嘘つき／正直により判定します。

Ａさん：

|配られたカード|発言内容（固定）|判定|
|:------------:|:--------------:|:--:|
|偶数|私のカードは、偶数です．|正直|
|偶数でない|私のカードは、偶数です．|嘘つき|


Ｂさん：

|配られたカード|発言内容（固定）|判定|
:-------------:|:--------------:|:--:|
|3か４|私のカードは、3か4のどちらかです．|正直|
|3でも4でもない|私のカードは、3か4のどちらかです．|嘘つき|


Ｃさん：

|Ｂさんが|発言内容（固定）|判定|
:-------:|:--------------:|:--:|
|正直|Ｂさんは、正直者です．|正直|
|嘘つき|Ｂさんは、正直者です．|嘘つき|


Ｄさん：

|配られたカード|発言内容（固定）|判定|
:-------------:|:--------------:|:--:|
|1|私のカードは、1です．|正直|
|1でない|私のカードは、1です．|嘘つき|

#####嘘つきか正直かの組合せ
嘘つきか正直かの組合せは以下の6パターンです。嘘つきは0、正直は1で現わします。

|Ａさん|Ｂさん|Ｃさん|Ｄさん|
|:----:|:----:|:----:|:----:|
|0|0|1|1|
|0|1|0|1|
|0|1|1|0|
|1|0|0|1|
|1|0|1|0|
|1|1|0|0|

#####配るカードの組合せ
配るカードの組合せは、順列の<sub>n</sub>P<sub>k</sub>（n個のものからk個選ぶ場合の数）から求めます。今回は<sub>4</sub>P<sub>4</sub>で求めます。
Pythonのitertoolsパッケージに順列を求める関数permutations()があるので、それを使います。

#####実際のコード

```:Python
# 嘘つき族と正直族の問題
import itertools

#Ａさんの判定：私のカードは，偶数です．
def judge_A(card_no):
    if (card_no % 2) == 0:
        ret = 1
    else:
        ret = 0
    return ret

#Ｂさんの判定：私のカードは，３か４のどちらかです．
def judge_B(card_no):
    if card_no == 3 or card_no == 4:
        ret = 1
    else:
        ret = 0
    return ret

#Ｃさんの判定：Ｂさんは，正直族です．
def judge_C(judge_of_B):
    if judge_of_B == 1:
        ret = 1
    else:
        ret = 0
    return ret

#Ｄさんの判定：私のカードは，１です．
def judge_D(card_no):
    if card_no == 1:
        ret = 1
    else:
        ret = 0
    return ret

# 判定
#   deal_card : 配ったカード（１、２、３、４）．要素数４のリスト．
#               [0]=Ａさん、[1]=Ｂさん、｢2｣=Ｃさん、[3]=Ｄさん
#   return    : 判定結果．要素数４のリスト．
#               [0]=Ａさん、[1]=Ｂさん、｢2｣=Ｃさん、[3]=Ｄさん
def judge(deal_card):
    lh_judge = [None, None, None, None]
    lh_judge[0] = judge_A(deal_card[0])
    lh_judge[1] = judge_B(deal_card[1])
    lh_judge[2] = judge_C(lh_judge[1])
    lh_judge[3] = judge_D(deal_card[3])
    return lh_judge

def main():
    # 嘘つきと正直の組合せ
    lh_comb = [[0, 0, 1, 1],
               [0, 1, 0, 1],
               [0, 1, 1, 0],
               [1, 0, 0, 1],
               [1, 0, 1, 0],
               [1, 1, 0, 0]]

    # 配るカード(1から4)の組合せ（順列：nPk）
    cards_comb = list(itertools.permutations([1, 2, 3, 4]))

    # 嘘つきと正直の組合せ×カードの組合せで調べる．
    print("\
嘘つき(0)／正直(1)          |配ったカード\n\
Ａさん Ｂさん Ｃさん Ｄさん |Ａさん Ｂさん Ｃさん Ｄさん\n\
---------------------------------------------------------")
    for lh_assumption in lh_comb:
        for deal_card in cards_comb:
            lh_judge = judge(deal_card)
            if lh_assumption == lh_judge:
                print("{:^7d}{:^7d}{:^7d}{:^7d}|{:^7d}{:^7d}{:^7d}{:^7d}".
                      format(lh_judge[0],lh_judge[1],lh_judge[2],lh_judge[3],
                             deal_card[0],deal_card[1],deal_card[2],deal_card[3]))
    return

if __name__ == '__main__':
    main()
```

#####実行結果
以下の６ケースあることが分かりました。

```
嘘つき(0)／正直(1)           |配ったカード
Ａさん  Ｂさん  Ｃさん  Ｄさん |Ａさん  Ｂさん  Ｃさん  Ｄさん
---------------------------------------------------------
   0      1      1      0   |   1      3      2      4   
   0      1      1      0   |   1      3      4      2   
   0      1      1      0   |   1      4      2      3   
   0      1      1      0   |   1      4      3      2   
   0      1      1      0   |   3      4      1      2   
   1      0      0      1   |   4      2      3      1   
```

#####おわりに

頭の体操に良い問題でした。