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. We were discussing the  end to end performance study of Jigsaw. 

Today we continue to discuss related work. We saw the differences between Jigsaw and Dojo, Fbjs and Caja. We now look into Secure ECMA script. This provides Caja like isolation without the rewriting and runtime virtualization. It pushes security checks into the Javascript engine. This can reduce costs significantly and Jigsaw can use some of thsee checks from the upcoming versions of SES.

We now look at pass by value systems. PostMash uses iframes as isolation containers and performs cross domain communication with asynchronous pass by value calls. These become quite expensive when each container clones the object graph. The degradation was to the tune of 60% for a Google maps mashup.  The expense comes from marshaling as well as asynchronous calls that increase traffic. Moreover  such calls are not really suited for modules that require a lot of computations such as those involving databases, cryptographic methods, input scrubbing, and image manipulation. 

Iframes are better at isolation than Jigsaws box boundaries because a parent can make progress when a child is busy. In Jigsaw, several boxes can exist in the same iframe. If one box misbehaves, it can cause denial of service to others. But this is not a major concern because browsers terminate unresponsive scripts with user consent 

ObjectViews enable full policy code to be written in Javascript

 This is very expressive but the same benefit can be achieved with simpler declarations such as  public private keywords.

#codingexercise

Given an array of prices of a stock in a day on each day and with unlimited sequential transactions, find the max profit.

int GetMaxProfit(List<int> prices)

{

int max = 0;

int sum = 0;

for (int i = 1; i < prices.Count(); i++)

{

int diff = prices[i] - prices[i-1];

if (diff > 0)

    sum+=diff;

}

return sum;

}

If there were two simultaneous transactions that can be performed  then we can use dynamic programming to combine the max profit from each.

TotalMaxProfit = max(MaxProfit(0,i) + MaxProfit(i+1, n))  for 0<=i<n

The maxprofit example shown above can also target  a single transaction only.

On this case,  instead of cumulative positive differences, we keep track of the min price and take the difference between the current price and the minimum price. We return the maximum of such differences as the answer 

int MaxProfit(List <int> prices)

{

int min=INT_MAX; 
int max =0; 
int diff=0; 
for(int i =0; i< prices.Count(); i++) 
{ 
if(prices[i]<min) min = prices[i]; 
diff = prices[i] - min; 
if(max<diff) 
max = diff;
} 
 return max; 
 }

We discuss a Google code jam problem

 A large storage facility has  2⁴⁰ storage locations arranged in a circle.

A truck with a crane on it moves along the circle of storage locations, picking up or putting down crates according to a program. (The truck has an unlimited supply of crates on board, so it can always put more crates down.)

The program consists of a sequence of these instructions:

