#codingexercise
Given a room and a robot that can move in one of four directions, find the size of the room.
Int GetSize(int x, int y) // current co-ordinate of GetSize
{
// if one of the directions faces the wall, use it as the start
// else walk in one of four directions that is available
// or start from top-left and start the walk along the boundary of the room
// noting the four corners
// use it to calculate width and length
Int wallstartx=INT_MIN;
Int wallstarty=INT_MIN;
int i = x;
int j = y;
//start at top left
For (; Move(i,j,0);I--);
Wallstartx=i;
Wallstarty=j;
If (wallstartx==INT_MIN || wallstarty==INT_MIN)
{
Int I = x;
Int j = y;
// move left to wall
While(Move(i,j,0) == true))
i--;
Wallstartx = i;
Wallstarty =j;
}
// we have a position on the wall, now we run along the boundary
I = wallstartx;
For (int j=wallstarty; Move(I, j,1); j++);
Int topleftx=I;
Int toplefty = j;
For (int i=wallstartx; Move(I, j,2); i++);
Int toprightx=I;
Int toprighty = j;
For (int j=toprighty; Move(I, j,3); j--);
Int bottomrightx=I;
Int bottomrighty=j;
For (int i=bottomrightx; Move(I, j,0); I--);
Int bottomleft=I;
Int bottomleft = j;
For (int j = bottomlefty; Move(I,j,1) && I != wallstartx && j != wallstarty; j--);
Assert(wallstartx == I && wallstarty == j);
Int width = Math.Abs(bottomrightx-bottomleftx);
Int height = Math.Abs(toplefty-bottomlefty);
Return width*height;
}
If the room was irregular and not a rectangle, we would cover each coordinate horizontally and count each postion occupied as a unit square, when we cover all the squares in one row, we proceed to the next. In this case, we could always try to begin from top left.
Given a room and a robot that can move in one of four directions, find the size of the room.
Int GetSize(int x, int y) // current co-ordinate of GetSize
{
// if one of the directions faces the wall, use it as the start
// else walk in one of four directions that is available
// or start from top-left and start the walk along the boundary of the room
// noting the four corners
// use it to calculate width and length
Int wallstartx=INT_MIN;
Int wallstarty=INT_MIN;
int i = x;
int j = y;
//start at top left
For (; Move(i,j,0);I--);
Wallstartx=i;
Wallstarty=j;
If (wallstartx==INT_MIN || wallstarty==INT_MIN)
{
Int I = x;
Int j = y;
// move left to wall
While(Move(i,j,0) == true))
i--;
Wallstartx = i;
Wallstarty =j;
}
// we have a position on the wall, now we run along the boundary
I = wallstartx;
For (int j=wallstarty; Move(I, j,1); j++);
Int topleftx=I;
Int toplefty = j;
For (int i=wallstartx; Move(I, j,2); i++);
Int toprightx=I;
Int toprighty = j;
For (int j=toprighty; Move(I, j,3); j--);
Int bottomrightx=I;
Int bottomrighty=j;
For (int i=bottomrightx; Move(I, j,0); I--);
Int bottomleft=I;
Int bottomleft = j;
For (int j = bottomlefty; Move(I,j,1) && I != wallstartx && j != wallstarty; j--);
Assert(wallstartx == I && wallstarty == j);
Int width = Math.Abs(bottomrightx-bottomleftx);
Int height = Math.Abs(toplefty-bottomlefty);
Return width*height;
}
If the room was irregular and not a rectangle, we would cover each coordinate horizontally and count each postion occupied as a unit square, when we cover all the squares in one row, we proceed to the next. In this case, we could always try to begin from top left.
No comments:
Post a Comment