Advent 2019 Day 3
Today's problem dealt with intersecting paths. You start with two inputs, figure out the paths they represent and where they intersect and then find the intersection that correctly answers the question.
For part 1 you have to find the intersection closest to the origin. From a teacher's point of view, the interesting part here is data representation. This problem deals with a two dimensional grid on which the paths live. For most students, at least in my experience, if they're trained in a language like C++ or Java they go for the direct representation - a 2D array. For many problems this makes a lot of sense. For this one, however, it probably doesn't. We start at a specific point but can travel in any direction for any distance. This means we might need a crazy large array and what's more, it's probably going to be sparsely filled.
A more practical solution involves maintaining a data structure with just the individual points of interest - the points on the path.
I chose a dictionary (or hash-map or hash-table depending on language) The key would be a tuple representing a point and the value would hold whatever data was needed. For part one that would be a set of the paths that went through the point.
So, if we had a path made up of 2 intersecting lines:
|
-+-----
|We could use a 2D array to represent it (assume the lines have ID's 1 and 2):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | nil | #{2} | nil | nil | nil | nil | nil |
| 1 | #{1} | #{1 2} | #{1} | #{1} | #{1} | #{1} | #{1} |
| 2 | nil | #{2} | nil | nil | nil | nil | nil |
That's already a good deal of wasted space. using a dictionarey we'd have:
| key (row,col) | Value |
|---|---|
| (0,1) | #{2} |
| (1,0) | #{1} |
| (1,1) | #{1 2} |
| (1,2) | #{1} |
| (1,3) | #{1} |
| (1,4) | #{1} |
| (1,5() | #{1} |
| (1,6) | #{1} |
| (2,1) | #{2} |
Which becomes much more space efficient once we go beyond the smallest test cases.
Once we have the representation, the problem becomes one of stepping through the paths and adding them to the dictionary. After that we can pull out the small number of entries in our dictionary that were visited by both paths and then we can find the final answer.
I coded this up in Clojure (solution here) but forgot to account for the fact that when a path repeats itself it shouldn't count as an intersection for the purpose of the problem. Oops. I fudged things to get the right answer but then had to head off to Albany.
When I arrived I fixed the code but was pretty zonked so decide to code the second part in Python (solution here). Both solutions are pretty similar but as I'm more comfortable with Python it didn't require too much focus to get it right.
Given the wording of this problem, I think that most people will steer towards the type of dictionary representation I used rather than a 2D array but this way of storing data is worth discussing with classes when you might otherwise use a 2D array.
When might you ask?
How about something like Conway's Game of Life. When this is done in a CS1 class the world is usually represented as a 2D array. It's simple and direct. Another approach would be to only store the live cells in a list. You can check out a Clojurescript implementation that does just that here.
Another would be the N-Queens problem. Insead of a board, just store the queens locations.
Image processing? Well, there probably not. When doing image work, you actually use all the cells in the 2D array.
That's pretty much all I have to say about today's problem. It got me thinking about alternate ways of representing our data. That's something we usually don't have too much of an opportunity to discuss with our students. That's unfortunate.