Advent of Code 2020: Day 2-9

Code for all days is on GitHub

Day 2

Nothing terribly fancy going on with the day 2 challenge – essentially, reading in a text file and doing operations on strings. After developing the ability to split the input lines and validate them in part one, part 2 throws a curveball by changing up how the lines should be validated. I refactored my “isValidLine” code to take a validation function as one of its arguments, since the parsing/splitting of the line is the same for both parts 1 and 2.

(The names of the validation functions come from the problem description – they validate the passwords for a sled company and a toboggan company, respectively.)

Day 3

A slightly more involved bit of data and text processing today, as we help our would-be tobogganist make it down a snowy slope covered in trees. As a way of pushing my Python knowledge, I tried to complete both parts of today’s challenge using list comprehensions and iterative functions like map, reduce, enumerate, etc. My impulse is to write things out more explicitly by iterating through the elements of input in a for loop, but practicing the list comprehensions and their related utility functions feels good.

Is the inline code better than the more verbose versions? I’m not entirely sure – it’s certainly less readable than the expanded-into-a-loop versions. It’s also somewhat harder to debug, because there aren’t logical places to, say, print intermediate results. So something like my getSlopeTrees() function, as written, is just silly-long and hard to read – the getSlopeTreesVerbose() function, which I wrote as part of troubleshooting a specific issue is definitely more readable.

The punchline of my issue was: at least in Python 3.9, floats can’t be used as list indices, even if they’re integers. That is, even if a float for which is_integer() returns true, you must explicitly cast that float to an integer to use it index a list. In code form:

So, another thing learned. Thanks Advent of Code!

Here’s the full code from Day 3:

Day 4

We can slowly feel the difficulty starting to ramp up here in day four. We’re still walking on paved roads, as it were, but they’re not as well maintained as they used to be in day one.

Today’s problem concerns more text parsing – the first part just says to validate, essentially, that 7 unique strings are present between sets of blank lines in the input file. The code for this is pretty straightforward – I tried for a little while to do it all in one list comprehension, but ended up splitting it into two lines, which I think is clearer. To be sure, I don’t think that doing it in one comprehension would be better, just that I thought it would be fun practice.

Of course, with the problem statement framing these 7 strings as labels for values in a passport (eyc:blu, hgt:171cm, etc), it seemed like a straight guess that we’d actually have to parse those values by field and do something with them in part two. And of course, we were right. For each of the 7 fields, validation criteria are listed, including ensuring certain fields are numerical and within certain bounds, prepended or postended by certain characters, and so on.

This part turned out ok – it takes the text file, splits it into individual passport strings, then splits each of those into a list of strings of the form “key:value”. The part that feels most “un-Pythonic” to me is the part (commented below) that turns that list of lists of strings into a list of dictionaries. I figure there’s got to be a way to do that with a comprehension, but I couldn’t quite make it work, so I did it as a couple For loops. It works fun, just feels a little clunky.

I also implemented my own prettyPrintPassword function (and its alias ‘ppp’) – it doesn’t do any sorting of the fields, and it doesn’t show you why a passport is invalid if it fails, but it did what I needed it to do for troubleshooting purposes.

Day 5

Wow, a quickie today! The title of the day’s challenge (‘Binary Boarding’) gives you a pretty strong clue what it’s going to be about. The challenge is essentially to parse text representing binary numbers in your language of choice and find the minimum, maximum, and missing values in between.

This is my shortest solution so far, at only 5 lines of code (for both parts!):

This is where Python’s use of convenience generators (like range), built in math functions on general iterators (like min and max), and lots of string functionality (like replace) really shines – the code is easy to write and clean.

Looking back at my goals for Code Advent 2020, I’d say I’m doing pretty well – I’m already feeling more fluent/comfortable with list/dictionary comprehensions, the git workflow is becoming more natural, and I’ve completed each project on the day it’s issued. Not too much challenge in terms of the algorithms and data structures so far, but then it is only day 5….

This post will be updated with code from a handful of future days, until it gets too long/unwieldy.

Day 6

As it turns out, talking out loud while generating algorithms while writing code is… hard.

