グラフを使ってクリスマスゲームを作る

紹介

子供の頃、クリスマスの時期にシークレット・サンタというゲームがやりました。子供たちだけでなく、友人や家族、職場の大人たちにも人気のゲームです。
基本的なルールは、プレゼントを開けるまで、誰からのプレゼントなのかを明かさずに、グループ全員にプレゼントを渡すことです。

遊び方

1. ゲームしたい人は皆、紙に名前を書く。その紙切れはすべて箱に入れられる。
2. 一人ずつ順番に箱から名前を引いていく。
3. 誰の名前を選んだかは誰にも言わない
4. ウリスマス日、みんなが集まる。一人ずつ、自分が選んだ人に秘密のプレゼントを渡す。

プレゼントを受け取った後、贈り主の身元を明かしてもよいが、秘密にしておいても構わないです。

ゲームを作ろう

プログラムするのは簡単なはずなので、何かアルゴリズムを考えて書いてみよう。

簡単なアルゴリズムの作成

1. 参加者リストを定義する
2. 贈り手と受け手に空の配列を作成する
3. ループを使用して、参加者リストの各人を調べます。
4. 一人一人に：
   • 贈り主に印をつける
   • ランダムに別の人を「受け取る」として選ぶ
   • 贈り手と受け手をペアリング・リストに登録する
5. 一人ずつプロセスを繰り返す。
6. ループが終了すると、ペアリング配列には参加者のペアがあり、各ペアは誰が誰にプレゼントを贈るかを示す。

コーディング

const participants = ["アリス", "ボブ", "キャロル", "デーブ"]; // 参加者の配列
const pairings = []; // 送り手と受け手のペア

// ランダムにペアをマッチする
for (let i = 0; i < participants.length; i++) {
  const giver = participants[i];
  const randomIndex = Math.floor(Math.random() * participants.length);
  const receiver = participants[randomIndex];

  pairings.push({ giver, receiver });
}

// 結果を表示
pairings.forEach((pairing) => {
  console.log(` ${pairing.receiver} にプレゼントを贈る ${pairing.giver}`);
});

プログラムにはいくつかの問題があることは理解している

プログラムを実行すると、すぐにいくつかの問題があるみたいです。

> node secret_santa.js
 アリス にプレゼントを贈る アリス
 アリス にプレゼントを贈る ボブ
 デーブ にプレゼントを贈る キャロル
 デーブ にプレゼントを贈る デーブ

• 自分へのプレゼントかもしれない。
• 誰もがプレゼントをもらえるわけではない
• 複数のプレゼントをもらう人もいる

問題を解決するひとつの方法は

1 - 参加者配列のクローンを作成し、ユーザーが選択された後にその配列からユーザーを削除する。参加者が何度も選択されるのを避けるためです。

const availableReceivers = [...participants];
let receiver = availableReceivers[randomIndex];

availableReceivers.splice(randomIndex, 1);

2 - 贈る側と受け取る側が同じでないことを確認する

  while (receiver === giver) {
    const newIndex = Math.floor(Math.random() * availableReceivers.length);
    receiver = availableReceivers[newIndex];
  }

実行の結果

node santa.js
 ボブ にプレゼントを贈る アリス
 キャロル にプレゼントを贈る ボブ
 デーブ にプレゼントを贈る キャロル
 アリス にプレゼントを贈る デーブ

その方がはるかに良さそう結果です。すべての条件は満たされているが、最適解ではないです。

人数が多くなり、新しいルールが導入されれば、複雑になります。例えば、プレゼントを交換したくない人もいるかもしれない。

グラフ理論で解決

この種の問題は通常、グラフを使って解かれます。

グラフの簡単な説明

グラフは、エッジ（辺）で接続されたノード（頂点）のコレクションで構成されるデータ構造です。

• ノード（頂点）： オブジェクト、エンティティ、またはポイントを表します。シークレット・サンタ・ゲームでは、各参加者がノードとなります。

• エッジ (辺)： ノード間の接続または関係を表します。シークレットサンタの有向グラフでは、エッジは誰が誰にプレゼントを贈るかを示します。これらの辺には方向があり、プレゼントの流れを示します。

グラフには複数の種類がありますが、現在の例で有向グラフが最も適しているようです。
グラフ例は結構シンプルです。誰もが自分には贈らず相手に贈る

各人には3つの選択肢があります。順番は関係ないです。誰にでも与えることができるし、受け取ることもできます。

ゲームにルールを追加

残念ながら、現実の世界はそれほど単純ではない。
アリスとデーヴがカップルで、お互いにプレゼントを贈り合っているのでもう一回渡したくないが、ゲームには参加したいと仮定しよう。
アリスとデイブの間のリンクを削除します：

可能な解決策の1つを表示解決

前の例を使うことは可能だが、最適ではないです。
アリスとデーヴがプレゼントを交換しなければならない場合、失敗する可能性があります。この場合、このようなことが起こらない解決策を見つけるまでプログラムを再実行することができるが、より良い方法を見つけよう。

例では、Hamiltonian Pathと呼ばれるものを使う必要があります。このグラフは有向グラフであり、各ノードはちょうど一度だけ訪れます。

可能性のあるすべてのノードを結ぶために5つのステップを使って視覚化してみよう:

