CareerCup

This is similar to the Travelling Salesman problem, which is NP-hard.

- If the number S of specific islands is quite small, say <= 20, we can perform S+1 Breadth First Searches to find all pairs of distances between the S islands and the initial position. Then, we can check all permutations of the S islands and calculate the cost of the possible paths "Initial pos -> Island_1 -> .. Island_S" using the distances calculated above. We can use dynamic programming to find the best path. The DP state can be the current specific island and a bitmask with the covered islands so far.
The running time will be O(S^2 * 2^S + S * N^2).
Note that 2^20 is about 1 million which allows this solution to be fast.

- If there are more specific islands, we can try A*. I don't know much about heuristics but we should try to discuss them with the interviewer. Like using the number of the islands covered so far and the current cost.

I think Gedo Mazo might be right....

He is saying use grid's geometric properties instead of viewing this problem in isolation as an abstract graph.

The example that Miguel posted seems misleading, since on a grid it would look something like
this:

###############
E_ _D_ _A_B_ _C
###############
so the distances are from A { B=1, D=2, C=3, E=4}
Select B.
from B { D=3, C=2, E=5}
Select C.
from C {D=5, E=7}
Select D
From D { E=2}
select E
total : 1+2+5+2 = 10.



Maybe the question poster should add if edges between the given islands need to be calculated or are already provided ?

I think this problem is not asked by FB, but it is asked in Illuminati Hiring Challenge that ended today on HackerRank.com. Only the words have been changed, problem seems to be exactly what was asked there.

Hi, i implemented this algo...i dont print NOT POSSIBLE TO DELIVER ALL...but the rest should be there...

please give me some feedback.

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <stack>
using namespace std;

const int grid_x_max = 6;
const int grid_y_max = 6;
array<array<int, grid_y_max+1>, grid_y_max+1> A;
	
class pos 
{
public:
    int x;
	int y;
    
    pos(): x(0), y(0) {}
	pos(int x_, int y_): x(x_), y(y_) {}
    
    pos &operator=(const pos &rhs) {
      	x = rhs.x;
      	y = rhs.y;
      	return *this;
    }
    
    bool operator==(const pos &rhs) {
      	return x == rhs.x && y == rhs.y;
    }
    
    bool operator!=(const pos &rhs) {
    	return x != rhs.x && y != rhs.y;
    }
};

void init_grid(vector<pos> &dang_islands) {
	for(int x = 0; x <= grid_x_max; x++) {
		for(int y = 0; y <= grid_y_max; y++) {
			bool allowed_pos = true;

			for(int i = 0; i < dang_islands.size(); i++) {
				if(x == dang_islands[i].x && y == dang_islands[i].y) {
					allowed_pos = false;
					break;
				}	
			}

			if(allowed_pos) {
				A[x][y] = 1;
			}
			else { 
				A[x][y] = 0;
			}
		}
	}	
}

bool is_valid_coord(pos &current_pos) {
	if((A[current_pos.x][current_pos.y] == 1) && (current_pos.x >= 0 && current_pos.x <= grid_x_max) && (current_pos.y >= 0 && current_pos.y <= grid_y_max)) {
		return true;
	}

	return false;
}

float calc_heuristic(pos &next_pos, vector<pos> &spec_islands) {
	set<float> heuristic_dist;

	for(int i = 0; i < spec_islands.size(); i++) {
		float dist = sqrt(pow(next_pos.x - spec_islands[i].x, 2) + pow(next_pos.y - spec_islands[i].y, 2));
		heuristic_dist.insert(dist);
	}

	return *heuristic_dist.begin();
}

void set_grid_pos_invalid(pos &current_pos) {
	A[current_pos.x][current_pos.y] = 0;
}

bool get_next_move(pos &current_pos, vector<pos> &spec_islands) {
	                               // Right,  Down,  Left,  Up 
	vector<pos> next_possible_move = {{-1,0}, {0,1}, {1,0}, {0,-1}};
	map<float, pos> distance_map;
	pos start_pos = current_pos;
	
	for(int i = 0; i < next_possible_move.size(); i++) {
		pos next_pos(current_pos.x + next_possible_move[i].x, current_pos.y + next_possible_move[i].y);

		if(is_valid_coord(next_pos)) {
			float heuristic = calc_heuristic(next_pos, spec_islands);
			distance_map.insert(make_pair(heuristic, next_pos));
		}
	}
	
	if(distance_map.size() > 0) {
		current_pos = distance_map.begin()->second;
	}
	
	if(start_pos == current_pos) { // no move was possible
		return false;
	}
	
	return true;
}

bool is_current_pos_at_dest(pos &current_pos, vector<pos> &spec_islands) {
	for(int i = 0; i < spec_islands.size(); i++) {
		if(current_pos.x == spec_islands[i].x && current_pos.y == spec_islands[i].y) {
			return true;
		}
	}
	
	return false;
}

