CommonSenseRobotics-GuessDeltaGame.cpp

#include <iostream>

#define MAX_SIZE 1000
#define SHIFT MAX_SIZE/2

using namespace std;

bool check(int dx, int dy, int round, bool board[][MAX_SIZE]) {
	cout << "dx="<< dx << ",dy=" << dy << " [" << (dx*round) << "," << (dy*round) << "]" << endl;
	return board[SHIFT + dx*round][SHIFT + dy*round];
}

bool guess(int round, bool board[][MAX_SIZE]) {
	static int n=0;
	static int x=0;
	static int y=0;
	bool res = check(x,y, round, board);

	if (x==y && x>-1) {
		n++;
		x=n-1;
		y=n;
	}
	else if (y==n && x > -n) {
		x--;
	}
	else if (x==-n && y > -n) {
		y--;
	}
	else if (y==-n && x < n) {
		x++;
	}
	else if (x==n && y < n) {
		y++;
	}

	if (res)
		cout << "Found! (after " <<  round << " iterations)" << endl;

	return res;
}

/* Guess: round[dx,dy]
	21[ 2,-2] 22[ 2,-1] 23[ 2, 0] 24[ 2, 1] 25[ 2, 2]
	20[ 1,-2]  7[ 1,-1]  8[ 1, 0]  9[ 1, 1] 10[ 1, 2]
	19[ 0,-2]  6[ 0,-1]  1[ 0, 0]  2[ 0, 1] 11[ 0, 2]
	18[-1,-2]  5[-1,-1]  4[-1, 0]  3[-1, 1] 12[-1, 2]
	17[-2,-2] 16[-2,-1] 15[-2, 0] 14[-2, 1] 13[-2, 2]
	
	Time complexity: O(1+2*max(x,y))^2
*/

int main() {
	int dx = 3;
	int dy = 3;

	int round = 1;
	bool board[MAX_SIZE][MAX_SIZE] = {false};

	while (!guess(round, board)) {
		board[SHIFT + dx*round][SHIFT + dy*round] = false;
		round++;
		board[SHIFT + dx*round][SHIFT + dy*round] = true;
	}
}