手動でパスの見つけ方は簡単です。他のパスもあります：

• 同じ道だが、反対
• 対角線を結ばない端の周辺

プログラムを作ってみよう

この問題を解決するために、バックトラック・アルゴリズムを使用する：

1. 最初の参加者から始めます
2. ルールに従って、プレゼントを贈る参加者を選ぶ。
3. もし問題（ルール違反）にぶつかったら、最初の参加者に戻って別の参加者を試す。
4. ルールを破ることなく、全員にプレゼントを贈ったり受け取ったりしてもらう方法を見つけるまで、すべての参加者にこの手順を繰り返す。

javascriptのプログラム例

プログラムを作成し、読みやすくするためにコメントで内容を説明します。

// グラフのクラスを定義
class Graph {
  constructor(vertices) {
    this.vertices = vertices; // 頂点の数
    this.adjacencyMatrix = Array.from({ length: vertices }, () => Array(vertices).fill(0)); // 隣接行列の初期化
  }

  /* すべてのエッジが追加された後、最終的にマトリックスはこのようになります
  [ [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
  [ [ 0, 1, 1, 0 ], [ 1, 0, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
  [ [ 0, 1, 1, 1 ], [ 1, 0, 0, 0 ], [ 1, 0, 0, 0 ], [ 1, 0, 0, 0 ] ]
  [ [ 0, 1, 1, 1 ], [ 1, 0, 1, 0 ], [ 1, 1, 0, 0 ], [ 1, 0, 0, 0 ] ]
  [ [ 0, 1, 1, 1 ], [ 1, 0, 1, 0 ], [ 1, 1, 0, 1 ], [ 1, 0, 1, 0 ] ]
  */

  // 辺を追加するメソッド
  addEdge(from, to) {
    this.adjacencyMatrix[from][to] = 1; // 辺を追加
    this.adjacencyMatrix[to][from] = 1; // 逆向きの辺も追加
  }

  // パスが追加できるかどうかを判定するメソッド
  isSafe(v, path, pos) {
    // 頂点がパスに追加できるかを確認
    if (this.adjacencyMatrix[path[pos - 1]][v] === 0) return false;

    // 頂点が既にパスに含まれているかを確認
    if (path.includes(v)) return false;

    // アリスとデーブが直接つながっていないかを確認するルール
    if (path[pos - 1] === "アリス" && v === "デーブ") return false;
    if (path[pos - 1] === "デーブ" && v === "アリス") return false;

    return true;
  }

  // ハミルトンパスを探す再帰関数
  hamiltonianPathUtil(path, pos) {
    if (pos === this.vertices) return true;

    for (let v = 1; v < this.vertices; v++) {
      if (this.isSafe(v, path, pos)) { // ルールチェック
        path[pos] = v;

        if (this.hamiltonianPathUtil(path, pos + 1)) return true;

        path[pos] = -1; // バックトラック
      }
    }

    return false;
  }

  // ハミルトンパスを探して表示するメソッド
  findHamiltonianPath() {
    const path = new Array(this.vertices).fill(-1); // パスの初期化

    // 最初の頂点からスタート
    path[0] = 0;

    // パスが存在するかチェック
    if (!this.hamiltonianPathUtil(path, 1)) {
      console.log("ハミルトンパスは存在しません。");
      return;
    }

    // パスが存在する場合、結果を表示
    console.log("ハミルトンパスが存在します: ");
    for (let i = 0; i < this.vertices; i++) {
      console.log(participants[path[i]]);
    }
  }
}

// 全参加者を無作為化するメソッド
const shuffleArray = (array) => {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

// 参加者の名前を配列で定義
const participants = shuffleArray(["アリス", "ボブ", "キャロル", "デーブ"]);
const numberOfParticipants = participants.length; // 参加者の数

// グラフのインスタンスを作成
const g = new Graph(numberOfParticipants);

// 接続を表す辺を追加
/* 以前の画像を覚えてますか？　このようになります
アリス    ---   ボブ
  |        /      |
キャロル  ---   デーブ
*/
for (let i = 0; i < participants.length; i++) {
  for (let j = i + 1; j < participants.length; j++) {
    const giver = participants[i];
    const receiver = participants[j];
    // アリスとデーブが直接つながっていないルールを適用
    if (!((giver === "アリス" && receiver === "デーブ") || (giver === "デーブ" && receiver === "アリス"))) {
      g.addEdge(i, j); // 問題なければエッジを追加
    }
  }
}

//　すべてのノードを一度通過する
g.findHamiltonianPath();

結語

グラフを実際の世界でどのように使うかの楽しい例です。
最初のプログラムは、ごく基本的なケースには十分だったと言うように、現実の問題にはもっと複雑な解決策が必要です。
最初のプログラムは拡張性がなく、ルールを追加することも難しい。問題を考え抜き、最適解を見つけることは、より複雑な問題を解決するための入り口なのです。
今では、参加者やルールをより簡単に追加できるシークレット・サンタ・ゲームがあります。

---

長さのようなプロパティをエッジに追加した場合、それは巡回セールスマンの問題になります。これは非常に有名な問題であり、多くの応用例があります。ノードの数が多くなると、解くのが非常に難しくなります。
サンタが同じアルゴリズム使用で世界中の都市を訪問できると思いますか？