paritybit.ca

# Advent of Code 2022

Documenting my journey solving Advent of Code 2022 challenges.

This year I’m writing all of my solutions in C. I quite like the challenge of using language and want to become more proficient with it. If time allows, I might also attempt some problems using Clojure.

All of my solutions are also stored in a git repository.

Whenever I need a reference for a given function in C, I’m consulting the OpenBSD manpages as they are generally higher quality (they have better code examples and talk more about the drawbacks of a given function) than those on Linux.

## Day 1

Day 1: Calorie Counting

This was a nice challenge to get back into the flow of things.

For the second part of the challenge, we needed to keep track of the top three Calorie counts. The C standard library doesn’t provide any fancy data structures such as lists, so I wrote a function that allows me to insert a value into an array, pushing existing entries to higher indices (to the right). This maintains a sorted list of the top three highest Calorie counts in the order of most to least, as the lowest Calorie count gets pushed off the end of the array when a new one is inserted.

An alternative solution would be to create an array that holds the Calorie count for every elf, and then qsort(3) it to get the top values needed. That might be computationally faster for certain datasets, though it would require more memory.

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

void
intarrayInsert(int *array, size_t arrayLength, size_t index, int value)
{
for (size_t i = arrayLength-1; i > index; i--)
array[i] = array[i-1];
array[index] = value;
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
printf("Failed to open file %s", "input.txt");
exit(EXIT_FAILURE);
}

int bestElves[3] = {0, 0, 0};
int bestElvesCalories[3] = {0, 0, 0};
int currentCalories = 0;
int currentElf = 1;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
if (strncmp(line, "\n", linelen) == 0)
{
for (int i = 0; i < 3; i++)
{
if (currentCalories > bestElvesCalories[i])
{
intarrayInsert(bestElvesCalories, sizeof(bestElvesCalories)/sizeof(int), i, currentCalories);
intarrayInsert(bestElves, sizeof(bestElves)/sizeof(int), i, currentElf);
break;
}
}
currentCalories = 0;
currentElf += 1;
}
else
{
// strtonum(3) is on OpenBSD only 😠
currentCalories += atoi(line);
}
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

printf("PART 1: The elf carrying the most Calories is elf %d with %d Calories\n", bestElves[0], bestElvesCalories[0]);
printf("PART 2: The top three elves carrying the most Calories are elves %d, %d, and %d with %d Calories total\n",
bestElves[0], bestElves[1], bestElves[2],
bestElvesCalories[0] + bestElvesCalories[1] + bestElvesCalories[2]);

exit(EXIT_SUCCESS);
}
``````

## Day 2

Day 2: Rock Paper Scissors

My first solution, and the one I used to solve the problem just to get the stars out of the way, involved basically a bunch of if-else statements:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
printf("Failed to open file %s", "input.txt");
exit(EXIT_FAILURE);
}

int totalScoreFirstPart = 0;
int totalScoreSecondPart = 0;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
// Lazy string parsing
char opponentMove = line[0];
char myMove = line[2];

// Super good code
if (opponentMove == 'A' && myMove == 'X')
totalScoreFirstPart += 1 + 3;
else if (opponentMove == 'A' && myMove == 'Y')
totalScoreFirstPart += 2 + 6;
else if (opponentMove == 'A' && myMove == 'Z')
totalScoreFirstPart += 3 + 0;
else if (opponentMove == 'B' && myMove == 'X')
totalScoreFirstPart += 1 + 0;
else if (opponentMove == 'B' && myMove == 'Y')
totalScoreFirstPart += 2 + 3;
else if (opponentMove == 'B' && myMove == 'Z')
totalScoreFirstPart += 3 + 6;
else if (opponentMove == 'C' && myMove == 'X')
totalScoreFirstPart += 1 + 6;
else if (opponentMove == 'C' && myMove == 'Y')
totalScoreFirstPart += 2 + 0;
else if (opponentMove == 'C' && myMove == 'Z')
totalScoreFirstPart += 3 + 3;

// Super DUPER good code
char outcome = myMove;
if (opponentMove == 'A' && outcome == 'X')
totalScoreSecondPart += 3 + 0;
else if (opponentMove == 'A' && outcome == 'Y')
totalScoreSecondPart += 1 + 3;
else if (opponentMove == 'A' && outcome == 'Z')
totalScoreSecondPart += 2 + 6;
else if (opponentMove == 'B' && outcome == 'X')
totalScoreSecondPart += 1 + 0;
else if (opponentMove == 'B' && outcome == 'Y')
totalScoreSecondPart += 2 + 3;
else if (opponentMove == 'B' && outcome == 'Z')
totalScoreSecondPart += 3 + 6;
else if (opponentMove == 'C' && outcome == 'X')
totalScoreSecondPart += 2 + 0;
else if (opponentMove == 'C' && outcome == 'Y')
totalScoreSecondPart += 3 + 3;
else if (opponentMove == 'C' && outcome == 'Z')
totalScoreSecondPart += 1 + 6;
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

