ladybug.c

#include <stdio.h>
#include <stdlib.h>
/*
	#define DEBUG
*/
 
#define PLUS 4
#define MINS 8
#define MULT 16
#define DIVD 32
#define NUM0 64
#define NUM1 128
#define NUM2 256
#define NUM3 512
#define NUM4 1024
#define NUM5 2048
#define NUM6 4096
#define NUM7 8192
#define NUM8 16384
#define NUM9 32768
#define EQAL 65536
 
struct solution {
	int n;
	unsigned int length;
};
 
struct stack {
	struct solution s[1000000];
	char solved[1000000];
	unsigned int slen;
	unsigned int enlargement;
};
 
 
void stack_init(struct stack *s)
{
	int i;
	for (i = 0; i < 1000000; i++){
		s->solved[i] = 'u';
	}
	s->slen = 0;
	s->enlargement = 0;
};
 
void stack_add(struct stack *s, int n, unsigned int length)
{
	if (s->solved[n+500000] == 's') {
		return;
	}
	s->solved[n+500000] = 's';
	struct solution * f = &s->s[s->slen];
	f->n = n;
	f->length = length;
	s->slen++;
};
 
int chartokey(char num)
{
	switch (num) {
		case '+': return PLUS; break;
		case '-': return MINS; break;
		case '*': return MULT; break;
		case '/': return DIVD; break;
		case '0': return NUM0; break;
		case '1': return NUM1; break;
		case '2': return NUM2; break;
		case '3': return NUM3; break;
		case '4': return NUM4; break;
		case '5': return NUM5; break;
		case '6': return NUM6; break;
		case '7': return NUM7; break;
		case '8': return NUM8; break;
		case '9': return NUM9; break;
		case '=': return EQAL; break;
		default: return 0; break;
	}
}
 
int havenum (int oper, int num)
{
	if (num < 0) {
		if (oper & MINS)
			return 1 + havenum(oper, -num);
		return 0;
	}
	if (oper & chartokey((num % 10) + '0')) {
		unsigned int divnum = num/10;
		if (divnum)
			return 1 + havenum(oper, divnum);
		return 1;
	}
	return 0;
}
 
 
int sol(int oper, struct stack *s, int stateb)
{
	unsigned int i;
 
/*
	#ifdef DEBUG
	printf("%s %i \n",__func__, n);
	#endif
*/
 
	int mindepth = 2000000000;
	for (i = 0; i<s->slen; i++) {
		struct solution *solu;
		solu = &s->s[i];
		int state =  solu->n;
		unsigned int length = solu->length;
		int depth = length + havenum(oper, state);
		if (depth != 0)
			if (depth < mindepth)
				mindepth = depth;
 
	}
	if (mindepth != 2000000000) {
		printf("%i\n", mindepth);
		return 0;
	}
 
 
 
	return 1;
}
 
int solve(struct stack *s, char * keys, unsigned int skeys, int n)
{
 
 
	int oper = 0;
	unsigned int j;
	for (j = 0; j< skeys; j++) {
		oper|=chartokey(keys[j]);
 
 
	}
 
	if (n == 0)
		{printf("0\n"); return;}
 
	stack_add(s, n, 0);
 
	while (sol(oper, s, 0))
		{
 
		int i;
		int snowlen = s->slen;
		for (i = s->enlargement; i<snowlen; i++) {
			struct solution *solu;
			solu = &s->s[i];
			int state =  solu->n;
			unsigned int length = solu->length;
			int j;
			for (j = 0; j < 9; j++) {
				if (havenum(oper, j)) {
 
 
					if (oper & PLUS) {
	#ifdef DEBUG
						printf("Adding %i %i with difficulty %u\n", state-j, j, length+2);
		#endif
						stack_add(s, state-j, length+2);
					}
					if (oper & MINS) {
	#ifdef DEBUG
						printf("Adding %i %i with difficulty %u\n", state+j, j, length+2);
		#endif
						stack_add(s, state+j, length+2);
					}
					if (oper & MULT) {
	#ifdef DEBUG
						printf("Adding %i %i with difficulty %u\n", state/j, j, length+2);
		#endif
						stack_add(s, state/j, length+2);
					}
					if (oper & DIVD) {
	#ifdef DEBUG
						printf("Adding %i %i with difficulty %u\n", state*j, j, length+2);
		#endif
						stack_add(s, state*j, length+2);
					}
 
				}
			}
 
		}
		s->enlargement = 0;
 
		}
	#ifdef DEBUG
	printf("konec\n");
		#endif
/*
	#ifdef DEBUG
	printf("%s %i \n",__func__, n);
	#endif
*/
 
 
 
}
 
int main(void)
{
/*
#ifdef DEBUG
	printf("%s \n",__func__);
#endif
*/
	while (1) {
 
 
	char keys[30];
	keys[0] = 0;
	unsigned int n;
	scanf("%20s %u",&keys, &n);
	if (keys[0] == 0)
		return 0;
 
 
/*
 
#ifdef DEBUG
	printf("[%s]", keys);
#endif
*/
	int i = strlen(keys);
 
 
/*
#ifdef DEBUG
	printf("%s \n",__func__);
#endif
*/
/*	
#ifdef DEBUG
	printf("%s \n",__func__);
#endif
*/
	struct stack stek;
	stack_init(&stek);
 
 
	solve(&stek, keys, i, n);
 
#ifdef DEBUG
	printf("---------\n\n\n");
#endif
 
 
 
 
	}
		return 0;
}