あいつの日誌β

人生はお酒があれば何とかなります。 drunkard.tokyo

Youtube で MIT OpenCourseWare でやっている Programming for the Puzzled が面白い(2)

Puzzle 3: You Can Read Minds (with a little calibration) も面白かったのでなんとなくブログにします。

www.youtube.com

クイズ

教授が助手に命じて生徒たちに52枚のトランプカードからランダムに5枚引いてもらう。助手はそのうち4枚を順番に教授に見せて、残り1枚がどのカードなのかを推測し、それを当てて見せた。

教授曰く、これはアルゴリズムを使っている。どんな方法を使えば良いだろうか?

隠すカードを選ぶ

選ばれた5枚のうち、4枚を並べて表示する。この方法によって助手は教授に最後に隠されたカードに関する情報を伝えています。

単純に4枚数のカードを並び替えると 4! = 4 * 3 * 2 * 1 = 24 通り の情報を付与できますが、52枚のカードから4枚引くと、残りのカードは48通りです。この差分を埋めるためにどんな工夫ができるのでしょうか?

最初のポイントは最初に並べるカードと隠すカードを選ぶことです。5枚のカードを選んだ時点で必ず同じ絵柄のカードが選ばれます。最初に並べるカードと隠すカードの絵柄を揃える事で隠されたカードの絵柄を特定する事ができます。

この時点で残り12通りに特定できます。(1から13までの数字のうち、いずれかの数字は最初に並べるカードで使用されている)

ただし、残り3枚のカードを使って情報を付与できるのは 3! = 3 * 2 * 1 = 6通り です。

最初のカードと隠すカードの数字の差を考える

例えば以下のような配置ではどうでしょう。この場合は絵柄のペアが diamond だけなので必然的に最初に並べるカードと隠すカードは 3_diamond, 5_diamond のみとなります。

3_diamond, 1_heart, 6_spade, 4_club, 5_diamond

そういえば 3 と 5 の差は2です。このように差が1から6の場合は残りの3枚の並び方に意味を持たせるとマジックは成立しそうです。では以下の場合はどうでしょう。

1_diamond, 1_heart, 6_spade, 4_club, 12_diamond

ところで最初のカードと隠すカードの数字の差は普通に考えれば1 から 12 なので 11 です。

しかし、考え方を変えると、12 から 1 まで差はいくつでしょう?13を超えた場合は1に戻ると考えれば12と1の差は 2 です

もし、最初に並べるカードと隠すカードが2と7の場合は最初に並べるカードは2です。もし2と9の組み合わせの場合は9です。

残り3枚に意味をもたせる

ここまでくればあとは簡単です。数字の大きさによって残り3枚数を並べてみましょう。例えば Small, Medium, Large を以下のように並べると良いでしょう。

S M L => 1
S L M => 2
M S L => 3
M L S => 4
L S M => 5
L M S => 6

同じ絵柄の場合はポーカーのように スペード、ハート、ダイヤ、クラブ の順番にすればよいでしょう。

実装

少し雑ですがこのような感じになりました。

const _ = require('lodash');

function _num(card) {
  return parseInt(card.split('_')[0], 10);
}

function _suit(card) {
  return card.split('_')[1];
}

const suitOrders = ["Spade", "Heart", "Diamond", "Club"].reverse();

function _order(a, b) {
  if (_num(a) === _num(b)) {
    const aIndex = suitOrders.indexOf(_suit(a));
    const bIndex = suitOrders.indexOf(_suit(b));
    return aIndex - bIndex;
  }
  return _num(a) - _num(b);
}

function getCards() {
  return _.flatten(
    _.times(13).map(n => ["Spade", "Heart", "Diamond", "Club"].map(suit => `${n+1}_${suit}`))
  )
}

function getSameSuitCards(cards) {
  const suitOf = {
    "Spade": null,
    "Heart": null,
    "Diamond": null,
    "Club": null,
  };

  let pair;
  for (let i = 0; i < cards.length; i++) {
    const card = cards[i];
    const suit = _suit(card);
    if (suitOf[suit]) {
      return [suitOf[suit], card];
    }
    suitOf[suit] = card;
  };

  throw new Error("omg");
}

function selectShouldHiddenCard(cards) {
  // 先頭のカードが大きい
  if (_num(cards[0]) > _num(cards[1])) {
    return _num(cards[0]) - _num(cards[1]) > 6 ? cards[1] : cards[0];
  }
  return _num(cards[1]) - _num(cards[0]) > 6 ? cards[0] : cards[1];
}

function getDiffNumber(firstCard, hiddenCard) {
  if (_num(hiddenCard) > _num(firstCard)) {
    return _num(hiddenCard) - _num(firstCard);
  }
  return 13 - _num(firstCard) + _num(hiddenCard);
}

function reordereThreeCards(threeCards, diff) {
  const indexes = {
    1: [0, 1, 2],  // S, M, L
    2: [0, 2, 1],  // S, L, M
    3: [1, 0, 2],  // M, S, L
    4: [1, 2, 0],  // M, L, S
    5: [2, 0, 1],  // L, S, M
    6: [2, 1, 0]   // L, M, S
  }[diff]

  return indexes.map(i => threeCards[i]);
}

function main() {
  const cards = getCards();

  const fiveCards = _.sampleSize(cards, 5);
  console.log({fiveCards});

  const sameSuitCards = getSameSuitCards(fiveCards);
  console.log({sameSuitCards});

  const hiddenCard = selectShouldHiddenCard(sameSuitCards);
  console.log({hiddenCard});

  const firstCard = _.without(sameSuitCards, hiddenCard)[0];
  console.log({firstCard});

  const restThreeCards = _.without(fiveCards, firstCard, hiddenCard);
  console.log({restThreeCards});

  const orderedThreeCards = restThreeCards.sort(_order);
  console.log({orderedThreeCards});

  const diff = getDiffNumber(firstCard, hiddenCard);
  console.log({diff});

  const reorderedThreeCards = reordereThreeCards(restThreeCards, diff);
  console.log(reorderedThreeCards);
}

main();

実行結果

{ fiveCards: [ '7_Diamond', '13_Club', '6_Club', '3_Club', '12_Diamond' ] }
{ sameSuitCards: [ '13_Club', '6_Club' ] }
{ hiddenCard: '6_Club' }
{ firstCard: '13_Club' }
{ restThreeCards: [ '7_Diamond', '3_Club', '12_Diamond' ] }
{ orderedThreeCards: [ '3_Club', '7_Diamond', '12_Diamond' ] }
{ diff: 6 }
{ reorderedThreeCards: [ '12_Diamond', '7_Diamond', '3_Club' ] }

上記の結果ですと最初のカードが13のクラブなので最後に隠されたカードもクラブです。そのあとに続くカードは L, M, S の順番なので 13 との差は6です。13 の次は 1 なので、最後に隠されたカードはクラブの6です。

まとめ

最近 MIT OpenCourseWare の Programming for the Puzzled を気に入っていて良く見ています。無料でこういう動画が見れるなんて本当にいい時代になったものです。というわけで他にも面白い動画がないか探索しようと思います。