diff options
author | Thomas "Cakeisalie5" Touhey <thomas@touhey.fr> | 2018-01-10 20:00:47 +0100 |
---|---|---|
committer | Thomas "Cakeisalie5" Touhey <thomas@touhey.fr> | 2018-01-10 20:00:47 +0100 |
commit | 3b24dc9b961c238a58083ba1e68dfd5f21915e7f (patch) | |
tree | 01d16e7c523a4c8828cd3109058203d34146f139 |
Ugly solution (bruteforce ftw), but works.
-rw-r--r-- | .gitignore | 3 | ||||
-rw-r--r-- | Makefile | 11 | ||||
-rw-r--r-- | src/count.c | 29 | ||||
-rw-r--r-- | src/illumination.h | 64 | ||||
-rw-r--r-- | src/input.c | 203 | ||||
-rw-r--r-- | src/main.c | 80 | ||||
-rw-r--r-- | src/output.c | 155 | ||||
-rw-r--r-- | src/solve.c | 38 |
8 files changed, 583 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..1263b6a --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +illum +*.txt +.*.swp diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..88b0d28 --- /dev/null +++ b/Makefile @@ -0,0 +1,11 @@ +#!/usr/bin/make -f + CWARN := -Weverything -Wno-vla -Wno-padded + SRC := src/input.c src/count.c src/main.c src/output.c src/solve.c + +illum: src/illumination.h $(SRC) + clang $(CWARN) -o "$@" $(SRC) + +test: illum + $(VAL) ./illum solve input.example.txt solution.example.txt + +.PHONY: test diff --git a/src/count.c b/src/count.c new file mode 100644 index 0000000..fbbecc9 --- /dev/null +++ b/src/count.c @@ -0,0 +1,29 @@ +#include "illumination.h" +#include <stdio.h> +#include <stddef.h> +#include <string.h> + +int count_lamps_turned_on(input_t *inp, output_t *outp, long *are_onp) +{ + size_t lsize = ((size_t)get_lamp_count(inp) >> 5) + 1; + uint32_t lamps[lsize], *lmp, bit; + long are_on = 0; + inputgen_t gen; relation_t rel; + + memset(lamps, 0, lsize * sizeof(uint32_t)); + prepare_input_gen(&gen, inp); + + while (!get_relation(&gen, &rel)) { + if (!switch_is_on(outp, rel.switch_id)) + continue; + + lmp = &lamps[rel.lamp_id >> 5]; + bit = 1 << (31 - (rel.lamp_id & 0x1f)); + + *lmp ^= bit; + are_on += *lmp & bit ? 1 : -1; + } + + *are_onp = are_on; + return (0); +} diff --git a/src/illumination.h b/src/illumination.h new file mode 100644 index 0000000..185a8ce --- /dev/null +++ b/src/illumination.h @@ -0,0 +1,64 @@ +#ifndef ILLUMINATION_H +# define ILLUMINATION_H 2018011001 +# include <stdint.h> + +/* The input file gives the number of switches and lamps, and the relations + * between them, i.e. which lamps a switch toggles the state of. */ + +struct input_s; +typedef struct input_s input_t; + +extern int parse_input(input_t **inp, const char *path); +extern int make_input(input_t **inp, long sw, long lamps); +extern void free_input(input_t *inp); + +extern long get_switch_count(input_t *inp); +extern long get_lamp_count(input_t *inp); + +extern void wire_switch_and_lamp(input_t *inp, long switch_id, long lamp_id); +extern int switch_toggles_lamp(input_t *inp, long switch_id, long lamp_id); + +/* Get relations from an input. */ + +typedef struct relation_s { + long switch_id; + long lamp_id; +} relation_t; + +typedef struct inputgen_s { + /* DO NOT USE THIS DIRECTLY! + * The content of this structure is only there to allow users to + * not having to use the heap. */ + + uint32_t *mat, bit; + long swid, swc; + long lid, lc; +} inputgen_t; + +extern int prepare_input_gen(inputgen_t *gen, input_t *inp); +extern int get_relation(inputgen_t *gen, relation_t *rel); + +/* The output file gives which switches are on. */ + +struct output_s; +typedef struct output_s output_t; + +extern int parse_output(output_t **outp, input_t *from, const char *path); +extern int make_output(output_t **outp, input_t *from); +extern int save_output(output_t *outp, const char *path); +extern void free_output(output_t *outp); + +extern void set_switch_on(output_t *outp, long id); +extern void set_switch_off(output_t *outp, long id); +extern void toggle_switch(output_t *outp, long id); +extern int switch_is_on(output_t *outp, long id); + +/* Count the number of lamps turned on using the input and output data. */ + +extern int count_lamps_turned_on(input_t *inp, output_t *outp, long *are_on); + +/* Main algorithm to solve the problem. */ + +extern int solve_illumination(input_t *inp, const char *solution_path); + +#endif /* ILLUMINATION_H */ diff --git a/src/input.c b/src/input.c new file mode 100644 index 0000000..59a7480 --- /dev/null +++ b/src/input.c @@ -0,0 +1,203 @@ +#include "illumination.h" +#include <stdio.h> +#include <stdlib.h> +#include <inttypes.h> +#include <string.h> +#include <ctype.h> + +/* Switch offset using 32-bit words! */ + +struct input_s { + long sw, lamp; /* switches and lamp count */ + long blocksize; + uint32_t matrix[]; +}; + +/* --- + * Input file management. + * --- */ + +int make_input(input_t **inp, long sw, long lamps) +{ + size_t len; + long blocksize; + input_t *in; + + blocksize = (lamps >> 5) + 1; + len = (size_t)(sw * blocksize) * sizeof(uint32_t); + in = malloc(sizeof(input_t) + len); + if (!in) return (-1); + + in->sw = sw; + in->lamp = lamps; + in->blocksize = blocksize; + memset(in->matrix, 0, len); + + *inp = in; + return (0); +} + +long get_switch_count(input_t *inp) +{ + return (inp->sw); +} + +long get_lamp_count(input_t *inp) +{ + return (inp->lamp); +} + +void wire_switch_and_lamp(input_t *inp, long switch_id, long lamp_id) +{ + uint32_t *mat, bit; + + if (switch_id >= inp->sw || lamp_id >= inp->lamp) + return ; + mat = &inp->matrix[switch_id * (long)inp->blocksize + (lamp_id >> 5)]; + bit = 1 << (31 - (lamp_id & 0x1f)); + *mat |= bit; +} + +int switch_toggles_lamp(input_t *inp, long switch_id, long lamp_id) +{ + long off; + + if (switch_id >= inp->sw || lamp_id >= inp->lamp) + return (0); + off = switch_id * inp->blocksize + (lamp_id >> 5); + lamp_id &= 0x1f; + return (!!(inp->matrix[off] & (1 << (31 - lamp_id)))); +} + +void free_input(input_t *inp) +{ + free(inp); +} + +/* --- + * Input file parsing. + * --- */ + +static int gettab(FILE *fp, long *tab, long *lenp) +{ + char *line = NULL, *s; + size_t linesz = 0; + long n, len = *lenp; + long i; + + if (getline(&line, &linesz, fp) < 0) { + free(line); /* see getline(3) */ + return (-1); + } + + s = line; + n = 0; + + while (len--) { + for (; isspace(*s); s++); + if (!*s) break; + + i = 0; + for (i = 0; isdigit(*s); s++) + i = 10 * i + (*((unsigned char*)s) - '0'); + tab[n++] = i; + + for (; isspace(*s); s++); + if (*s != ',') break; + s++; + } + + free(line); + *lenp = n; + return (0); +} + +int parse_input(input_t **inp, const char *path) +{ + FILE *fp = NULL; + input_t *in = NULL; + long len = 2, dim[2]; + + fp = fopen(path, "r"); + if (!fp) return (-1); + + /* Get the dimensions (dim[0]: number of lamps, dim[1]: number of sw.) */ + if (gettab(fp, dim, &len) || len < 2 || dim[0] == 0 || dim[1] == 0) + goto fail; + + if (make_input(&in, dim[1], dim[0])) + return (-1); + + { + long nums[in->lamp]; + long sw; int i; + + for (sw = 0; sw < in->sw; sw++) { + len = in->lamp; + if (gettab(fp, nums, &len)) + goto fail; + + for (i = 0; i < len; i++) + wire_switch_and_lamp(in, sw, nums[i]); + } + } + + fclose(fp); + *inp = in; + return (0); +fail: + if (fp) + fclose(fp); + if (in) + free(in); + *inp = NULL; + return (-1); +} + +/* --- + * Relations generator. + * --- */ + +int prepare_input_gen(inputgen_t *gen, input_t *inp) +{ + gen->mat = inp->matrix; + gen->bit = (uint32_t)1 << 31; + gen->swid = 0; + gen->swc = inp->sw; + gen->lid = 0; + gen->lc = inp->lamp; + + return (0); +} + +int get_relation(inputgen_t *gen, relation_t *rel) +{ + int found = 0; + + if (gen->swid >= gen->swc) + return (-1); + + do { + if (*gen->mat & gen->bit) { + rel->switch_id = gen->swid; + rel->lamp_id = gen->lid; + found = 1; + } + + gen->lid++; + if (gen->lid == gen->lc) { + gen->swid++; + if (!found && gen->swid >= gen->swc) + return (-1); + + gen->lid = 0; + gen->mat = gen->mat + 1 + (gen->bit & 1); + gen->bit = (uint32_t)1 << 31; + } else { + gen->mat += gen->bit & 1; + gen->bit = ((gen->bit & 1) << 31) | (gen->bit >> 1); + } + } while (!found); + + return (0); +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..6337ecd --- /dev/null +++ b/src/main.c @@ -0,0 +1,80 @@ +#include <stdio.h> +#include <string.h> +#include <getopt.h> +#include "illumination.h" + +static const char help_message[] = +"Usage: illum [-h|--help]\n" +" illum count <input file> <output file>\n" +" illum solve <input file> <solution file to write>\n" +"\n" +"Report bugs to Thomas \"Cakeisalie5\" Touhey <thomas@touhey.fr>.\n"; + +static int main_count(const char *ipath, const char *opath) +{ + input_t *inp = NULL; + output_t *outp = NULL; + long count; + + if (parse_input(&inp, ipath)) + return (1); + if (parse_output(&outp, inp, opath)) { + free_input(inp); + return (1); + } + + if (!count_lamps_turned_on(inp, outp, &count)) + printf("%ld\n", count); + + free_input(inp); + free_output(outp); + return (0); +} + +static int main_solve(const char *ipath, const char *spath) +{ + input_t *inp = NULL; + + if (parse_input(&inp, ipath)) + return (1); + if (solve_illumination(inp, spath)) { + free_input(inp); + return (1); + } + + free_input(inp); + return (0); +} + +int main(int ac, char * const av[]) +{ + int c, help; + const char short_opts[] = "h"; + const struct option long_opts[] = { + {"help", no_argument, NULL, 'h'}, + {NULL, 0, NULL, 0} + }; + + opterr = 0; + while ((c = getopt_long(ac, av, short_opts, long_opts, NULL)) != -1) + switch (c) { + case 'h': + help = 1; break; + case '?': + break; + } + + ac -= optind; av = &av[optind]; + if (ac < 1) help = 1; + else if (!strcmp(*av, "count") && ac == 3) + return (main_count(av[1], av[2])); + else if (!strcmp(*av, "solve") && ac == 3) + return (main_solve(av[1], av[2])); + else + help = 1; + + if (help) + fputs(help_message, stdout); + + return 0; +} diff --git a/src/output.c b/src/output.c new file mode 100644 index 0000000..8961316 --- /dev/null +++ b/src/output.c @@ -0,0 +1,155 @@ +#include "illumination.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <ctype.h> + +struct output_s { + long sw; /* switch count */ + uint32_t matrix[]; /* switches state */ +}; + +/* --- + * Output file management. + * --- */ + +int make_output(output_t **outp, input_t *from) +{ + long sw = get_switch_count(from); + size_t len; output_t *out; + + len = (((size_t)sw >> 5) + 1) * sizeof(uint32_t); + out = malloc(sizeof(output_t) + len); + if (!out) return (-1); + + out->sw = sw; + memset(out->matrix, 0, len); + + *outp = out; + return (0); +} + +#define big_off(id) ((id) >> 5) +#define lil_off(id) (1 << (31 - ((id) & 0x1f))) + +void set_switch_on(output_t *outp, long id) +{ + if (id >= outp->sw) + return ; + outp->matrix[big_off(id)] |= lil_off(id); +} + +void set_switch_off(output_t *outp, long id) +{ + if (id >= outp->sw) + return ; + outp->matrix[big_off(id)] &= ~lil_off(id); +} + +void toggle_switch(output_t *outp, long id) +{ + if (id >= outp->sw) + return ; + outp->matrix[big_off(id)] ^= lil_off(id); +} + +int switch_is_on(output_t *outp, long id) +{ + if (id >= outp->sw) + return (0); + return (!!(outp->matrix[big_off(id)] & lil_off(id))); +} + +void free_output(output_t *outp) +{ + free(outp); +} + +/* --- + * Output file parsing. + * --- */ + +static int getid(FILE *fp, long *id) +{ + char *line = NULL, *s; + size_t n = 0; + long i; + + if (getline(&line, &n, fp) < 0) { + free(line); /* see getline(3) */ + return (errno ? -1 : 1); + } + + s = line; + for (; isspace(*s); s++); + + i = 0; + for (i = 0; isdigit(*s); s++) + i = 10 * i + (*((unsigned char*)s) - '0'); + *id = i; + + free(line); + return (0); +} + +int parse_output(output_t **outp, input_t *from, const char *path) +{ + FILE *fp = NULL; + output_t *out = NULL; + + fp = fopen(path, "r"); + if (!fp) return (-1); + + if (make_output(&out, from)) + return (-1); + + { + long id; + int ret; + + while (!(ret = getid(fp, &id))) + set_switch_on(out, id); + if (ret < 0) + goto fail; + } + + fclose(fp); + *outp = out; + return (0); +fail: + if (fp) + fclose(fp); + if (out) + free(out); + *outp = NULL; + return (-1); +} + +/* --- + * Output file saving. + * --- */ + +int save_output(output_t *outp, const char *path) +{ + FILE *fp; long i; + uint32_t *mat, bit; + int ret = -1; + + fp = fopen(path, "w+"); + if (!fp) return (-1); + + mat = outp->matrix; bit = (uint32_t)1 << 31; + for (i = 0; i < outp->sw; i++) { + if ((*mat & bit) && !fprintf(fp, "%ld\n", i)) + goto fail; + + mat += bit & 1; + bit = ((bit & 1) << 31) | (bit >> 1); + } + + ret = 0; +fail: + fclose(fp); + return (ret); +} diff --git a/src/solve.c b/src/solve.c new file mode 100644 index 0000000..9ddbb03 --- /dev/null +++ b/src/solve.c @@ -0,0 +1,38 @@ +#include "illumination.h" +#include <stdio.h> + +/* Basically bruteforce. */ + +int solve_illumination(input_t *inp, const char *solpath) +{ + long swid = 0, swmax = get_switch_count(inp) - 1; + long count, record = 0; + output_t *outp = NULL; + + if (make_output(&outp, inp)) + return (-1); + + while (1) { + if (count_lamps_turned_on(inp, outp, &count)) + goto fail; + if (count > record) { + printf("Saving new record: %ld lamps!\n", count); + record = count; + save_output(outp, solpath); + } + + for (swid = swmax; switch_is_on(outp, swid); swid--) { + if (!swid) + goto tested_it_all; + set_switch_off(outp, swid); + } + set_switch_on(outp, swid); + } + +tested_it_all: + free_output(outp); + return (0); +fail: + free_output(outp); + return (-1); +} |