pos move_to_spec_island(pos &start_pos, vector<pos> &spec_islands, vector<pos> &dang_islands) {
	stack<pos> movements;
	bool move_possible = false;
	bool dest_reached = false;
	bool do_move = true;
	pos current_pos = start_pos;
	
	init_grid(dang_islands);
	set_grid_pos_invalid(current_pos);
	movements.push(current_pos);
			
	do {
		do_move = true;
		
    	move_possible = get_next_move(current_pos, spec_islands);
    	set_grid_pos_invalid(current_pos);
       	dest_reached = is_current_pos_at_dest(current_pos, spec_islands);
       	
     	// Backtrack
       	if(!move_possible && !dest_reached) {
       		if(!movements.empty()) {
       			do {
       				pos prev_pos = movements.top();
       				movements.pop();
       				
       				if(prev_pos != current_pos) {
       					current_pos = prev_pos;
       					break;
       				}
       				
       				current_pos = prev_pos;
       			}while(!movements.empty());
       		}
       		else {
       			do_move = false;
       		}
       	}
       	else {
       		movements.push(current_pos);
       	}
       	
       	cout << "x: " << current_pos.x << ", y: " << current_pos.y << endl;
	}while(do_move && !dest_reached);
	
    return current_pos;
}

void dest_visited(pos &current_pos, vector<pos> &spec_islands) {
	for(int i = 0; i < spec_islands.size(); i++) {
		if(current_pos.x == spec_islands[i].x && current_pos.y == spec_islands[i].y) {
			spec_islands.erase(spec_islands.begin() + i);
			break;
		}
	}
}

int main() {
	vector<pos> spec_islands = {{4,6}, {5,5}, {3,3}, {1,2}};
	vector<pos> dang_islands = {{3,6}, {2,5}, {2,2}, {0,3}, {1,3}, {2,3}};
	pos start_pos = {1,6};
	pos current_pos = start_pos;
	
	while(!spec_islands.empty()) {
		cout << "move to dest: " << endl;
		
		start_pos = current_pos;
    	current_pos = move_to_spec_island(start_pos, spec_islands, dang_islands);
    	if(current_pos == start_pos) {
    		break;
    	}
    	dest_visited(current_pos, spec_islands);
    	
    	cout << '\n';
	}
}

this could be done by BFS several times.

1) find the first reach able island by BFS from start point.
and let's count the #mov
2) empty that start point, and set the node the we found from previous as start point and repeat 1) again





int valid(vector<vector<int>> &vv, int n, int nx, int ny, queue<Point*> &nq)
{
if (nx >= 0 && nx < n && ny >=0 && ny < n && (vv[nx][ny] == 0 || vv[nx][ny] == 1))
{
Point * p = new Point(nx, ny);
nq.push(p);
int ret = vv[nx][ny];
vv[nx][ny] = -1;
return ret;
}
return -1;
}

int traval(int n, vector<Point> &spec, vector<Point> &dan, Point* start){
// no need to travel
if (spec.size() == 0)
return 0;

// init matrix, set as all pass
vector<vector<int>> vv;
for(int i=0; i<n; i++)
{
vector<int> v(n, 0);
vv.push_back(v);
}

// set spec points
for(int i=0; i<spec.size(); i++)
{
vv[spec[i].x][spec[i].y] = 1;
}

// set dangerous points
for(int i=0; i<dan.size(); i++)
{
vv[dan[i].x][dan[i].y] = 2;
}
int mov = 0;
for(int i=0; i<spec.size(); i++)
{
int nmov = nextNode(n, vv, start);
if (nmov > 0){
mov +=nmov;
}
else{ // no possible path
return -1;
}
}
return mov;
}

int nextNode(int n, vector<vector<int>> &vv, Point* &start)
{
// reset
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if (vv[i][j] < 0)
{
vv[i][j] = 0;
}
}
}

// BFS, start from start point
queue<Point*> q;
vv[start->x][start->y] = -1;
q.push(start);

int mindepth = INT_MAX;
int depth = 0;
while(!q.empty())
{
queue<Point*> nq;
depth ++;
while(!q.empty())
{
// for each current, add children
Point* p = q.front();
q.pop();
if (valid(vv, n, p->x-1, p->y, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x, p->y-1, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x+1, p->y, nq) == 1)
{
start = p;
return depth;
}
if (valid(vv, n, p->x, p->y+1, nq) == 1){
start = p;
return depth;
}
}
q = nq;
}

return 0; // not possible
}

Given a pair of nodes <n1,n2> meaning the shortest path from n1 to n2, we could build DP[x][y][steps] to solve it. Each node could possibly be reached through 4 directions, so DP[x][y][steps] = min(DP[x-1][y][steps-1] + 1, DP[x][y-1][steps-1] + 1, DP[x+1][y][steps-1] + 1,DP[x][y+1][steps-1] + 1) if corresponding islands[x-1/x+1][y-1/y+1] is safe. After this is computed for any pair of islands (which I think will take O(N^3 * N^2)), then search minimal spanning tree on the graph covering all necessary islands.

Its a simple MST problem. There is no condition that the tour should end at the starting point, therefore its not a TSP problem.

I would use Prims since edges need to be calculated.

Edge calculation can be tricky. I would use the line formula to get the straight line between two "islands". , if it has any objectionable islands, just move around them.
If the dangerous islands are together and form some random shape, then go around the shortest periphery.

Repeat that for all the islands, then you get a set of edges, select the one with least number of steps and add it to your edge set.

proceed till no vertices are left untouched.

MST

variation of flood fill algorithm