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);

}