printf("PART 1: Your total score after following the strategy guide: %d\n", totalScoreFirstPart);
printf("PART 2: Your total score after following the real strategy guide: %d\n", totalScoreSecondPart);

exit(EXIT_SUCCESS);
}

``````

While this works, it’s not very maintainable or expandable. It’s already hard to figure out which letter corresponds to what, and if there were more than 9 combinations then this approach gets unwieldy fast.

A much more compact way is to convert the characters `A, B, C` and `X, Y, Z` to `1, 2, 3` by taking advantage of the fact that each `char` in C can nicely map to an `int` with a little arithmetic, and the outcome of each comparison is unique:

``````int opponentMove = line[0] - 64;
int myMove = line[2] - 87;

totalScoreFirstPart += myMove;
if (opponentMove == myMove)
totalScoreFirstPart += 3;
else if (opponentMove - myMove == -1 || opponentMove - myMove == 2)
totalScoreFirstPart += 6;
else if (opponentMove - myMove == 1 || opponentMove - myMove == -2)
totalScoreFirstPart += 0;
``````

This is much smaller, though it’s not really better for readability and still would require heavy commenting. A nicer way to do this that would be more readable would be to have a bunch of `#define`s that map the characters and win conditions to their respective numbers, or create some kind of map data structure. A neat way to do comparisons would be to have a four-element list where each successive item in the list beats the previous (e.g. `Rock->Scissors->Paper->Rock`) so you could simply check if your move is immediately before or after the opponent’s move and determine who wins using only three, single-condition comparisons.

## Day 3

Day 3: Rucksack Reorganization

This was a fun one! Here is my initial solution:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

int
determinePriority(char item)
{
// Upper case A-Z (returns 27-52)
if (item - 96 < 0)
return item - 38;
// Lower case a-z (returns 1-26)
else
return item - 96;
}

int
firstPart(FILE* fp)
{
char firstCompartment[64] = { 0 };
char secondCompartment[64] = { 0 };
int sumOfPriorities = 0;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
// The line we got includes the newline character at the end
int compartmentSize = (linelen - 1) / 2 ;

// Split the line into the first and second compartments
strncpy(firstCompartment, line, compartmentSize);
strncpy(secondCompartment, &line[compartmentSize], compartmentSize);
firstCompartment[compartmentSize] = '\0';
secondCompartment[compartmentSize] = '\0';

// I love O(n^2)
for (int i = 0; i < compartmentSize; i++)
{
for (int j = 0; j < compartmentSize; j++)
{
if (firstCompartment[i] == secondCompartment[j])
{
sumOfPriorities += determinePriority(firstCompartment[i]);
// Break out of both loops
i = compartmentSize;
break;
}
}
}
}
free(line);
if (ferror(fp))
err(1, "getline");
return sumOfPriorities;
}

int
secondPart(FILE *fp)
{
char firstRucksack[64] = { 0 };
char secondRucksack[64] = { 0 };
char thirdRucksack[64] = { 0 };
int sumOfPriorities = 0;
int lineCounter = 1;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
switch (lineCounter)
{
case 1:
lineCounter++;
strncpy(firstRucksack, line, linelen - 1);
firstRucksack[linelen-1] = '\0';
break;
case 2:
lineCounter++;
strncpy(secondRucksack, line, linelen - 1);
secondRucksack[linelen-1] = '\0';
break;
case 3:
lineCounter++;
strncpy(thirdRucksack, line, linelen - 1);
thirdRucksack[linelen-1] = '\0';
break;
}

// We have the next set of three rucksacks, now we compare
if (lineCounter > 3)
{
lineCounter = 1;
// Friendship ended with O(n^2), now O(n^3) is my best friend
for (size_t i = 0 ; i < strlen(firstRucksack); i++)
{
for (size_t j = 0; j < strlen(secondRucksack); j++)
{
for (size_t k = 0; k < strlen(thirdRucksack); k++)
{
if (firstRucksack[i] == secondRucksack[j]
&& firstRucksack[i] == thirdRucksack[k])
{
sumOfPriorities += determinePriority(firstRucksack[i]);
// Break out of all loops
i = strlen(firstRucksack);
j = strlen(secondRucksack);
break;
}

}
}
}
}
}
free(line);
if (ferror(fp))
err(1, "getline");
return sumOfPriorities;
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

printf("PART 1: The sum of of the priorities of the common item types is: %d\n", firstPart(fp));
rewind(fp);
printf("PART 2: The sum of of the priorities of the badges is: %d\n", secondPart(fp));
fclose(fp);

exit(EXIT_SUCCESS);
}
``````

