// return:
//   if impossible, null
//   if possible, array of indexes to used in *an* optimal solution
function minPopulation(electors, populations, goal)
{
  var total = sum(electors);
  var count = electors.length;
  
  // This function uses a dynamic programming algorithm based on the one in Garey and Johnson for Subset Sum.

  // cell[upto][tsum].population: 
  //   minimum population needed to get exactly tsum electors using a subset of only electors[0..upto].
  //   (Ininity if impossible -- this is clever and eliminates lots of ifs.)
  // cell[upto][tsum].usedThis:
  //   true if the minimum population can only be achieved by using state upto.
  var cell = [];
  
  // Fill in the first row of the table.  (More of a base case than Garey and Johnson's.)
  cell[-1] = [];
  cell[-1][0] = { population: 0 };

  // Fill in the body of the table.  (The interesting part of the dynamic programming algorithm.)
  for (var upto = 0; upto < count; ++upto) {
    cell[upto] = [];
    for (var tsum = 0; tsum <= total; ++tsum) {
      var notUsingThis = getCellPopulation(cell, upto - 1, tsum);
      var usingThis = getCellPopulation(cell, upto - 1, tsum - electors[upto]) + populations[upto];

      cell[upto][tsum] = { 
        usedThis: usingThis < notUsingThis, // hint for extracting a solution from the table, not used until end
        population: Math.min(usingThis, notUsingThis) 
      };
    }
  }
  
  // Find the winning number of electors that can be won with the smallest population.
  // Look at cell[count-1][goal..count] 
  var lastRow = cell[count-1];
  var bestPopulation = Infinity; // Smallest population that lets me win
  var bestElectoral; // The exact number of total electoral votes I get with that population
  for (var i = goal; i <= total; ++i)
    if (lastRow[i].population < bestPopulation) {
      bestPopulation = lastRow[i].population;
      bestElectoral = i;
    }
  
  if (bestPopulation == Infinity)
    return null;

  // Calculate indicesUsed so we can return it.
  var tsum = bestElectoral;
  var indicesUsed = [];
  for (var upto = count - 1; upto >= 0; --upto) {
    t = cell[upto][tsum];

    if (t.usedThis) {
      indicesUsed.push(upto);
      tsum -= electors[upto];
    }
  }
  return indicesUsed;
}

function getCellPopulation(a, i, j)
{
  if (a[i] && a[i][j])
    return a[i][j].population;
  else // out of range of the table
    return Infinity; 
}

// sum: returns the sum of an array
function sum(a) {
  var s = 0;
  for (var i = 0; i < a.length; ++i)
    s += a[i];
  return s;
}








// tests minPopulation using subset sum problems (where populations == electors and our goal is exact)
function testSubsetSum(numbers, goal, shouldBeSolution)
{
  var indicesUsed = minPopulation(numbers, numbers, goal);
  
  if (!indicesUsed) {
    if (shouldBeSolution) {
      print("Expected a solution [1]");
      print("numbers: " + numbers);
      print("Goal: " + goal);
    }
    return;
  }
  
  var s = 0;
  for (var i = 0; i < indicesUsed.length; ++i)
    s += numbers[indicesUsed[i]];
  
  if ((s == goal) != shouldBeSolution) {
    if (shouldBeSolution)
      print("Expected a solution [2]");
    else
      print("Expected no solution [2]");

    print("numbers: " + numbers);
    print("Goal: " + goal);
    print("Solution: " + indicesUsed);
  }  
}

testSubsetSum([1,2,4,8,16,32], 0,  true);  // []
testSubsetSum([1,2,4,8,16,32], 32, true);  // [5]
testSubsetSum([1,2,4,8,16,32], 1,  true);  // [0]
testSubsetSum([1,2,4,8,16,32], 13, true);  // [3,2,0]
testSubsetSum([1,2,4,8,16,32], 63, true);
testSubsetSum([1,5],           2,  false);
testSubsetSum([1,2,4,  16,32], 13, false);
testSubsetSum([1,1,1,1],       3,  true);
testSubsetSum([1,1,1,1],       5,  false);



// I didn't write any direct tests for minPopulation.



// Data from http://www.census.gov/population/cen2000/tab01.txt 
// Except for DC's populuation, which is from tab05.txt
var apportionment = [
["Alabama",4461130,7,9],
["Alaska",628933,1,3],
["Arizona",5140683,8,10],
["Arkansas",2679733,4,6],
["California",33930798,53,55],
["Colorado",4311882,7,9],
["Connecticut",3409535,5,7],
["Delaware",785068,1,3],
["DC",  572059,1,3],           // sketchy population
["Florida",16028890,25,27],
["Georgia",8206975,13,15],
["Hawaii",1216642,2,4],
["Idaho",1297274,2,4],
["Illinois",12439042,19,21],
["Indiana",6090782,9,11],
["Iowa",2931923,5,7],
["Kansas",2693824,4,6],
["Kentucky",4049431,6,8],
["Louisiana",4480271,7,9],
["Maine",1277731,2,4],       // not winner-takes-all
["Maryland",5307886,8,10],
["Massachusetts",6355568,10,12],
["Michigan",9955829,15,17],
["Minnesota",4925670,8,10],
["Mississippi",2852927,4,6],
["Missouri",5606260,9,11],
["Montana",905316,1,3],
["Nebraska",1715369,3,5],    // not winner-takes-all
["Nevada",2002032,3,5],
["New Hampshire",1238415,2,4],
["New Jersey",8424354,13,15],
["New Mexico",1823821,3,5],
["New York",19004973,29,31],
["North Carolina",8067673,13,15],
["North Dakota",643756,1,3],
["Ohio",11374540,18,20],
["Oklahoma",3458819,5,7],
["Oregon",3428543,5,7],
["Pennsylvania",12300670,19,21],
["Rhode Island",1049662,2,4],
["South Carolina",4025061,6,8],
["South Dakota",756874,1,3],
["Tennessee",5700037,9,11],
["Texas",20903994,32,34],
["Utah",2236714,3,5],
["Vermont",609890,1,3],
["Virginia",7100702,11,13],
["Washington",5908684,9,11],
["West Virginia",1813077,3,5],
["Wisconsin",5371210,8,10],
["Wyoming",495304,1,3]
];

function rotateTable(a)
{
  var b = []
  for (var j = 0; j < a[0].length; ++j) {
    b[j] = []
    for (var i = 0; i < a.length; ++i)
      b[j][i] = a[i][j]
  }
  
  return b;  
}

var apportionment2 = rotateTable(apportionment);

var numStates = apportionment2[0].length;
var stateNames = apportionment2[0];
var statePopulations = apportionment2[1];
var stateElectors = apportionment2[3];
var needToWin = 270;

var indices = minPopulation(stateElectors, statePopulations, needToWin);
var electoralVotesWon = 0;
var populationWon = 0;

for (var i = 0; i < indices.length; ++i) {
  var stateIndex = indices[i];
  electoralVotesWon += stateElectors[stateIndex];
  populationWon += statePopulations[stateIndex] / 2; // hehe
  print(stateNames[stateIndex]);
}

print("Electoral votes won: " + electoralVotesWon);
print("Popular votes won: " + populationWon);

var totalPopulation = 0;

for (var i = 0; i < numStates; ++i) {
  totalPopulation += statePopulations[i];
}

print("Total population: " + totalPopulation);
print("Percent of popular vote won: " + populationWon / totalPopulation);