teratailの「嘘つき族と正直族の問題」をPythonで解いてみた。

C Python

　teratailで見つけた「嘘つき族と正直族の問題」をPythonで解いてみました。(^_^;

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

　C++で作るのは難しいですが、Pythonなら簡単です。

● LiarsAndTruth-tellers.py

# coding: UTF-8
# LiarsAndTruth-tellers.py

import itertools
from time import time

# 論理等価Eqv
def Eqv(p,q):
    return not(p^q)

def main():
    tm = time() # Timer Start
    TF = (True, False)
    CARDS = range(1,5)  # カード1~4
    print("配られたカード/正直族[1]，嘘つき族[0]")
    print(" (A, B, C, D) / [A, B, C, D]")
    for p in itertools.permutations(CARDS):
        ca,cb,cc,cd = p         # card_a ~ card_d
        for q in itertools.product(TF,repeat=4):
            if not q.count(True)==2: continue
            la,lb,lc,ld = q     # liar_a ~ liar_d
            if not Eqv(la,ca%2==0): continue
            if not Eqv(lb,cb in [3,4]): continue
            if not Eqv(lc,lb): continue
            if not Eqv(ld,cd==1): continue
            pass # チェックを潜り抜けたものを表示
            print(' %s / %s'%(p,[int(x) for x in q]))

    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

配られたカード/正直族[1]，嘘つき族[0]
 (A, B, C, D) / [A, B, C, D]
 (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) / [0, 1, 1, 0]
 (4, 2, 3, 1) / [1, 0, 0, 1]
Runtime : 0.000 [sec]

　ちなみに、Borland C++で、＜algorithm＞のnext_permutation()を使って作ると次のようになります。変数名などは、元のプログラムに合わせました。(^_^;

● LiarsAndTruth-tellers.cpp

/*
 * LiarsAndTruth-tellers.cpp
 */

#include<iostream>
#include<string>
#include <algorithm>    // next_permutation()を使うため
using namespace std;

int card_a, card_b, card_c, card_d;
int liar_a, liar_b, liar_c, liar_d;

void output() {
    cout << "配られたカード： ";
    cout << card_a << ", " << card_b << ", " << card_c << ", " << card_d << ", ";
    cout << "正直族[1]，嘘つき族[0]：";
    cout << liar_a << ", " << liar_b << ", " << liar_c << ", " << liar_d << endl;
}

// 論理等価Eqv
int Eqv(int a, int b){
    return !(a^b);
}

int check() {
    int liars[] = {0,0,1,1};
    do{
        liar_a = liars[0]; liar_b = liars[1]; liar_c = liars[2]; liar_d = liars[3];
        if (! Eqv(liar_a, card_a%2==0)) continue;
        if (! Eqv(liar_b, card_b==3 || card_b==4)) continue;
        if (! Eqv(liar_c, liar_b==1)) continue;
        if (! Eqv(liar_d, card_d==1)) continue;
        return 1;   // true
    } while (next_permutation(liars, liars+4));
    return 0; // false
}

int main() {
    int cards[] = {1,2,3,4};
    do{
        card_a = cards[0]; card_b = cards[1]; card_c = cards[2]; card_d = cards[3];
        if (check()) {
            output();
        }
    } while (next_permutation(cards, cards+4));
    cout << "プログラム終了時は何かを入力" << endl;
    int x;    cin >> x;
    return 0;
}

●実行結果

配られたカード： 1, 3, 2, 4, 正直族[1]，嘘つき族[0]：0, 1, 1, 0
配られたカード： 1, 3, 4, 2, 正直族[1]，嘘つき族[0]：0, 1, 1, 0
配られたカード： 1, 4, 2, 3, 正直族[1]，嘘つき族[0]：0, 1, 1, 0
配られたカード： 1, 4, 3, 2, 正直族[1]，嘘つき族[0]：0, 1, 1, 0
配られたカード： 3, 4, 1, 2, 正直族[1]，嘘つき族[0]：0, 1, 1, 0
配られたカード： 4, 2, 3, 1, 正直族[1]，嘘つき族[0]：1, 0, 0, 1
プログラム終了時は何かを入力

　はてなで質問すればよかったのに。(^_^;

※参考URL
●嘘つき族と正直族の問題
●next_permutationがイマイチよくわからなかったのでまとめてみた #C++ - Qiita

●知恵袋の「ウソつき問題」をPythonで解いてみた。 - rscのブログ
●知恵袋の「ウソつき問題」をPythonで解いてみた。(2) - rscのブログ
●知恵袋の「ウソつき問題」をPythonで解いてみた。(5) - rscのブログ