I split up each part into its own function this time just because each part is relatively large. Also, breaking out of multiple loops at once is a great use of `goto`, but I chose to just set the for loop conditions to cause the loops to end. Using `goto` would save some CPU cycles. I also realized after the fact that in `determinePriority()` I could greatly simplify my comparisons by just checking `if (item < 97)`, and in that case subtract 38 from it, otherwise subtract 96.

My initial solution isn’t the fastest, though it pretty simple and straightforward. Some possible ways this could be sped up would be:

1. Create some kind of collection of the characters already checked, so that if we encounter the same character again in the first string that we already know doesn’t exist in the second string, we don’t have to bother looping through the second string again.
2. Loop through each string once, creating a bitmap of which letters of the alphabet exist in the string, where `a` corresponds to the least significant bit, and `Z` the most significant bit of the range, then `&` the bitmaps together. The index of the position with a `1` corresponds to the letter they have in common and that index (plus 1 since the priorities start at 1) would be the priority.
3. Keep track of the number of times a letter appears in each string using an array of integers, where the indices correspond to priorities (letters) and the values at those indices would be `1` if the letter appears in one string, `2` if it appears in two, and so on. This would eliminate the entire `switch` statement I have and would be much simpler. (I got this one from looking at another’s solution after finishing mine).

In the code below, I implemented the second way for part 2:

``````int
secondPart(FILE *fp)
{
unsigned long firstRucksack  = 0;
unsigned long secondRucksack = 0;
unsigned long thirdRucksack  = 0;
int sumOfPriorities = 0;
int lineCounter = 1;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
switch (lineCounter)
{
case 1:
lineCounter++;
for (int i = 0; i < linelen-1; i++)
firstRucksack |= ((unsigned long)1 << (determinePriority(line[i])-1));
break;
case 2:
lineCounter++;
for (int i = 0; i < linelen-1; i++)
secondRucksack |= ((unsigned long)1 << (determinePriority(line[i])-1));
break;
case 3:
lineCounter++;
for (int i = 0; i < linelen-1; i++)
thirdRucksack |= ((unsigned long)1 << (determinePriority(line[i])-1));
break;
}

if (lineCounter > 3)
{
lineCounter = 1;
unsigned long commonItem = firstRucksack & secondRucksack & thirdRucksack;
for (int i = sizeof(unsigned long)*8; i >= 0; i--)
if (commonItem & ((unsigned long)1 << i))
sumOfPriorities += i + 1;
firstRucksack = 0;
secondRucksack = 0;
thirdRucksack = 0;
}
}
free(line);
if (ferror(fp))
err(1, "getline");
return sumOfPriorities;
}
``````

Not only does this code look much nicer, it’s also significantly faster than the first way:

``````\$ for i in (seq 3); time ./bitmap; end
PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in  593.00 micros    fish           external
usr time  556.00 micros  118.00 micros  438.00 micros
sys time   68.00 micros   68.00 micros    0.00 micros

PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in  600.00 micros    fish           external
usr time  505.00 micros    0.00 micros  505.00 micros
sys time  122.00 micros  122.00 micros    0.00 micros

PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in  521.00 micros    fish           external
usr time  426.00 micros    0.00 micros  426.00 micros
sys time  118.00 micros  118.00 micros    0.00 micros
``````
``````for i in (seq 3); time ./nobitmap; end
PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in    5.84 millis    fish           external
usr time    5.66 millis    0.00 micros    5.66 millis
sys time    0.19 millis  192.00 micros    0.00 millis

PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in    5.68 millis    fish           external
usr time    5.52 millis    0.00 micros    5.52 millis
sys time    0.13 millis  131.00 micros    0.00 millis

PART 2: The sum of of the priorities of the badges is: 2602

________________________________________________________
Executed in    5.69 millis    fish           external
usr time    5.56 millis    0.00 micros    5.56 millis
sys time    0.14 millis  142.00 micros    0.00 millis
``````

An average of 5.74 ms compared to 571 μs. That’s an order of magnitude faster!

## Day 4

Day 4: Camp Cleanup

Today’s challenge was pretty straightforward. Here is my solution:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

void
splitString(char *string, char delim, char **result)
{
int index = 0;
for (int i = 0; i < strlen(string); i++)
{
if (string[i] == delim)
index++;
else
strncat(result[index], &string[i], 1);
}
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

int fullOverlaps = 0;
int overlaps = 0;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[linelen-1] = '\0'; // cut off the newline

// Is there a better way to allocate memory for this?
char *ranges[2]; ranges[0] = malloc(8); ranges[1] = malloc(8);
char *range1[2]; range1[0] = malloc(8); range1[1] = malloc(8);
char *range2[2]; range2[0] = malloc(8); range2[1] = malloc(8);

splitString(line, ',', ranges);
splitString(ranges[0], '-', range1);
splitString(ranges[1], '-', range2);

if (atoi(range1[0]) <= atoi(range2[1])
&& atoi(range1[1]) >= atoi(range2[0]))
overlaps++;
if (atoi(range1[0]) >= atoi(range2[0])
&& atoi(range1[1]) <= atoi(range2[1]))
fullOverlaps++;
else if (atoi(range1[0]) <= atoi(range2[0])
&& atoi(range1[1]) >= atoi(range2[1]))
fullOverlaps++;
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

printf("PART 1: There are %d pairs in which one range fully contains the other.\n", fullOverlaps);
printf("PART 2: There are %d pairs which overlap.\n", overlaps);

exit(EXIT_SUCCESS);
}
``````

