rosrun tf view_frames
node balance(int min, int max,node[] arr) {
if(min == max)
return arr[min];
int mid = (min + max )/2;
node curr = arr[mid];
curr.left = balance(min, mid-1, arr);
curr.right = balance(mid + 1, max, arr);
return curr;
}
public long numWays( int maxX, int maxY, String[] bad) {
this.maxX = maxX;
this.maxY = maxY;
processBads(bad);
pathArr = new long[maxX +1 ][maxY + 1];
for(int i = 0; i <= maxX; i++)
for(int j = 0; j <= maxY; j++)
pathArr[i][j] = -1;
return pathsRec(maxX, maxY);
}
public long pathsRec(int x, int y) {
if(x <0 || y < 0)
return 0;
if( pathArr[x][y] != -1)
return pathArr[x][y];
if(x > maxX || x < 0 || y > maxY || y < 0)
return 0;
if(x == 0 && y == 0)
return 0;
if(x == 0 && y == 1 && valid(0,0,0,1))
return 1;
if(x == 1 && y == 0 && valid(0,0,1,0))
return 1;
long path1 = 0, path2 = 0;
if( valid(x, y, x-1, y) )
path1 = pathsRec(x -1, y);
if( valid(x, y, x, y-1) )
path2 = pathsRec(x, y-1);
pathArr[x][y] = path1 + path2;
return (path1 + path2);
}
public boolean valid(int x, int y, int x1, int y1) {
if(x > maxX || x < 0 || y > maxY || y < 0)
return false;
for(int i =0; i< blocked.length; i++) {
boolean cond1 = x == blocked[i][0] && y == blocked[i][1] && x1 == blocked[i][2] && y1 == blocked[i][3];
boolean cond2 = x1 == blocked[i][0] && y1 == blocked[i][1] && x == blocked[i][2] && y == blocked[i][3];
if(cond1 || cond2 ) {
return false;
}
}
return true;
}
public void processBads(String[] bad) {
blocked = new int[bad.length][4];
for(int i = 0; i < bad.length; i++) {
String[] temp = bad[i].split(" ");
blocked[i][0] = Integer.parseInt(temp[0]);
blocked[i][1] = Integer.parseInt(temp[1]);
blocked[i][2] = Integer.parseInt(temp[2]);
blocked[i][3] = Integer.parseInt(temp[3]);
}
}
public int longestZigZagRec(int[] n, int index, boolean pos) {
if(index==0)
return 1;
int posMax = 1,negMax = 1;
if(pos) {
for(int i=0;i<index;i++)
if(n[i] < n[index])
posMax = max(longestZigZagRec( n, i, !pos) + 1, posMax);
}
else {
for(int i=0;i<index;i++)
if(n[i] > n[index])
negMax = max(longestZigZagRec( n, i, !pos) + 1, negMax);
}
int temp = pos==true?posMax:negMax;
//System.out.println(" from index "+ index+ " longest zigzap length is " + temp +" for "+ pos);
return pos==true?posMax:negMax;
}
ZigZag z = new ZigZag();
int [] in = {20,10,1,7,4,9,2,5};
System.out.println(z.max(z.longestZigZagRec(in, in.length-1, true),z.longestZigZagRec(in, in.length-1, false)));
class edge{
public edge(int vertex1, int vertex2, int weight2) {
this.vertices[0] = vertex1;
this.vertices[1] = vertex2;
this.weight = weight2;
}
int weight;
int[] vertices = new int[2];
}
import java.util.ArrayList;
class node{
public void getDijkstra(){
int processed = 0;
while(processed<vertices.length){
flag = 1;
Arrays.sort(vertices);
int currVertexNum = vertices[processed].vertexNum;
flag = 0;
Arrays.sort(vertices);
for(int e:nodeList[currVertexNum].edges){
int otherEnd = edgeList[e].vertices[0] == currVertexNum? edgeList[e].vertices[1]: edgeList[e].vertices[0];
if(vertices[currVertexNum].dist!=Integer.MAX_VALUE &&vertices[currVertexNum].dist+edgeList[e].weight<vertices[otherEnd].dist)
vertices[otherEnd].dist = vertices[currVertexNum].dist+edgeList[e].weight;
}
processed++;
}
}
Dijkstra's relies on the fact that if we have a set of neighbours from one vertex, the cheapest distance to that neighbour cannot get any cheaper. But, what if we have negative edge costs? Then, for a vertex v, if we have neigbhours w and x, and x is cheaper, then cost from source to x will be cost from source to v and cost from v to x. However, if we have negative edges, we might find a path from v->w->(some more negative edges)->x which might be cheaper than the earlier one. Hence, Dijkstra babu gives up on negative edges.
private int manford(int destination, int maxEdges) {
System.out.println("destination "+destination+" Maxedges "+maxEdges);
if(cost[destination][maxEdges] != Integer.MAX_VALUE || maxEdges==0)
return cost[destination][maxEdges] ;
node dest = nodeList[destination];
int tempMin = manford(destination,maxEdges-1);
for(int e: dest.edges){
int restPlace = edgeList[e].vertices[0] == destination? edgeList[e].vertices[1]: edgeList[e].vertices[0];
int coster = manford(restPlace,maxEdges-1);
if(coster<Integer.MAX_VALUE)
tempMin = tempMin < coster+edgeList[e].weight?tempMin:coster+edgeList[e].weight;
}
cost[destination][maxEdges] = tempMin;
return tempMin;
}
int minAvgCost(int start, int end){
if(start>end)
return 0;
if(start==end)
return freq[start];
int min = Integer.MAX_VALUE;
int sumOfSubP = sum(start,end);
for(int i=start;i<=end;i++){
int temp = sumOfSubP+minAvgCost(start,i-1) +minAvgCost(i+1,end);
min = min>temp?temp:min;
}
return min;
}
Some Memoization later:
int minAvgCost(int start, int end){
if(start>end)
return 0;
if(recArray[start][end]!=-1)
return recArray[start][end];
if(start==end)
return freq[start];
int min = Integer.MAX_VALUE;
int sumOfSubP = sum(start,end);
for(int i=start;i<=end;i++){
int temp = sumOfSubP+minAvgCost(start,i-1) +minAvgCost(i+1,end);
min = min>temp?temp:min;
}
recArray[start][end] = min;
return min;
}
public class sqq {
String X,Y;
int blankfine=10,matchfine = 100;
int fine(char a, char b){
if(a==b)
return 0;
if(a=='-'||b=='-')
return blankfine;
return matchfine;
}
int seqAlign(int i, int j){
if(i==0&&j==0)
return fine(X.charAt(0),Y.charAt(0));
if(i<0&&j>=0)
return j*blankfine;
if(j<0&&i>=0)
return i*blankfine;
int t1 = seqAlign(i-1,j-1)+fine(X.charAt(i),Y.charAt(j));
int t2 = seqAlign(i-1,j)+fine(X.charAt(i),'-');
int t3 = seqAlign(i,j-1)+fine(Y.charAt(j),'-');
int temp = min(t1 , t2 , t3);
System.out.println("i= "+i+" j= "+j+" Ans: " + temp);
System.out.println(t1+" "+t2+" "+t3);
System.out.println("char i: "+X.charAt(i)+" char j: "+Y.charAt(j));
return temp;
}
int min(int a,int b, int c){
if(a<b&& a<c)
return a;
if(b<a&& b<c)
return b;
if(c<b&& c<a)
return c;
if(a<b)
return a;
else
return b;
}
public static void main(String farts[]){
sqq sq = new sqq();
sq.X = "ce";
sq.Y = "cd";
System.out.println(sq.seqAlign(sq.X.length()-1,sq.Y.length()-1));
}
}