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 - Flatten

Nested Hidden
答えは、(1,4)ですかね？ 
 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
using System;
using System.Collections.Generic;
class Program
{
  static void Main()
  {
    Dictionary<int, Dictionary<KeyValuePair<int, int>, object>> A = new Dictionary<int, Dictionary<KeyValuePair<int, int>, object>>();
    Dictionary<int, Dictionary<KeyValuePair<int, int>, object>> B = new Dictionary<int, Dictionary<KeyValuePair<int, int>, object>>();
    Dictionary<KeyValuePair<int, int>, object> v;
    for (int i = 1; i <= 13; ++i)
    {
      for (int j = i; j <= 13; ++j)
      {
        KeyValuePair<int, int> kv = new KeyValuePair<int, int>(i, j);
        if (!A.TryGetValue(i * j, out v)) A[i * j] = v = new Dictionary<KeyValuePair<int, int>, object>();
        v.Add(kv, null);
        if (!B.TryGetValue(i + j, out v)) B[i + j] = v = new Dictionary<KeyValuePair<int, int>, object>();
        v.Add(kv, null);
      }
    }
    // Bさん「私も分かりません．ただ，Aさんが『分かりません』というのは分かっていました」
    foreach (int k in new List<int>(B.Keys))
    {
      if (B[k].Count > 1)
      {
        bool b = true;
        foreach (KeyValuePair<int, int> kv in new List<KeyValuePair<int, int>>(B[k].Keys))
          if (b = A[kv.Key * kv.Value].Count == 1) break;
        if (!b) continue;
      }
      B.Remove(k);
    }
    // Aさん「(この情報だけでは)分かりません」
    foreach (int k in new List<int>(A.Keys))
      if (A[k].Count == 1) A.Remove(k);
    // それを聞いたAさん「それなら，分かりました」
    foreach (int k in new List<int>(A.Keys))
    {
      foreach (KeyValuePair<int, int> kv in new List<KeyValuePair<int, int>>(A[k].Keys))
        if (!B.ContainsKey(kv.Key + kv.Value) || !B[kv.Key + kv.Value].ContainsKey(kv)) A[k].Remove(kv);
      if (A[k].Count != 1) A.Remove(k);
    }
    // それを聞いたBさん「それなら，私も分かりました」  }
    foreach (int k in new List<int>(B.Keys))
    {
      foreach (KeyValuePair<int, int> kv in new List<KeyValuePair<int, int>>(B[k].Keys))
        if (!A.ContainsKey(kv.Key * kv.Value) || !A[kv.Key * kv.Value].ContainsKey(kv)) B[k].Remove(kv);
      if (B[k].Count != 1) B.Remove(k);
    }
    foreach (KeyValuePair<int, Dictionary<KeyValuePair<int, int>, object>> kvp in B)
    {
      foreach (KeyValuePair<int, int> kv in kvp.Value.Keys) Console.Write(kv + ",");
      Console.WriteLine();
    }
  }
}


うー、一番乗りできなかった。

というわけで若干一般化して、1からnまでのカードの場合の
解を求めてみました。総当たりなので効率は悪いでしょう。

1から13までの場合は、(1,4)が唯一の解のようですね。
*Main> solve 13
[(1,4)]

カードを増やしてゆくと解が複数出るようになりますが、
解の個数が必ずしも単調増加にならないようで
おもしろいです。

*Main> map (length . solve) [5..50]
[0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4]


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
solve n = answer where
  numbers = [1..n]
  picks = [ (a,b) | a <- numbers, b <- numbers, a<=b ]
  multiplesTo x = [ (a,b) | (a,b) <- picks, a*b == x]
  sumsTo x      = [ (a,b) | (a,b) <- picks, a+b == x]

  a1 = [m | m <- [1..13*13], length(multiplesTo m) > 1]
  b1 = [s | s <- [1..13+13], length(sumsTo s) > 1, check s]
    where check s = all (\ (a,b) -> elem (a*b) a1) $ sumsTo s

  a2 = [m | m <- a1, length (possible m) == 1]
    where possible m = filter (\ (a,b) -> elem (a+b) b1) $ multiplesTo m
  b2 = [s | s <- b1, length (possible s) == 1]
    where possible s = filter (\ (a,b) -> elem (a*b) a2) $ sumsTo s

  answer = [(a,b) | (a,b) <- picks, elem (a+b) b2, elem (a*b) a2]