I coded up the solution to Day 6 live on stream on Sunday night, which was both fun and challenging. Part one of the challenge wasn’t too terribly hard – it basically asks whether each letter of the alphabet is contained between any pair of blank links (“\n\n”) in the input file. That’s a solution that only takes a few lines to write.

I ended up writing three solutions to part 2. I ended up ordering them in the code in order of their complexity/lines of code, but that’s not the order I wrote them in. I first wrote a really over-complicated solution (3), then condensed it down to a single list comprehension (1), then expanded that back out just a little to make it more readable. Like I said on stream, if I were writing this code to go into some kind of actual codebase, I think solution (2) is the one I’d use – it’s concise enough to be comprehensible, but long enough to not be overwhelmingly dense.

Day 7

Oof, this day too far, far longer than it should have, all because I misunderstood Python’s strip() function. strip, for those who are wondering, removes any of the set of characters given as its arguments from the beginning or end of a string. So, “Hello World”.strip(‘Hld’) => “ello Wor”. Unfortunately, I thought that the strip function removed the exact string given it it as an argument, leading to it stripping additional characters off of the end of some inputs and causing my parsing to be wrong. Oof.

In any case, the two halves of day 7 involve creating a tree of data in two different ways (one in which parents reference children, and one in which children reference parents). Then we sum up the total number of parents or children, unweighted or weighted, respectively.

Day 8

Day 8 is giving me flashbacks to the intcode challenges of 2019! But it’s a much softer start this time – we only have three pseudo-assembly instructions to parse, and simpler questions to answer. Once we’ve built a simple function for processing a given list of these instructions, we’ve solved part one. Part 2 requires iterating over our input data and manipulating it slightly, and testing to see whether the new version of the input fulfills the required condition, so our code will need to work over general lists of instructions.

The only thing that hung me up today was forgetting to take into account how Python’s lists handle objects. Specifically, this is the behavior that I was (rightly, but unwantedly) seeing:

listA = [[1,2],[2,4],[3,6]]
listB = [a for a in listA]
listB[0] = [4, 8]
print(listA)
>>>[[4,8],[2,4],[3,6]]

Though it doesn’t look like listA is ever being modified, the way we’ve constructed listB, it actually references the same objects as listA. So when we change the object [1,2] to be [4,8], it changes everywhere that object is referenced in both lists. A little thing I once knew, but had skipped my brain for about 8 minutes. Whoops!

Day 9

Well that felt pretty good! The consensus across the interwebs (twitter, reddit) seems to be that today was relatively easy, and I’d agree. The problem involved two different ways of comparing integers in an input list to the previous 25 numbers, and doing some math on them. There are probably slightly more efficient algorithms, especially for part 2 – currently when the running sum starting from a given position, I throw out the entire sum and start again from the next position, which is likely wasteful. But for only 1000 inputs, the code still runs in ~160 milliseconds, so I don’t think it’s worth the time to make it more efficient. If this problem comes back in future days, that may be worth revisiting.

Advent of Code 2020: Day 1

I know in my introductory post I said I wasn’t going to post something every day, and I meant it! But I ended up with a little extra time on my hands today and this casual summary has turned into an actual post… I’m going to have to think about how I categorize these posts so anyone who stumbled across my blog isn’t wading through five pages of Advent of Code writeups before getting to tiny moving lights. But for now, here’s day 1.

Full code is available on GitHub.

Much like last year, this year’s Day 1 challenge starts by essentially making sure we can read in a text file and do basic math on it. The first problem asks us to find which two integers in a text file that sum to 2020 and retrieve their product; the second asks the same question, but for a set of 3 integers.

Just for gits and shiggles, I implemented the solution to part one in two different ways. The first, in a function I title “naiveFind”, just loads all of the numbers from the file into a list, then loops over every pair of numbers until it finds a pair that sums to 2020 (the success() function is detailed below). This is a fine way to approach this problem, but not terribly efficient for long lists:

The speedier way to solve this problem is to use a hashmap, which we get for free in the form of Python dictionary lookups (in most implementations of Python.) Rather than looping over all pairs of numbers, we can just proceed through the the list once, storing each member in a dictionary, and as we load each new number, we check to see if it’s “2020’s complement” is already in our dictionary’s keys. This is faster than a raw comparison because looking via hashing is cheaper than doing a ‘by-hand’ comparison of all of the numbers ourselves.

