stergios/temp/stergios-int128.c

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

typedef __int128 int128_t;
typedef unsigned __int128 uint128_t;

#define HASH_SIZE 200003
//static const int128_t LIMIT = (int128_t)1000000000ULL * (int128_t)1000000000ULL * (int128_t)100ULL;
#define LIMIT 1000000000LL

static int is_prime(int128_t n) {
	if (n < 2) return 0;
	if (n % 2 == 0) return n == 2;
	for (int128_t i = 3; i * i <= n; i += 2) if (n % i == 0) return 0;
	return 1;
}

typedef struct Node {
	int128_t a, b, c;
	char move;
	struct Node *parent;
	struct Node *next;
} Node;

typedef struct VisEntry {
	int128_t a, b, c;
	struct VisEntry *next;
} VisEntry;

static VisEntry *hash_table[HASH_SIZE] = {0};

static inline uint128_t mix128(uint128_t a, uint128_t b, uint128_t c) {
    uint128_t x = a + (uint128_t)0x9e3779b97f4a7c15ULL + ((uint128_t)0x9e3779b97f4a7c15ULL << 64);
    x ^= b + ((uint128_t)0xbf58476d1ce4e5b9ULL + ((uint128_t)0xbf58476d1ce4e5b9ULL << 64)) + (x << 6) + (x >> 2);
    x ^= c + ((uint128_t)0x94d049bb133111ebULL + ((uint128_t)0x94d049bb133111ebULL << 64)) + (x << 6) + (x >> 2);
    return x;
}

static unsigned int hash_three128(uint128_t a, uint128_t b, uint128_t c) {
	uint128_t x = mix128(a, b, c);
	return (unsigned int)(x % HASH_SIZE);
}

static unsigned int hash_three(int128_t a, int128_t b, int128_t c) {
	uint128_t x = (uint128_t)(a + 0x9e3779b97f4a7c15ULL);
	x ^= (uint128_t)(b + 0xbf58476d1ce4e5b9ULL) + (x<<6) + (x>>2);
	x ^= (uint128_t)(c + 0x94d049bb133111ebULL) + (x<<6) + (x>>2);
	return (unsigned int)(x % HASH_SIZE);
}

static int visit_and_mark(int128_t a, int128_t b, int128_t c) {
	//unsigned int h = hash_three(a,b,c);
	unsigned int h = hash_three128(a,b,c);
	VisEntry *cur = hash_table[h];
	while (cur) {
		if (cur->a == a && cur->b == b && cur->c == c) return 0;
		cur = cur->next;
	}
	VisEntry *e = (VisEntry*)malloc(sizeof(VisEntry));
	if (!e) { fprintf(stderr, "Out of memory\n"); exit(1); }
	e->a = a; e->b = b; e->c = c;
	e->next = hash_table[h];
	hash_table[h] = e;
	return 1;
}

static Node *q_front = NULL;
static Node *q_back = NULL;

static void enqueue(Node *n) {
	n->next = NULL;
	if (!q_back) q_front = q_back = n;
	else {
		q_back->next = n;
		q_back = n;
	}
}

static Node *dequeue(void) {
	if (!q_front) return NULL;
	Node *r = q_front;
	q_front = q_front->next;
	if (!q_front) q_back = NULL;
	r->next = NULL;
	return r;
}

static int safe_val(int128_t x) {
	if (x > LIMIT || x < -LIMIT) return 0;
	return 1;
}

static int128_t gcd(int128_t x, int128_t y) {
	while (y != 0) {
		int128_t t = y;
		y = x % y;
		x = t;
	}
	return x < 0 ? -x : x;
}


