diff options
author | Olivier Gayot <duskcoder@gmail.com> | 2012-11-19 02:13:14 +0100 |
---|---|---|
committer | Olivier Gayot <duskcoder@gmail.com> | 2014-03-05 18:38:41 +0100 |
commit | e36cbdb62ef0b6b74285455b88604494cfdd6a63 (patch) | |
tree | 12b6a0540e14e345849f8cb09e54d357653f4a47 /main.c |
god_hands_solver: commit first version of the project
This version of the project is entirely functionnal. Nevertheless, we
should make a small interface showing the values as a circle because the
id's on standard output do not seem very clear.
Diffstat (limited to 'main.c')
-rw-r--r-- | main.c | 141 |
1 files changed, 141 insertions, 0 deletions
@@ -0,0 +1,141 @@ +#include <stdint.h> +#include <stdlib.h> +#include <stdio.h> +#include <assert.h> +#include <stdbool.h> + +typedef uint8_t byte; +typedef int8_t rang_t; + +typedef struct { + byte value; + rang_t rang; +} elem_t; + +typedef struct { + int len; + elem_t *elem; +} map_t; + +map_t *map_g; + +/* resolve {{{ */ + +static bool map_is_empty(void) +{ + for (int i = 0; i < map_g->len; i++) { + if (map_g->elem[i].rang == -1) { + return false; + } + } + + return true; +} + +static inline int get_next(int current) +{ + return (current + map_g->elem[current].value) % map_g->len; +} + +static inline int get_prev(int current) +{ + int prev = current - map_g->elem[current].value; + + if (current < map_g->elem[current].value) + prev += map_g->len; + + return prev; +} + +static int perform_resolve_god_hands(int activated, int level) +{ + int next, prev; + + /* this one is already activated, not possible captain */ + if (map_g->elem[activated].rang != -1) { + return -1; + } + + /* activate the current case */ + map_g->elem[activated].rang = level; + + if (map_is_empty()) { + /* we won */ + return 0; + } + + next = get_next(activated); + prev = get_prev(activated); + + if (perform_resolve_god_hands(next, level + 1) == 0) + return 0; + + if (perform_resolve_god_hands(prev, level + 1) == 0) + return 0; + + /* reset to default */ + map_g->elem[activated].rang = -1; + return -1; +} + +int solve_god_hands(map_t *map) +{ + for (int i = 0; i < map->len; i++) { + map->elem[i].rang = -1; + } + + map_g = map; + + for (int i = 0; i < map->len; i++) { + if (perform_resolve_god_hands(i, 0) == 0) { + return 0; + } + } + + return -1; +} + +/* }}} */ + +static void display_solution(const map_t *map) +{ + for (int i = 0; i < map->len; i++) { + /* run through the order */ + for (int j = 0; j < map->len; j++) { + /* run through the elems */ + + assert (map->elem[j].rang != -1); + + if (map->elem[j].rang == i) { + printf("[%d] ", j); + break; + } + } + } + putchar('\n'); +} + +int main(void) +{ + map_t map; + char buffer[8]; + + puts("size of the map"); + map.len = atoi(fgets(buffer, 8, stdin)); + + map.elem = malloc(sizeof(byte) * map.len); + + for (int i = 0; i < map.len; i++) { + printf("(%02d/%02d): ", i + 1, map.len); + map.elem[i].value = atoi(fgets(buffer, 8, stdin)); + } + + if ((solve_god_hands(&map)) != 0) { + fputs("cannot resolve paradox kupo\n", stderr); + } else { + fputs("we resolved the paradox kupo\n", stdout); + display_solution(&map); + } + + return 0; +} |