The only issue I can see with my solution is that the memory allocation for the ranges is a bit awkward… I’m not sure if there’s a better way to do that aside from manually `malloc`ing each component of the array of strings.

## Day 5

Day 5: Supply Stacks

This was a very fun challenge! Here is my solution to part 1:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

struct stack {
char contents[64];
int size;
};

char
pop(struct stack *stack)
{
stack->size--;
return stack->contents[stack->size];
}

void
push(struct stack *stack, char item)
{
stack->contents[stack->size++] = item;
}

void
splitString(char *string, char delim, char **result)
{
int index = 0;
for (int i = 0; i < strlen(string); i++)
{
if (string[i] == delim)
index++;
else
strncat(result[index], &string[i], 1);
}
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

struct stack *stacks[9];
for (int i = 0; i < 9; i++)
{
stacks[i] = (struct stack*)malloc(1*sizeof(struct stack));
stacks[i]->size = 0;
}

// This is way easier than trying to parse the drawing
for (int i = 0; i < strlen("DTRBJLWG"); i++)
push(stacks[0], "DTRBJLWG"[i]);
for (int i = 0; i < strlen("SWC"); i++)
push(stacks[1], "SWC"[i]);
for (int i = 0; i < strlen("RZTM"); i++)
push(stacks[2], "RZTM"[i]);
for (int i = 0; i < strlen("DTCHSPV"); i++)
push(stacks[3], "DTCHSPV"[i]);
for (int i = 0; i < strlen("GPTLDZ"); i++)
push(stacks[4], "GPTLDZ"[i]);
for (int i = 0; i < strlen("FBRZJQCD"); i++)
push(stacks[5], "FBRZJQCD"[i]);
for (int i = 0; i < strlen("SBDJMFTR"); i++)
push(stacks[6], "SBDJMFTR"[i]);
for (int i = 0; i < strlen("LHRBTVM"); i++)
push(stacks[7], "LHRBTVM"[i]);
for (int i = 0; i < strlen("QPDSV"); i++)
push(stacks[8], "QPDSV"[i]);

char *command[6];
for (int i = 0; i < 6; i++)
command[i] = (char *)malloc(8);

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[linelen-1] = '\0'; // cut off the newline

for (int i = 0; i < 6; i++)
memset(command[i], 0, 8);

splitString(line, ' ', command);

int count = atoi(command[1]);
int fromStack = atoi(command[3])-1;
int toStack = atoi(command[5])-1;

for (int i = 0; i < count; i++)
push(stacks[toStack], pop(stacks[fromStack]));
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

printf("Crates on top of each stack: ");
for (int i = 0; i < 9; i++)
printf("%c", pop(stacks[i]));
printf("\n");

for (int i = 0; i < 6; i++)
free(command[i]);
for (int i = 0; i < 9; i++)
free(stacks[i]);

exit(EXIT_SUCCESS);
}
``````

For part 2, the second `for` loop in the `while` block was replaced with the following:

``````for (int i = 0; i < count; i++)
push(stacks[toStack],
stacks[fromStack]->contents[stacks[fromStack]->size-count+i]);

for (int i = 0; i < count; i ++)
pop(stacks[fromStack]);
``````

Today, I think the only really awkward thing with my solution is how I initially set up the state of the stacks. But, instead of trying to write code to parse the “drawing” we were given, this seemed much easier and more straightforward. I did also make an effort to ensure all the memory I allocated was freed, even though that’s not strictly necessary for this program.

Another improvement I noticed I could make is in my `splitString` function where I could make sure each segment of `**result` is large enough to hold its respective string because `strncpy` doesn’t check for this. However, I’d also have to write some error handling code for that and it’s easier for AoC to just allocate a big enough buffer ;).

## Day 6

Day 6: Tuning Trouble

A simple challenge today. Here is my code:

``````#include <stdio.h>
#include <stdlib.h>
#include <err.h>

#define NUM_CHARS 14

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
linelen = getline(&line, &linesize, fp);
fclose(fp);
line[--linelen] = '\0'; // cut off the newline

char window[NUM_CHARS];

// Grab first NUM_CHARS chars
for (int i = 0; i < NUM_CHARS; i++)
window[i] = line[i];

