2012 maze http://www.matrix67.com/blog/archives/4790

gistfile1.cpp

#include <string.h>
#include <stdio.h>
#include <queue>

#define LOWER 0
#define UPPER 10000

#define S_MID_TOP_TO_LEFT 0
#define S_MID_BOTTOM_TO_LEFT 1
#define S_LEFT_TOP_TO_MID 2
#define S_LEFT_BOTTOM_TO_MID 3
#define S_RIGHT_TOP_TO_MID 4
#define S_RIGHT_BOTTOM_TO_MID 5
#define S_MID_TOP_TO_RIGHT 6
#define S_MID_BOTTOM_TO_RIGHT 7

std::pair<bool,int> path_1 (int i) { return std::make_pair(i+7 > LOWER && i+7 < UPPER, i + 7); }
std::pair<bool,int> path_2 (int i) { return std::make_pair(i/2 > LOWER && i/2 < UPPER && i%2 == 0, i/2); }
std::pair<bool,int> path_3 (int i) { return std::make_pair(i*3 > LOWER && i*3 < UPPER, i*3); }
std::pair<bool,int> path_4 (int i) { return std::make_pair(i-5 > LOWER && i-5 < UPPER, i-5); }
typedef std::pair<bool,int> (*path) (int i);

path routes[8] = { path_1, path_2, path_1, path_2, path_3, path_4, path_3, path_4 };

char (*dp)[8];
std::queue<std::pair<int, int> > search;

bool check_path(int i, int step, int route) {
	std::pair<bool,int> t = routes[route](i);
	if (t.first && dp[t.second][route] == 0) {
		dp[t.second][route] = step;
		search.push(std::make_pair(t.second, route));
		return t.second == 2012;
	}
	return false;
}

void reverse(int step, int route);

int main () {
	dp = new char[UPPER-LOWER][8];
	memset(dp, (UPPER-LOWER)*8, 0);
	dp = &dp[LOWER];
	search.push(std::make_pair(2018, S_LEFT_TOP_TO_MID));
	dp[2018][S_LEFT_TOP_TO_MID] = 1;

	while (!search.empty()) {
		std::pair<int, int> p = search.front();
		search.pop();
		char step = dp[p.first][p.second] + 1;
		//printf ("step %d, year %d, route %d\n", step, p.first, p.second);
		switch (p.second) {
			case S_MID_TOP_TO_LEFT:
				check_path(p.first, step, S_LEFT_BOTTOM_TO_MID);
				break;
			case S_MID_BOTTOM_TO_LEFT:
				check_path(p.first, step, S_LEFT_TOP_TO_MID);
				break;
			case S_LEFT_TOP_TO_MID:
				check_path(p.first, step, S_MID_BOTTOM_TO_LEFT);
				if (check_path(p.first, step, S_MID_TOP_TO_RIGHT))
					reverse(step, S_MID_TOP_TO_RIGHT);
				if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT))
					reverse(step, S_MID_BOTTOM_TO_RIGHT);
				break;
			case S_LEFT_BOTTOM_TO_MID:
				check_path(p.first, step, S_MID_TOP_TO_LEFT);
				if (check_path(p.first, step, S_MID_TOP_TO_RIGHT))
					reverse(step, S_MID_TOP_TO_RIGHT);
				if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT))
					reverse(step, S_MID_BOTTOM_TO_RIGHT);
				break;
			case S_RIGHT_TOP_TO_MID:
				check_path(p.first, step, S_MID_TOP_TO_LEFT);
				check_path(p.first, step, S_MID_BOTTOM_TO_LEFT);
				if (check_path(p.first, step, S_MID_BOTTOM_TO_RIGHT))
					reverse(step, S_MID_BOTTOM_TO_RIGHT);
				break;
			case S_RIGHT_BOTTOM_TO_MID:
				check_path(p.first, step, S_MID_TOP_TO_LEFT);
				check_path(p.first, step, S_MID_BOTTOM_TO_LEFT);
				if (check_path(p.first, step, S_MID_TOP_TO_RIGHT))
					reverse(step, S_MID_TOP_TO_RIGHT);
				break;
			case S_MID_TOP_TO_RIGHT:
				check_path(p.first, step, S_RIGHT_BOTTOM_TO_MID);
				break;
			case S_MID_BOTTOM_TO_RIGHT:
				check_path(p.first, step, S_RIGHT_TOP_TO_MID);
				break;
		}
	}

}


int reverse_path_1 (int i) { return i-7; }
int reverse_path_2 (int i) { return i*2; }
int reverse_path_3 (int i) { return i/3; }
int reverse_path_4 (int i) { return i+5; }

typedef int (*reverse_path) (int i);
reverse_path reverse_routes[8] = { reverse_path_1, reverse_path_2, reverse_path_1, reverse_path_2, reverse_path_3, reverse_path_4, reverse_path_3, reverse_path_4 };

#define reverse_check_path(year, step, previous_route) \
{ \
	if (dp[year][previous_route] == step) { \
		route = previous_route; \
		continue; \
	} \
}

const char* route_text(int route) {
	switch (route) {
		case 0:
			return "+7";
		case 1:
			return "/2";
		case 2:
			return "+7";
		case 3:
			return "/2";
		case 4:
			return "*3";
		case 5:
			return "-5";
		case 6:
			return "*3";
		case 7:
			return "-5";
	}
}

// back trace to find path O(step)
void reverse(int step, int route) {
	printf("Total step: %d, path below (reversed):\n", step);
	int year = 2012;
	for (step -= 1; step >= 0; step -= 1) {
		printf ("step %d, year %d (%s)\n", step+1, year, route_text(route));
		year = reverse_routes[route](year);
		switch (route) {
			case S_LEFT_BOTTOM_TO_MID:
				reverse_check_path(year, step, S_MID_TOP_TO_LEFT);
				break;
			case S_LEFT_TOP_TO_MID:
				reverse_check_path(year, step, S_MID_BOTTOM_TO_LEFT);
				break;
			case S_MID_TOP_TO_LEFT:
				reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID);
				reverse_check_path(year, step, S_RIGHT_TOP_TO_MID);
				reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID);
				break;
			case S_MID_TOP_TO_RIGHT:
				reverse_check_path(year, step, S_LEFT_TOP_TO_MID);
				reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID);
				reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID);
				break;
			case S_MID_BOTTOM_TO_LEFT:
				reverse_check_path(year, step, S_LEFT_TOP_TO_MID);
				reverse_check_path(year, step, S_RIGHT_TOP_TO_MID);
				reverse_check_path(year, step, S_RIGHT_BOTTOM_TO_MID);
				break;
			case S_MID_BOTTOM_TO_RIGHT:
				reverse_check_path(year, step, S_LEFT_TOP_TO_MID);
				reverse_check_path(year, step, S_LEFT_BOTTOM_TO_MID);
				reverse_check_path(year, step, S_RIGHT_TOP_TO_MID);
				break;
			case S_RIGHT_BOTTOM_TO_MID:
				reverse_check_path(year, step, S_MID_TOP_TO_RIGHT);
				break;
			case S_RIGHT_TOP_TO_MID:
				reverse_check_path(year, step, S_MID_BOTTOM_TO_RIGHT);
				break;
		}
		throw "ERROR";
	}
	printf ("step %d, year %d\n", 0, 2011);
}

Worship