パスワードを忘れた? アカウント作成
この議論は、tuneo (2938)によって ログインユーザだけとして作成されたが、今となっては 新たにコメントを付けることはできません。

超久しぶりにあれげメモ:3桁のHit & Blowを俺の代わりに解くプログラム」記事へのコメント

  • はじめに、基本戦略として、
    相手に提示する記号列(チャレンジ記号列)は、現在の解候補記号列の集合から選択する。ヒントが得られる毎に、解候補記号列の集合から、ヒントと矛盾する記号列を除外する事で、正解に至る事を目指す。

    チャレンジ記号列と正解記号列を照合すると、3桁各々について、{Hit, Blow, Miss} の3種類の状態があり得る。
    例えば、チャレンジ記号列 cha を照合した各桁の結果が [Hit, Miss, Blow] だとして、これを満たす解候補記号列 may の条件は、定義通りにベタ書きすれば、
    (cha[0] == may[0]) && (cha[1] != may[0] && cha[1] !=

    • 上述の解候補の絞り込み処理を、JavaScriptで実装した。


      var Hit = 0;
      var Blow = 1;
      var Miss = 2;

      var pred = [[[], [], []], [[], [], []], [[], [], []]];
      pred[Hit][Hit][Hit] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[1] && cha[2] == may[2]; };
      pred[Hit][Hit][Blow] = function(cha, may) { return null; };
      pred[Hit][Hit][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[1] && cha[2] != may[2]; };
      pred[Hit][Blow][Hit] = function(cha, may) { return null; };
      pred[Hit][Blow][Blow] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[2] && cha[2] == may[1]; };
      pred[Hit][Blow][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[2] && cha[2] != may[1]; };
      pred[Hit][Miss][Hit] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[1] && cha[2] == may[2]; };
      pred[Hit][Miss][Blow] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[2] && cha[2] == may[1]; };
      pred[Hit][Miss][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[1] && cha[1] != may[2] && cha[2] != may[1] && cha[2] != may[2]; };
      pred[Blow][Hit][Hit] = function(cha, may) { return null; };
      pred[Blow][Hit][Blow] = function(cha, may) { return cha[0] == may[2] && cha[1] == may[1] && cha[2] == may[0]; };
      pred[Blow][Hit][Miss] = function(cha, may) { return cha[0] == may[2] && cha[1] == may[1] && cha[2] != may[0]; };
      pred[Blow][Blow][Hit] = function(cha, may) { return cha[0] == may[1] && cha[1] == may[0] && cha[2] == may[2]; };
      pred[Blow][Blow][Blow] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && (cha[1] == may[0] || cha[1] == may[2]) && (cha[2] == may[0] || cha[2] == may[1]); };
      pred[Blow][Blow][Miss] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && (cha[1] == may[0] || cha[1] == may[2]) && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
      pred[Blow][Miss][Hit] = function(cha, may) { return cha[0] == may[1] && cha[1] != may[0] && cha[2] == may[2]; };
      pred[Blow][Miss][Blow] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && (cha[2] == may[0] || cha[2] == may[1]); };
      pred[Blow][Miss][Miss] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
      pred[Miss][Hit][Hit] = function(cha, may) { return cha[0] != may[0] && cha[1] == may[1] && cha[2] == may[2]; };
      pred[Miss][Hit][Blow] = function(cha, may) { return cha[0] != may[2] && cha[1] == may[1] && cha[2] == may[0]; };
      pred[Miss][Hit][Miss] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[2] && cha[1] == may[1] && cha[2] != may[0] && cha[2] != may[2]; };
      pred[Miss][Blow][Hit] = function(cha, may) { return cha[0] != may[1] && cha[1] == may[0] && cha[2] == may[2]; };
      pred[Miss][Blow][Blow] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && (cha[1] == may[0] || cha[1] == may[2]) && (cha[2] == may[0] || cha[2] == may[1]); };
      pred[Miss][Blow][Miss] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && (cha[1] == may[0] || cha[1] == may[2]) && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
      pred[Miss][Miss][Hit] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[1] != may[0] && cha[1] != may[1] && cha[2] == may[2]; };
      pred[Miss][Miss][Blow] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && (cha[2] == may[0] || cha[2] == may[1]); };
      pred[Miss][Miss][Miss] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };

      var states = [[], [], [], []];
      states[0][0] = [[Miss, Miss, Miss]];
      states[0][1] = [[Blow, Miss, Miss], [Miss, Blow, Miss], [Miss, Miss, Blow]];
      states[0][2] = [[Blow, Blow, Miss], [Blow, Miss, Blow], [Miss, Blow, Blow]];
      states[0][3] = [[Blow, Blow, Blow]];
      states[1][0] = [[Hit, Miss, Miss], [Miss, Hit, Miss], [Miss, Miss, Hit]];
      states[1][1] = [[Hit, Blow, Miss], [Hit, Miss, Blow], [Blow, Hit, Miss], [Blow, Miss, Hit], [Miss, Hit, Blow], [Miss, Blow, Hit]];
      states[1][2] = [[Hit, Blow, Blow], [Blow, Hit, Blow], [Blow, Blow, Hit]];
      states[2][0] = [[Hit, Hit, Miss], [Hit, Miss, Hit], [Miss, Hit, Hit]];
      states[2][1] = [[Hit, Hit, Blow], [Hit, Blow, Hit], [Blow, Hit, Hit]];
      states[3][0] = [[Hit, Hit, Hit]];

      /**
        * チャレンジ記号列とヒントに基づいて解候補記号列の絞り込みを行う。
        * @param {Array.>Array<} cand 現在の解候補記号列の配列
        * @param {Array} cha チャレンジ記号列
        * @param {number} hits ヒントのHit個数
        * @param {number} blows ヒントのBlow個数
        * @return {Array.>Array<} 絞り込まれた解候補記号列の配列
        */
      function refinement(cand, cha, hits, blows) {
              var result = [];
              cand.forEach(function (may) {
                        var valid = false;
                        states[hits][blows].forEach(function (state) {
                                valid = valid || pred[state[0]][state[1]][state[2]](cha, may);
                        });
                        if (valid) {
                                result.push(may);
                        }
              });
              return result;
      }

      親コメント

Stay hungry, Stay foolish. -- Steven Paul Jobs

処理中...