aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authornytpu <alex@nytpu.com>2020-12-13 09:19:54 -0700
committernytpu <alex@nytpu.com>2020-12-13 10:44:47 -0700
commit83ea9dc9af708a8a961facd0360125230c1633b5 (patch)
treeabef9a3ba70236d4c0c3d69d7d47512bf78f14d7
parentadded day 7 (diff)
downloadadvent_of_code_2020-83ea9dc9af708a8a961facd0360125230c1633b5.tar.bz2
advent_of_code_2020-83ea9dc9af708a8a961facd0360125230c1633b5.zip
added day 13
-rw-r--r--day13/input.txt2
-rw-r--r--day13/problem_1.c58
-rw-r--r--day13/problem_2.c106
-rw-r--r--day13/test_input.txt2
4 files changed, 168 insertions, 0 deletions
diff --git a/day13/input.txt b/day13/input.txt
new file mode 100644
index 0000000..435ec62
--- /dev/null
+++ b/day13/input.txt
@@ -0,0 +1,2 @@
+1000655
+17,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,571,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,x,23,x,x,x,x,x,29,x,401,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,19
diff --git a/day13/problem_1.c b/day13/problem_1.c
new file mode 100644
index 0000000..73a388a
--- /dev/null
+++ b/day13/problem_1.c
@@ -0,0 +1,58 @@
+/* advent of code day 13, problem 1
+ * by nytpu
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define BUS_BUF 256
+
+int main (int argc, char *argv[])
+{
+ char buses[BUS_BUF];
+ int target_time;
+ char *tok;
+ int id, wait_time, id_best = 0, wait_time_best = -1;
+
+ if (argc != 2) {
+ printf("Usage: problem_[x] [input]");
+ }
+
+ FILE *infile = fopen(argv[1], "r");
+ if (infile == NULL) {
+ fprintf(stderr, "Unable to open file %s\n", argv[1]);
+ exit(EXIT_FAILURE);
+ }
+
+ if (fscanf(infile, "%d\n", &target_time) <= 0) {
+ fprintf(stderr, "Unable to read initial timestamp!\n");
+ exit(EXIT_FAILURE);
+ }
+
+ if (fgets(buses, BUS_BUF, infile) == NULL) {
+ fprintf(stderr, "Unable to read bus list!\n");
+ exit(EXIT_FAILURE);
+ }
+
+ if (fclose(infile) != 0) {
+ fprintf(stderr, "Could not close file %s", argv[1]);
+ }
+
+ for (
+ tok = strtok(buses, ",");
+ tok && *tok;
+ tok = strtok(NULL, ",\n")
+ ) {
+ if (!strncmp(tok, "x", 1)) continue;
+ id = atoi(tok);
+ wait_time = id - (target_time % id);
+ if (wait_time_best < 0 || wait_time < wait_time_best) {
+ wait_time_best = wait_time;
+ id_best = id;
+ }
+ }
+
+ printf("ID * Wait time: %d\n", wait_time_best * id_best);
+ return EXIT_SUCCESS;
+}
diff --git a/day13/problem_2.c b/day13/problem_2.c
new file mode 100644
index 0000000..d4da428
--- /dev/null
+++ b/day13/problem_2.c
@@ -0,0 +1,106 @@
+/* advent of code day 13, problem 2
+ * by nytpu
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define LINE_BUF 256
+#define BUS_BUF 15
+
+unsigned long long chinese_remainder (
+ const int *buses,
+ const int *mods,
+ size_t len
+);
+
+int main (int argc, char *argv[])
+{
+ int i = 0;
+ char bus_line[LINE_BUF], *tok;
+ int buses[BUS_BUF] = {-1}, mods[BUS_BUF];
+ size_t buses_len = 0;
+
+ if (argc != 2) {
+ printf("Usage: problem_[x] [input]");
+ }
+
+ FILE *infile = fopen(argv[1], "r");
+ if (infile == NULL) {
+ fprintf(stderr, "Unable to open file %s\n", argv[1]);
+ exit(EXIT_FAILURE);
+ }
+
+ fscanf(infile, "%*d\n");
+
+ if (fgets(bus_line, LINE_BUF, infile) == NULL) {
+ fprintf(stderr, "Unable to read bus list!\n");
+ exit(EXIT_FAILURE);
+ }
+
+ if (fclose(infile) != 0) {
+ fprintf(stderr, "Could not close file %s", argv[1]);
+ }
+
+ for (
+ tok=strtok(bus_line, ",");
+ tok && *tok;
+ tok = strtok(NULL, ",\n")
+ ) {
+ if (!strncmp(tok, "x", 1)) {
+ //buses[buses_len] = -1;
+ ++i;
+ continue;
+ } else {
+ buses[buses_len] = atoi(tok);
+ }
+ mods[buses_len] = i;
+ ++buses_len; ++i;
+ }
+
+ printf(
+ "First timestamp that matches: %llu\n",
+ chinese_remainder(buses, mods, buses_len)
+ );
+ return EXIT_SUCCESS;
+}
+
+unsigned long long chinese_remainder (
+ const int *buses,
+ const int *mods,
+ size_t len
+)
+{
+ unsigned long long jmp = buses[0], ts = buses[0], i;
+ for (i = 1; i < len; ++i) {
+ while ((ts + mods[i]) % buses[i] != 0) {
+ ts += jmp;
+ }
+ jmp *= buses[i];
+ }
+ return ts;
+}
+
+/*
+#define GUESS 100000000000000
+// brute force solution (takes too long)
+unsigned long long chinese_remainder (int *buses, size_t len)
+{
+ size_t i = 0;
+ unsigned long long timestamp = GUESS;
+ mod
+
+ while (true) {
+ for (i = 1; i < len; ++i) {
+ if (buses[i] < 0) continue;
+ if ((timestamp+i) % buses[i] != 0) break;
+ }
+ if (i == len) return timestamp;
+
+ ++timestamp;
+ }
+
+ return 0;
+}
+*/
diff --git a/day13/test_input.txt b/day13/test_input.txt
new file mode 100644
index 0000000..d76f619
--- /dev/null
+++ b/day13/test_input.txt
@@ -0,0 +1,2 @@
+939
+7,13,x,x,59,x,31,19