Algorithms Case Study: Dynamic Programming in JavaScript

Several days ago, a civil engineer friend of mine asked me if he could pick my brains.  He'd run into a bit of a problem analyzing a bridge design, and wanted to see if I had any thoughts on how to attack the problem.  So we sat down over Jimmy Johns and he explained his problem to me, and my first impression was that is sounded like a textbook dynamic programming problem.  I told him I would have a look at it, which I finally did today.

The Problem

My friend was calculating the forces acting on the bridge pier.  In order to do that, he has to calculate the forces acting on all the girders, which depends on where hypothetical trucks are traveling over the bridge deck.

This is a three column pier.

The above photo (from Ohio DOT) is a single pier with four girders, whereas this design is two piers with five girders each.  The total bridge width, from curb to curb (i.e. the "traveled way") is 85 feet.

Girders aren't to scale, but you get the gist

A hypothetical truck is 10 feet wide, and truck positions start at 1 (the far left curb) and increase in 1 foot intervals to position 76 (when a truck would be adjacent to the far right curb).  Multiple trucks are seperated by a two foot margin.

As long as they are seperated by at least two feet, any combination of trucks on the bridge must be considered.  So it may be two or three trucks with large margins, or they may be packed across the whole bridge deck.

The forces for a single truck at each position are calculated by special engineering software.  How those numbers are calculated really isn't important for my part of the story.  What is interesting, however, is that to calculate the forces across all the girders for any combination of trucks, you need only sum the forces for those truck positions.  Cool ey?

This is the basic data set (rows 14-73 hidden)

So just how many possible combinations are there?  Well figuring out the two truck combos was easy enough.  1 with 13-76, 2 with 14-76, etc.  So a total of 64*76/2 or 2432.  For three it gets bigger quick.  1_13 can combine with every legal combination for position 13, so 25 through 76, another 52 positions.  1_14 with 51 other positions, 1_15 with 50... and as another colleague of mine said recently "It's turtles all the way down".  While it isn't infinite, it is certainly well beyond what one would want to attempt by hand.

Optimal Subproblem

While I initially had something of an intuition about the structure of the problem and how to approach it, I struggled at first.  The problem struck me as very similar to Fibonnaci.  My first failed attempt started with a couple loops.  Failing there I tried a recursive approach, but found myself passing around alot of state and other information that seemed counterproductive.  Finally I took a breathe and stepped back from the problem.  I reviewed a tutorial about using dynammic programming to solve Fibonnaci.  I asked myself, "What is my subproblem?"

Generally, the bottom of a dynammic programming problem is where you get to the trivial cases that you can just return a value.  What where my simple cases here?  "Well", I thought, "that is at right side, where you can only fit one truck."  Ok, so positions 65-76 only allow for one truck.  What about as I continue left?  "Well, 64 can combine with 76, and 63 can combine with everything greater than 75..."  Ok, bear with me, we're almost to the lightbulb moment.  What about when I get to position 52? "Well, that one combines with all the posibilities at 64, including the combination with 76 (i.e. combination 64_76).  Wait... all I have to do is work backwards and just combine with everything that is legal at every position > current position + 12.  Once I figured that out I was golden.

The algorithm works like this:

• In a For loop, iterate backward over all the positions starting from the end
• Along with the force values, store an encoded "name" signifying which positions were combined as well as a "depth" indication how many positions were combined
• Store this positions single truck values in D[n], where n is the position number
• Combine n with all the legal positions starting at n + 12
• Store all these combinations in D[n]

This is the function running the DP.  The rest can be found in this gist.

function runCombine(state){

  var end = state.max;
  var D = [];
  
  for(var i = end; i >= 1; i--){
    var baseRow = state.data[i - 1].slice();
    baseRow.unshift(i.toString());
    baseRow.unshift(1); //this is the lane count, or "depth"
    D[i] = [];
    D[i].push(baseRow);
    
    for(var j = i + 12; j <= end; j++){
      for(var x = 0; x < D[j].length; x++){
        var row = D[j][x];
        var name = baseRow[1] + "_" + row[1];
        var depth = baseRow[0] + 1;
        var newRow = [depth, name];
        for(var k = 2; k < row.length; k++)
          newRow.push(row[k] + baseRow[k]);
        D[i].push(newRow);
      }
    } 
    console.log(i + ": " + D[i].length);
  }
  
  D.forEach(function (group) {
    group.forEach(function (combo){
      var name = combo[1];
      var mpCombo = [name];
      for(var m = 2; m < combo.length; m++)
        mpCombo.push(combo[m] * mpFactor(combo[0]));     
      state.combos.push(mpCombo);
    });
  });
}

I threw in a bit of console logging while I was developing the next bit, and found that there were actually a bit over 343,000 combinations possible.  Whooee!

Now... about that data...

But now I had another problem.  343k rows x 11 cells per row ("name" plus the ten girder forces) and I was way over the 2M cell limit in Google Sheets.  So I had a bit of a problem.  I figured I could probably just encode it as a csv file and save it to Google drive.  No problem right?  Yeah... good luck trying to join 340,000 array elements into one string.  I'm not sure why it died in this particular fashion, but every time I tried to join the full result set, AppScript complained that my 50M element array was larger than the implementation specifications or something.

After fumbling around with it for a bit, I finally tried just slice()ing the array into 50k row chunks and writting those to seperate files, which I was able to get working:

function saveCSV(combos){
  console.log("Started csv generation");
  
  var folder = DriveApp.getRootFolder();
  var content = "";
  
  var h = combos.map(function (a) { return a.join(",") + "\n";}); 
  
  for(var i = 0; i < h.length; i += 50000){
    var rows = h.slice(i, i + 50000);
    content = rows.join("");
    folder.createFile("results("+ i +").csv", content);   
  }
}

Several minutes in, I saw these results pop up in my drive folder:

I opened the first file up and was annoyed to see that Excel decided that 1-13 and 1-13-25 were dates, so I switched the dashes to underscores and ran it again.  Second time around was molto bene!