summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas "Cakeisalie5" Touhey <thomas@touhey.fr>2018-01-10 20:00:47 +0100
committerThomas "Cakeisalie5" Touhey <thomas@touhey.fr>2018-01-10 20:00:47 +0100
commit3b24dc9b961c238a58083ba1e68dfd5f21915e7f (patch)
tree01d16e7c523a4c8828cd3109058203d34146f139
Ugly solution (bruteforce ftw), but works.
-rw-r--r--.gitignore3
-rw-r--r--Makefile11
-rw-r--r--src/count.c29
-rw-r--r--src/illumination.h64
-rw-r--r--src/input.c203
-rw-r--r--src/main.c80
-rw-r--r--src/output.c155
-rw-r--r--src/solve.c38
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);
+}