code – Page 3 – Juan's adventures in security & compliance

Days 3, 4 & 5

For day 3 it was required to find how many trees a specific slope would encounter. The field was given as a field of limited width, far smaller than the height. The problem states that the pattern repeats to the right, which means for any real position X, the relative position within the input would be given by modulo division. That is to say if the input has a width of 10, any real position X can be mapped onto the limited width input by X mod 10. For part 2 it was required to find the product of encountered trees across various slopes, which I hard coded and then got the product from.

Day 4

Day 4 had data in key:value pairs but the formatting was not constant accross the entries. The idea was then to split each record into a hash table and test that hash table. For part 1 it was a case of hard coding the required fields and then checking if they existed in the keys of the record (hash table). With return 0 in the case of a negative it reduces the number of tests.

Part 2 required the same tests and then data validation. The three year data fields were simple comparisons. However, the other fields di allow for some interesting regular expressions. By making the check subroutine return 0 upon the first failed test reduced (a little) the amount of tests performed.

Day 5

The input for this challenge consisted in a set of letters representing a seat. The first letters used a binary representation of the row, and the final 3 represented the which seat in that row the seat was. The data is already binary numbers, just with different characters… Regex to the rescue. Capturing the part which was required (row or column), converting to binary and then to decimal => easy to understand. With the getRow and getCol subroutines sorted and tested, all that remained was to find the highest sanity check. Part 1 sorted.

Part 2, perhaps as I was running on remnants of ~~sleep~~ coffee fumes encountered far more issues. Initially I wanted to create an array of anonymous arrays such that if a seat existed it would get marked as “X”, and I could then look up which seat was not labeled as “X”. Except that was not what the questions was asking -> I needed the missing ID. What data structure lets me find items incredibly fast? The hash table. By using the same code from part 1, it was then just a matter of adding each sanity check into a hash table. $seats{$sanity} = 1.

From part 1, the highest sanity check is 801, so simply checking for all numbers up to 801 if exists $seats{$_} and printing all those where the check failed. The terminal printed the numbers 0-39 and then one single ID in the hundreds. The problem stated that the first couple IDs weren’t occupied as they were not seats => verifying that the ids 1 above and 1 below the result existed and voila. Could it have been done more neatly? Yes, but then, that would mean keeping up with perl idioms and using it more than once a year.

Day 1

Part 1

I solved part 1 with Excel. Despite all its shortcomings, Excel remains an excellent tool to visualise and manipulate data. The logic was as follows: if any 2 unique numbers add up to 2020, then I cannot have any numbers with a sum greater than 2020. First step was to sort the data and find the smallest number, which for me was 60. Now for any number k in the list, if a different number from the list, say b, sums to 2020, then 2020-k-b would be equal to 0. The check is therefore to add an additional column where the values are given by 2020-k-b. When k+b is greater than 2020, the check returns a negative number. By deleting all entries with negative values it is possible to reduce the list and I found that 60 did not give any solutions. The next number in the list was 107. 107 was sadly also not a part of the solution, but did reduce the amount of testing data significantly. Continuing with this method until eventually the check column provided a 0 and I had the 2 numbers required.

Part 2

Part 2 was also solvable using Excel, but not in 5 minutes as was the case for part 1. Part 2 required finding 3 numbers in the list whose sum was 2020. First instinct was to have a symmetrical matrix, setting the values within to be 2020-ColumnHeader-RowHeader and then using conditional formatting such that if a number was a part of the original date it would get a green background.

Instead I went with Python for the solution. After sorting the data, I was able to use the below to get the solution.

for i in range(len(data)-3):
    n1 = data[i]
    for j in range(i+1, len(data)-2):
        n2 = data[j]
        if (n1 + n2 < 2020):
        for k in range(len(data)-1, j, -1):
            n3 = data[k]
            if n1 + n2 + n3 == 2020:
                print(n1*n2*n3)
                exit()

This takes advantage of the fact that at any point, i < j < k slightly reducing the calculation time although not the time complexity, which remains at O(n³). A colleague managed to reduce it to O(n²) by making a smart use of sets.

Day 2

Day 2 was all about data parsing. Nothing better for data parsing than ~~headache inducing~~ regular expressions. The best regex engine is from perl. Most other languages invoke ‘perl-equivalent’ regex, but the syntax is never quite as simple. After looking at the problem again, I could have solved it in a much simpler regex than I did, but then, Advent of Code is about getting a solution, rather than the solution.

$data =~ /(\d)-(\d)*([a-z])\:\s([az]+)/;
my $min = $1;
my $max = $2;
my $check = $3;
my $pw = $4;

Not sure if that could be combined into a single line by making the initialisation a part of the regex check. But then, that’s why people say perl is unreadable so back to good, human readable code. Instead I did several substitution expressions at each line to transform it into a CSV line, split it into an array and then used variables such that I wouldn’t need to be referencing array indices in the rest of the code. In order to solve the first part, I removed all characters which were not a part of the password policy and then verified that the remaining string had a length between the min & max character occurences.

The second part involved checking a different policy, verifying if the password had the given letter at one of the 2 positions provided, but not both. I wasn’t able to get perl to treat the passwords as an array of characters as I remember doing in C eons ago. This meant splitting the pw into an array. Because the elves don’t recognise that arrays start at 0 there is a large risk of OBOE errors => reduce both min & max variables by 1, and then through the use of xor verify if only 1 of the 2 conditions works. Could it have been done with regex? Yes. Was using the array index much easier to implement, and later on, read? I certainly hope so.