// Then check if they are unique and slide the window along the text
for (int i = NUM_CHARS; i <= linelen; i++)
{
for (int j = 0; j < NUM_CHARS; j++)
for (int k = 0; k < NUM_CHARS; k++)
if (k == j)
continue;
else if (window[j] == window[k])
goto next_char;

printf("A marker appears after %d characters.\n", i);
break;

next_char:
for (int i = 0; i < NUM_CHARS-1; i++)
window[i] = window[i+1];
window[NUM_CHARS-1] = line[i];

}
free(line);

exit(EXIT_SUCCESS);
}
``````

This time I used a `goto` to break out of the nested loop which also allowed me to make my code a bit more terse by skipping past code that should only run when the characters are unique. This saved me from having to use to use something like a variable with an `if` statement to track if the characters were unique.

Later in the day when I had some more time, I came back to the code to fix it up with some improvements that some people online mentioned could be made. Namely, I didn’t need to start `k` at `0` since all values `k < j` would have already been checked, and I could remove the sliding window and replace it with a direct insert at index `i` modulo `NUM_CHARS` since the exact order of the characters doesn’t matter for this problem as long as the array has all `NUM_CHARS` previous characters. This is the new code with those changes:

``````// Then check if they are unique and test the rest of the text
for (int i = NUM_CHARS; i <= linelen; i++)
{
for (int j = 0; j < NUM_CHARS; j++)
for (int k = j+1; k < NUM_CHARS; k++)
if (window[j] == window[k])
goto next_char;

printf("A marker appears after %d characters.\n", i);
break;

next_char:
window[i % NUM_CHARS] = line[i];
}
``````

## Day 7

Day 7: No Space Left On Device

This was a bit of an annoying challenge. It’s not that it was necessarily difficult, it just felt like a lot of work since I hadn’t programmed a tree-like structure in C before. I ended up fighting a lot with trying to do things the right way with memory allocation and so on before eventually giving up and just hammering out a solution. Here it is:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

int unusedSpace = 0;
int smallestDirSize = 30000000;

struct node {
char name[32];
char type;
int size;
int numChildren;
struct node *parent;
struct node *children[16];
};

void
splitString(char *string, char delim, char **result)
{
int index = 0;
for (int i = 0; i < strlen(string); i++)
{
if (string[i] == delim)
index++;
else
strncat(result[index], &string[i], 1);
}
}

int
sumDirSizeLT100k(struct node *node)
{
int totalSize = 0;
for (int i = 0; i < node->numChildren; i++)
totalSize += sumDirSizeLT100k(node->children[i]);

if (node->type == 'd' && node->size <= 100000)
totalSize += node->size;
}

void
findSmallestDirToDelete(struct node *node)
{
for (int i = 0; i < node->numChildren; i++)
findSmallestDirToDelete(node->children[i]);

if (node->type == 'd' && node->size+unusedSpace >= 30000000
&& node->size <= smallestDirSize)
smallestDirSize = node->size;
}

void
calculateDirSizes(struct node *node)
{
for (int i = 0; i < node->numChildren; i++)
{
calculateDirSizes(node->children[i]);
node->size += node->children[i]->size;
}
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

struct node *rootDir = (struct node*)malloc(sizeof(struct node));
strcpy(rootDir->name, "/");
rootDir->type = 'd';
rootDir->size = 0;
rootDir->numChildren = 0;
rootDir->parent = NULL;

struct node *currentDir = rootDir;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[--linelen] = '\0';

char *strings[3];
strings[0] = (char *)malloc(32);
strings[1] = (char *)malloc(32);
strings[2] = (char *)malloc(32);

// Line is either:
//   \$ cd <dir>
//   \$ ls
//   dir name
//   <size> filename
if (line[0] == '\$' && line[2] == 'c')
{
if (line[5] == '.')
{
currentDir = currentDir->parent;
}
else
{
splitString(line, ' ', strings);
for (int i = 0; i < currentDir->numChildren; i++)
{
if (!strcmp(currentDir->children[i]->name, strings[2]))
{
currentDir = currentDir->children[i];
break;
}
}
}

}
else if (line[0] == '\$' && line[2] == 'l')
{
continue;
}
else
{
splitString(line, ' ', strings);

struct node *newNode = (struct node*)malloc(sizeof(struct node));
strcpy(newNode->name, strings[1]);
newNode->numChildren = 0;
newNode->parent = currentDir;
currentDir->children[currentDir->numChildren++] = newNode;

if (strings[0][0] == 'd')
{
newNode->type = 'd';
newNode->size = 0;
}
else
{
newNode->type = 'f';
newNode->size = atoi(strings[0]);
}
}
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

calculateDirSizes(rootDir);

int totalSize = sumDirSizeLT100k(rootDir);
printf("Part 1: %d\n", totalSize);

unusedSpace = 70000000 - rootDir->size;
findSmallestDirToDelete(rootDir);
printf("Part 2: %d\n", smallestDirSize);

exit(EXIT_SUCCESS);
}
``````