static void try_push_children(Node *curr) {
	int128_t a = curr->a, b = curr->b, c = curr->c;

	int128_t g = gcd(a, gcd(b, c));
	if (g > 1) {
		int128_t ga = a / g;
		int128_t gb = b / g;
		int128_t gc = c / g;

		int prime_count = is_prime(ga) + is_prime(gb) + is_prime(gc);

		if (prime_count >= 1) return;
	}

	int128_t na = 2*(b + c) - a;
	if (safe_val(na) && safe_val(b) && safe_val(c)) {
		if (visit_and_mark(na, b, c)) {
			Node *n = (Node*)malloc(sizeof(Node));
			n->a = na; n->b = b; n->c = c; n->move = 'A'; n->parent = curr; n->next = NULL;
			enqueue(n);
		}
	}

	int128_t nb = 2*(a + c) - b;
	if (safe_val(a) && safe_val(nb) && safe_val(c)) {
		if (visit_and_mark(a, nb, c)) {
			Node *n = (Node*)malloc(sizeof(Node));
			n->a = a; n->b = nb; n->c = c; n->move = 'B'; n->parent = curr; n->next = NULL;
			enqueue(n);
		}
	}

	int128_t nc = 2*(a + b) - c;
	if (safe_val(a) && safe_val(b) && safe_val(nc)) {
		if (visit_and_mark(a, b, nc)) {
			Node *n = (Node*)malloc(sizeof(Node));
			n->a = a; n->b = b; n->c = nc; n->move = 'C'; n->parent = curr; n->next = NULL;
			enqueue(n);
		}
	}
}

// Convert string -> int128
int128_t str_to_int128(const char *s) {
	int128_t value = 0;
	int sign = 1;

	if (*s == '-') {
		sign = -1;
		s++;
	}

	while (*s >= '0' && *s <= '9') {
		value = value * 10 + (*s - '0');
		s++;
	}

	return sign * value;
}

// Print __int128 (for debugging)
void print_int128(int128_t x) {
	if (x == 0) {
		printf("0");
		return;
	}

	if (x < 0) {
		putchar('-');
		x = -x;
	}

	char buf[64];
	int i = 0;

	while (x > 0) {
		buf[i++] = '0' + (int)(x % 10);
		x /= 10;
	}

	while (i--) putchar(buf[i]);
}

int main(void) {
	char sa[256], sb[256], sc[256];
	int128_t a0, b0, c0;
	if (printf("Enter initial a b c: ") < 0) return 1;
	if (scanf("%255s %255s %255s", sa, sb, sc) != 3) {
		fprintf(stderr, "Invalid input\n");
		return 1;
	}

	a0 = str_to_int128(sa);
	b0 = str_to_int128(sb);
	c0 = str_to_int128(sc);

	if (a0 == 0 || b0 == 0 || c0 == 0) {
		printf("Already zero present: (");
		print_int128(a0); printf(", ");
		print_int128(b0); printf(", ");
		print_int128(c0); printf(")\n");
		return 0;
	}

	if (!safe_val(a0) || !safe_val(b0) || !safe_val(c0)) {
		fprintf(stderr, "Initial values exceed safe limit.\n");
		return 1;
	}

	Node *root = (Node*)malloc(sizeof(Node));
	if (!root) { fprintf(stderr, "Out of memory\n"); return 1; }
	root->a = a0; root->b = b0; root->c = c0; root->move = '\0'; root->parent = NULL; root->next = NULL;
	enqueue(root);
	visit_and_mark(a0,b0,c0);

	Node *found = NULL;
	while ((root = dequeue()) != NULL) {
		if (root->a == 0 || root->b == 0 || root->c == 0) {
			found = root;
			break;
		}
		try_push_children(root);
	}

	if (!found) {
		printf("No solution found within bounds/search limits.\n");
		return 0;
	}

	int max_moves = 0;
	Node *p = found;
	while (p && p->move != '\0') { max_moves++; p = p->parent; }

	char *moves = (char*)malloc(max_moves + 1);
	if (!moves) { fprintf(stderr, "Out of memory\n"); return 1; }
	moves[max_moves] = '\0';
	p = found;
	int idx = max_moves - 1;
	while (p && p->move != '\0') {
		moves[idx--] = p->move;
		p = p->parent;
	}

	printf("\nSolution found!\n");
	printf("Initial: (");
	print_int128(a0); printf(", ");
	print_int128(b0); printf(", ");
	print_int128(c0); printf(")\n");

	printf("Final: (");
	print_int128(found->a); printf(", ");
	print_int128(found->b); printf(", ");
	print_int128(found->c); printf(")\n");
	printf("Moves (%d): %s\n", max_moves, moves);
	return 0;
}