• b : move back one location
• f : move forward one location
• u : pick up one crate at the current location
• d : put down one crate at the current location
• ( : do nothing
• ) : if there is more than one crate at the current location, move back to the most recent ( in the sequence of instructions, and continue the program from there. (This doesn't move the truck.)

( and ) instructions in the program will always come in pairs: a ( will be followed later by a matching ). There will be at most two such pairs in the program, and if there are two pairs, they will not be nested – that is, there will be either:

• no ( or ) instructions;
• one ( instruction somewhere in the program, followed later by one ) instruction;
• a ( instruction, followed later by a ) instruction, followed later by another (, and again later by another ).
• There are always between 1 and 256 crates at any location.

How many movements will the truck make before reaching the end of the program.

For example :

Input :
ufffdddbbbdd has three forward and three backward movements.
ddd (fdbu)fff had two movements repeated one for instruction in the enclosed sequence and followed by three forward motions totalling 11
dddd (fdddddbu)f (fddddddu) has sixteen motions due to the pattern of the enclosed sequence with the motions from the second sequence repeated twice due to the single forward instruction just prior to the sequence leading to a total of 3×16+1=48

Int getMotions (string sequence)
{
Int  total = 0;
Int I = 0;
While( I < sequence.Count)
{
I++;
If (sequence[i] == 'f'  || sequence  [i] == 'b') {total++; }
If (sequence[i] == '(')
{
 Int count = 0;
 Int sum = 0;
 For ( int j = i+1; j < sequence.Count && sequence [j] != ')'; j++)
 {
  count += 1;
  if (sequence[j] == 'f'  || sequence  [j] == 'b') sum++;  
  assert (sequence[j] == '('  || sequence  [j] == ')');
 }
 sum *= count;
 If ( i > 1 && ( sequence[i-1] == 'f'  || sequence  [i-1] == 'b'))
   sum *= 2;
 total += sum;
 i += count;
}

}

Return total;
}

Today we present a solution to a coding question:

Given an array S of n integers, find three integers in S
such that sum is closest to a given number, target. Return the sum of the three
integers. You may assume that each input would have exactly one solution.

Array S = {-1, 2, 1, -4 } and target = 1. The sum that is
closest to the target is 2. (-1 +2 + 1) = 2

Int getClosestSum(List<int> sorted, int target)

{

sorted.sort();

Int min = INT_MAX;

Int val = 0;

Int len = sorted.count;

For (int i=0; i<len; i++)

{

Int start = I + 1, end = len-1;

While (start<end)

{

Int sum = sorted[i] + sorted[start] + sorted[end];

If (sum == target)

{

min = 0;

val = sum;

break;

}

If (sum  < target)

{

If (target-sum< min)

{

min = target –sum;

val = sum;

}

start++;

}

Else

{

If (sum – target < min)

{

min = sum – target;

val = sum;

}

end--;

}

}

If (val == target) break;

While (i < len -1 && sorted[i] == sorted[i+1]) i++; 

}

Return val;

}

We could also use a different technique for arbitrary length selections such as number of integers chosen = 4, 5, 6,  ... N-1 etc.

Here we could generate all combinations of length = 4, 5, 6 ,... N-1 from the given set of integers.

They need not be sorted in this case.

Then for each combination we find the sum and pick the one that closes to the target.

The combine() method described earlier in the posts does just this - given an array of n elements, generate combinations of all lengths.

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. We were discussing the  end to end performance study of Jigsaw. 



Today we discuss related work. There are many preexisting frameworks that try to secure mashup applications. Jigsaw differs from those with a simple syntax. Moreover it provides hierarchical security and enables a pass by reference synchronous calls.Dojo Secure uses a restricted portion of the Javascript language and forces legacy applications to be rewritten. Jigsaw on the other hand doesn't. Fbjs also requires rewriting by prepending a prefix to all identifiers. Caja places scripts in virtualize execution environments and defines a tame (obj). A tame method performs many of the security checks that Jigsaw also does.





Jigsaw differs from Caja in the following ways:

Caja implements checks at sharing time not at declaration  time.

Developer must remember to call tame(obj)

Boundary crossings are not clearly discernible.

Caja is focused on making it easy for integrating page to load untrusted scripts. Jigsaw supports guest to guest access just as much.

Introduction:
Have you ever misplaced an item and couldn’t recollect where you kept it ? Did you ever have to close your eyes and recollect when and what happened to recall something.  Wouldn’t it be ideal if you had photographs at frequent intervals that told you everything you saw and you could scroll through forwards and backwards. Further lets assume that this capability had very little physical presence but something part of what you already wear. For example your eyeglasses could have a small detachable storage and a pinhole camera that could take frequent pictures.  The size of the pictures can be such that many of them can be taken and stored. In this case even thumbnails would do. Their storage can be detached and fed into a computer. Hence the use of a storage card on the glass and a USB adapter sold separately
How is it different from a google glass ?
First google glass is a computer attached to the eyeglass. Second  google glass appears external to the eyeglass and third it is lot more general purpose that what we propose. Our proposal is just a camera and memory. It sits flush with the glass rim and has no other external add-ons. Customers opt in to it just as they would with the tint or coating for their lenses.  The camera merely captures images at frequent intervals into a circular buffer. If the images are small, it can store say 86400 of them. These images are sufficient for a 24 by 7 timeframe.
Software:
Since the hardware is merely a camera with a detachable storage seamless with the eyeglass, it behaves the same as an external storage. This external storage can then be inserted into any personal computer for facilitating all kinds of operations on the images.
The circular ring buffer used for these images can be configured with a schedule. For example, the frequency can be changed from every second to every minute. Additionally certain hours of the day can be used to deactivate the camera. All of these configurations are mounted for reading by the camera using a predetermined file which is edited only with when the detachable storage is used with a personal computer.
The algorithm to store the images can be one of the following:
Round robin: The images are progressively stored in sequential order and wraps around. This can also be considered First In First Out
Clock is similar to FIFO but more efficient. When there are no empty frames, if the next frame has an R bit or referenced bit set then it is cleared otherwise it is replaced. The reference here comes from when a user taps the camera to pin the image
Least recently Used: These evicts the images based on those that are less frequently used in a specific time interval. A reset operation clears the time interval but not the images. The word 'used' here comes from a predetermined linear range of relevance and not the classical definition of actual usage by something other than the camera.
The difference is that the former doesn’t need to use timestamps where as the latter does.
Aesthetics:
There are some aesthetics involved here just as it would be on Apple devices. The camera and memory should not be conspicuous or interfere with the style and look of the glasses. Therefore they may appear only in full rimmed glasses and the storage can be mounted as a tip of the eyeframe.

#Google code jam exercise:

I have a sequence of N binary digits. I am looking for a substring with just the right proportion of 0s and 1s, but it may not exist, so I will settle for something that's just pretty good.

Can you find a substring where the fraction of 1s is as close as possible to the given fraction F? Output the earliest possible index at which such a substring starts.

Solution

We maintain a running total of 1s encountered so far at any index. When we pick two indexes on this running total such that the difference in the total divided by span of the indexes is closer to the fraction, we return the lower index as the answer :

Int getIndex ( int N, int F, List <int> map)

{

var y = new List <int> (N+2);

for (int i = 0; i < n; ++i) {
    y[i + 1] = y[i] + map[i];
}
double previous =0;
int index = 0;
for (int i = 0; i < n; ++i) {
 for (int j = i + 1; j <= n; ++j) {
double t = (y[j] - y[i]) / (j - i);

if (t > previous && t <= F) {
index = i;

previous = t;
}
}

return index;
}

In the code above we assume 0 to be the default because the question implies that there will be one found 

Also note that we can even have  a threshold of how accurate you want to be with regard to the fraction.

In this case, we would compare t-F to be less than a margin of error and we would make sure that the delta is less than zero. This way we are just under the fraction.

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. We were discussing the porting effort involved with Jigsaw and performance improvements. We now review end to end performance study of Jigsaw. Jigsaw performs checks on property accesses. It does bookkeeping of all objects be setting their box id and object id. It checks access to virtualized browser resources for compliance to security policies. All this might affect the end to end performance. Consequently three different libraries were ported over to Jigsaw and their performance evaluated. These libraries include  JSON-RPC a library that performs RPC over Ajax connections.  A local host server is chosen over a remote server to avoid network delays in performance evaluation. A DOM-SQL library that uses SQL as the storage for DOM was another library used. The AES encryption function I'm the standard crypto library was also used for the study. Mousemove is another simple benchmark library that registers handlers on mode moves. In each case, the library code was put in a box separate from that of the integrator. All cross box communication with the integrator took place through virtualized resources or via a principal object.
#codejam exercise  Campinatorics 
A park ranger has to distribute families to tents in a N×N grid subject to the following rules:
Families can be 1 or 2 or 3 members 
The number of 3 member families is X
Thereally are plenty of 1 or 2 member families as fillers 
A cell can be occupied by only one tent
The number of members in any row or column must be exactly 3
The number of tents in any row or column cannot exceed two.
Find how many arrangements are possible if two arrangements are different if any of their cells are different or if the members in the same cell are different.
Solution : we are looking at different arrangements of 0, 1, 2 or 3 in an N×N grid subject to the above combinations. Therefore one way to do this would be to combine those values for each N×N cell . After all the cells have been given a number, we can quickly reject or accept an arrangement by running the checks above. We return the count of all accepted arrangements.
If we list the cells row wise as a string then the ith element belongs to the i/N row and i%N column.
Void arrange (StringBuilder a, int start)
{
  If (start == N×N){ print a.toString (); return; }
  For ( int m = 0; m <= 3; m++)
  {

      a [start] = m;
      arrange (a, start +1);
      a [start] = '/0';
}
}

Bool isValid (string s, int N, int X) // representation for 
{
Int [,] matrix = s.toMatrix ();
Int threes = 0;
For ( int I = 0; I < N; i++)
{
Int sum = 0;
Int count = 0;
For (int j=0; j < N; j++)
{
If (matrix [i][j] != 0) count++;
If (count >2) return False;
If (matrix [i][j] == 3) threes++;
sum += matrix [i][j];
}
If (sum != 3) return False;
}
For ( int j = 0; j< N; j++)
{
Int sum = 0;
Int count = 0;
For (int i=0; i< N; i++)
{
If (matrix [i][j] != 0) count++;
If (count >2) return False;
If (matrix [i][j] == 3) threes++;
sum += matrix [i][j];
}
If (sum != 3) return False;
}
If (threes != X) return False;
Return True;
}

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. We were discussing the porting effort involved with Jigsaw and how the surrogate log and fail stop exceptions on private property access made it easy to identify legacy code properties that needed to be marked public. PortMash and Caja were other two software examples cited for comparison with jigsaw. Unlike PortMash, jigsaw does not have to change asynchronous calls and unlike Caja jigsaw does not have to do object sanitization on boundary crossing. Jigsaw automatically wraps objects with a proxy in such cases. Moreover jigsaw enables pass by reference for all objects and this significantly reduces the marshaling otherwise. When large object trees have to be passed across isolation barriers, jigsaw creates surrogates lazily on first access to a sharing object. Initially only the root of the object tree gets a surrogate by this example.
In pass by value the entire object tree is recreated  that said, the surrogates introduce getters and setters that have more overhead than property access. However, this is acceptable because of three reasons:
First, this cost is only paid on access to external objects and not paid otherwise.
Second, jigsaw's initial sharing cost is a constant with respect to the size of the graph  thus is orders of magnitude better than pass by value. It is in fact very common to have large object graphs.
Third, jigsaw allows mashups to communicate synchronously with pass by reference as opposed to the asynchronous required in large object graph pass by value that may have significant latencies.
#codejam
In yesterday's post, we were solving a code jam problem
This involved a graph with N vertices and M edges where guards traverse from a source to destination node and we can obstruct upto K vertices. Each edge takes a unit time to traverse and each obstruction takes an additional unit time to clear. What is the minimum time for the guards to reach destination. ?
We discussed the solution. Today we look at a few steps 
First the breadth first traversal:
 Void bfs ()
{
  // initialize a list q for nodes to be visited and add the source 
// initialize a list for distances and set the first to be zero and all else unreachable.
While we have nodes to visit in q:
       Pick a node x and for each edge associated with x
         If distance has not been set and node y is not blocked :
             Add y to q;
             Distance of y = distance of x +1;
             Parent of y = x;
              
}
Void getTime ()
{
  bfs ();
  Int time = distance of destination node d [n-1]
  K--;
  While (k)
   {
        bfs ();
        If  d [n-1]  > time or n-1 is unreachable
           return time+2;
        Int z = n-1; 
        While  (z){
              If (Z!= n-1)
                  Blocked [z] = true;
              Z = parent of z;
         }
        K--;
   }
   bfs ();
   If  d [n-1]  > time or n-1 is unreachable
           return time+2;
   Return time +1;
}

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.

 

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. We saw how Jigsaw improves the language and runtime for its purpose. It supports robust encapsulation technique using a Jigsaw to Javascript compiler and a client side library. The latter introduces box management interface and the rewriter adds an integer object id to every object created. This ensures that at most one proxy is created for every object. In addition, jigsaw includes the id of the creating box with each object so that it can determine if the surrogate object is executing within the same box. If so, it in wraps the object  and executes methods. Jigsaw adds a per object map of visibility Metadata by listing properties that are declared public and private and this map is immutable which secures the object from an untrusted box. Jigsaw also creates new boxes using the eval () statement  the boxes are created by the function that adds aliases to the global objects. This adds a security layer when out of box calls are made. This later enforces security policies and prevents virtual operations to be applied to their real counterparts.

#code jam exercise
We have to insert an element into a sorted array of N elements no tworries of which are duplicates ever. Typically we do binary search to find the position where we insert. In this modified problem, each comparison has a varying cost between 1 and 9 inclusive. What will be the total cost of this binary search in the worst case ?

 Here the cost of a comparison can vary. Therefore for each comparison there may be a better pick that achieves the same result of narrowing down the range. The final position of insertion is only one where the elements to the left are smaller and the elements to the right are bigger. This can be one of N+1 positions. The worst case is when we have exhausted all these positions to arrive at this one.
Consequently we create two sufficiently large matrices  where the rows cover the cumulative costs (arbitrarily large) and the columns span from 0 to N+1. These matrices keep track of the final position as columns against each possible cost as rows with the values initially ranging from 0 to N+1 aND iNC reading fRon left to right. We need two because one for left and another for right of the range we are considering. We update this matrix to reflect the monimum position for the given cost and  keep the values sorted before each update. Finally we read the row index of the right matrix as the answer where the first column equals N as the positions considered.

National databases – SQL or NoSQL a comparision
National databases have to integrate data from a variety of sources mostly regional in nature. What are some of the challenges and how are they overcome ? We take a look in this study. Further we will explore what could be an integrator for various upstream databases. We will also compare SQL and NoSQL solutions in this regard.
Integration:
Regional databases evolve different from the National database. They are the primary source of truth for their region. They need not have the same convention, syntax and semantics as the national one.
It’s also likely that they have overlapping information about the same entity as that entity moves from region to region. Consider name-address pair as an example. This varies for individuals as they go out of state. Fortunately such information has a schema and the data is often indexed.
Consequently, data with schema is extracted , transformed and loaded into central databases with or without code. As the data flows through this process, there is no straightforward way of knowing that origin or the final destination completely  therefore staging tables are used to consolidate, scrub and translate data.  Periodic  work flows are required to add data as and when differences arise. This is a fairly complicated process because changes in the data affect this process.
If we look at the interface to plug in data sources of various regions, they look like the standard query operators on the C# LINQ pattern. But essentially we just need an iterator that can get one record at a time with state information from one to the other. Sure some of the attributes may be different or unrecognizable or even missing but the they can be filled in a large sparse table where columns are mapped to the attributes. A connecting string including the credentials is required for each data source. This may not be the final destination table but it can be used to feed the final destination
On the other hand, NoSQL databases enable a homogenous document model across heterogeneous data. Here each regional database can have any kind of information. Since they are documents or key value pairs they are easily combined or collected together. Searches over these fairly large and possibly redundant data is made better with parallelization techniques such as map-reduce algorithm.
Considerations for NoSQL databases include :
Searrch by key, by cell or for values in column families.
Limiting search to key/column ranges
Retaining the last N historical values.
If it supports bit operations, set operations, list operations, hashes and sorted sets.
If it  has  scriptability
If it supports transactions and publisher subscriber messaging
If the dataset size can be predicted.
Etc

The operations on public databases are mostly read only. Therefore transaction semantics for create-update-delete operations and isolation levels are  not as important as retrieving some or all records. Consequently a nosql option and parallelization  techniques are favored.
#merlin qa
In the previous code exercise problem, we showed an approach based on permutations that we can exploit to cover all possible orderings of spells before taking the one that yields maximum materials. I called this the naive approach. An alternative would be to have a score for each spell and then order the spells by that score in a strictly increasing materials. The score can be based on the maximum material produced if any or zero or a combination of the materials produced. 

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. We saw how Jigsaw improves the language and runtime for its purpose
We also saw that jigsaw has robust encapsulation tecniques for cross principal sharing. The execution context for the children are determined with the resource permissions and this is strictly dropping. All data is accessible by reference which is a performance gain.
Jigsaw introduces restrictions on the Javascript language. For example surrogate objects don't expose their prototype. The prototype of global builtin objects cannot be tampered. But Jigsaw supports many Javascript features and even improves them such as function objects, object literals, and pass by reference for objects shared across domains.
The compiler parses the Jigsaw code using ANTLR toolchain. The library implements the runtime security checks.
#coding exercise

We discussed Merlin QA in the previous message:
We discussed how to generate permutations
We calculate the benefit this way
Int getBenefit (List <Spell> spells)
{
Int benefit = 0;
Foreach (var spell in spells)
{
benefit += (new list <int> ( 0, spell [0], spell[0]+ spell [1]).max (); // the first two materials may suffice for determining relative cost between spells otherwise we can cumulate all materials for each spell.
The order in which we iterate is sufficient to find the cumulative across this order of spells.
}
Return benefits;
}

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. We saw how Jigsaw improves the language and runtime for its purpose. Specifically we saw the public private access modifiers and visibility modifiers, that can be used for all variables and properties, cross box event listeners and scrubbing of private references, surrogate objects, predefined objects etc.
We saw that Jigsaw.getParentPrincipals () and getSameDomainPrincipals() allow a child to access it's parents resources and a parent to access it's children principal objects. Privileges are restricted down the hierarchy and this is strictly decreasing order. Privileges apply to network communication, visual fields and local storage such as DOM.
This we see that jigsaw has robust encapsulation tecniques for cross principal sharing. The execution context for the children are determined with the resource permissions and this is strictly dropping. All data is accessible by reference which is a performance gain.
#Google code jam - merlin QA
This is  a problem about a quality assurance engineer in Merlin Inc who has to test N spells. Each spell takes a certain amount of material and converts it to another. There are M materials in all.She has no materials to begin with but she can take as much as she wants from the Merlin inventory. She gets to keep all the materials left behind from her tests. Each Material has a certain value so she wants to profit most by picking an order of the N spells to test that yields most.
Solution:
The naiive solution would be to permute the N spells and for each permutation determine the value of byproducts left behind. The one with the max value is the solution  and the chosen order. Permutation of N spells is equivalent to the permit code below :

Permutations of  a string: 

Void Permute (String a, StringBuilder b, bool[] used) 

{ 

  If ( b.Length == a.Length)  { print b.ToString(); return;} 

  For (int I = 0; I < a.Length ; i++) 

  { 

    If (used[i]) continue; 

     used[i] = true; 

     B += A[i]; 

     Permute(a, b, used); 

     B [B.Length – 1] = ‘/0’; 

     used[i] = false; 

  } 

} 
As we list each order of the spells above, we find the value of the outcomes and pick the one with the maximum value.

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. We were reviewing boxes and the choice of encapsul]ation syntax for principal objects.
This syntax can also be used not just as access modifiers but also visibility modifiers. They can be applied on property and anywhere on variables.
Jigsaw checks whether the statement in which public or private appears has visibility settings for the relevant prototype object. If there's a public method on 'obj', the surrogate wraps the this and binds it to the obj preventing attacks where the 'this' pointer can be changed. Jigsaw also does lazy evaluation because the objects graph can be big with most objects lightly used.
Surrogates automatically protect cross box data exchanges.

Jigsaw also virtualizes the DOM tree in each box. It lives inside each box's Javascript namespace. This is also an example of a set of predefined Javascript objects that jigsaw manages. As we can see, jigsaw improves the language and usage for its purpose.

Crossbox events are also supported. If a box X wants to register an event handler in a different box Y, it passes the handler to Y via Y's public interface. Y can then register the handler with the browser's event engine in the standard way. The difference is that the event object may not contain Y's references so its scrubbed before its passed externally. This prevents information leakage via foreign event handlers. The handler executes in the Javascript context of the box that created it.

Access from child to parents namespace is facilitated with Jigsaw.getParentPrincipal() and the access to the principal objects of its own children is facilitated with Jigsaw.principals Jigsaw.getSameDomainPrincipals. Jigsaw associates each principal with a unique id, and parent can restrict a child's access to a subset of the principal ids.

Similarly networking privileges and visual fields can be further restricted or relinquished but this has to be progressive down the hierarchy. This means that privileges decrease strictly down the hierarchy.

#codingexercise
uint factorial(uint n)
{
 if (n == 1) return 1;
 return n * factorial(n-1);
}
#codingexercise
uint GetEven (int n)
{
 If (n%2 != 0) return n+1;
Return n;
}

Today we continue to discuss the paper on 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. We were reviewing how boxes were different from iframes. We saw the use of principal objects and DOM tree.the latter is constrained by the parent. A child may update its visual field and receive GUI events by modifying the DOM. A parent can dynamically change a child's visual field by writing to it. Jigsaw will not permit a child to do the same for a parent unless the visual field is delegated. Overlapping visual fields from different boxes are treated as opaque. The box with the highest z-order prevails. Even with these protections, a principal  object must rely on its hierarchy. Like visual field, network access is also secured hierarchically with increasinglyrics restrictive scope. The top level box may communicate with all servers using http requests while the children may be allowed to communicate with select domains. Special tokens such as self and parent may be used to represent the origins of the respective boxes. Like network resources, local storage is also secured but here Jigsaw partitions the key value client side database with separate DOM storage. Cross principal access to this is allowed only via corresponding public operations  on the principal objects. We will shortly see why the public private syntax is better for securing objects than existing encapsulation syntax from the Javascript language. The language provides prototype as a means for inheritance. The objects are merely key value dictionaries. A prototype is an exemplar that defines property names and default values for other instances of these objects.  Javascript has a permissive reflective interface that allows properties or methods of all objects to be enumerated.
By setting the __proto__ property, an object can dynamically become an instance of the exemplars class. Properties may be dynamically added to any object. Even the __proto__ property van be assigned dynamically which makes an object change its inheritance dynamically. Thus jigsaw has to add some syntax to provide cross domain encapsulation  and borrows it from more object oriented languages.

A scientist recorded the temperatures with some unit on regular intervals. She has N data points and she proceeded to calculate the averages for a smoothing window of size K. This means she took K consecutive readings and calculated their average on a sliding scale. The next K data points are chosen starting from the second. And so on  this gives n-k+1 averages and she writes them down as just the sums omitting the division by k. But she loses the original data set. Assuming that the original data points were all integers, How do we find out the minimum difference between possible lowest and highest temperatures.
Solution we know the consecutive sums give us the last individual element added and the first element removed. Consequently we write down these n-k+1 successive differences. Now for each of the k positions within a window say i, we do the following  operations :
We  initialize an array b of length (n-1-i)/k and fill them with the values of the last element of a in the corresponding k sized jumps  then for these elements of b we add up the adjacent pairs  successively
and append a zero. Then we take the difference between the min and max of b.
Since we do this for each position in k, we get the highest among all such differences as the least possible

The central idea here is to collate the differences starting at I and every k step size because the last element participates in the difference every k step size. In other word after every k the last element becomes the first element. Consequently these collated differences can then give an idea of  the differences between individual original elements. Therefore when we aggregate them towards the right pair wise we build up the maximum difference between the elements . With the cycles that we iterate we are sure to find the maximum of the  differences between individual elements by considering them to participate in first and last differences. We only have to refine the answer by 1 if we be conservative due to the potential exclusion by taking lower bounds.
Int GetMinDifference (int n, int k, list <int> sums){

Var a = new List <int> (n-k);
Var r = new List <int> (k);
Var q = new List <int> (sums);
For ( int I =1; I < n-k+1; I ++)
A [i-1] = sums [i-1] -sums [i];
For ( int I = 0; I < k: i++)
{
Var b = new List <>(n);
For (int x = 0; x < (n-1-i)/k; x++)
b [x] = a [I + k*x];
For (int c=1; c < b.Count: c++)
{b [c] = b [c-1] + b [c];
}
b.add(0);
Int d = Math.abs (b.max ()-b.min ());
r [i] = d;
q [i] = b.max ();
}
Var m = r.max ();
Var rem = (sums [0]-q.sum ())%k;
Var n = m * k -r.sum ();
If ( n >=rem )
   Return m;
Else 
    Return m+1;
}
Courtesy: codejam solutions.
The original problem statement suggests you to come up with an integer data point distribution for each of the averages and then overlap them 

Today we continue to discuss the paper on 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. We saw how iFrames differ from boxes and why boxes are helpful with the Jigsaw design goals. A Jigsaw  application can have multiple boxes, but all of the boxes live in the same frame. Jigsaw code uses access modifiers to expose state to external domains. The Jigsaw runtime uses these modifiers to validate cross-domain operations. A single Jigsaw application may contain multiple  principals. Jigsaw places each of these principals in a separate box.  As with the DOM, a principal can access its parent principal object or the root.Principal objects can synchronize their writes to DOM storage. Each Jigsaw box can potentially contain a DOM tree and an associated visual field. The updates to these are constrained by the parent. A visual field consists of width height and location within the parents visual field and a z-order.  A parent can set these for the child. If a child wants to modify these, it can try but it has to be permitted by the parent. The child fires a  Jigsaw event on any modification and the parent must have a registered handler for the same. Visual fields can overlap but boxes cannot request overlapping  visual region. With the hierarchy, there  is fine control of the visual field and storage but a principal must still trust in its ancestors. DOM storage obstruction allows each origin to maintain a client-side key/value database. Jigsaw partitions this DOM storage.

#google codejam Riverflow problem:
A river receives water from tributaries that can be diverted to farms by farmers. Farmers choose an integer power of 2 from 1 to D both inclusive and toggle their usage everytime that many number of days has passed. Given N days history of water flow in the river, determine if the farmers are cheaters or the smallest number of farmers who could be diverting from the river.

int GetMinFarmers(int D, int N, List<int> flows)
{
bool cheaters = false;
int net = 0;
int farmers = 0;
for (int d = D; d >= 1; d /= 2)
{
    for (int i = 0; i < d; i++) {
         int net = flows[i+d]-flows[i] - flows[i+d-1] + flows[(i+2*d-1)%(2*d)];
                                                                 // i+d-1 stands for previous day to be reduced by next cycle
                                                                                          // (i+2*d-1)%(2*d) stands for the next cycle
         if (net%2) cheaters = true;
         net /= 2;
         if (net > 0){
                     farmers += net;
                     for(int j = i+d; j <= i+2*d;j++){
                           flows[j%(2*d)] -= net;
                     }
         }else{
                     farmers -= net;
                     for(int j = i; j <= i+d;j++){
                           flows[j%(2*d)] += net;
                     }
         }
    }
}
if (cheaters || flows[0] < 0)
   Console.WriteLine("cheaters");
return farmers;
}
#courtesy: Gnurdux

We discuss another code jam problem today

This one is about N-quails running away from a person where initially the person stands at the origin and the quails are on a straight line at some offset Pi from the origin. They are running  away from the person either to the left or to the right of the origin and continue to run in that direction with their respective constant speed Si. The speed of the man is Y another constant and he can change his direction at any time to collect all the quails.  How much time does it take at the minimum to collect all the quails.
For the quails moving in the same direction, he will have to catch up at the max of pi + Si × t. This will be the quail whose abs (pi ×si) weighting factor is greatest.  For the quails running in the other direction, he can finish running in one direction first and then switch to catching up on another side.  This will save him the trouble of covering already negotiated distances repeatedly. Consequently he must first pick the direction with the shorter weighting factor is greatest.
Assume si is all positive it's direction given by pi which is minus for left and plus for right
Int getMinTime (list <int> Pi, list <int> Si, int K)
{
Int min = 0; int leftmost=-1;
Int max = 0; int rightmost=Pi.count+1;
For ( int I = 0; I < Pi.Count; i++)
{
 If (Pi × Si < min) {min = Pi × Si;
 leftmost = i}
 If (Pi × Si > max) {max = Pi x Si;
rightmost=i;}
}
If (rightmost < pi.count +1 && K - S [rightmost] == 0) return -1;
If ( leftmost > -1 && K - S [leftmost] == 0) return -1;
Int t-right = 0;
Int t-left = 0;
If (rightmost < Pi.Count +1) t-right= P[rightmost]/ K - S [rightmost];
If (leftmost > -1) t-left = P [leftmost] / K  - S [leftmost];
Int total = 0;
If (abs(min) > abs (max))
{
// first right then left
total = t-left + 2 × t-right;
}
else
{
// first left then right
total = t-right + 2 x t-left;
}
return total;
}

Today we continue to discuss the paper on 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. We saw how iFrames differ from boxes and why boxes are helpful with the Jigsaw design goals.
First boxes have no way to communicate with each other even if they belong to the same origin. Only functions marked public on principal objects can make cross domain calls. Boxes define the set  of domains they interact with by exposing their principal objects
Second boxes can use hierarchical relationships to manage resources. The topmost box has full access as possible. The descendants are further narrowed in scope. The delegations are possible from parent to child but with increasing strictness.  The integrator can set acts that restrict access of a child to its local storage but cannot allow access to its own storage.
Third boxes allow synchronous calls with objects being passed by reference. This is a significant improvement over asynchronous calls with significant marshalling.

Today we continue reading 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. We saw some of the features and design goals of Jigsaw. We got familiar with some of the terms such as domain, principal and integrator. We also reviewed box which is an isolation container much like an iFrame for each principal  however there are three differences between a box and an iFrame . Two iFrames can directly access each other's Javascript's namespaces using frame references. But box explicitly prohibits this.  The only way to allow cross principal access is with access modifiers on the principal object. IFrames share same origin.
But boxes enable fault isolation and privilege separation from different principals that originate from the same domain
Another difference is that boxes use nesting relationships to secure the resoutces of the children. With this hierarchy, common object oriented practice of encapsulation and inheritance can be used to better facilitate the management of resources. The third difference between box and iFrame is their use of communication channels.  IFrames uses asynchronous  postmessage calls . These calls can only transmit immutables and not pass objects by reference. Boxes facilitate synchronous calls and don't require marshaling of objects with the use of proxy.
#coding exercise
Find least common multiple of two integers
Int lcm (int x, int y)
{
Return (x*y)/gcd (x,y);
}

#codejam problem

A R x C matrix of positive numbers wraps around a drum. Each number represents the number of cells that share an edge with the cell of the same number. For eg the front and back of the drum can be :

3  3  3

3  3  3

2  2  2

The top and bottom of the drum can be different so the line containing 2 can appear in the first line instead of the last and this will make it a different arrangement. If an arrangement can be rotated to get another, they are the same. How many different arrangements exist for given R x C

const int a[5][6]={1,1,4,1,1,10,2,2,2,6,2,2,1,1,7,1,1,19,1,1,7,9,1,19,2,2,14,10,2,92};

int GetMinArrangements(int R, int C)

{

assert(R > 0 && C> 0);

Int answer = 0;

For (int I = 1; I <= C; i++)

{

    Int d = gcd(C, i)

    answer += a[R-2][d-1];

}

return answer/C;

}

 

Int gcd(int x, int y)

{

If y == 0 return x;

return gcd(y, x % y);

}