Frog Jumping!

frogs.cpp

#include <stdio.h>
#include <string>
#include <iostream>
#include <chrono>

using namespace std;

typedef int lilly;

struct Move{
	int From;
	int To;

	Move(int from,int to){
		From = from;
		To = to;
	}
	Move(){}
};

void PrintPads(lilly pads[],int size){
	for(int i =0; i < size;i++){
		printf("%i ",pads[i]);
	}
	printf("\n");
}

struct moves_strct{
	Move moves[50];
	int size; 
};

lilly* padBuffer;
moves_strct* moveBuffer;

inline void GenMoves(lilly pads[],int size, int depth){
	auto moves = &moveBuffer[depth];	
	int count = 0;
	for(int i = 0; i < size; i++){
		int pad = pads[i];		
		if(pad > 0){
			int back = i-pad;
			int forward = i+pad;
			if(back >=0 && pads[back] > 0){
				moves->moves[count].From = i;
				moves->moves[count].To = back;
				count++;
			}
			if(forward < size && pads[forward] > 0){
				moves->moves[count].From = i;
				moves->moves[count].To = forward;
				count++;
			}
		}
	}
	moves->size = count;
}


inline bool IsSymmertric(lilly pads[],int size){
	int s = 0;
	int e = size-1;

	while(s < e){
		if(pads[s] != pads[e]) return false;
		s++;
		e--;
	}
	return true;
}



lilly* Solve (lilly pads[],int size,int depth){
	if(depth >= 100){
		printf("DEPTH LIMIT REACHED");
		exit(1);
	}
	int end = size;
	if(IsSymmertric(pads,size)){
		end = size/2+1;
	}

	GenMoves(pads,end,depth);
	auto moves = &moveBuffer[depth];
	if(moves->size == 0) return nullptr;
	else{
		auto newPads = padBuffer + depth*size;
		for(int i = 0; i < moves->size; i++){
			auto move = moves->moves[i];
			memcpy(newPads,pads,size*sizeof(lilly));
			newPads[move.To] += newPads[move.From];
			newPads[move.From] = 0;
			if(newPads[move.To] == size-2) return newPads;
			auto solution = Solve(newPads,size,depth+1);
			if(solution != nullptr) return solution;
		}		
	}


	return nullptr;
}

int main(){

	auto begin = chrono::high_resolution_clock::now();

	moveBuffer = new moves_strct[100];
	for(int i = 0; i < 100; i++){
		auto move = &moveBuffer[i];
		for(int j = 0; j < 50; j++){
			move->moves[j] = Move(0,0);
		}
	}
	padBuffer = new lilly[50*100];

	for(int size = 5; size < 20; size++){

		printf("Trying %i:",size);
		auto pads = padBuffer;
		for(int i = 0; i < size;i++){
			pads[i] = 1;
		}
		pads[1] = 0;
		pads[size-2] = 0;

		auto solution = Solve(pads,size,1);
		if(solution != nullptr){
			printf("SOLUTION EXISTS\n");
			PrintPads(solution,size);
		}
		else{
			printf("SOLUTION DOES NOT EXISTS\n");
		}		
	}
	auto end = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<std::chrono::milliseconds>(end-begin).count();
	printf("Duration:%i",duration);
	string str;
	getline(cin,str);
	return 0;
}