Categories
code perl Tech

Advent of Code 2020 day 14

Day 14

The days challenge starts explaining that a binary representation needs to be observed with a filter, and then the new representation stored in a specific place of memory. It is not mentioned at any point that memory is full, suggesting that a hash table will allow for the best way of storing the values. The first roadblock is accessing the elements of the mask, this is made easy by using split and storing the mask as an array.

Storing the mask

There are 2 possibilities. Either the mask is updated, or a value is stored in memory. After chomping the line, we immediately check if it is a mask instruction. If it is a mask instruction, we extract the 36 characters by extracting the match to 36 adjacent characters composed of 1, 0 and X. The extraction is then split into @mask (declared outside of scope because… scope.

The second part didn’t allow for 2 greedy matched. $line =~ /(\d+).*(\d+)/ only matches the first digit of the second pattern. Overcame the issue by using substitutions and matching twice with $1.

Extracting the memory adress and value

As the value is given in decimal, sprintf provides a string representation of the binary. From there it’s split into an array, and 0s added to the front until it is the same size as the mask. Given that the value can have different sizes, using the last index of the array as the control allows to verify the size without calculating the size. Finally, conversion back in decimal is done using the builtin oct function.

Finally, find the sum of the values using a simple foreach loop:

Part 1

The main challenge here was working with decimal and binary representations and changing between them. Additionally, because of the binary numbers are not stored as strings, analysing them on a character by character basis meant converting into an array of chars. Highly similar to a C representation.

Link: https://github.com/jspinel/AdventofCode/tree/main/2020/14

Categories
Tech

Advent of Code 2020 days 10 & 11

Day 10

Todays challenge required analysing a list of numbers (output units). The first thing was to place these numbers in an array, sort it, and add 0 (initial output unit) at the begining of the array. I couldn’t find a nice way to regex this one, most likely because the challenge did not involve text processing. Given the list was sorted from the previous steps, and I trust the data to not be poisoned with impossible elements, I used a simple foreach loop to check wether the increase in (output units) is of 1 or 3.

Possibly the fastest solution this year

Part 2 was a bit more of a roller coaster. My initial thoughts involved combinations and permutations. Permutations and combinations are nice and all, but figuring out the adequate mechanisms was beyond my pay grade. I initially wanted to try arriving at the end and work my way from the start, but this doesn’t work as the only fixed point is the start with 0 (output units). By using a hash with the output of the devices as the key and 0 as the initial value, it is possible to traverse the keys in order such that the value is how many routes there are up to that output. The initial output, 0, has only 1 route and is therefore defined before the loop.

Simple iteration

By checking at each key if the next 3 integers are keys, no routes are forgotten, and no need to look at possible combinations of selected or non selected devices which still provide a valid route. The twist at part 2 made it a rather challenging day, while keeping the initial part accessible for people switching languages, brushing up on them, or simply starting out in code.

Day 11

It looks like day 11 is the day my over engineering ways start making sense. Until they don’t. Had to call it a day after spending far too long on part 1. This challenge was fairly interesting, in essence an implementation of the game of life. I started off by selecting the data structure. Against my better judgement, or perhaps due to the better judgement I went with an array of arrays. Or… array of array refs.

Processing input data

Here I already have 2 variables which will help later on for the data processing. After some testing, they are in scope of the subroutine and don’t need to be passed as arguments (trivial to do for the testing if that were the case). The next part was writing the test subroutine. I wanted the subroutine to perform the change on the waiting room and return if it had made a change. At just over 100 lines, this is the engine for this problem.

Some basic definitions
All the edge cases

Each position in the map can have 1 of 3 states: Empty chair, Occupied chair or floor. Floor is never occupied so doesn’t change. Because the mutations all happen simultaneously, I need to check if the adjacent chairs are occupied. However, given some chairs may change states and affect this decision I needed the 2 additional states: Future Empty (FE) and Future Used (FU). By using return 0 I was able ti limit the number of checks done on each chair although that is not necessarily the most elegant solution.

There are only edge cases

Same logic as before, except in this case rather than returning 0, counter went up and was analysed at the end. Of course, if the state is neither empty or occupied, then the floor is lava.

The actual calculation

After a few too many infinite loops (see the interesting debugging tool from the 00’s) this do-while loop provided the solution. I had initially tried $changes++ if testchange($i,$j); but most likely that wasn’t working due to other factors leading to the infinite loops. Used a tiny regex, just for the sake of it. That initial loop does the entire control, as it checks each cell if it will change, thus changing the variable for the control. The second for loop simply standardises the content being worked on.

Finally, the solution to the task at hand:

8/174 lines, or approx 6%

Because this happens after the do-while block the state of the waiting room won’t change. From there it’s a simple nested loop to check the number of occupied chairs. could have been added to the do while loop with a control block depending on changes being equal to 0. I did not have the patience for part 2… maybe later