Google Interview Question SDE-2s
Country: India
Interview Type: Phone Interview
Take all sensor and create interval along the x axis and find any gaps in between to passthrough
@ankit3600 How did you manage to leave a comment to an answer?Tell us your secret, or at least browser. I thought this feature was broken for like 2 months.
We can solve it recursively. We always want to go a straight line parallel to x axis. This basic principle. You if collision ( start, end, array of sensors) -end is straight line to the end of rect return no collision, you return c-a.
If it returnes a P that is center of a circle which collide, you call method byPass(start, P). By pass is a straight line that reaches top or bottom of circle. If collision happen during that process you by pass. If you successfully bypass P, you solve problem for point P now instead of start.
So there is 2 way I can think of it
1> Try a version on flood fill algorithm where you have to put sensor radius as a barrier and avoid it.
2> Using graph theory. Algo may be complicated so here it goes.
For each sensor (interms of it radius), try to find the connected components. Between each two component, find the min distance between them and collect the co-ordinates in array. Along with this, you have to add, the maximum x deflection in order to avoid sensor range area. This will be easy as you know the the component, just find the max-x in that component and add that to the add co-ordinate.Now, this array will serve as a node of your new graph. Run modified dijkstra on it to find the min distance traversed from the starting point y of robot to end y.
How about a wall follower maze solver that always has a wall to it's right? Below is a simple implementation. O(x*y*N) due the lame collision detection. But it finds it's way through dead ends etc.
Strategy is as follows:
1: find a place to start by scanning the start column (y=0, a<=x<c): there must be a point that is not surveillanced otherwise it can't start
2: go downwards so there is the left wall to it's right (looking into the "robots" direction)
3: if there is nothing on the right, go into that space (doesn't happen on the left wall)
4: if there is something ahead, turn left until way is free
5: if you somehow end up at the start position, the "maze" is not solveable
PS: There is an infinite loop if it has only one "pixel" to move at the start, we should cover that special case
Improvements:
1: proper termination
2: improve that lame collision detection to something smart, any idea?
3: Think about optimizing it, e.g. when returning from a dead end, some
#include <iostream>
using namespace std;
const int sensor_r = 2;
const int sensor_rr = sensor_r * sensor_r;
struct Pt {
int x;
int y;
Pt(int ay, int ax) { x = ax; y = ay; }
};
bool Collision(int a, int b, int c, int d, int y, int x, const Pt* ss, int nss)
{
if (y < a) return true; // hit left wall, right wall we don't check, since it is "open"
if (x < b) return true; // hit top wall
if (x >= d) return true; // hit bottom wall
for (int i = 0; i < nss; ++i) // lame collision detection on sensor
{
int dx = ss[i].x - x;
int dy = ss[i].y - y;
if (dx*dx + dy*dy <= sensor_rr)
{
return true;
}
}
return false;
}
void FindWay(int a, int b, int c, int d, const Pt* ss, int nss, char* track)
{
if (c-a <= 0) return;
if (d-b <= 0) return;
int y = a;
int x = b;
for (x = b, y = a; x <= d && Collision(a, b, c, d, y, x, ss, nss); ++x);
if (x == d) { cout << "can't start: all starting points are checked by sensors" << endl; return; }
int ox = x;
int oy = y;
int dx = 1;
int dy = 0;
while (y < c)
{
track[x*(c - a + 1) + y] = 'O'; // +1: due to \n
if (!Collision(a,b,c,d, y - dx, x + dy, ss, nss)) // there must be something on the right to follow the "wall"
{
// if not, turn right ... and do a step in this direction
int t = dx;
dx = dy;
dy = -t;
}
else if (Collision(a, b, c, d, y + dy, x + dx, ss, nss))
{
// collision ahead, turn left and do not move
int t = dx;
dx = -dy;
dy = t;
continue;
}
// turned right into an empty space or just continue into the direction
x += dx;
y += dy;
if (x == ox && y == oy)
{
cout << "can't solve it, way is blocked" << endl;
return;
}
}
}
char *CreateTrackBuf(int a, int b, int c, int d);
int main()
{
int a = 0;
int b = 0;
int c = 15;
int d = 10;
char *track = CreateTrackBuf(a,b,c,d);
Pt ss[] = { {6,7} , {12,7}, {12,3} /*, {12, 2} */ };
FindWay(0, 0, 15, 10, ss, sizeof(ss) / sizeof(ss[0]), track);
cout << track;
getchar();
}
char *CreateTrackBuf(int a, int b, int c, int d)
{
if (c - a <= 0) return nullptr;
if (d - b <= 0) return nullptr;
// create a char buffer to record and print the path he went
int y2 = c - a + 1; // +1: due to '\n'
int x2 = d - b;
int os = y2 * x2;
char *po = new char[os];
for (int i = 0; i < os; ++i) po[i] = ' ';
for (int i = 1; i <= x2; i++)
{
po[i*y2 - 1] = '\n';
}
po[os - 1] = '\0';
return po;
}
/* output on above sample:
O OOO
O OO OO
O OO O
O O
O OOO OO
O OO OO OO
O OO OOO
O O O
O OO OOO
OOOOOO OOOOO
with the 12,2 sensor (blocked path)
can't solve it, way is blocked
OOOOOOOOOOOO
O OO
O O
O O
O OOO OO
O OO OO OO
O OO OOO
O O O
O OO OOO
OOOOOO OOOOO
*/
"he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c"
Just to clarify, you basically have to move from any point at the top of the rectangle to any point at the bottom of the rectangle?
I think you can construct a graph with nodes as the coordinates and add edges to each neighboring node if it's not within the circular range of the sensor. Then do dijkstra's from start to end.
/*
* Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates.
* Also given some coordinates (m,n) of sensors inside the rectangle.
* All sensors can sense in a circular region of radius r about their centre (m,n).
* Total N sensors are given. A player has to reach frolm left side of rectangle to
* its right side (i.e. he can start his journey from any point whose y coordinate
* is b and x coordinate is a<=x<=c. he has to end his journey to any point whose
* y coordinate is d and x coordinate is a<=x<=c).
*
* Write an algorithm to find path (possibly shortest but not necessary) from
* start to end as described above.
* NOTE: all coordinates are real numbers.
* You have to avoid sensors and can move in any direction any time.
*
*/
#include <iostream>
#include <list>
#include <map>
#define MAX_INT 2147483647 // represents infinity
using namespace std;
class Coordinate {
public:
Coordinate(int a, int b): x(a), y(b) {};
int getX() { return x; }
int getY() { return y; }
void setX(int x) { this->x = x; }
void setY(int y) { this->y = y; }
operator std::string() const { return "(" + std::to_string(x) + ", " + std::to_string(y) + ")"; }
private:
int x, y;
};
typedef Coordinate Coord;
class Range {
public:
Range(int i, int r): min(i-r), max(i+r) {}
int getMin() { return min; }
int getMax() { return max; }
private:
int min, max;
};
// forward declare
class Node;
class Sensor;
typedef Node* NodeP;
typedef Sensor* SensorP;
class Node {
public:
Node(int m, int n): distance(MAX_INT), n(NULL) {
xy = new Coordinate(m,n);
edges = list<NodeP>();
};
Node(Coordinate *c): xy(c), distance(MAX_INT), n(NULL) {
//name = "a";
edges = list<NodeP>();
};
Node(Coordinate *c, string n): xy(c), distance(MAX_INT), n(NULL) {
//name = n;
edges = list<NodeP>();
};
// ERROR: Parameter needs a pointer!
void addEdge(Node *a) { edges.push_back(a); }
void print() {
cout << "{x: " << std::to_string(xy->getX()) << ", y: " << std::to_string(xy->getY()) << "}\n";
}
//operator std::string() const
std::string to_string() { return "{x: " + std::to_string(xy->getX()) + ", y: " + std::to_string(xy->getY()) + "}"; }
std::string edges_to_string() {
std::string s;
for (list<NodeP>::iterator it=edges.begin(); it != edges.end(); it++) {
s += " {x: " + std::to_string((*it)->xy->getX()) + ", y: " + std::to_string((*it)->xy->getY()) + "} ";
}
return s;
}
Coordinate *xy;
int distance;
list<NodeP> edges;
void addNext(NodeP n) { this->n = n; }
NodeP next() { return n; }
protected:
std::string name;
NodeP n;
};
class Sensor : public Node {
public:
Sensor(Coordinate *c, int r) : Node(c), radius(r), x_range(new Range(c->getX(),r)), y_range(new Range(c->getY(), r)) {}
bool isWithinRange(int x, int y) {
if ((x >= x_range->getMin()) && (x <= x_range->getMax())
&& ((y >= y_range->getMin()) && (y <= y_range->getMax()))
) {
if (x == x_range->getMin() && y != xy->getY()) return false;
if (x == x_range->getMax() && y != xy->getY()) return false;
if (y == y_range->getMin() && x != xy->getX()) return false;
if (y == y_range->getMax() && x != xy->getX()) return false;
return true;
}
return false;
}
bool isWithinRange(Coordinate *c) {
if ((c->getX() >= x_range->getMin()) && (c->getX() <= x_range->getMax())
&& ((c->getY() >= y_range->getMin()) && (c->getY() <= y_range->getMax()))
) {
if (c->getX() == x_range->getMin() && c->getY() != xy->getY()) return false;
if (c->getX() == x_range->getMax() && c->getY() != xy->getY()) return false;
if (c->getY() == y_range->getMin() && c->getX() != xy->getX()) return false;
if (c->getY() == y_range->getMax() && c->getX() != xy->getX()) return false;
return true;
}
return false;
}
void print() {
cout << "{x: " << xy->getX() << ", y: " << xy->getY() << ", r: " << radius << "}\n";
}
protected:
int radius;
Range *x_range;
Range *y_range;
};
list<NodeP>* dijkstra(NodeP start, NodeP end) {
list<NodeP> todo = list<NodeP>();
list<NodeP> path = list<NodeP>();
NodeP tmp;
todo.push_back(start);
// Start with distance 0
start->distance = 0;
while (!todo.empty()) {
tmp = todo.back();
todo.pop_back();
cout << "Searching " << tmp->to_string() << " with edges: " << tmp->edges_to_string() << "\n";
for (list<NodeP>::iterator it = tmp->edges.begin(); it != tmp->edges.end(); it++) {
cout << "Distance " << std::to_string(tmp->distance + 1) << " < " << std::to_string((*it)->distance) << "?\n";
if ((tmp->distance + 1) < (*it)->distance) {
cout << "Updating distance of " << (*it)->to_string() << "\n";
(*it)->distance = tmp->distance + 1;
todo.push_back(*it);
tmp->addNext((*it));
}
if (((*it)->xy->getX() == end->xy->getX()) &&
((*it)->xy->getY() == end->xy->getY())) {
cout << "Found!\n";
break;
}
}
}
tmp = start;
path.push_back(tmp);
while ((tmp = tmp->next())) {
cout << "Path " << tmp->to_string() << "\n";
path.push_back(tmp);
}
return &path;
}
int main() {
int a = 0, b = 0, c = 4, d = 4;
map<std::string, NodeP> graph;
map<std::string,NodeP>::iterator it;
list<SensorP> sensors = list<SensorP>();
Sensor *s = new Sensor(new Coordinate(1,2),1);
s->print();
sensors.push_back(s);
Sensor *s1 = new Sensor(new Coordinate(3,0),1);
s1->print();
sensors.push_back(s1);
bool bad = s->isWithinRange(3,6);
cout << "bad: " << bad << "\n";
bad = s->isWithinRange(4,3);
cout << "bad: " << bad << "\n";
Node *end = new Node(c, d);
bool safe = false;
// Construct graph
for (int i=0; i<c; i++) {
for (int j=0; j<d; j++) {
Coord *c = new Coord(i,j);
safe = true;
// Check if we're safe from all sensors
for (list<SensorP>::iterator sen=sensors.begin(); sen != sensors.end(); sen++) {
if ((*sen)->isWithinRange(c)) {
safe = false;
break;
}
}
if (safe) {
Node *next = new Node(c);
std::string s = std::to_string(i) + std::to_string(j);
// add neighboring nodes
std::string top = std::to_string(i) + std::to_string(j-1);
std::string left = std::to_string(i-1) + std::to_string(j);
std::string topleft = std::to_string(i-1) + std::to_string(j-1);
it = graph.find(top);
if (it != graph.end()) {
it->second->addEdge(next);
}
it = graph.find(left);
if (it != graph.end()) {
it->second->addEdge(next);
}
it = graph.find(topleft);
if (it != graph.end()) {
it->second->addEdge(next);
}
graph.insert(pair<std::string,Node*>(s, next));
}
}
}
for (auto& x: graph) {
cout << x.first << ": " << x.second->to_string() << " edges: " << x.second->edges_to_string() << '\n';
}
// Do dijkstra's
// Get start node
list<NodeP> *path;
std::string start_str = std::to_string(0) + std::to_string(0);
it = graph.find(start_str);
if (it != graph.end()) {
path = dijkstra((it->second), end);
}
cout << "path: ";
for (list<NodeP>::iterator it=path->begin(); it != path->end(); it++) {
cout << (*it)->to_string() << " ";
}
cout << "\n";
return 0;
};
I think you can create a graph with nodes as coordinates and an edges to each neighboring node if the node is not within range of the all the sensors. Then do dijkstra's from start to end given a list of possible starting positions and a list of possible ending positions.
So something like this:
/*
* Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates.
* Also given some coordinates (m,n) of sensors inside the rectangle.
* All sensors can sense in a circular region of radius r about their centre (m,n).
* Total N sensors are given. A player has to reach frolm left side of rectangle to
* its right side (i.e. he can start his journey from any point whose y coordinate
* is b and x coordinate is a<=x<=c. he has to end his journey to any point whose
* y coordinate is d and x coordinate is a<=x<=c).
*
* Write an algorithm to find path (possibly shortest but not necessary) from
* start to end as described above.
* NOTE: all coordinates are real numbers.
* You have to avoid sensors and can move in any direction any time.
*
*/
#include <iostream>
#include <list>
#include <map>
#define MAX_INT 2147483647 // represents infinity
using namespace std;
class Coordinate {
public:
Coordinate(int a, int b): x(a), y(b) {};
int getX() { return x; }
int getY() { return y; }
void setX(int x) { this->x = x; }
void setY(int y) { this->y = y; }
operator std::string() const { return "(" + std::to_string(x) + ", " + std::to_string(y) + ")"; }
private:
int x, y;
};
typedef Coordinate Coord;
class Range {
public:
Range(int i, int r): min(i-r), max(i+r) {}
int getMin() { return min; }
int getMax() { return max; }
private:
int min, max;
};
// forward declare
class Node;
class Sensor;
typedef Node* NodeP;
typedef Sensor* SensorP;
class Node {
public:
Node(int m, int n): distance(MAX_INT), n(NULL) {
xy = new Coordinate(m,n);
edges = list<NodeP>();
};
Node(Coordinate *c): xy(c), distance(MAX_INT), n(NULL) {
//name = "a";
edges = list<NodeP>();
};
Node(Coordinate *c, string n): xy(c), distance(MAX_INT), n(NULL) {
//name = n;
edges = list<NodeP>();
};
// ERROR: Parameter needs a pointer!
void addEdge(Node *a) { edges.push_back(a); }
void print() {
cout << "{x: " << std::to_string(xy->getX()) << ", y: " << std::to_string(xy->getY()) << "}\n";
}
//operator std::string() const
std::string to_string() { return "{x: " + std::to_string(xy->getX()) + ", y: " + std::to_string(xy->getY()) + "}"; }
std::string edges_to_string() {
std::string s;
for (list<NodeP>::iterator it=edges.begin(); it != edges.end(); it++) {
s += " {x: " + std::to_string((*it)->xy->getX()) + ", y: " + std::to_string((*it)->xy->getY()) + "} ";
}
return s;
}
Coordinate *xy;
int distance;
list<NodeP> edges;
void addNext(NodeP n) { this->n = n; }
NodeP next() { return n; }
protected:
std::string name;
NodeP n;
};
class Sensor : public Node {
public:
Sensor(Coordinate *c, int r) : Node(c), radius(r), x_range(new Range(c->getX(),r)), y_range(new Range(c->getY(), r)) {}
bool isWithinRange(int x, int y) {
if ((x >= x_range->getMin()) && (x <= x_range->getMax())
&& ((y >= y_range->getMin()) && (y <= y_range->getMax()))
) {
if (x == x_range->getMin() && y != xy->getY()) return false;
if (x == x_range->getMax() && y != xy->getY()) return false;
if (y == y_range->getMin() && x != xy->getX()) return false;
if (y == y_range->getMax() && x != xy->getX()) return false;
return true;
}
return false;
}
bool isWithinRange(Coordinate *c) {
if ((c->getX() >= x_range->getMin()) && (c->getX() <= x_range->getMax())
&& ((c->getY() >= y_range->getMin()) && (c->getY() <= y_range->getMax()))
) {
if (c->getX() == x_range->getMin() && c->getY() != xy->getY()) return false;
if (c->getX() == x_range->getMax() && c->getY() != xy->getY()) return false;
if (c->getY() == y_range->getMin() && c->getX() != xy->getX()) return false;
if (c->getY() == y_range->getMax() && c->getX() != xy->getX()) return false;
return true;
}
return false;
}
void print() {
cout << "{x: " << xy->getX() << ", y: " << xy->getY() << ", r: " << radius << "}\n";
}
protected:
int radius;
Range *x_range;
Range *y_range;
};
list<NodeP>* dijkstra(NodeP start, NodeP end) {
list<NodeP> todo = list<NodeP>();
list<NodeP> path = list<NodeP>();
NodeP tmp;
todo.push_back(start);
// Start with distance 0
start->distance = 0;
while (!todo.empty()) {
tmp = todo.back();
todo.pop_back();
cout << "Searching " << tmp->to_string() << " with edges: " << tmp->edges_to_string() << "\n";
for (list<NodeP>::iterator it = tmp->edges.begin(); it != tmp->edges.end(); it++) {
cout << "Distance " << std::to_string(tmp->distance + 1) << " < " << std::to_string((*it)->distance) << "?\n";
if ((tmp->distance + 1) < (*it)->distance) {
cout << "Updating distance of " << (*it)->to_string() << "\n";
(*it)->distance = tmp->distance + 1;
todo.push_back(*it);
tmp->addNext((*it));
}
if (((*it)->xy->getX() == end->xy->getX()) &&
((*it)->xy->getY() == end->xy->getY())) {
cout << "Found!\n";
break;
}
}
}
tmp = start;
path.push_back(tmp);
while ((tmp = tmp->next())) {
cout << "Path " << tmp->to_string() << "\n";
path.push_back(tmp);
}
return &path;
}
int main() {
int a = 0, b = 0, c = 4, d = 4;
map<std::string, NodeP> graph;
map<std::string,NodeP>::iterator it;
list<SensorP> sensors = list<SensorP>();
Sensor *s = new Sensor(new Coordinate(1,2),1);
s->print();
sensors.push_back(s);
Sensor *s1 = new Sensor(new Coordinate(3,0),1);
s1->print();
sensors.push_back(s1);
bool bad = s->isWithinRange(3,6);
cout << "bad: " << bad << "\n";
bad = s->isWithinRange(4,3);
cout << "bad: " << bad << "\n";
Node *end = new Node(c, d);
bool safe = false;
// Construct graph
for (int i=0; i<c; i++) {
for (int j=0; j<d; j++) {
Coord *c = new Coord(i,j);
safe = true;
// Check if we're safe from all sensors
for (list<SensorP>::iterator sen=sensors.begin(); sen != sensors.end(); sen++) {
if ((*sen)->isWithinRange(c)) {
safe = false;
break;
}
}
if (safe) {
Node *next = new Node(c);
std::string s = std::to_string(i) + std::to_string(j);
// add neighboring nodes
std::string top = std::to_string(i) + std::to_string(j-1);
std::string left = std::to_string(i-1) + std::to_string(j);
std::string topleft = std::to_string(i-1) + std::to_string(j-1);
it = graph.find(top);
if (it != graph.end()) {
it->second->addEdge(next);
}
it = graph.find(left);
if (it != graph.end()) {
it->second->addEdge(next);
}
it = graph.find(topleft);
if (it != graph.end()) {
it->second->addEdge(next);
}
graph.insert(pair<std::string,Node*>(s, next));
}
}
}
for (auto& x: graph) {
cout << x.first << ": " << x.second->to_string() << " edges: " << x.second->edges_to_string() << '\n';
}
// Do dijkstra's
// Get start node
list<NodeP> *path;
std::string start_str = std::to_string(0) + std::to_string(0);
it = graph.find(start_str);
if (it != graph.end()) {
path = dijkstra((it->second), end);
}
cout << "path: ";
for (list<NodeP>::iterator it=path->begin(); it != path->end(); it++) {
cout << (*it)->to_string() << " ";
}
cout << "\n";
return 0;
};
from collections import deque
from math import pi, cos, sin
def draw_circle(grid, x_o, y_o, R):
h = len(grid)
w = len(grid[0])
for theta in range(0, 361, 10):
x = int(x_o + R * cos (theta * pi / 180))
y = int(y_o + R * sin (theta * pi / 180))
if x >= 0 and x < w and y >= 0 and y < h:
grid[x][y] = '0'
def dfs(grid, source, possible_start, c, d):
visited = set()
parents = {source: None}
stack = [source]
while stack:
x, y = stack.pop()
visited.add((x,y))
if y == d:
# reached other side, return path (build in reverse)
path = deque(tuple((x,y)))
while parents[(x,y)]:
x, y = parents[(x,y)]
path.appendleft((x,y))
if y == 0: # the start of the path can be which ever (row, 0) position we encounter first
break
return path
if (x,y) in possible_start: #if a possible start can be reached from this connected component, remove it
possible_start.remove((x,y))
for x_adj, y_adj in [(x-1, y), (x+1,y), (x, y-1), (x, y+1)]:
if x_adj >= 0 and x_adj <= d and y_adj >= 0 and y_adj <= c\
and grid[x_adj][y_adj] == ' ' and (x_adj, y_adj) not in visited:
parents[(x_adj, y_adj)] = (x,y)
stack.append((x_adj, y_adj))
return None
def cross_grid(c, d, sensors, R):
grid = [ [' ' for i in range(d + 1)] for i in range(c + 1) ]
for x_s, x_y in sensors:
draw_circle(grid, x_s, x_y, R)
starts = set()
for i in range(d+1):
if grid[i][0] == ' ':
starts.add((i,0))
path = None
while starts: # dfs on all unconnected components
if path:
break
source = starts.pop()
path = dfs(grid, source, starts, c, d)
for r in grid: to print grid
print(r)
return path
from collections import deque
from math import pi, cos, sin
def draw_circle(grid, x_o, y_o, R):
h = len(grid)
w = len(grid[0])
for theta in range(0, 361, 10):
x = int(x_o + R * cos (theta * pi / 180))
y = int(y_o + R * sin (theta * pi / 180))
if x >= 0 and x < w and y >= 0 and y < h:
grid[x][y] = '0'
def dfs(grid, source, possible_start, c, d):
visited = set()
parents = {source: None}
stack = [source]
while stack:
x, y = stack.pop()
visited.add((x,y))
if y == d:
# reached other side, return path (build in reverse)
path = deque(tuple((x,y)))
while parents[(x,y)]:
x, y = parents[(x,y)]
path.appendleft((x,y))
if y == 0: # the start of the path can be which ever (row, 0) position we encounter first
break
return path
if (x,y) in possible_start: #if a possible start can be reached from this connected component, remove it
possible_start.remove((x,y))
for x_adj, y_adj in [(x-1, y), (x+1,y), (x, y-1), (x, y+1)]:
if x_adj >= 0 and x_adj <= d and y_adj >= 0 and y_adj <= c\
and grid[x_adj][y_adj] == ' ' and (x_adj, y_adj) not in visited:
parents[(x_adj, y_adj)] = (x,y)
stack.append((x_adj, y_adj))
return None
def cross_grid(c, d, sensors, R):
grid = [ [' ' for i in range(d + 1)] for i in range(c + 1) ]
for x_s, x_y in sensors:
draw_circle(grid, x_s, x_y, R)
starts = set()
for i in range(d+1):
if grid[i][0] == ' ':
starts.add((i,0))
path = None
while starts: # dfs on all unconnected components
if path:
break
source = starts.pop()
path = dfs(grid, source, starts, c, d)
for r in grid: to print grid
print(r)
return path
// travel.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <queue>
enum BitType{
eEmpty,
ePath,
eSensor,
eVisited,
eInvalid
};
class Sensor{
public:
Sensor(int x, int y, int radius) : _x(x), _y(y), _radius(radius) {
}
bool hitTest(int x, int y) {
int h = _x - x;
int v = _y - y;
if(v*v + h*h <= _radius* _radius){
return true;
}
return false;
}
private:
int _x, _y;
int _radius;
};
class Bitmap{
public :
Bitmap(int width, int height) : _width(width), _height(height) {
_buffer = new char [_width * _height];
if(_buffer != NULL) {
memset(_buffer, eEmpty, _width *_height);
}
}
void setBit(int x, int y, BitType bitType) {
if(_buffer == NULL || x<0||y<0 || x>=_width || y>=_height)
return;
_buffer [y * _width + x] = bitType;
}
BitType getBit(int x, int y) {
if(_buffer == NULL || x >= _width || x < 0|| y >= _height || y < 0) {
return eInvalid;
} else {
return (BitType)_buffer[y * _width + x];
}
}
void printBitmap() {
for(int y = 0; y < _height; ++y){
printf("|");
for (int x =0; x < _width; ++x) {
if(_buffer[x + y * _width] == eEmpty){
printf(" ");
} else if(_buffer[x + y * _width] == ePath) {
printf("-");
} else if(_buffer[x + y * _width] == eSensor) {
printf("S");
} else if(_buffer[x + y * _width] == eVisited) {
printf(" ");
}
}
printf("|\n");
}
}
int getWidth() {
return _width;
}
int getHeight() {
return _height;
}
private :
int _height;
int _width;
char * _buffer;
};
class Node {
public :
Node(int x, int y, Node * parent) : _x(x), _y(y), _parent(parent) {
}
int getX(){
return _x;
}
int getY() {
return _y;
}
Node * getParent() {
return _parent;
}
void addChild(Node * child) {
_childs.push_back(child);
}
void addChildsInQueue(std::queue<Node *> &queue) {
std::vector<Node *>::iterator itr = _childs.begin();
while(itr != _childs.end()){
queue.push(*itr);
++itr;
}
}
private:
int _x;
int _y;
Node * _parent;
std::vector<Node *> _childs;
};
class Terrain {
public:
Terrain(Bitmap *bitmap, std::vector<Sensor *> & sensors) :_bitmap(bitmap), _sensors(sensors) {
}
~Terrain(){
std::vector<Sensor *>::iterator itr = _sensors.begin();
while(itr != _sensors.end()) {
delete (*itr);
}
_sensors.erase(_sensors.begin(), _sensors.end());
delete _bitmap;
}
void traversePath() {
if(_bitmap == NULL) {
return;
}
for(int y = 0; y < _bitmap->getHeight(); ++y){
for (int x =0; x < _bitmap->getWidth(); ++x) {
std::vector<Sensor *>::iterator itr = _sensors.begin();
while(itr != _sensors.end()) {
if((*itr)->hitTest(x,y)) {
_bitmap->setBit(x,y, eSensor);
}
++itr;
}
}
}
std::queue<Node *> queue;
Node * root = new Node(-1,-1,NULL);
for(int y = 0; y < _bitmap->getHeight(); ++y) {
if(_bitmap->getBit(0, y) == eEmpty) {
Node * node = new Node(0,y,root);
_bitmap->setBit(0,y, eVisited);
queue.push(node);
root->addChild(node);
}
}
Node * destination = NULL;
while(!queue.empty()){
Node * node = queue.front();
if(_bitmap->getBit(node->getX() + 1, node->getY()) == eEmpty){
Node *child = new Node (node->getX() + 1, node->getY(), node);
_bitmap->setBit(node->getX() + 1, node->getY(), eVisited);
queue.push(child);
node->addChild(child);
if(node->getX() +1 == _bitmap->getWidth() -1) {
destination = child; //We reached the right side. So break
break;
}
}
if(_bitmap->getBit(node->getX(), node->getY() + 1) == eEmpty){
Node *child = new Node (node->getX(), node->getY() + 1, node);
_bitmap->setBit(node->getX(), node->getY() + 1, eVisited);
queue.push(child);
node->addChild(child);
}
if(_bitmap->getBit(node->getX(), node->getY() - 1) == eEmpty){
Node *child = new Node (node->getX(), node->getY() - 1, node);
_bitmap->setBit(node->getX(), node->getY() - 1, eVisited);
queue.push(child);
node->addChild(child);
}
queue.pop();
}
while(destination != NULL) {
_bitmap->setBit(destination->getX(), destination->getY(), ePath);
destination = destination->getParent();
}
while(!queue.empty()) {
queue.pop();
}
_bitmap->printBitmap();
//Delete the tree
queue.push(root);
while(!queue.empty()){
Node * node = queue.front();
node->addChildsInQueue(queue);
delete node;
queue.pop();
}
}
private:
Bitmap * _bitmap;
std::vector<Sensor *> _sensors;
};
int _tmain(int argc, _TCHAR* argv[])
{
Bitmap * bitmap = new Bitmap(20, 20);
std::vector<Sensor *> sensors;
sensors.push_back(new Sensor(4, 4, 4));
sensors.push_back(new Sensor(11, 11, 4));
sensors.push_back(new Sensor(15, 15, 4));
sensors.push_back(new Sensor(14, 5, 4));
Terrain terrain(bitmap, sensors);
terrain.traversePath();
getchar();
return 0;
}
I beleieve this should be a dynamic obstacle resolving problem.
The player must start from top of Rectangle to bottom at shortest distance. The shortest distance will be a vertical line from top to bottom. But there are obstacles in shape of circles which may be intersecting. The player must avoid them.
I think the logic to solve should be as below:
a) The player start from top and tries to move bottom in straight vertical line.
b) If he encounters an obstacle the program will call method goLeftOrRight(). This method will determine how many intersecting circle are to right and how many are to left. The direction with least X-direction movement will be taken up.
NOTE: Above is a workable but still a bit naive implementation. It may happen that suppose right direction has two obstacles and left have four. But right also have an intersecting obstacle just below the obstacle at its rightmost corner which further has 4 more intersecting obstacles on its right. In that case Right one will be more costly. Therefore the best solution will be we determine the total X-direction movement with all intersections horizontal or vertical and take that direction.
I beleieve this should be a dynamic obstacle resolving problem.
The player must start from top of Rectangle to bottom at shortest distance. The shortest distance will be a vertical line from top to bottom. But there are obstacles in shape of circles which may be intersecting. The player must avoid them.
I think the logic to solve should be as below:
a) The player start from top and tries to move bottom in straight vertical line.
b) If he encounters an obstacle the program will call method goLeftOrRight(). This method will determine how many intersecting circle are to right and how many are to left. The direction with least X-direction movement will be taken up.
NOTE: Above is a workable but still a bit naive implementaion. It may happen that suppose right direction has two obstacles and left have four. But right also have an intersecting obstacle just below the obstacle at its rightmost corner which further has 4 more intersecting obstacles on its right. In that case Right one will be more costly. Therefore the best solution will be we determine the total X-direction movement with all intersections horizontal or vertical and take that direction.
public class Maze {
private final Point upperCorner;
private final Point lowerCorner;
private final int radius;
private final Point [] sensors;
public Maze(Point upperCorner, Point lowerCorner, int radius, Point[] sensors) {
this.upperCorner = upperCorner;
this.lowerCorner = lowerCorner;
this.radius = radius;
this.sensors = sensors;
}
public List<Point> getPath() {
boolean [][] map = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];
for (Point sensor : sensors) {
for (int i = sensor.y - radius; i <= sensor.y + radius; i++) {
for (int j = sensor.x - radius; j <= sensor.x + radius; j++) {
if (i >= lowerCorner.y && i <= upperCorner.y && j >= upperCorner.x && j <= lowerCorner.x) {
map[i][j] = true;
}
}
}
}
for (int i = lowerCorner.y; i <= upperCorner.y; i++ ) {
if (map[i][upperCorner.x] == false) {
// DFT search for solution
Stack<Point> stack = new Stack<>();
stack.add(new Point(i, upperCorner.x));
boolean [][] visited = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];
while (!stack.isEmpty()) {
Point p = stack.pop();
if (visited[p.y][p.x]) {
continue;
}
visited[p.y][p.x] = true;
if (p.x == lowerCorner.x) {
// we found solution
// TODO: get the path
}
// add all child to stack if they are not visited
if (p.y+1 <= upperCorner.y && map[p.y+1][p.x] == false) {
stack.add(new Point(p.y+1, p.x));
}
if (p.y-1 >= lowerCorner.y && map[p.y-1][p.x] == false) {
stack.add(new Point(p.y-1, p.x));
}
if (p.x+1 >= lowerCorner.x && map[p.y][p.x+1] == false) {
stack.add(new Point(p.y, p.x+1));
}
if (p.x-1 >= upperCorner.x && map[p.y][p.x-1] == false) {
stack.add(new Point(p.y, p.x-1));
}
}
}
}
// no solution
return null;
}
}
First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.
Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.
With this setup, the problem becomes a standard A* search.
First of all, we need to cast this problem into a discrete one. We can calculate the pair-wise distances between sensor discs and find the smallest "gap". This should give a heuristics to how fine our grid should be. For instance, if there's only a narrow passage of 0.01 in the middle, guarded by two sensors, our agent needs to be able to move in delta of at most that size to maneuver through.
Once we put everything on a grid, we need a way to mark cells that are covered by sensors. One way is to just store this information in a bit array, but if the grid is very large this is inefficient both in time and space. Instead, we can store the coordinates of sensors in a kd-tree, and to know if a cell is covered we gather all sensors at most R away from the cell and test each one's coverage, where R is the largest radius of all sensors. This doesn't work well if sensors overlap a lot and have a rather disparaging radii. Again, this is a trade-off with the bit array method.
With this setup, the problem becomes a standard A* search.
The idea is to merge sensors crossed with other into sensor ranges. Keep track of the crosses with rectangle boundaries of sensor rangers. If there does not exist any sensor range with valid left and right cross, then there is a horizontal path. Otherwise not path. For vertical path, checking the top and bottom cross.
If the path exists, then work out the first pair of complement range of sensors range's cross with rectangle boundaries. Return the mid point of the very first ranges of left and right ranges for horizontal path. Return the mid point of the very first ranges of top and bottom ranges for a vertical path.
Details please see: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-find-path.html
Both Python and C++ implementations are provided.
//Assumption:When finding a path from start to end you can only move to the right or down.
//Time complexity: O(mn + m+n).Space: O(mn)
public class Point
{
double x;
double y;
public class Point(double r, double c)
{
x=r;
y=c;
}
public int hashCode()
{
return Objects.hash(new Double(x),new Double(y));
}
public boolean equals(Object obj)
{
if(obj==null|| !obj instanceOf(Point))
{
return false;
}
Point p=(Point)obj;
return p.hashCode()==hashCode();
}
}
public ArrayList<Point> findPath(Point top,Point bott,Point[] sensors,double r)
{
if(top==null||bott==null||sensors==null)
{
return null;
}
ArrayList<Point> path=new ArrayList<Point>();
HashMap<Point,Boolean> mp=getBlockedZones(sensors,top,bott,r);
for(doube startX=top.x; startX<=bott.x;startX++)
{
if(dfs(startX,top,bott,mp,path))
{
break;
}
}
return path;
}
private boolean dfs(Point start, Point top,Point bott, HashMap<Point,Boolean> blocked, ArrayList<Point> pth)
{
if(start.y==bott.y)
{
pth.add(start);
return true;
}
if(blocked.containsKey(start) || (start.x<top.x) || (start.x>bott.x) || (start.y>top.y) || (start.y<bott.y))
{
return false;
}
Point next=new Point(start.x+1.0,start.y);
if(dfs(next,top,bott,blocked,pth))
{
pth.add(0,next);
return true;
}
next=new Point(start.x,start.y+1.0);
if(dfs(next,top,bott,blocked,pth))
{
pth.add(0,next);
return true;
}
blocked.put(start,false);
return false;
}
private HashMap<Point,Boolean> getBlockedZones(Point[] sensors,Point t,Point b, double rad)
{
HashMap<Point,Boolean> blocked=new HashMap<Point,Boolean>();
for(Point s:sensors)
{
updateBlocked(blocked,s,t,b,rad);
}
return blocked;
}
private void updateBlocked(HashMap<Point,Boolean> mp, Point sensor,Point top,Point bott, double rad)
{
Deque<Point>q=new LinkedList<Point>();
q.addFirst(sensor);
mp.put(sensor,true);
while(!q.isEmpty())
{
Point top=q.removeFirst();
for(double i=top.x-1.0;i<=top.x+1.0;i++)
{
for(double j=top.y-1.0;j<=top.y+1.0;j++)
{
Point p=new Point(i,j);
if(inBounds(p,sensor,rad,top,bott) && !mp.containsKey(p))
{
mp.put(p,true);
q.addLast(p);
}
}
}
}
}
private boolean inBounds(Point p,Point s, double r, Point top,Point bott){
return(p.x>=top.x && p.x<=bott.x) && (p.y>=top.y && p.y<=bott.y) && dist(p,s)<=r);
}
private double dist(Point f,Point g)
{
double xDist=Math.abs(f.x-g.x);
double yDist=Math.abs(f.y-g.y);
return Math.sqrt(Math.pow(xDist,2) + Math.pow(yDist,2));
}
Why BFS won't work on this?
- Vivek August 22, 2016