I’m fully aware that this code is probably not very great, but I don’t really care since I basically just wanted to get it done and move on to something else after the several hours I worked on this.

## Day 8

Day 8: Treetop Tree House

Here is my code for today’s challenge:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

#define DIMENSION 99

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

int trees[DIMENSION][DIMENSION] = { 0 };
int numTreesVisible = 0;
int mostScenicTree = 0;

int linecount = 0;
char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[--linelen] = '\0'; // cut off the newline
for (int i = 0; i < DIMENSION; i++)
trees[linecount][i] = line[i] - 48;
linecount++;
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

for (int i = 0; i < DIMENSION; i++)
{
for (int j = 0; j < DIMENSION; j++)
{
int visibleDirections = 4;
int scenicValues[4] = { 0 };
int scenicScore = 0;
// North
for (int k = j-1; k >= 0; k--)
{
scenicValues[0]++;
if (trees[i][j] <= trees[i][k])
{
visibleDirections--;
break;
}
}
// South
for (int k = j+1; k < DIMENSION; k++)
{
scenicValues[1]++;
if (trees[i][j] <= trees[i][k])
{
visibleDirections--;
break;
}
}
// East
for (int k = i+1; k < DIMENSION; k++)
{
scenicValues[2]++;
if (trees[i][j] <= trees[k][j])
{
visibleDirections--;
break;
}
}
// West
for (int k = i-1; k >= 0; k--)
{
scenicValues[3]++;
if (trees[i][j] <= trees[k][j])
{
visibleDirections--;
break;
}
}

if (visibleDirections)
numTreesVisible++;
scenicScore = scenicValues[0] * scenicValues[1]
* scenicValues[2] * scenicValues[3];

if (scenicScore > mostScenicTree)
mostScenicTree = scenicScore;
}
}
printf("PART 1: The number of trees visible from the edge is %d\n", numTreesVisible);
printf("PART 2: The most scenic tree has a scenic value of %d\n", mostScenicTree);

exit(EXIT_SUCCESS);
}
``````

This challenge was much nicer compared to yesterday’s. Something tells me this is probably the most straightforward way to approach it, though not the most efficient given all the looping.

## Day 9

Day 9: Rope Bridge

This was okay. It was very satisfying to program something and watch as the tail followed around the head… until I realized I’d have to extend my program to 9 tails. Here is my code for part 1:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

#define DIMENSION 2000 // Brute forcing because idk the starting point

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

int positionsVisited = 1;
char grid[DIMENSION][DIMENSION] = {{ 0 }};

// Coords are Y,X
int hpos[2] = {DIMENSION/2, DIMENSION/2};
int tpos[2] = {DIMENSION/2, DIMENSION/2};

grid[tpos[0]][tpos[1]] = 'T';
grid[hpos[0]][hpos[1]] = 'H';
int headOnVisitedTile = 0;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[linelen-1] = '\0'; // cut off the newline

char direction = line[0];
int numMoves = atoi(&line[2]);

for (int i = 0; i < numMoves; i++)
{
grid[hpos[0]][hpos[1]] = '#';
else
grid[hpos[0]][hpos[1]] = 0;
grid[tpos[0]][tpos[1]] = '#';

switch (direction)
{
case 'U': hpos[0]--; break;
case 'D': hpos[0]++; break;
case 'L': hpos[1]--; break;
case 'R': hpos[1]++; break;
}

if (abs(hpos[0] - tpos[0]) > 1 || abs(hpos[1] - tpos[1]) > 1)
{
if (hpos[0] > tpos[0] && hpos[1] < tpos[1])
{
tpos[1]--;
tpos[0]++;
}
else if (hpos[0] > tpos[0] && hpos[1] > tpos[1])
{
tpos[1]++;
tpos[0]++;
}
else if (hpos[0] < tpos[0] && hpos[1] < tpos[1])
{
tpos[1]--;
tpos[0]--;
}
else if (hpos[0] < tpos[0] && hpos[1] > tpos[1])
{
tpos[1]++;
tpos[0]--;
}
else if (hpos[0] > tpos[0])
tpos[0]++;
else if (hpos[0] < tpos[0])
tpos[0]--;
else if (hpos[1] > tpos[1])
tpos[1]++;
else if (hpos[1] < tpos[1])
tpos[1]--;
}

if (grid[hpos[0]][hpos[1]] == '#')
else

grid[hpos[0]][hpos[1]] = 'H';
grid[tpos[0]][tpos[1]] = 'T';
}
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

for (int i = 0; i < DIMENSION; i++)
for (int j = 0; j < DIMENSION; j++)
if (grid[i][j] == '#')
positionsVisited++;
positionsVisited++;

printf("PART 1: The tail visits %d positions at least once.\n", positionsVisited);
printf("PART 2: No\n");

exit(EXIT_SUCCESS);
}
``````

