SenselessCoder SenselessCoder - 1 month ago
131 0

No description

C

AASDASD

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

#define MAX_EXPRESSION_SIZE 11 + 1
#define MAX_VARIABLES 9

int zero_nine[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int one_nine[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

struct variable {
	int coefficient;
	int* ptr;
	int side;
	int* value_set;
	unsigned value_count;
};

typedef struct variable Variable;

struct equation {
	Variable* variables[9]; // max
	unsigned var_count;
};

typedef struct equation Equation;

int int_pow(int n, int k) {
	int res = 1;
	for(int i = 0; i < k; ++i)
		res *= n;
	return res;
}

void AddVariable(Equation* E, Variable* V) {
	E->variables[E->var_count++] = V;
}

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;
}

char* evaluate(char* expression) {
	char* res;
	
	// check for impossible cases first
	if(IsImpossible(expression)) {
		res	= (char *) malloc(sizeof(char) * strlen("No Solution!"));
		strcpy(res, "No Solution!");
		return res;
	}
	res = (char *) malloc(sizeof(char) * MAX_EXPRESSION_SIZE);
	// now try to find solutions, first describe the given characters as equations
	Equation E;
	E.var_count = 0;
	int a = -1, b = -1, c = -1, d = -1, e = -1, f = -1, g = -1, h = -1, i = -1;
	int* max_variables[MAX_VARIABLES] = { &a, &b, &c, &d, &e, &f, &g, &h, &i };
	int side_mode = 0, powcounter = 0;
	for(int j = 0; j < MAX_EXPRESSION_SIZE; ++j) {
		if(expression[j] == '+')
			continue;
		if(expression[j] == '=') {
			side_mode = 1;
			continue;
		}
		Variable* V = (Variable *) malloc(sizeof(Variable));
		// we know we always get 3 digit numbers but we can easily change if we need to
		V->coefficient = int_pow(10, 2 - (powcounter % 3));
		V->ptr = max_variables[expression[j] - 'A'];
		V->side = side_mode;
		if(!(powcounter % 3)) { // beginning of a number
			V->value_count = 9;
			V->value_set = one_nine;
		}
		else {
			V->value_count = 10;
			V->value_set = zero_nine;
		}
		AddVariable(&E, V);
		++powcounter;
	}
	--E.var_count; // we counted 1 too many in add function
	for(int j = 0; j < E.var_count; ++j)
		printf("%d %c %d\n", E.variables[j]->coefficient, 'A' + (E.variables[j]->ptr - max_variables[0]), E.variables[j]->side);
	// we got a representaion of the equation, now try to solve it
	int solved = 0;
	// O(N), where N is number of distinct variables. All of them have a constant x9 multiplier.
	// An optimization we can do is, we first assign possible max values to rhs number, then go down. We need max number.
	do {
		// try to assign values to all variables and try if it solves the equation
		for(int j = E.var_count; j >= 0; --j) {
			// first assign rhs numbers (check if assigned by using -1 equality, reset to -1 after computation)
			for(int k = E.variables[j]->value_count; k >= 0; --k) {
				if(*(E.variables[j]->ptr) != -1) // can be set before due to same variable cases
					*(E.variables[j]->ptr) = E.variables[j]->value_set[k];
			}
		}
	} while(!solved);
	return res;
}

int main() {
	char expression[MAX_EXPRESSION_SIZE] = { 0 };
	do {
		printf("Enter the formula: ");
		scanf("%s", expression);
		char* res = evaluate(expression);
		printf("%s\n", res);
		free(res);
	} while(expression[0] != '-');
	return 0;
}
Comments