javascript - 如何提出正确的递归解决方案

Question

这是场景，我在面试中被问到以下问题，我设法解决了一部分，但我在问题的第二部分遇到了一些麻烦(我什至不知道我是否解决了第一部分是正确的，我只是想出了在这种情况下我最能编写的代码)。那么让我来介绍一下问题:

考虑以下在一串破折号和加号上玩的 2 人游戏。如果在您的回合开始时，该字符串不包含一对相邻的破折号，您就赢了!否则，选择字符串中任意一对相邻的破折号“--”并将其替换为“++”。我们轮流直到有人赢了。示例游戏:-+-----+ --> -+-++--+ --> -++-+++++ (游戏结束)。

编写一个函数 listMoves()，它将位置字符串作为参数并返回所有有效移动的列表。示例:

listMoves("") == []
listMoves("--+---+") == ["+++---+", "--+++-+", "--+-+++"] 

我对此的解决方案(在 JavaScript 中)是:

var listMoves = function(arg) { 
    if (arg === null) return;

    if (arg === "") {
        return [];
    }

    var result = [];
    var temp = '';
    var string = [];
    for (var i=0; i<arg.length; i++) {
        if (temp == '-' && arg[i] == '-') {
            string = arg.split(''); 
            string[i-1] = '+';
            string[i] = '+';
            console.log(string);
            result.push(string);
        } else if (arg[i] == '-') {
            temp = arg[i];
        } else if (arg[i] == '+' && temp == '-') {
            temp = '';
        }
     }

     return result;
}

问题的第二部分是:

在最佳游戏中，每个位置对于玩家来说要么是赢要么是输。编写一个函数 isWin(position) ，当位置是玩家移动的胜利时返回 true。示例:

isWin("") == true
isWin("---+") == false
isWin("----") == true
isWin("--+----+--+---++--") == ???

我设法理解我需要一个递归算法来解决这个问题，并且我可以使用我为问题 #1 创建的函数(因此我将它包括在内)。

但是，我无法将自己的想法转化为代码。

为了将来引用，有人可以告诉我他们将如何解决这样的问题吗？

edit#1(在采访中添加了我的尝试):

var isWin = function (position) {

    if (position === null) return;
    if (position === "") return true;

    var possibleMoves = listMoves(position); 

    var win;

    if (possibleMoves.length < 1) {
        win = true;
    } else if (possibleMoves.length == 1) {
        win = false;
    } else {
        for (move in possibleMoves) {
            isWin(move);
        } 
    }

    return win;
}

Answer 1

通过对结果递归调用 listMoves，您可以获得所有可能结果的树。

例如------:

所有终端节点都是游戏可能的结束状态。然而，我们正试图从任何起始位置找出，当玩家发挥最佳状态时，该状态是否为获胜状态。

这可以通过检查是否存在导致其他玩家被迫选择导致起始玩家获得获胜条件状态的移动的一系列移动来确定:

所以对于我们之前的例子，起始玩家有 5 个选择:

1. 选择 1 会给下一个玩家 3 个选择:

   • 其中一个选择会导致先手玩家在轮到他们时获胜。
   • 其他 2 个选择导致起始玩家获得另一个回合。在那个回合中，起始玩家只有导致他们失败的选择。与下一位玩家一样聪明，他会选择其中一个选项。

2. 选择 2 会给下一个玩家 2 个选择。当再次轮到他们时，下一位玩家的两个选择都会导致先手玩家获胜。

3. 选择 3 会给下一位玩家 2 个选择。下一个玩家的两个选择都会导致起始玩家轮到一个选择。这种单一选择会导致下一位玩家在轮到他们时获胜。

4. 与选项 2 相同。

5. 与选项 1 相同。

因为选项 2 和 4 存在，所以起始状态是起始玩家获胜。

---

minimax 是一个递归函数，它使用该逻辑来确定起始位置对于起始玩家来说是赢还是输。

对于我们的问题，我们可以将起始玩家 player1 标记为 True。另一位玩家 player2 为 False。

