Day 3: Rucksack Reorganization
View puzzle page »
Skip to the code?
If you’d like to read my solution first, the code is available on GitHub.
The first puzzle presents an input which is a list of alphabetic strings where each character represents an item in an inventory. The inventories are divided into two ‘compartments’ which are always defined as the first and second halves of the strings respectively. The goal of the puzzle is to identify the ‘item’ that appears in both compartments and then calculate it’s value based on the following two rules:
zis equal to 1 to 26
Zis equal to 27 to 52
The answer to the puzzle is the sum of all of the values of the common character in each inventory.
We can repurpose our file open and loop from the previous days again. We’ll also define a variable to hold the sum.
The first thing we need to do with each line is split it in half. We can employ Python’s
len functions for this.
first_half variable, we store the chars from the string which are previous to the halfway mark. We use
len(line) to get the length of the whole string and then we divide this length by 2 using the
// operator which gives us the floor of the division. We know the strings should be even length but it’s always good practice to account for edge cases.
We repeat the same calculation but shift the
: to capture from the right of halfway mark.
To discover the common character in both strings, we can employ various algorithmic approaches but I always favour using built-ins. The
set function when called against a string will coerce it to a sequence of unique characters. Once it is a set, we can employ binary operators (
&) to determine characters common to two sets.
We’re kind of abusing
set here so we pay for it by not having a object-level method to grab the first element. We know in this context that there is only one item in the set so we could just use
set.pop which returns an item from the set at random but, if there’s ever more than one item, this is not a good choice.
Python has a neat function called
iter which will let us treat our set like an iterator and call the
next function to consume the first element in the iterable. This is orders of magnitude faster than, say, coercing the set to a list and using the index.
Now we need to get the value of the character returned. The
ord function in Python returns the integer representation of the Unicode code point for the character, e.g. ‘a’ returns 97 and ‘A’ returns ‘65’. The example here should hint at the initial problem. Firstly, the ord values don’t immediately align with the values in the puzzle and lowercase chars end up with higher values that uppercase. The math is simple enough though - we can take the lowercase characters down to their representative values for the puzzle by subtracting 96 and the uppercase characters by subtracting 38. ‘a’ becomes 1 and ‘A’ becomes 27.
We can make use of a conditional expression for an elegant solution to retrieve the value of the character.
The use of
isupper lets us subtract the right value to get the corresponding value for the puzzle. We them add that value to the
sum_of_values defined earlier and the resulting total is the answer to puzzle 1.
In the second puzzle, the challenge is to identify a character (item) common to sequences of three strings (inventories) from the input and to sum the total of the values (priorities) of those characters.
To read multiple lines at once, we could try a number of different options. The first that comes to mind is to ditch the
for loop and switch to a
while so we can read in three lines and then repeat. I’m always cautious of while loops and prefer loops with pre-defined iterations.
An alternative option is to call the
next function on our file operator during the loop to consume additional lines.
next, we have to drop the
readlines method. We also have to account for the
\n character in our sets which adds a couple of lines to the previous code.
We re-apply the set logic to extract the common characters and then exclude
\n. After we iterate the set, we can then do our value calculation from the puzzle 1 code and the resulting total is the answer to puzzle 2.
View the code on GitHub.