For the second part of the problem, I only implemented a “naive” solution, running in O(n³) time:

With the need to now communicate a set of three numbers (and their product) that form a solution, I rewrote my success() function to accommodate any number of inputs as arguments. (The original, two-input function is commented-out at the bottom.)

To see how efficient these various functions were, I wrote a quick decorator function that allows me to see the (rough) execution time of each solution:

Running all three of our search functions in turn:

We can see that:

  • The naïve way of looping over all the pairs of products takes about 1.5 ms to complete
  • The hashset (dictionary) method of finding one pair of numbers takes about 0.6 ms to complete
  • The naïve way of finding a triple of numbers takes about 65 ms to complete

Some stray thoughts from today

  • When I originally tried to run my basic test code to ensure I was reading the input text file correctly, I got the error: “No such file or directory.” Which is odd, because the text file was just sitting in the same folder as my Python script, like always. It turns out that by default, VSCode uses the open folder as its source, not where the script is actually being executed. You can change this in the Python terminal settings:image
  • I’ve made use of the functools.wraps wrapper to assist me in writing my own decorator functions before, but using it again today to write the timer function makes me want to look a little deeper under the hood to see what it’s doing.

Postscript:

I was just kicking around the #AdventOfCode hashtag on Twitter after completing my solutions, and ran across these super-nifty “Pythonic” solutions by @Brotherluii:

https://twitter.com/Brotherluii/status/1333756750579830784

For those for whom the embedded tweet doesn’t work:

with open('input.txt', 'r') as file:
    data = {int(number) for number in file}

#Part 1
print({entry * (2020-entry) for entry in data if (2020-entry) in data})

#Part 2
print({entry1 * entry2 * (2020 - entry1 - entry2)
    for entry1 in data for entry2 in data
    if (2020 - entry1 - entry2) in data})

Though I understand list comprehensions, I feel like they’re never my go-to tool, but seeing them composed like this, I can see how they can be pretty beautiful in the right hands.

Advent of Code 2020

Last winter, I participated in the annual Advent of Code Challenge, a website which offers small (but not necessarily easy) programming challenges every day from December 1 through 25. It turned out to be a great way to get exposed to different corners of development in my language of choice (Python), and with a little more time on my hands this Winter, I’m excited to dive into it again.

The challenges are all written in a non-programming-language-specific way. For example, the first part of the problem from December 1, 2019 boils down to:

* Ingest a list of numbers from a text file, with one line per number
* For each number, divide it by 3, round down, and subtract 2
* Sum all these results together
* Print/return/somehow give the user back the sum

While I was doing this in Python, there’s no reason you couldn’t do it in C, or Java, or Haskell, or ALGOL, or any language of your choice (though of course, some of the problems will be more tractable using structures built into some langauges and not others). The actual prompts are a bit more flavorful that that example – a narrative about needed to rescue Santa from outer-space was woven through all 25 problem last year.

I’m confident in saying that my Python has gotten significantly stronger over the past year, but I’m feeling like I could be stronger in some algorithmic thinking (the mazes last year slayed me) and in some process crevices around my workflow. To that end, my goals for this year are:

  • To strengthen my intuition for solving data-based problems with time-efficient algorithms
  • To cement the core concepts around Pythonic data structures in my knowledgebase
  • To become more comfortable with Git/GitHub, in particular its command line interface and the branch/merge/HEAD flow
  • To complete each challenge on the day it’s issued

Because nobody needs their RSS feed flooded by me every day for a month, I think I’ve found a way to start a blog post on, say, December 1st, update it every day for a week, then only push to the RSS feed on the 7th – so if you want to check on them daily, you can go to the actual factual blog, or just wait for the summary posts to come out.

If you’re just interested in the code (or are reading this from the future) and want to see my solutions, I’ll be posting the code over on GitHub. I’m not going to be striving to be one of the first 100 people posting successes to each problem (for which there is a leaderboard), I’m just solving these for me. And I encourage anyone out there looking to build their programming confidence to do the same!