How to come up with the proper recursive solution

Question

Here is the scenario, I was asked the following question at an interview and I managed to solve part of it, but I had some trouble with the second part of the question (and I don't even know if I solved the first part correctly, I just came up with what I could code best under the circumstances). So let me introduce the problem:

Consider the following 2-player game played on a string of dashes and plusses. If, at the beginning of your turn, the string doesn't contain a pair of adjacent dashes, you win! Otherwise, choose any pair of adjacent dashes “--” in the string and replace it with “++”. We take turns until someone wins. Example game: -+-----+ --> -+-++--+ --> -+-+++++ (game is over).

Write a function listMoves() which takes a position string as an argument and returns a list of all the valid moves. Examples:

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

My solution to this (in JavaScript) was:

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;
}

The second part of the question was:

In best play, each position is either a win or a loss for the player to move. Write a function isWin(position) that returns true just when the position is a win for the player to move. Examples:

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

I managed to fathom that I needed a recursive algorithm for this, and that I could use the function I created for question #1 (hence why I included it).

I couldn't, however, put my thoughts into code.

For future reference, could someone show me how they would go about solving a problem like this?

edit#1 (added my attempt during the interview):

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

By recursively calling listMoves on the results, you can obtain a tree of all possible outcomes.

For example ------:

All terminal nodes are possible end states for the game. However we are trying to figure out from any starting position, when players play optimally, if that state is a winning state.

This can be determined by checking if there exists a chain of moves that results in the other playing being forced to choose a move that leads to the starting player to be given a win condition state:

So for our previous example, starting player has 5 choices:

1. Choice 1 would give the next player 3 choices:

   • One of those choices results in the starting player winning when it becomes their turn.
   • The other 2 choices results in the starting player getting another turn. In that turn the starting player only has choices that leads to them losing. Being as smart as the next player is, he will choose one of those options.

2. Choice 2 would give the next player 2 choices. Both of the next player's choices would result in the starting player winning when it becomes their turn again.

3. Choice 3 would give the next player 2 choices. Both of the next player's choices result in the starting player getting their turn with a single choice. That single choice results in the next player would winning when they get their turn back.

4. Same as choice 2.

5. Same as choice 1.

Because choice 2 and 4 exist, the starting state is a win for the starting player.

---

minimax is a recursive function that uses that logic to find if the starting position is a win or loss for the starting player.

For our problem we can label the starting player, player1, as True. The other player, player2, as False.

If minimax is called for some state, s, and that state has no possible moves. Then minimax will return the player it was called with.

When minimax is called for s and player1, player == True, where there are possible moves, it returns if there are any moves that result in minimax(move, player2) that return player1. (If there are any player1 results, the player would choose that result).

When minimax is called for s and player2, player == False, where there are possible moves, it returns if all results of minimax(move, player1) returns player1. (If there no results that return player2, player2 must choose a move that results in player1, otherwise player2 would choose a move that results player2 winning).

---

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>