javascript - How to come up with the proper recursive solution -

here scenario, asked following question @ interview , managed solve part of it, had trouble second part of question (and don't know if solved first part correctly, came code best under circumstances). let me introduce problem:

consider following 2-player game played on string of dashes , plusses. if, @ beginning of turn, string doesn't contain pair of adjacent dashes, win! otherwise, choose pair of adjacent dashes “--” in string , replace “++”. take turns until wins. example game: -+-----+ --> -+-++--+ --> -+-+++++ (game over).

write function listmoves() takes position string argument , returns list of valid moves. examples:

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

my solution (in javascript) was:

var listmoves = function(arg) {      if (arg === null) return;      if (arg === "") {         return [];     }      var result = [];     var temp = '';     var string = [];     (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 question was:

in best play, each position either win or loss player move. write function iswin(position) returns true when position win player move. examples:

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

i managed fathom needed recursive algorithm this, , use function created question #1 (hence why included it).

i couldn't, however, put thoughts code.

for future reference, show me how go solving problem this?

edit#1 (added attempt during 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 {         (move in possiblemoves) {             iswin(move);         }      }      return win; } 

by recursively calling listmoves on results, can obtain tree of possible outcomes.

for example ------:

all terminal nodes possible end states game. trying figure out starting position, when players play optimally, if state winning state.

this can determined checking if there exists chain of moves results in other playing being forced choose move leads starting player given win condition state:

so our previous example, starting player has 5 choices:

1. choice 1 give next player 3 choices:

   • one of choices results in starting player winning when becomes turn.
   • the other 2 choices results in starting player getting turn. in turn starting player has choices leads them losing. being smart next player is, choose 1 of options.

2. choice 2 give next player 2 choices. both of next player's choices result in starting player winning when becomes turn again.

3. choice 3 give next player 2 choices. both of next player's choices result in starting player getting turn single choice. single choice results in next player winning when turn back.

4. same choice 2.

5. same choice 1.

because choice 2 , 4 exist, starting state win starting player.

---

minimax recursive function uses logic find if starting position win or loss starting player.

for our problem can label starting player, player1, true. other player, player2, false.

if minimax called state, s, , state has no possible moves. minimax return player called with.

when minimax called s , player1, player == true, there possible moves, returns if there any moves result in minimax(move, player2) return player1. (if there player1 results, player choose result).

when minimax called s , player2, player == false, there possible moves, returns if all results of minimax(move, player1) returns player1. (if there no results return player2, player2 must choose move results in player1, otherwise player2 choose move results player2 winning).

---

javascript:

function listmoves(s) {    var moves = [];    (var = 0; < s.length - 1; i++) {      if (s.substring(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>");    // 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 = {}  (var = 1; <= 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 = []      in range(len(s) - 1):          if s[i] == "-" , 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) 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>