seek

seek.c

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char byte;
#define STEP 8
#define LP  1023
#define NEXT_STEP(t, d) do{path[max_step-step]=(t);_run(_pass_func[path[max_step-step]](number), step-1, (d));}while(0)
#define MASK(v)      (((v)-1)>>1)
#define _pass(d, n, t) (map[(d)-1][(n)-1][(t)-1])
static byte path[LP+1] = {0};
static int max_step = STEP;
static char* _desc[] = {
	"null",
	"+7 ",
	"/2 ",
	"*3 ",
	"-5 "
};

static byte map[3][4][4] = {
	{{0, 2, 3, 3}, {2, 0, 3, 3}, {0, 0, 0, 2}, {0, 0, 2, 0}},
	{{0, 1, 0, 0}, {1, 0, 0, 0}, {3, 3, 0, 1}, {3, 3, 1, 0}},
	{{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 2}, {0, 0, 2, 0}}
};

static int pass0(int number){
	return number+7;
}

static int pass1(int number){
	return number/2;
}

static int pass2(int number){
	return number*3;
}

static int pass3(int number){
	return number-5;
}

typedef int (*pass)(int);
static pass _pass_func[] = {
	NULL,
	pass0,
	pass1,
	pass2,
	pass3	
};

static void print_path(){
	int i=0;
	while(path[i]){
		printf("%s ", _desc[path[i++]]);
	}
	printf("\n");
}

static void _run(int number, int step, int dir){
	if(step==max_step){				          // goto step 1
		NEXT_STEP(1, 1);
		NEXT_STEP(2, 1);
	}else if(step == 0){ 					  // end step
		if(number == 2012 && MASK(path[max_step-step-1])){
			printf("find it !\n");
			print_path();
			exit(0);
		}
		return;
	}else{							  // other step
		int i, d;
		for(i=1; i<=4; i++){
			if(path[max_step-step-1]==i || !(d=_pass(dir, path[max_step-step-1], i)))
				continue;
			NEXT_STEP(i, d);
		}
	}
}

int main(int argc, char const *argv[])
{
	int i;
	for(i=2; i<=LP; i++){
		_run(2011, max_step=i, 0);
		printf("not find it! max step = %d\n", max_step);
	}
	return 0;
}