aboutsummaryrefslogtreecommitdiff
path: root/2020
diff options
context:
space:
mode:
Diffstat (limited to '2020')
-rw-r--r--2020/14/solve.c97
-rw-r--r--2020/15/Makefile2
-rw-r--r--2020/15/solve.c53
-rw-r--r--2020/README26
4 files changed, 82 insertions, 96 deletions
diff --git a/2020/14/solve.c b/2020/14/solve.c
index 2f89ca2..98e62fe 100644
--- a/2020/14/solve.c
+++ b/2020/14/solve.c
@@ -1,70 +1,24 @@
+#include "../../lib/uthash.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
-struct mem_entry {
+struct mem {
long address;
long value;
- struct mem_entry *next;
+ UT_hash_handle hh;
};
-struct mem_map {
- struct mem_entry *head;
- struct mem_entry *tail;
-};
-
-// THIS FUNCTION IS THE SPEED PROBLEM!
-struct mem_entry *get_entry(struct mem_map *mem_map, int address)
+void new_entry(struct mem **mem, long address, long value)
{
- if (!mem_map || !mem_map->head || !mem_map->tail)
- return NULL;
-
- struct mem_entry *iterator = mem_map->head;
- while (iterator) {
- if (iterator->address == address)
- return iterator;
- iterator = iterator->next;
+ struct mem *addr;
+ HASH_FIND(hh, *mem, &address, sizeof(address), addr);
+ if (addr == NULL) {
+ addr = malloc(sizeof(*addr));
+ addr->address = address;
+ HASH_ADD(hh, *mem, address, sizeof(address), addr);
}
- return NULL;
-}
-
-void new_entry(struct mem_map *mem_map, long address, long value)
-{
- if (!mem_map)
- return;
-
- struct mem_entry *override = NULL;
- if ((override = get_entry(mem_map, address))) {
- override->value = value;
- return;
- }
-
- struct mem_entry *new = malloc(sizeof(*new));
- new->address = address;
- new->value = value;
- new->next = NULL;
-
- if (mem_map->head && mem_map->tail) {
- mem_map->tail->next = new;
- mem_map->tail = new;
- } else {
- mem_map->head = new;
- mem_map->tail = mem_map->head;
- }
-}
-
-long count_doku(struct mem_map *mem_map)
-{
- if (!mem_map || !mem_map->head || !mem_map->tail)
- return 0;
-
- long cnt = 0;
- struct mem_entry *iterator = mem_map->head;
- while (iterator) {
- cnt += iterator->value;
- iterator = iterator->next;
- }
- return cnt;
+ addr->value = value;
}
long part_one(FILE *fp)
@@ -72,7 +26,7 @@ long part_one(FILE *fp)
char *line = NULL;
size_t len = 0;
char mask[36] = { 0 };
- struct mem_map mem_map = { 0 };
+ struct mem *mem = NULL;
while (getline(&line, &len, fp) != -1) {
if (line[0] == 'm' && line[1] == 'a') {
sscanf(line, "mask = %s\n", &mask[0]);
@@ -87,11 +41,20 @@ long part_one(FILE *fp)
else if (*p == '1')
value |= shift;
}
- new_entry(&mem_map, address, value);
+ new_entry(&mem, address, value);
}
}
- return count_doku(&mem_map);
+ long sum = 0;
+ struct mem *addr, *tmp;
+ HASH_ITER(hh, mem, addr, tmp)
+ {
+ sum += addr->value;
+ HASH_DEL(mem, addr);
+ free(addr);
+ }
+
+ return sum;
}
long part_two(FILE *fp)
@@ -100,7 +63,7 @@ long part_two(FILE *fp)
size_t len = 0;
char mask[36] = { 0 };
int floating_bits[64];
- struct mem_map mem_map = { 0 };
+ struct mem *mem = NULL;
while (getline(&line, &len, fp) != -1) {
if (line[0] == 'm' && line[1] == 'a') {
sscanf(line, "mask = %s\n", &mask[0]);
@@ -124,12 +87,20 @@ long part_two(FILE *fp)
for (int j = 0; j < floating; j++)
if (perm & (1ul << j))
address ^= (1ul << (36 - floating_bits[j] - 1));
- new_entry(&mem_map, address, value);
+ new_entry(&mem, address, value);
}
}
}
- return count_doku(&mem_map);
+ long sum = 0;
+ struct mem *addr, *tmp;
+ HASH_ITER(hh, mem, addr, tmp)
+ {
+ sum += addr->value;
+ HASH_DEL(mem, addr);
+ free(addr);
+ }
+ return sum;
}
int main(int argc, char *argv[])
diff --git a/2020/15/Makefile b/2020/15/Makefile
index 9c7ab36..fc2ff1a 100644
--- a/2020/15/Makefile
+++ b/2020/15/Makefile
@@ -1,7 +1,7 @@
.PHONY: solve.c
solve.o: solve.c
- @gcc -g -Ofast $+ -o $@
+ @gcc -Ofast $+ -o $@
clean:
@rm -f *.o
diff --git a/2020/15/solve.c b/2020/15/solve.c
index 0707208..a3406f0 100644
--- a/2020/15/solve.c
+++ b/2020/15/solve.c
@@ -1,29 +1,43 @@
+#include "../../lib/uthash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
-#define MAX_NUMS 30000000
+struct num {
+ int num;
+ int index;
+ UT_hash_handle hh;
+};
-static int nums[MAX_NUMS] = { 0 };
-
-int part_one(FILE *fp, int count)
+int add(struct num **nums, int index, int num)
{
- long size = 0;
- while (size < count)
- if (fscanf(fp, "%d,", &nums[size++]) != 1)
- break;
-
- for (int i = size - 2; i < count - 1; i++) {
- for (int j = i - 1; j >= 0; j--) {
- if (nums[j] == nums[i]) {
- nums[i + 1] = i - j;
- break;
- }
- }
+ struct num *n;
+ HASH_FIND_INT(*nums, &num, n);
+ if (!n) {
+ n = malloc(sizeof(*n));
+ n->index = index;
+ n->num = num;
+ HASH_ADD_INT(*nums, num, n);
+ return 0;
}
+ int diff = index - n->index;
+ n->index = index;
+ return diff;
+}
+
+int calc(FILE *fp, int count)
+{
+ struct num *nums = NULL;
+
+ int num, index = 1;
+ while (fscanf(fp, "%d,", &num) == 1)
+ num = add(&nums, index++, num);
+
+ while (index < count)
+ num = add(&nums, index++, num);
- return nums[count - 1];
+ return num;
}
int main(int argc, char *argv[])
@@ -33,10 +47,9 @@ int main(int argc, char *argv[])
exit(EXIT_FAILURE);
clock_t tic = clock();
- printf("%d\n", part_one(fp, 2020));
- memset(nums, 0, 2020);
+ printf("%d\n", calc(fp, 2020));
rewind(fp);
- printf("%d\n", part_one(fp, 30000000));
+ printf("%d\n", calc(fp, 30000000));
clock_t toc = clock();
printf("TIME: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
diff --git a/2020/README b/2020/README
index d4c7ca5..e3d433d 100644
--- a/2020/README
+++ b/2020/README
@@ -1,13 +1,15 @@
Day 01: TIME: 0.006000 seconds
-Day 02: TIME: 0.001094 seconds
-Day 03: TIME: 0.000053 seconds
-Day 04: TIME: 0.003551 seconds
-Day 05: TIME: 0.000491 seconds
-Day 06: TIME: 0.018786 seconds
-Day 07: TIME: 0.046968 seconds
-Day 08: TIME: 0.021613 seconds
-Day 09: TIME: 0.013302 seconds
-Day 10: TIME: 0.000010 seconds
-Day 11: TIME: 0.037025 seconds
-Day 12: TIME: 0.000236 seconds
-Day 13: TIME: 0.000024 seconds
+Day 02: TIME: 0.000652 seconds
+Day 03: TIME: 0.000135 seconds
+Day 04: TIME: 0.001582 seconds
+Day 05: TIME: 0.000210 seconds
+Day 06: TIME: 0.028217 seconds
+Day 07: TIME: 0.045297 seconds
+Day 08: TIME: 0.020880 seconds
+Day 09: TIME: 0.012765 seconds
+Day 10: TIME: 0.000006 seconds
+Day 11: TIME: 0.036359 seconds
+Day 12: TIME: 0.000527 seconds
+Day 13: TIME: 0.000025 seconds
+Day 14: TIME: 0.024130 seconds
+Day 15: TIME: 4.223709 seconds