Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. 
Many preexisting Javascript libraries shared a notion of public and private priperties. Jigsaw makes these implicit visibility properties explicit. These libraries also used a root object for their purpose. The jigsaw runtime was instrumented to find such root objects and make them principal objects and expose the properties as public. The public properties of all other library objects were marked next by modifying the runtime.If the library used any surrogate objects that crossed the boc boundary, the runtime logged the public and private properties of the backing object.  Also the runtime was modified to throw an exception and not returned an undefined for private accessors. With logging and failstop behaviour, all preexisting libraries could be ported to Jigsaw because now all the properties that needed to be marked public could be found.
#code jam exercise
Yesterday we were discussing code jam solution to costly binary search. Here's how the solution looks like:

Int getCost (List <int> a)
{
Int N = a.Count ();
var dpL = new int [190, 1000010];
Var dpR = new int [190, 1000010];
For (int i=0; I < 190; i++)
For (int j=0; j < N+1; j++)
{
dpL[i][j] = j;
dpR[i][j] = j;
}

 
 for(int cost=1;cost<190;cost++){
    For ( int i = 0; I < N; i++)

if(a[i] <= cost){
   int L = dpL[cost-a[i]][i];
   int R = dpR[cost-a[i]][i+1];
   dpL[cost][R] = min(dpL[cost][R], L);
   dpR[cost][L] = max(dpR[cost][L], R);
  }
  for(i=1;i<=N;i++) dpR[cost][i] = max(dpR[cost][i], dpR[cost][i-1]);
  for(i=N-1;i>=0;i--) dpL[cost][i] = min(dpL[cost][i], dpL[cost][i+1]);
 }
 
 for(i=0;i <190;i++) if(dpR[i][0] == N) return i;
 Return 190;
}

Courtesy:rng..58

We discuss another code jam problem today. 

This one is about a maze represented as a graph with N vertices  and M edges where  guards run from an entrance to a destination vertex. They take a unit time to cross each edge. We have to delay their pursuit. We can mark upto k vertex as obstructed  each of which costs one more additional unit of time. How long will the guards take ?

Solution: the graph is traversed breadth wise. This let's us keep track of distance and parent. The distance is -1 for unconnected and incremented otherwise.

First we traverse the graph ourselves to find the k vertices to obstruct. We traverse fir each of the k times we obstruct. Then the guards traverse it to find the total time taken. We know the k to begin with and decrement it one by one as we mark the vertices as obstructed. The destination vertex is the nth vertex and if it is reachable then the time taken is the computed distance so far plus the entrance and destination obstruction. For each of the k-2 vertices in between the entrance and destination in each iteration, we obstruct the destination vertex and successive parents all the way to the entrance to compute the time taken.

 

the choice of breadth first search over depth first search is appropriate here because the guards will take unit time to cover each edge.