Keeping track of one tail segment was not too difficult, but keeping track of 9 felt like a chore because my initial solution wasn’t very generalizable so I gave up on part 2. I might come back to it later, but I already spent enough time getting caught up on challenges and didn’t want to sink more into it.

## Day 10

Day 10: Cathode-Ray Tube

I enjoyed this one. Here is my code:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

int
sampleValues(int x, int cycle)
{
// Could compact this with cycle - 20 % 40
switch (cycle)
{
case 20:
case 60:
case 100:
case 140:
case 180:
case 220: return x * cycle;
}
return 0;
}

void
drawPixel(int x, int cycle)
{
if ((cycle - 1) % 40 >= x - 1 && (cycle - 1) % 40 <= x + 1)
printf("#");
else
printf(" ");

if (cycle % 40 == 0)
printf("\n");
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

int x = 1;
int cycle = 0;
int change = 0;
int sum = 0;

char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[--linelen] = '\0'; // cut off the newline
change = atoi(&line[5]);

cycle++;
drawPixel(x, cycle);
sum += sampleValues(x, cycle);

if (line[0] == 'a')
{
cycle++;
drawPixel(x, cycle);
sum += sampleValues(x, cycle);
x += change;
}
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

printf("PART 1: %d\n", sum);

exit(EXIT_SUCCESS);
}
``````

This challenge was pretty nice. There are probably some places I could clean up my code, such as removing duplicate code in the while loop and following the comment in the `sampleValues` function, but I’m otherwise happy with that.

## Day 11

Day 11: Monkey in the Middle

Here is an abbreviated version of my code:

``````#include <stdio.h>
#include <stdlib.h>

struct monkey {
unsigned long items[32];
int numItems;
char operator;
int operand;
int modulus;
int trueMonkey;
int falseMonkey;
int inspections;
};

void
throwItem(struct monkey **monkeys, int from, int to)
{
monkeys[to]->items[monkeys[to]->numItems++] = monkeys[from]->items[0];
for (int i = 0; i < monkeys[from]->numItems; i++)
{
monkeys[from]->items[i] = monkeys[from]->items[i+1];
}
monkeys[from]->numItems--;
}

int
main (void)
{
struct monkey *monkeys[8];
for (int i = 0; i < 8; i++)
monkeys[i] = (struct monkey *)malloc(sizeof(struct monkey));

unsigned long items0[] = {85, 77, 77};
monkeys[0]->numItems = 3;
for (int i = 0; i < monkeys[0]->numItems; i++)
monkeys[0]->items[i] = items0[i];
monkeys[0]->operator = '*';
monkeys[0]->operand = 7;
monkeys[0]->modulus = 19;
monkeys[0]->trueMonkey = 6;
monkeys[0]->falseMonkey = 7;
monkeys[0]->inspections = 0;

// Repeat the above for the rest of the monkeys

// I just used an external calculator
unsigned long lcm = 9699690;

/* for(int i = 0; i < 20; i++) */
for(int i = 0; i < 10000; i++)
{
for (int j = 0; j < 8; j++)
{
monkeys[j]->inspections += monkeys[j]->numItems;
while (monkeys[j]->numItems > 0)
{

if (monkeys[j]->operator == '*' && monkeys[j]->operand == 0)
monkeys[j]->items[0] *= monkeys[j]->items[0];
else if (monkeys[j]->operator == '*')
monkeys[j]->items[0] *= monkeys[j]->operand;
else
monkeys[j]->items[0] += monkeys[j]->operand;

/* monkeys[j]->items[0] /= 3; */
monkeys[j]->items[0] %= lcm;

if (monkeys[j]->items[0] % monkeys[j]->modulus == 0)
throwItem(monkeys, j, monkeys[j]->trueMonkey);
else
throwItem(monkeys, j, monkeys[j]->falseMonkey);
}
}
}

for (int i = 0; i < 8; i++)
printf("Monkey %d inspected items %d times.\n",
i, monkeys[i]->inspections);

exit(EXIT_SUCCESS);
}
``````

This challenge was pretty straightforward until the second part. It wasn’t obvious to me that you needed to find the least common multiple of the monkeys’ comparison values (`monkeys[x]->modulus` in my code). Looking online, it seems that many others struggled with this because it just comes down to having seen this kind of problem before or having a maths background that covered this. Kind of annoying, to be honest.

I also just hardcoded the monkey data into my program since I didn’t want to bother parsing and there were only 8 monkeys.

## Day 12

Day 12: Hill Climbing Algorithm

This one involved a good bit of work. I don’t think I’ve ever had to program a depth-first search algorithm before, let alone in C, so this was a good learning exercise.

Here is my code:

``````#include <stdio.h>
#include <stdlib.h>
#include <err.h>

struct coords
{
int x;
int y;
int elevation;
int explored;
struct coords *parent;
};

