SenselessCoder SenselessCoder - 1 month ago
123 0

No description

C

Izi liek dat

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

#define MAX_DIGITS 10
#define MAX_VARIABLES 9
#define MAX_EXPRESSION_SIZE 11

int IsImpossible(char* expression) {
	// if all letters are same or end letters are same, no solution
	if(
		(expression[0] == expression[4] && expression[0] == expression[8]) ||
	    (!strncmp(expression, expression + 4, 3) && !strncmp(expression, expression + 8, 3))
	  )
	  	return 1;
	return 0;
}

int ArePointersAssigned(int*** pointers) {
	for(int i = 0; i < MAX_VARIABLES; ++i) {
		if(**pointers[i] == -1)
			return 0;
	}
	return 1;
}

int evaluate(int*** pointers) {
	int ABC = *(*pointers[0]) * 100 + *(*pointers[1]) * 10 + *(*pointers[2]);
	int DEF = *(*pointers[3]) * 100 + *(*pointers[4]) * 10 + *(*pointers[5]);
	int GHI = *(*pointers[6]) * 100 + *(*pointers[7]) * 10 + *(*pointers[8]);
	if (ABC + DEF == GHI) { // since we use dfs, if this is a solution simply return it
		//printf("%d + %d = %d\n", ABC, DEF, GHI);
		return 1;
	}
	return 0;
}

// use the solved pointer to escape recursion early
// check_end checks if we reached 6 for the 2nd time, if it's first time we ignore (because it's start state)
void form_combos(int pool[], int pool_count, int object_count, int*** pointers, int* solved) {
	if(object_count == MAX_DIGITS - 1)
		object_count = 0;
	if(*solved) // if a branch solved this, escape recursion
		return;
	if (ArePointersAssigned(pointers)) { // that means we got a full equation set
		*solved = evaluate(pointers);
		if(*solved)
			return;
	}
	int *pool_end = pool + pool_count - 1;
	for (int p = pool_count - 1; p >= 0 && !*solved; p--) {
		int sample = pool[p];  // take one out
		pool[p] = *pool_end;   // replace it with the end
		int temp = **pointers[object_count];
		if(**pointers[object_count] == -1)
			**pointers[object_count] = sample;
		form_combos(pool, pool_count - 1, object_count + 1, pointers, solved);
		pool[p] = sample;      // restore pool item
		if(!*solved)
			**pointers[object_count] = temp;
	}
}

int main() {
	char expression[MAX_EXPRESSION_SIZE] = { 0 };
	printf("Enter the formula: ");
	scanf("%s", expression);
	while(expression[0] != '-') {
		if(IsImpossible(expression))
			printf("No solution!\n");
		else {
			int digits[MAX_DIGITS] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
			int object[MAX_VARIABLES] = { -1, -1, -1, -1, -1, -1, -1, -1, -1 }; // stack for dfs
			int *A = &object[0], *B = &object[1], *C = &object[2], 
				*D = &object[3], *E = &object[4], *F = &object[5], 
				*G = &object[6], *H = &object[7], *I = &object[8];
			// set same pointers
			int** pointers[MAX_VARIABLES] = { &A, &B, &C, &D, &E, &F, &G, &H, &I };
		    
		    // analyze the equation
		    int var = 0;
			for(int p = 0; p < MAX_EXPRESSION_SIZE; ++p) {
				if(expression[p] >= 'A' && expression[p] <= 'I') {
					*pointers[var++] = &object[expression[p] - 'A']; // link same pointers
				}
			}
			int solved = 0, check_end = 0;
			form_combos(digits, MAX_DIGITS, MAX_DIGITS - 4, pointers, &solved);
			if(!solved) // it can be unsolvable still
				printf("No solution!\n");
			else
				printf("%d%d%d + %d%d%d = %d%d%d\n", *A, *B, *C, *D, *E, *F, *G, *H, *I);
		}
		printf("Enter the formula: ");
		scanf("%s", expression);
	}
	return 0;
}
Comments