とりあえず構造化もされていませんが…… 
 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
import java.util.HashMap;

public class Sample {
    private static final boolean[] prime = {
        /* 0    1     2     3     4      5     6      7     8      9      10 */
        false, true, true, true, false, true, false, true, false, false, false,
        true, false, true};
        /*11   12     13 */

    public static void main(String[] args) {
        boolean[] primeSum = new boolean[27];
        HashMap<Integer, Integer> productCount = 
            new HashMap<Integer, Integer>();
        int[] sumCount = new int[27];

        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (prime[i] && prime[j]) {
                    primeSum[i + j] = true;
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (!(prime[i] && prime[j]) && !primeSum[i + j]) {
                    int count = 0;
                    if (productCount.containsKey(i * j)) {
                        count = productCount.get(i * j);
                    }
                    productCount.put(i * j, count + 1);
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (!(prime[i] && prime[j]) && !primeSum[i + j] && 
                    productCount.get(i * j) == 1) {
                        sumCount[i + j]++;
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if ((!(prime[i] && prime[j]) && !primeSum[i + j] &&
                     productCount.get(i * j) == 1 && sumCount[i + j] == 1)) {
                    System.out.printf("%d, %d (product = %d, sum = %d)%n", 
                                      i, j, i * j, i + j);
                }
            }
        }
    }
}

冒頭部分が完全に間違っていました。訂正箇所が多すぎるので全体を投稿しなおします。 
 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
import java.util.HashMap;

public class Sample {
    public static void main(String[] args) {
        boolean[] sumFlag = new boolean[27];
        HashMap<Integer, Integer> productCount0 =
            new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> productCount = 
            new HashMap<Integer, Integer>();
        int[] sumCount = new int[27];

        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                int count = 0;
                if (productCount0.containsKey(i * j)) {
                    count = productCount0.get(i * j);
                }
                productCount0.put(i * j, count + 1);
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (productCount0.get(i * j) == 1) {
                    sumFlag[i + j] = true;
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (productCount0.get(i * j) > 1 && !sumFlag[i + j]) {
                    int count = 0;
                    if (productCount.containsKey(i * j)) {
                        count = productCount.get(i * j);
                    }
                    productCount.put(i * j, count + 1);
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (productCount0.get(i * j) > 1 && !sumFlag[i + j] && 
                    productCount.get(i * j) == 1) {
                        sumCount[i + j]++;
                }
            }
        }
        for (int i = 1; i <= 13; i++) {
            for (int j = i; j <= 13; j++) {
                if (productCount0.get(i * j) > 1 && !sumFlag[i + j] && 
                    productCount.get(i * j) == 1 && sumCount[i + j] == 1) {
                    System.out.printf("%d, %d (product = %d, sum = %d)%n", 
                                      i, j, i * j, i + j);
                }
            }
        }
    }
}

うう、13がまだハードコードされてた… 訂正ついでに少し整理。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
solve n = answer where
  picks = [ (a,b) | a <- [1..n], b <- [1..n], a<=b ]

  plural (_:_:_) = True
  plural _       = False
  singular [_]   = True
  singular _     = False

  multiplesTo x = [ (a,b) | (a,b) <- picks, a*b == x]
  sumsTo x      = [ (a,b) | (a,b) <- picks, a+b == x]

  multipleIn ms (a,b) = elem (a*b) ms
  sumIn ss (a,b)      = elem (a+b) ss

  a1 = [m | m <- [1..n*n], plural $ multiplesTo m ]
  b1 = [s | s <- [1..n+n], plural $ sumsTo s, all (multipleIn a1) $ sumsTo s]

  a2 = [m | m <- a1, singular $ filter (sumIn b1) $ multiplesTo m]
  b2 = [s | s <- b1, singular $ filter (multipleIn a2) $ sumsTo s ]

  answer = [(a,b) | (a,b) <- picks, sumIn b2 (a,b), multipleIn a2 (a,b)]

結構しんどかったです・・・ 
 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