struct FIFOqueue
{
int size;
struct coords *contents[128];
};

void
enqueue(struct FIFOqueue *queue, struct coords *item)
{
queue->contents[queue->size++] = item;
}

struct coords*
dequeue(struct FIFOqueue *queue)
{
struct coords *item = queue->contents[0];
queue->size--;
for (int i = 0; i < queue->size; i++)
queue->contents[i] = queue->contents[i+1];
return item;
}

// Depth-first search algorithm
int
traverseMountain(struct coords *map[41][77], struct coords *start, struct coords *end)
{
int steps = 0;

struct FIFOqueue *queue = (struct FIFOqueue *)malloc(sizeof(struct FIFOqueue));
queue->size = 0;

start->explored = 1;

enqueue(queue, start);

while (queue->size > 0)
{
// Current position
struct coords *cur = dequeue(queue);

if (cur == end)
{
int result = 0;
while (end->parent)
{
end = end->parent;
result++;
}
// Reset state
for(int x = 0; x < 41; x++)
{
for(int y = 0; y < 77; y++)
{
map[x][y]->explored = 0;
map[x][y]->parent = NULL;
}
}
free(queue);
return result;
}

// North
if (cur->y - 1 >= 0
&& ! map[cur->x][cur->y - 1]->explored
&& map[cur->x][cur->y - 1]->elevation - 1
<= map[cur->x][cur->y]->elevation)
{
map[cur->x][cur->y - 1]->explored = 1;
map[cur->x][cur->y - 1]->parent = map[cur->x][cur->y];
enqueue(queue, map[cur->x][cur->y - 1]);
}

// East
if (cur->x + 1 < 41
&& ! map[cur->x + 1][cur->y]->explored
&& map[cur->x + 1][cur->y]->elevation - 1
<= map[cur->x][cur->y]->elevation)
{
map[cur->x + 1][cur->y]->explored = 1;
map[cur->x + 1][cur->y]->parent = map[cur->x][cur->y];
enqueue(queue, map[cur->x + 1][cur->y]);
}

// South
if (cur->y + 1 < 77
&& ! map[cur->x][cur->y + 1]->explored
&& map[cur->x][cur->y + 1]->elevation - 1
<= map[cur->x][cur->y]->elevation)
{
map[cur->x][cur->y + 1]->explored = 1;
map[cur->x][cur->y + 1]->parent = map[cur->x][cur->y];
enqueue(queue, map[cur->x][cur->y + 1]);
}

// West
if (cur->x - 1 >= 0
&& ! map[cur->x - 1][cur->y]->explored
&& map[cur->x - 1][cur->y]->elevation - 1
<= map[cur->x][cur->y]->elevation)
{
map[cur->x - 1][cur->y]->explored = 1;
map[cur->x - 1][cur->y]->parent = map[cur->x][cur->y];
enqueue(queue, map[cur->x - 1][cur->y]);
}
}
}

int
main (void)
{
FILE *fp = fopen("input.txt", "r");
if (fp == NULL)
{
err(1, "Failed to open input.txt");
exit(EXIT_FAILURE);
}

struct coords *map[41][77] = { NULL };
struct coords *start = NULL;
struct coords *end = NULL;

int n = 0;
char *line = NULL;
size_t linesize = 0;
ssize_t linelen = 0;
while ((linelen = getline(&line, &linesize, fp)) != -1)
{
line[--linelen] = '\0';
for (int i = 0; i < linelen; i++)
{
map[n][i] = (struct coords *)malloc(sizeof(struct coords));
map[n][i]->x = n;
map[n][i]->y = i;
map[n][i]->elevation = (int)line[i];
map[n][i]->explored = 0;
map[n][i]->parent = NULL;

if (line[i] == 'S')
{
start = map[n][i];
start->elevation = 97; // 'a'
}
else if (line[i] == 'E')
{
end = map[n][i];
end->elevation = 123; // 'z' + 1
}
}
n++;
}
free(line);
if (ferror(fp))
err(1, "getline");
fclose(fp);

int part1 = traverseMountain(map, start, end);

int part2 = 999;
for(int x = 0; x < 41; x++)
{
for(int y = 0; y < 77; y++)
{
if (map[x][y]->elevation == 'a')
{
int temp = traverseMountain(map, map[x][y], end);
if (temp && temp < part2)
part2 = temp;
}
}
}

printf("The shortest path up to the peak requires %d steps.\n", part1);
printf("The shortest path from any lowest point requires %d steps.\n", part2);

exit(EXIT_SUCCESS);
}
``````

In the real world, this could be improved by having `traverseMountain` return `-1` if there is no path to the end instead of returning `0` by default. I also think the second part—where you’re just trying to find the shortest path from any `'a'` elevation to the end—could be done more efficiently by starting at the top and working your way down instead but, since I had already done it going bottom-up for the first part, I opted to stick with the bottom-up approach.