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.
Table of Contents
Day 1
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
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 #defines 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:
- 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.
- Loop through each string once, creating a bitmap of which letters of the
alphabet exist in the string, where
acorresponds to the least significant bit, andZthe most significant bit of the range, then&the bitmaps together. The index of the position with a1corresponds to the letter they have in common and that index (plus 1 since the priorities start at 1) would be the priority. - 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
1if the letter appears in one string,2if it appears in two, and so on. This would eliminate the entireswitchstatement 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
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 mallocing each component of the array of strings.
Day 5
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
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;
return totalSize;
}
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
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
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++)
{
if (headOnVisitedTile)
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]] == '#')
headOnVisitedTile = 1;
else
headOnVisitedTile = 0;
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++;
if (headOnVisitedTile)
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
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
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.