サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

master mind by c++; part7 code generator

c++ mastermind

今日やること

ピンの色数, ピンの数, ピンの色の重複ありなしが与えられた時に 考えられるコード(ピンの配列)を全列挙する関数を作成する. これがあれば, どのようなピンの設定にも対応することができます.

コード集合の列挙

例

コード集合の例をいくつかのパターンで列挙してみましょう. 色を0から始まる数字で表現しています.

  • ピン色 = 2, ピン数 = 2, ピンの色の重複なし
[0, 1], [1, 0] の2つ
  • ピン色 = 2, ピン数 = 2, ピンの色の重複あり
[0, 0], [0, 1], [1, 0], [1, 1] の4つ
  • ピン色 = 3, ピン数 = 2, ピンの色の重複なし
[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1] の６つ
  • ピン色 = 3, ピン数 = 2, ピンの色の重複あり
[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2] の9つ

実装

上記の観察により

ピンの色の重複ありの場合は直積型の列挙になりますね. これはpython組み込み関数のproductをそのまま使えます. リンク先に(擬似)コードが載っているので助かります.

ピンの色の重複なしの場合は部分順列の列挙ですね. これもpython組み込み関数のpermutationsで実装できます.

c++にはこれらの列挙に関するスタンダードライブラリがなかったので 列挙関数を管理するiterator.hを自作し, それを用いてコード集合を生成する関数を作成します.

/**
* @fn CodeList allCodeGenerator(Config &config, CodeList &codeList)
* @brief 全てのコード配列を列挙する.
* @param[in] config パラメタ
* @param[out] codeList コード配列
*/
void allCodeGenerator(
      Config &config,
      CodeList &codeList
      )
{
   assert( codeList.size() == 0 );
   if( config.duplicate )  // 重複あり
   {
      Itertools itertools;
      auto colors = itertools.range(0, config.nColors);  // 色情報の順列
      itertools.product(colors, config.nPins, codeList);
   }
   else  // 重複なし
   {
      Itertools itertools;
      auto colors = itertools.range(0, config.nColors);  // 色情報の順列
      itertools.permutations(colors, config.nPins, codeList);
   }
}

itertools.h はこちら.

テストの作成

このような, 小さくて間違えやすそうな関数については単体テストがぴったりですね.

/**
 *
 * ItertoolsTest
 *
 */
/**
 * range
 */
TEST ( ItertoolsTest, rangeTest1 )
{
   Itertools itertools;
   std::vector v{0, 1, 2, 3, 4};
   ASSERT_EQ( itertools.range(0, 5), v );
}
TEST ( ItertoolsTest, rangeTest2 )
{
   Itertools itertools;
   std::vector v{-1, 0, 1, 2, 3, 4};
   ASSERT_EQ( itertools.range(-1, 5), v );
}
/**
 * permutations
 */
TEST ( ItertoolsTest, permutationsTest1 )
{
   Itertools itertools;
   std::vector<int> pool{0,1,2};
   int r = 2;
   CodeList codeList;
   itertools.permutations(pool, r, codeList);

   CodeList ans{
      Code{0,1}, Code{0,2}, Code{1,0},
      Code{1,2}, Code{2,0}, Code{2,1},
   };
   ASSERT_EQ( codeList, ans );
}
TEST ( ItertoolsTest, permutationsTest2 )
{
   Itertools itertools;
   std::vector<int> pool{0,1,2};
   int r = 1;
   CodeList codeList;
   itertools.permutations(pool, r, codeList);

   CodeList ans{
      Code{0}, Code{1}, Code{2},
   };
   ASSERT_EQ( codeList, ans );
}
/**
 * product
 */
TEST ( ItertoolsTest, product1 )
{
   Itertools itertools;
   std::vector<int> pool{0,1,2};
   int r = 2;
   CodeList codeList;
   itertools.product(pool, r, codeList);

   CodeList ans{
      Code{0,0}, Code{0,1}, Code{0,2},
      Code{1,0}, Code{1,1}, Code{1,2},
      Code{2,0}, Code{2,1}, Code{2,2},
   };
   ASSERT_EQ( codeList, ans );
}
TEST ( ItertoolsTest, product2 )
{
   Itertools itertools;
   std::vector<int> pool{0,1,2};
   int r = 1;
   CodeList codeList;
   itertools.product(pool, r, codeList);

   CodeList ans{
      Code{0}, Code{1}, Code{2},
   };
   ASSERT_EQ( codeList, ans );
}

まとめ

  • ピンの色数, ピンの数, ピンの色の重複ありなしが与えられた時に 考えられるコード(ピンの配列)を全列挙する関数を作成し, それをもとに全体のプログラムを微調整しました.
  • 上記関数の単体テストを追加しました.
  • mainプログラムで最低限の実行できるようになっています.

コード

参考

itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.9.4 ドキュメント

他の記事