advent-of-code

My solutions to Advent of Code
git clone https://git.sr.ht/~jbauer/advent-of-code
Log | Files | Refs | README | LICENSE

commit 96977d4888d798cdca327ae8ada461eb28537509
parent 9149ffedaf4231a9431cf7102332093c3c5dfb04
Author: Jake Bauer <jbauer@paritybit.ca>
Date:   Mon, 17 Jan 2022 17:45:50 -0500

Do half of day 3 (was done in late Dec.)

Diffstat:
Mmain1.c | 94++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
Mmain2.c | 116++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------
2 files changed, 179 insertions(+), 31 deletions(-)

diff --git a/main1.c b/main1.c @@ -2,6 +2,8 @@ #include <stdlib.h> #include <string.h> +#define ENTRY_LENGTH 12 + FILE * openInputFile(void) { @@ -14,36 +16,102 @@ openInputFile(void) return fp; } +struct list { + size_t used; + size_t size; + int *contents; +}; + +int +createList(struct list *list, size_t initialSize) +{ + list->contents = (int *) malloc(initialSize * sizeof(int)); + if (list->contents == NULL) + return 1; + list->used = 0; + list->size = initialSize; + return 0; +} + +int +insertIntoList(struct list *list, int item) +{ + if (list->used == list->size) + { + list->size *= 2; + list->contents = (int *) realloc(list->contents, list->size * sizeof(int)); + if (list->contents == NULL) + return 1; + } + list->contents[list->used++] = item; + return 0; +} + +void +freeList(struct list *list) +{ + free(list->contents); +} + +// Just computes most common value from a set of 1 or 0 because nothing more is +// needed for this challenge +int +mostCommonValue(struct list *list) +{ + int numZeros = 0; + int numOnes = 0; + for (int i = 0; i < list->used; i++) + { + if (list->contents[i] == 0) + numZeros++; + else + numOnes++; + } + if (numZeros > numOnes) + return 0; + else + return 1; +} + int main(void) { FILE *fp = openInputFile(); - int position = 0; - int depth = 0; + struct list bits[ENTRY_LENGTH]; + for (int i = 0; i < ENTRY_LENGTH; i ++) + if (createList(&bits[i], 1) != 0) + exit(EXIT_FAILURE); char *line = NULL; size_t len = 0; ssize_t read; while ((read = getline(&line, &len, fp)) != -1) { - char *direction = strtok(line, " "); - int magnitude = atoi(strtok(NULL, " ")); + for (int i = 0; i < ENTRY_LENGTH; i ++) + insertIntoList(&bits[i], line[i] - '0'); + } - if (strcmp("forward", direction) == 0) - position += magnitude; - else if (strcmp ("down", direction) == 0) - depth += magnitude; - else - depth -= magnitude; + int gamma = 0; + + for (int i = 0; i < ENTRY_LENGTH; i++) + { + printf("%d: %d\n", i, mostCommonValue(&bits[i])); + if (mostCommonValue(&bits[i])) + gamma = gamma | (1 << (ENTRY_LENGTH - i - 1)) ; + printf("Gamma is: %x\n", gamma); } - printf("Final position: %d\n", position); - printf("Final depth: %d\n", depth); - printf("Product: %d\n", position * depth); + int epsilon = ~gamma & ((1 << ENTRY_LENGTH) - 1); + + printf(" Gamma %d\n", gamma); + printf("Epsilon %d\n", epsilon); + printf("Product %d\n", gamma * epsilon); fclose(fp); if (line) free(line); + for (int i = 0; i < ENTRY_LENGTH; i++) + freeList(&bits[i]); exit(EXIT_SUCCESS); } diff --git a/main2.c b/main2.c @@ -2,6 +2,8 @@ #include <stdlib.h> #include <string.h> +#define ENTRY_LENGTH 12 + FILE * openInputFile(void) { @@ -14,40 +16,118 @@ openInputFile(void) return fp; } +struct list { + size_t used; + size_t size; + int *contents; +}; + +int +createList(struct list *list, size_t initialSize) +{ + list->contents = (int *) malloc(initialSize * sizeof(int)); + if (list->contents == NULL) + return 1; + list->used = 0; + list->size = initialSize; + return 0; +} + +int +insertIntoList(struct list *list, int item) +{ + if (list->used == list->size) + { + list->size *= 2; + list->contents = (int *) realloc(list->contents, list->size * sizeof(int)); + if (list->contents == NULL) + return 1; + } + list->contents[list->used++] = item; + return 0; +} + +void +freeList(struct list *list) +{ + free(list->contents); +} + +//TODO Make a function that handles deleting an element from the list by index + +//TODO Make a function that duplicates a list + +// Just computes most common value from a set of 1 or 0 because nothing more is +// needed for this challenge +int +mostCommonValue(struct list *list) +{ + int numZeros = 0; + int numOnes = 0; + for (int i = 0; i < list->used; i++) + { + if (list->contents[i] == 0) + numZeros++; + else + numOnes++; + } + if (numZeros > numOnes) + return 0; + else + return 1; +} + int main(void) { FILE *fp = openInputFile(); - int position = 0; - int depth = 0; - int aim = 0; + struct list bits[ENTRY_LENGTH]; + for (int i = 0; i < ENTRY_LENGTH; i ++) + if (createList(&bits[i], 1) != 0) + exit(EXIT_FAILURE); + + // TODO For Part 2: + // Add each _line_ into a list as a list of strings (not ints) + // (Duplicate the list for the second calculation) + // Iterate over each element, picking the nth bit and add that to a list + // of ints + // Compute the most common number (1 or 0) + // Iterate over each element again and remove the entries which don't + // start with the most common number + // Repeat until one number remains -> this is the result value + // Do the same for the second calculation, but take the least common + // number instead of the most common char *line = NULL; size_t len = 0; ssize_t read; while ((read = getline(&line, &len, fp)) != -1) { - char *direction = strtok(line, " "); - int magnitude = atoi(strtok(NULL, " ")); - - if (strcmp("forward", direction) == 0) - { - position += magnitude; - depth += aim * magnitude; - } - else if (strcmp ("down", direction) == 0) - aim += magnitude; - else - aim -= magnitude; + for (int i = 0; i < ENTRY_LENGTH; i ++) + insertIntoList(&bits[i], line[i] - '0'); } - printf("Final position: %d\n", position); - printf("Final depth: %d\n", depth); - printf("Product: %d\n", position * depth); + int gamma = 0; + + for (int i = 0; i < ENTRY_LENGTH; i++) + { + printf("%d: %d\n", i, mostCommonValue(&bits[i])); + if (mostCommonValue(&bits[i])) + gamma = gamma | (1 << (ENTRY_LENGTH - i - 1)) ; + printf("Gamma is: %x\n", gamma); + } + + int epsilon = ~gamma & ((1 << ENTRY_LENGTH) - 1); + + printf(" Gamma %d\n", gamma); + printf("Epsilon %d\n", epsilon); + printf("Product %d\n", gamma * epsilon); fclose(fp); if (line) free(line); + for (int i = 0; i < ENTRY_LENGTH; i++) + freeList(&bits[i]); exit(EXIT_SUCCESS); }