DouKaku?beta

challenge トランプの和と積のパズル 

ここにトランプが一組あります．
司会者がそこから二枚抜いて，その積をAさんに，その和をBさんに教えました．

#トランプにジョーカーはなく、1～13までの数字が書かれたカードであると考えて構いません．
#たとえば，二枚のトランプの数字が2と5なら，Aさんには10，Bさんには7を教えます．
#二つの数は同じかもしれません．

司会者がAさん，Bさんに二つの数字が分かるかと質問しました．
Aさん「(この情報だけでは)分かりません」
Bさん「私も分かりません．ただ，Aさんが『分かりません』というのは分かっていました」
それを聞いたAさん「それなら，分かりました」
それを聞いたBさん「それなら，私も分かりました」
元の二つの数はなんだったのでしょうか．
この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。 このお題は光成さんの投稿が元になっています。ご投稿ありがとうございます。 
Perl が無かったので取り敢えず。
ぜんぜんフラットですが。
三番目の四番目の条件を誤った理解をして
悩みました。
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
use strict;

sub solve {
    my ($ceil) = @_;

    # 一番目と二番目の条件から組み合わせを絞り込む。
    my $pairs = [];
    {
        # 最初に二人が取り得る組み合わせ。
        my $la = {};
        my $lb = {};
        for (my $i = 1; $i <= $ceil; $i++) {
            for (my $j = $i; $j <= $ceil; $j++) {
                my $p = $i * $j;
                if ($la->{$p}) {
                    $la->{$p}[$#{$la->{$p}} + 1] = [$i, $j];
                } else {
                    $la->{$p} = [[$i, $j]];
                }
                my $s = $i + $j;
                if ($lb->{$s}) {
                    $lb->{$s}[$#{$lb->{$s}} + 1] = [$i, $j];
                } else {
                    $lb->{$s} = [[$i, $j]];
                }
            }
        }

        # A さんも B さんも教えられた数字(積と和)から
        # 判定出来ない。
        foreach my $k (keys(%{$la})) {
            delete($la->{$k}) if ($#{$la->{$k}} == 0);
        }

        foreach my $k (keys(%{$lb})) {
            delete($lb->{$k}) if ($#{$lb->{$k}} == 0);
        }

        # B さんは A が判定不能だと云う事を判っていた。
        # つまり和を分解して得られる組み合わせの全てに於いて、
        # その積の取り得る組み合わせが複数在ると云う事。
        foreach my $k (keys(%{$lb})) {
            foreach my $e (@{$lb->{$k}}) {
                ($la->{$e->[0] * $e->[1]}) || delete($lb->{$k});
            }
        }

        foreach my $k (keys(%{$lb})) {
            foreach my $e (@{$lb->{$k}}) {
                $pairs->[$#{$pairs} + 1] = $e;
            }
        }
    }

    # それを聞いた A さんは判ったのであるから、
    # 残りの組み合わせに積の重複は無い筈。
    {
        my $t = {};
        foreach my $e (@{$pairs}) {
            my $p = $e->[0] * $e->[1];
            $t->{$p} && $t->{$p}++ || ($t->{$p} = 1);
        }
        my $r = [];
        foreach my $e (@{$pairs}) {
            my $p = $e->[0] * $e->[1];
            ($t->{$p} == 1) && ($r->[$#{$r} + 1] = $e);
        }

        $pairs = $r;
    }

    # A さんが判ったと聞いた B さんも判つたので、
    # 残りの組み合わせに和の重複は無い筈。
    {
        my $t = {};
        foreach my $e (@{$pairs}) {
            my $s = $e->[0] + $e->[1];
            $t->{$s} && $t->{$s}++ || ($t->{$s} = 1);
        }
        my $r = [];
        foreach my $e (@{$pairs}) {
            my $s = $e->[0] + $e->[1];
            ($t->{$s} == 1) && ($r->[$#{$r} + 1] = $e);
        }

        $pairs = $r;
    }

    return $pairs;
}

foreach my $n (1..100) {
    printf("%4d: ", $n);
    my $e = &solve($n);
    if (! @{$e}) {
        printf("None");
    } else {
        foreach my $f (sort {($a->[0] <=> $b->[0]) || ($a->[1] <=> $b->[1])} @{$e}) {
            printf("[%2d, %2d], ", @{$f});
        }
    }
    print("\n");
}

汚かったので書き直しました。
これから他の人の解答をよんで勉強します。
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
use strict;

sub _p { return $_[0][0] * $_[0][1]; }
sub _s { return $_[0][0] + $_[0][1]; }
sub _c { return ($a->[0] <=> $b->[0]) || ($a->[1] <=> $b->[1]); }

sub solve {
    my ($ceil) = @_;

    my @pairs; # 組み合わせのリスト。
    my %pdup;  # 積の重複度。
    my %sdup;  # 和の重複度。

    # 初期状態。全ての組み合わせと、積・和の重複度を求める。
    {
        for (my $i = 1; $i <= $ceil; $i++) {
            for (my $j = $i; $j <= $ceil; $j++) {
                my $e = [$i, $j];
                push(@pairs, $e);
                $pdup{&_p($e)} = [] if (! $pdup{&_p($e)});
                $sdup{&_s($e)} = [] if (! $sdup{&_s($e)});
                $pdup{&_p($e)}[$#{$pdup{&_p($e)}}+1] = $e;
                $sdup{&_s($e)}[$#{$sdup{&_s($e)}}+1] = $e;
            }
        }
    }

    # (1) A さんも B さんも教えられた数字(積と和)から判定出来ない。
    {
        my @tmp;
        foreach my $e (@pairs) {
            next if (@{$pdup{&_p($e)}} == 1);
            next if (@{$sdup{&_s($e)}} == 1);
            push(@tmp, $e);
        }
        @pairs = @tmp;
    }

    # (2) B さんは A が判定不能だと云う事を判っていた。
    # つまり和を分解して得られる組み合わせの全てに於いて、
    # その積の取り得る組み合わせが複数在ると云う事。
    {
        my @tmp;
        foreach my $e (@pairs) {
            my $is_exclude = 0;
            foreach my $f (@{$sdup{&_s($e)}}){
                if (@{$pdup{&_p($f)}} == 1) {
                    $is_exclude = 1;
                    last;
                }
            }
            push(@tmp, $e) if (! $is_exclude);
        }
        @pairs = @tmp;
    }

    # (3) それを聞いた A さんは判ったのであるから、
    # 残りの組み合わせに積の重複は無い筈。
    {
        my @tmp;
        my %dup;
        foreach my $e (@pairs) {
            $dup{&_p($e)} = 0 if (! $dup{&_p($e)});
            $dup{&_p($e)}++;
        }
        foreach my $e (@pairs) {
            push(@tmp, $e) if ($dup{&_p($e)} == 1);
        }
        @pairs = @tmp;
    }

    # (4) A さんが判ったと聞いた B さんも判つたので、
    # 残りの組み合わせに和の重複は無い筈。
    {
        my @tmp;
        my %dup;
        foreach my $e (@pairs) {
            $dup{&_s($e)} = 0 if (! $dup{&_s($e)});
            $dup{&_s($e)}++;
        }
        foreach my $e (@pairs) {
            push(@tmp, $e) if ($dup{&_s($e)} == 1);
        }
        @pairs = @tmp;;
    }

    return @pairs;
}

foreach my $n (1..100) {
    printf("%4d: ", $n);
    my @pairs = &solve($n);
    if (! @pairs) {
        printf("None");
    } else {
        foreach my $e (sort _c @pairs) {
            printf("[%2d, %2d], ", @{$e});
        }
    }
    print("\n");
}

まとめられるループをまとめました。
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
use strict;

sub _c { return ($a->[0] <=> $b->[0]) || ($a->[1] <=> $b->[1]); }

sub solve {
    my ($ceil) = @_;

    my @pairs; # 組み合わせのリスト。
    my %pdup;  # 積の重複度。
    my %sdup;  # 二番目の条件のための判定テーブル。

    {
        # 積の重複度を求める。
        foreach my $i (1..$ceil) {
            foreach my $j ($i..$ceil) {
                my $p = $i * $j;
                $pdup{$p} = 0 if (! exists($pdup{$p}));
                $pdup{$p}++;
            }
        }
        # 初期状態を作成する。その際に条件(1)を考慮する。
        # (1) A さんも B さんも教えられた数字(積と和)から判定出来ない。
        # 更に条件(2)のための判定テーブルを作成する。
        foreach my $i (1..$ceil) {
            foreach my $j ($i..$ceil) {
                my $p = $i * $j;
                my $s = $i + $j;
                $sdup{$s} = 1 if (! exists($sdup{$s}));
                $sdup{$s} = 0 if ($pdup{$p} == 1);

                next if ($pdup{$p} == 1);
                next if ($s == 2);
                next if ($s == 3);
                next if ($s == (2 * $ceil - 1));
                next if ($s == (2 * $ceil));
                push(@pairs, [$i, $j]);
            }
        }
    }

    # (2) B さんは A が判定不能だと云う事を判っていた。
    # つまり和を分解して得られる組み合わせの全てに於いて、
    # その積の取り得る組み合わせが複数在ると云う事。
    {
        my @tmp;
        foreach my $e (@pairs) {
            my $s = $e->[0] + $e->[1];
            push(@tmp, $e) if ($sdup{$s});
        }
        @pairs = @tmp;
    }

    # (3) それを聞いた A さんは判ったのであるから、
    # 残りの組み合わせに積の重複は無い筈。
    # (4) A さんが判ったと聞いた B さんも判つたので、
    # 残りの組み合わせに和の重複は無い筈。
    {
        my @tmp;
        my %dup3;
        my %dup4;
        # 条件(3)のための重複検査を行う。
        foreach my $e (@pairs) {
            my $p = $e->[0] * $e->[1];
            $dup3{$p} = 0 if (! exists($dup3{$p}));
            $dup3{$p}++;
        }
        # 条件(3)の重複を取り除きながら、条件(4)のための
        # 重複検査を行う。
        foreach my $e (@pairs) {
            my $p = $e->[0] * $e->[1];
            next if ($dup3{$p} > 1);

            push(@tmp, $e);
            my $s = $e->[0] + $e->[1];
            $dup4{$s} = 0 if (! exists($dup4{$s}));
            $dup4{$s}++;
        }
        # 条件(4)の重複を取り除く。
        @pairs = ();
        foreach my $e (@tmp) {
            my $s = $e->[0] + $e->[1];
            next if ($dup4{$s} > 1);
            push(@pairs, $e);
        }
    }

    return @pairs;
}

foreach my $n (1..200) {
    printf("%4d: ", $n);
    my @pairs = &solve($n);
    if (! @pairs) {
        printf("None");
    } else {
        foreach my $e (sort _c @pairs) {
            printf("[%2d, %2d], ", @{$e});
        }
    }
    print("\n");
}
post comment

Posted feedbacks - Python

結構しんどかったです・・・ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# coding: shift_jis

def all(iterable, key):
    for x in iterable:
        if not key(x):
            return False
    return True

def main():
    limit = 13 + 1

    add_table = [[] for _ in xrange(limit + limit)]
    mul_table = [[] for _ in xrange(limit * limit)]
    for i in xrange(1, limit):
        for j in xrange(i, limit):
            add_table[i + j].append((i, j))
            mul_table[i * j].append((i, j))

    # すべてのカードの組み合わせを生成
    pairs = [(i, j) for i in xrange(1, limit) for j in xrange(i + 1, limit)]

    # Aさん「(この情報だけでは)分かりません」
    # ... すべてのペアが、積のあいまいなペアである
    pairs = [pair for pair in pairs if len(mul_table[pair[0] * pair[1]]) >= 2]

    # Bさん「私も分かりません．ただ，Aさんが『分かりません』というのは分かっていました」
    # ... 和からとりうるペアは複数あり、そのすべてが積のあいまいなペアである
    def check(pair):
        a = add_table[pair[0] + pair[1]]
        return len(a) >= 2 and all(a, key=lambda pair: len(mul_table[pair[0] * pair[1]]) >= 2)
    pairs = [pair for pair in pairs if check(pair)]

    # それを聞いたAさん「それなら，分かりました」
    # ... 残ったペアを見て、積から一意に定まらないものを取り除く
    #（例えば、(1,12),(2,6)が残っていれば積12という情報から決められないので排除）
    h = {}
    for pair in pairs:
        h.setdefault(pair[0] * pair[1], []).append(pair)
    pairs = [v[0] for (k, v) in h.iteritems() if len(v) == 1]

    # それを聞いたBさん「それなら，私も分かりました」
    # ... 残ったペアを見て、和から一意に定まらないものを取り除く
    #（例えば、(1,3),(2,2)が残っていれば和4という情報から決められないので排除）
    h = {}
    for pair in pairs:
        h.setdefault(pair[0] + pair[1], []).append(pair)
    pairs = [v[0] for (k, v) in h.iteritems() if len(v) == 1]

    print pairs

if __name__ == '__main__':
    main()

これはおもしろいなぁ。 各関数でそれぞれのステップでの候補列挙。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def a1():
    table = [[] for i in xrange(13 * 13 + 1)]
    for i in xrange(1, 13 + 1):
        for j in xrange(i, 13 + 1):
            table[i * j].append((i, j))
    c = set()
    for lst in table:
        if len(lst) > 1:
            for t in lst:
                c.add(t)
    return c

def b1():
    candidates = a1()
    table = [[] for i in xrange(13 + 13 + 1)]
    for i in xrange(1, 13 + 1):
        for j in xrange(i, 13 + 1):
            table[i + j].append((i, j))

    c = set()
    for cand in table:
        if len(cand) < 2: continue
        if all(t in candidates for t in cand):
            for t in cand: c.add(t)
    return c

def a2():
    candidates = b1()
    table = dict()
    for i, j in candidates:
        if i * j in table:
            table[i * j].append((i, j))
        else:
            table[i * j] = [(i, j)]
    return set(c[0] for c in table.itervalues() if len(c) == 1)

def b2():
    candidates = a2()
    table = dict()
    for i, j in candidates:
        if i + j in table:
            table[i + j].append((i, j))
        else:
            table[i + j] = [(i, j)]

    return set(c[0] for c in table.itervalues() if len(c) == 1)

if __name__ == '__main__':
    for i, j in b2():

なんか、ズルしてるような。 
1
2
3
4
5
6
a=[i*j for i in range(1,14) for j in range(i,14)]
b=[i+j for i in range(1,14) for j in range(i,14)]
c=[(i,j) for i in range(1,14) for j in range(i,14) if a.count(i*j)==2 and b.count(i+j)==2]
a=[i*j for i,j in c]
b=[i+j for i,j in c]
print [(i,j) for i,j in c if a.count(i*j)==2 and b.count(i+j)==2]


あら、昨夜返信したと思ったら、ミスっていたようです。

根本的に問題が解けていませんでした。
他の方のコードを見てやっと理解できました。

というわけで、効率無視で閉包を多用した新版です。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
n=13+1
a=[i*j for i in range(1,n) for j in range(i,n)]
a=[(i,j) for i in range(1,n) for j in range(i,n) if a.count(i*j)>1]
d={};[(i+j not in d) and d.setdefault(i+j,[(i,j)]) or d[i+j].append((i,j)) for i in range(1,n) for j in range(i,n)]
c=[];[c.extend(v) for v in d.values() if len(v)>1 and set(v).issubset(a)]
a=[i*j for i,j in c]
c=[(i,j) for i,j in c if a.count(i*j)==1]
a=[i+j for i,j in c]
c=[(i,j) for i,j in c if a.count(i+j)==1]

for i,j in c:
  print '(%d,%d)' % (i,j)


最終バージョンです。

相変わらず効率は無視してますが、見た目は非常にシンプルになりました。
３行目から７行目がお題のフィルタ条件と1対1に対応しています。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
n=13+1
o=[(i,j,i*j,i+j) for i in range(1,n) for j in range(i,n)]
a=[t for t in o if [u[2] for u in o].count(t[2])>1]
o=[t for t in o if [u[3] for u in o].count(t[3])>1]
o=[t for t in o if set([u for u in o if u[3]==t[3]]).issubset(a)]
o=[t for t in o if [u[2] for u in o].count(t[2])==1]
o=[t for t in o if [u[3] for u in o].count(t[3])==1]

for i,j,x,x in o:
  print '(%d,%d)' % (i,j)

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]