le_compte_est_bon: implementation of the solver

4 files changed, 221 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..1e63a53
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,13 @@
+CC      = gcc
+CFLAGS  = -Wall -W -Wextra -std=c99 -g
+NAME    = solver
+
+$(NAME): .solver.o .main.o
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+.solver.o: solver.c solver.h
+	$(CC) -o $@ -c $< $(CFLAGS)
+
+.main.o: main.c solver.h
+	$(CC) -o $@ -c $< $(CFLAGS)
+
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..4a8fd98
--- /dev/null
+++ b/main.c
@@ -0,0 +1,26 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "solver.h"
+
+int main(int argc, char **argv)
+{
+    vect_t vect;
+
+    if (argc != 8) {
+	puts("takes exactly 7 args");
+	return -1;
+    }
+    vect.array = malloc(sizeof(int) * 6);
+    vect.array[0] = atoi(argv[1]);
+    vect.array[1] = atoi(argv[2]);
+    vect.array[2] = atoi(argv[3]);
+    vect.array[3] = atoi(argv[4]);
+    vect.array[4] = atoi(argv[5]);
+    vect.array[5] = atoi(argv[6]);
+
+    vect.len = 6;
+    solve(&vect, atoi(argv[7]));
+    free(vect.array);
+
+    return 0;
+}
diff --git a/solver.c b/solver.c
new file mode 100644
index 0000000..c0da05f
--- /dev/null
+++ b/solver.c
@@ -0,0 +1,171 @@
+#include <stdio.h>
+#include <string.h>
+#include <malloc.h>
+#include <limits.h>
+#include <stdint.h>
+#include "solver.h"
+
+#define _log(...)   fprintf(stderr, __VA_ARGS__)
+#define _abs(x)     (((x) < 0) ? -(x) : (x))
+
+typedef uint8_t byte;
+
+enum {
+    addition,
+    substraction,
+    multiplication,
+    division,
+};
+
+typedef struct {
+    int v1;
+    int v2;
+    byte op;
+} computation_t;
+
+typedef struct {
+    computation_t *computation;
+    int level;
+} solution_t;
+
+static solution_t solution_g;
+
+static int result;
+static int closer = -1;
+
+/* {{{ display */
+
+static void display_solution(void)
+{
+    puts("--------------------------");
+    puts("found a (better) solution:");
+    for (int i = 5; i >= solution_g.level; i--) {
+	char op;
+	int _result;
+
+	switch (solution_g.computation[i].op) {
+	    case addition:
+		op = '+';
+		_result = solution_g.computation[i].v1 + solution_g.computation[i].v2;
+		break;
+	    case substraction:
+		op = '-';
+		_result = solution_g.computation[i].v1 - solution_g.computation[i].v2;
+		break;
+	    case multiplication:
+		op = '*';
+		_result = solution_g.computation[i].v1 * solution_g.computation[i].v2;
+		break;
+	    case division:
+		op = '/';
+		_result = solution_g.computation[i].v1 / solution_g.computation[i].v2;
+		break;
+	}
+
+	printf("%d %c %d = %d\n", solution_g.computation[i].v1
+		, op
+		, solution_g.computation[i].v2
+		, _result);
+    }
+}
+
+/* }}} */
+
+    static inline
+void construct_new_vect(vect_t *new_vect, vect_t *vect, unsigned v1, unsigned v2)
+{
+    unsigned j = 0;
+
+    for (unsigned i = 0; i < vect->len; ++i) {
+	/* check is this is one of the taken values */
+	if (i == v1 || i == v2)
+	    continue;
+
+	new_vect->array[j++] = vect->array[i];
+    }
+}
+
+static void solve_rec(vect_t *vect)
+{
+    vect_t new_vect;
+
+    if (solution_g.level != 0 && ((unsigned)solution_g.level >= vect->len)) {
+	/* we have already found a better solution */
+	return;
+    }
+
+    if (vect->len == 0)
+	return;
+
+    for (unsigned i = 0; i < vect->len; ++i) {
+	if ((closer == -1)
+		|| (_abs(vect->array[i] - result) <= _abs(closer - result)))
+	{
+	    closer = vect->array[i];
+	    if (closer == result) {
+		solution_g.level = vect->len;
+		display_solution();
+		return;
+	    }
+
+	}
+    }
+
+    new_vect.array = malloc(sizeof(int) * (vect->len - 1));
+    new_vect.len   = vect->len - 1;
+    for (unsigned i = 0; i < vect->len; ++i) {
+	for (unsigned j = 0; j < vect->len; ++j) {
+	    /* we cannot use the same value twice */
+	    if (i == j)
+		continue;
+
+	    /* construct the new vector */
+	    construct_new_vect(&new_vect, vect, i, j);
+
+	    solution_g.computation[vect->len - 1].v1 = vect->array[i];
+	    solution_g.computation[vect->len - 1].v2 = vect->array[j];
+
+	    /* try adding (no condition) */
+	    new_vect.array[new_vect.len - 1] = vect->array[i] + vect->array[j];
+	    solution_g.computation[vect->len - 1].op = addition;
+	    solve_rec(&new_vect);
+
+	    /* try substracting (must be > 0) */
+	    if (vect->array[i] >= vect->array[j]) {
+		new_vect.array[new_vect.len - 1] = vect->array[i] - vect->array[j];
+		solution_g.computation[vect->len - 1].op = substraction;
+		solve_rec(&new_vect);
+	    }
+
+	    /* try multiplicating (no condition) */
+	    new_vect.array[new_vect.len - 1] = vect->array[i] * vect->array[j];
+	    solution_g.computation[vect->len - 1].op = multiplication;
+	    solve_rec(&new_vect);
+
+	    /* try dividing (no rest needed and cannot divide by 0) */
+	    if ((vect->array[j] != 0) && (vect->array[i] % vect->array[j] == 0)) {
+		new_vect.array[new_vect.len - 1] = vect->array[i] / vect->array[j];
+		solution_g.computation[vect->len - 1].op = division;
+		solve_rec(&new_vect);
+	    }
+	}
+    }
+    free(new_vect.array);
+}
+
+/* public function to use */
+void solve(vect_t *vect, int _result)
+{
+    result = _result;
+    solution_g.computation = malloc(sizeof(computation_t) * vect->len);
+    solution_g.level       = 0;
+
+    solve_rec(vect);
+
+    if (closer != result) {
+	result = closer;
+	closer = -1;
+	solve_rec(vect);
+    }
+    free(solution_g.computation);
+}
diff --git a/solver.h b/solver.h
new file mode 100644
index 0000000..357cd91
--- /dev/null
+++ b/solver.h
@@ -0,0 +1,11 @@
+#ifndef SOLVER_H
+#define SOLVER_H
+
+typedef struct {
+    int *array;
+    unsigned len;
+} vect_t;
+
+void solve(vect_t *vect, int result);
+
+#endif /* SOLVER_H */