Advent of Code: Day 1

2021-12-01

So, it’s December all ready. I haven’t written anywhere near as many blogs this year as I would like to. Hopefully the Advent of Code this year will give me some things to write about and make this years list of blogs look better.

This is the first year I am doing the Advent of Code so don’t really know what to expect. However, with day 1 done, I think I’ll probably enjoy it.

If you’re reading this, it is no longer day 1. I will refrain from publishing the solutions until at least the day after they go live. However, if previous years are anything to go by, you should still be able to view the puzzles and have a go for yourself:

https://adventofcode.com/2021/day/1

I am going to use the project puzzles this year to try and learn C. I have used it a little bit but certainly wouldn’t call myself proficient. This is supposed to be a way for me to get better so if you’re looking for well formed C code by someone who knows what they are doing, you should probably look elsewhere.

My solutions are available here:

https://git.jonathanh.co.uk/jab2870/Advent-of-Code/src/branch/master/day1

Part 1

The first part of today’s challenge involved taking a list of numbers and counting the number of times a number is higher than the previous number.

The example they gave is with this list of numbers:

199
200
208
210
200
207
240
269
260
263

I put those in a text file called example.txt.

Bash

I started by implementing it in bash. Why? Because I know bash and wanted to make sure I had understood the problem before trying to battle with C.

#!/usr/bin/env bash

file="$1"
increasing=0
last=99999999

while read line; do
    if [ "$line" -gt "$last" ]; then
        increasing="$(( increasing + 1 ))"
    fi
    last="$line"
done < <(cat "$file")

echo "$increasing were increasing"

There is not a huge amount going on here. If you are at all familiar with bash, you can probably see what is going on here. I initially set up variables to hold the file name (passed in as the first argument), a counter for the number of times we increase from one line to the next and the value of the last line we’ve seen that I initially set to a large number.

Then we enter the loop. It is worth noting that the loop had to be of the form:

while read line; do
    # Do stuff
done < <(cat "$file")

Rather than:

cat "$file" | while read line; do
    # Do stuff
done

The reason for this is that pipes are executed in a sub shell meaning they can’t change variables in the initial shell. In other words, with the second method, we wouldn’t be able to update the increasing and last variables from inside the loop.

Inside the loop, I check to see if the current value is larger than the previous value and if it is I increment the increacing variable by 1. I then set the last variable so it can be used for the next iteration.

Finally, once all the lines have been done, I print out the number of lines that were increasing.

C

So, in a surprise to nobody, my C implementation is not as short as the bash one. However, it wasn’t as bad as I thought it would be.

Step 1 was trying to work out how to read a file in to c one file at a time.

Given that I knew the format of the lines, I was able to use fscanf to get each of them.

Although the syntax is slightly different, the logic is very similar between the Bash and C implementations.

#include <stdio.h>

int main( int argc, char *argv[] ){
    if( argc == 2 ) {
        unsigned int last = ~0;
        unsigned int increasing = 0;
        unsigned int value;

        // Read the values into an array
        FILE *fp=fopen(argv[1], "r");
        while (!feof (fp)){
            fscanf(fp, "%d\n", &value);
            if ( value > last )
                increasing++;
            last = value;
        }
        fclose(fp);


        printf( "%d were increasing\n", increasing );

        return 0;
    } else {
        printf("You need to provide a file\n");
        return 1;
    }
}

Part 2

The extension for part 2 was to change the program so that rather than comparing lines with the previous line, the sum of 3 consecutive lines should be compared.

199  A
200  A B
208  A B C
210    B C D
200  E   C D
207  E F   D
240  E F G
269    F G H
260      G H
263        H

So, the sum of the numbers marked with A would be compared to the sum of those marked with B. Then B with C and so on.

I think the intended way of doing this is to first create an array type structure of sums then use the code from part 1 to work out how many of these sums are increasing. However, a short cut can be taken. The sum of the next group of numbers is always going to be the sum of the previous numbers plus the next digit, minus the first. It follows therefore that we can compare the groups by comparing the differences of every 3 numbers rather than adjacent numbers.

So, for example

A = 199 + 200 + 208

B = 200 + 208 + 210

We can confirm that group B increases from group A because 210 is greater than 199.

In order to do this, I want to be able to easily reference individual entries by their index so rather than doing the comparisons on the first pass through the file, I first create an array. I can then compare an entry with the entry 3 before it.

Bash

#!/usr/bin/env bash

file="$1"
increasing=0

readarray -t "arr" < "$file"

length="${#arr[@]}"

for i in $(seq 3 "$length"); do
    curr="${arr[$i]}"
    prev3="${arr[$((i - 3))]}"

    if [ -n "$curr" ] && [ "$curr" -gt "$prev3" ]; then
        increasing="$((increasing + 1))"
    fi
done

echo "$increasing were increacing"

You’ll see that bash has a nice built-in for turning a file into an array. However, any bonus points it it might get for that, it looses by having the worst syntax ever for getting the length of that array. Who thought that ${#arr[@]} would ever be a good idea‽

C

#include <stdio.h>

int countLines(char filename[]){
    FILE *fp;
    fp=fopen(filename, "r");
    long int lines =0;

    if ( fp == NULL ) {
        return -1;
    }

    while (EOF != (fscanf(fp, "%*[^\n]"), fscanf(fp,"%*c")))
        ++lines;

    fclose(fp);
    return lines;
}

int main( int argc, char *argv[] ){
    if( argc == 2 ) {
        // 1 less because file ends with trailing new line
        int lines=countLines(argv[1]);
        int values[lines];
        int line=0;
        FILE *fp=fopen(argv[1], "r");
        int increasing = 0;

        // Read the values into an array
        while (!feof (fp)){
            fscanf(fp, "%d\n", &values[line]);

            if ( (line >= 3) && (values[line] > values[line-3]) ){

                increasing++;
                
            }

            line++;
        }
        fclose(fp); // closing file

        printf( "Increasing: %d\n", increasing );

        return 0;
    } else {
        printf("You need to provide a file\n");
        return 1;
    }
}

So this is obviously longer than the bash version but mainly because there isn’t a nice way of putting a text file into an array. I have to first iterate through the file to determine how many lines there are, then allocate that much space for the array, then re-run through the file to get the values.

Initially, I then had a third loop where I iterated through the newly created array to determine if there was an increase. However, I then realised I could do that whilst populating the array.