Pots of Gold - Interview Question

Thursday, December 16, 2010 by gradbot

Given n pots of gold arranged in a line containing different quantities of coins. You are allowed to remove one pot of gold from either end and then another player gets to remove one. This is repeated until no pots remain. Write an algorithm to find the set of moves for collecting the most coins in a two player game. Assume your opponent also takes optimal moves.

var max_gold = function(pots) {
  var length = pots.length;
  if (length <= 1) {
    if (length == 1) {
      return {first: [pots[0]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots.slice(1));
  var right = max_gold(pots.slice(0, -1));
  
  var left_pot = pots[0]; 
  var right_pot = pots[length - 1];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
};

// sample input 
[11, 19, 18, 16, 1, 4, 7, 3, 6, 2]
// sample output
{first: [11, 18, 2, 3, 4], second: [19, 16, 6, 7, 1]}

This can be easily optimized from O(2^n) into O(n^2) by moving to array indexes and memoization. Note: I'm ignoring the cost of sum, slice and concat for BigO. If you only wanted the total then you could just keep track of it instead of an array and save a bunch of memory.

var max_gold = memoize(function(pots, start, stop) {
  if (start >= stop) {
    if (start == stop) {
      return {first: [pots[start]], second: []};
    } else {
      return {first: [], second: []};
    }
  }
  
  var left = max_gold(pots, start + 1, stop);
  var right = max_gold(pots, start, stop - 1);
  
  var left_pot = pots[start]; 
  var right_pot = pots[stop];
  
  var left_total = left_pot + sum(left.second);
  var right_total = right_pot + sum(right.second);

  if (left_total >= right_total) {
    return {
      first: [left_pot].concat(left.second), 
      second: left.first
    };
  } else {
    return {
      first: [right_pot].concat(right.second),
      second: right.first
    };
  }
});

var memoize = function(f) {
  var store = {};
  return function(pass_through, x, y) {
    var value;
    if (x in store) {
      if (y in store[x]) {
        value = store[x][y]; 
      } else {
        value = f(pass_through, x, y);
        store[x][y] = value;
      }
    } else {
      value = f(pass_through, x, y);
      store[x] = {};
      store[x][y] = value;
    }
    return value;
  }
};

You can remove the memoization with dynamic programming for extra speed at the cost of some readability.

var max_gold_dynamic = function(pots) {
  var length = pots.length;
  var gold_array = [];
  for (var start = length - 1; start >= 0; start--) {
    gold_array[start] = [];
    for (var stop = start; stop < length; stop++) {
      if (start >= stop) {
        if (start == stop) {
          gold_array[start][stop] = {first: [pots[start]], second: []};
          continue;
        } else {
          gold_array[start][stop] = {first: [], second: []};
          continue;
        }
      }
      
      var left = gold_array[start + 1][stop];
      var right = gold_array[start][stop - 1];
    
      var left_pot = pots[start]; 
      var right_pot = pots[stop];
      
      var left_total = left_pot + sum(left.second);
      var right_total = right_pot + sum(right.second);
    
      if (left_total >= right_total) {
        gold_array[start][stop] = {
          first: [left_pot].concat(left.second), 
          second: left.first
        };
      } else {
        gold_array[start][stop] = {
          first: [right_pot].concat(right.second),
          second: right.first
        };
      }
    }
  }
  return gold_array[0][length - 1];
};

0 comments: