diff options
| -rw-r--r-- | Makefile | 13 | ||||
| -rw-r--r-- | main.c | 26 | ||||
| -rw-r--r-- | solver.c | 171 | ||||
| -rw-r--r-- | solver.h | 11 |
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) + @@ -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 */ |