如果 minimax 为某个状态 s 调用，并且该状态没有可能的移动。然后 minimax 将返回调用它的玩家。

当 s 和 player1 调用 minimax 时，player == True，其中有可能的移动，如果有 任何 导致 minimax(move, player2) 的移动返回 player1，它就会返回。 (如果有任何 player1 结果，玩家将选择那个结果)。

当 s 和 player2 调用 minimax 时，player == False，其中有可能的移动，如果 minimax(move, player1) 的 all 结果返回 player1，则返回。 (如果没有返回 player2 的结果，player2 必须选择导致 player1 的移动，否则 player2 将选择导致 player2 获胜的移动)。

---

Javascript:

function listMoves(s) {
  var moves = [];
  for (var i = 0; i < s.length - 1; i++) {
    if (s.substring(i, i + 2) === '--') {
      moves.push(s.substring(0, i) + '++' + s.substring(i + 2));
    }
  }
  return moves;
}

function minimax(s, player) {
  var moves = listMoves(s);
  if (moves.length === 0) {
    return player;
  }
  if (player) {
    return moves.some(function(move) {
      return minimax(move, !player)
    });
  } else {
    return moves.every(function(move) {
      return minimax(move, !player);
    });
  }
}

function isWin(s) {
  return minimax(s, true);
}

document.write("<pre>" + isWin("--+----+--+---++--"), '"--+----+--+---++--"' + "</pre>");

// From http://stackoverflow.com/a/12628791/635411
function cartesianProductOf() {
  return _.reduce(arguments, function(a, b) {
    return _.flatten(_.map(a, function(x) {
      return _.map(b, function(y) {
        return x.concat([y]);
      });
    }), true);
  }, [[]]);
};

var res = {}
for (var i = 1; i <= 6; i++) {
  var s = Array.apply(null, new Array(i)).map(String.prototype.valueOf, "-+");
  res[i] = {};
  cartesianProductOf.apply(null, s).forEach(function(state) {
    res[i][state] = isWin(state);
  });
}

document.write("<pre>" + JSON.stringify(res, null, 4) + "</pre>");

<script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/3.8.0/lodash.min.js"></script>

---

python :

def list_moves(s):
    moves = []
    for i in range(len(s) - 1):
        if s[i] == "-" and s[i + 1] == "-":
            moves.append(s[:i] + "++" + s[i + 2:])
    return moves

def minimax(s, player=True):
    moves = list_moves(s)
    if not moves:
        return player
    n = (minimax(move, not player) for move in moves)
    return any(n) if player else all(n)

def is_win(s):
    return minimax(s)

print is_win(""), '""'
print
print is_win("-"), '"-"'
print is_win("+"), '"+"'
print
print is_win("--"), '"--"'
print is_win("+-"), '"+-"'
print is_win("-+"), '"-+"'
print is_win("++"), '"++"'
print
print is_win("----"), '"----"'
print is_win("+---"), '"+---"'
print is_win("-+--"), '"-+--"'
print is_win("--+-"), '"--+-"'
print is_win("---+"), '"---+"'
print is_win("++--"), '"++--"'
print is_win("-++-"), '"-++-"'
print is_win("--++"), '"--++"'
print is_win("-+-+"), '"-+-+"'
print is_win("+-+-"), '"+-+-"'
print is_win("+--+"), '"+--+"'
print is_win("+++-"), '"+++-"'
print is_win("-+++"), '"-+++"'
print is_win("++++"), '"++++"'
print
print is_win("-----"), '"-----"'
print is_win("------"), '"------"'
print is_win("-------"), '"-------"'
print
print is_win("--+----+--+---++--"), '"--+----+--+---++--"'

<pre>
True ""

True "-"
True "+"

False "--"
True "+-"
True "-+"
True "++"

True "----"
False "+---"
False "-+--"
False "--+-"
False "---+"
False "++--"
True "-++-"
False "--++"
True "-+-+"
True "+-+-"
False "+--+"
True "+++-"
True "-+++"
True "++++"

True "-----"
True "------"
False "-------"

True "--+----+--+---++--"
</pre>