Hour of No Code [Solving Day 1 Part 1 of Advent of Code 2016 without writing any code]
Advent of Code is a cool idea! Author Eric Wastl describes it as "a series of small programming puzzles for a variety of skill levels". I thought I might work through the first few days with non-programmer children, so I read the description of Day 1: No Time for a Taxicab:
[...] start at the given coordinates [...] and face North. Then, follow the provided sequence: either turn left (L) or right (R) 90 degrees, then walk forward the given number of blocks [...]
Following simple, mechanical steps seemed like a fine introduction to programming for young people, so I signed in and requested the data for Part 1 of the puzzle.
Oh...
You see, while the examples Eric provides are quite simple, the actual input is over 150 steps and some of the distances are three-digit numbers. So while this puzzle is perfect for a small programming challenge, it'd be too tedious to work through manually.
Unless...
What if we could solve the programming puzzle without any programming?
What if we could solve it with something familiar to non-developers?
What if we could solve it with a basic spreadsheet???
Hmmm...
Let's try!
We'll be using Google Sheets because it's free, easy to use, and convenient. (But any decent spreadsheet will do.) And we'll be working with the sample data (not the actual puzzle data) so as not to give too much away. Keep reading to see all the steps - or follow along in a spreadsheet if you want to get your hands dirty.
Good, let's start with the sample data:
R5, L5, R5, R3 leaves you 12 blocks away.
To understand why and familiarize yourself with the puzzle, read about taxicab geometry and work through the steps on paper first.
It's important to realize that R and L steps do not necessarily alternate and that the direction at the end of each step depends on the direction at the beginning of the step.
However, given the state after N steps, the state after step N+1 is completely defined by that direction and distance.
Spreadsheets typically go "down", so let's set ours up like that by adding the steps to a Data column (leaving row 2 blank for reasons that will be clear later):
| A | |
|---|---|
| 1 | Data |
| 2 | |
| 3 | R5 |
| 4 | L5 |
| 5 | R5 |
| 6 | R3 |
Each step contains two pieces of information: the Direction to turn and the Distance to move.
Let's start by pulling them apart so we can deal with them separately.
The LEFT and RIGHT functions are our friends here (with a little help from LEN).
The Direction is simply the first character of the data, or =LEFT(A3, 1) (assuming we're looking at row 3, the first value).
And the Distance is just the rest of the string, or =RIGHT(A3, LEN(A3)-1).
Type those formulas into cells B3 and C3 and replicate the formulas down to row 6.
(Your spreadsheet program should automatically update the formulas for rows 4-6 to be relative to their respective cells.)
Done correctly, that gives the following:
| A | B | C | |
|---|---|---|---|
| 1 | Data | Direction | Distance |
| 2 | |||
| 3 | R5 | R | 5 |
| 4 | L5 | L | 5 |
| 5 | R5 | R | 5 |
| 6 | R3 | R | 3 |
We'd like to turn the Direction letter into a number so we can do math on it - the IF function works nicely for that.
By using -1 to represent a left turn and 1 to represent a right turn, use the formula =IF(B3="L", -1, 1) to create a Rotation field for row 3 (and then replicate the formula down):
| A | B | C | D | |
|---|---|---|---|---|
| 1 | Data | Direction | Distance | Rotation |
| 2 | ||||
| 3 | R5 | R | 5 | 1 |
| 4 | L5 | L | 5 | -1 |
| 5 | R5 | R | 5 | 1 |
| 6 | R3 | R | 3 | 1 |
Now let's use Rotation to create a Heading that tracks where the player is pointing after each move.
The four possible values are North, East, South, and West - it's convenient to use the numbers 0, 1, 2, and 3 respectively.
Because we're adding and subtracting numbers to determine the Heading, it's possible to get values outside that range (ex: 3 + 1 = 4).
Just like with a 12-hour clock (11am + 2 hours = 1pm), we'll use modular arithmetic to stay within the desired range.
The starting direction is North, so we'll seed an initial Heading by putting the value 0 in cell E2.
(See, I told you row 2 would be useful!)
After that, the MOD function can be used to figure out the new Heading by adding the Rotation to the current value: =MOD(E2 + D3, 4).
Replicating this formula down gives the following:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | Data | Direction | Distance | Rotation | Heading |
| 2 | 0 | ||||
| 3 | R5 | R | 5 | 1 | 1 |
| 4 | L5 | L | 5 | -1 | 0 |
| 5 | R5 | R | 5 | 1 | 1 |
| 6 | R3 | R | 3 | 1 | 2 |
Knowing a Heading and a Distance means we can track of the X and Y coordinates as the player moves around the city.
If the player is facing East and moves forward, the X coordinate will increase by that Distance; if facing West, it will decrease.
Similarly, a move facing North will increase the Y coordinate, while a move South will decrease it.
The CHOOSE function allows us to represent this quite easily.
The only catch is that CHOOSE indices are 1-based and our Heading values are 0-based, so we need to adjust for that by adding 1.
After seeding 0 values for the starting X and Y coordinates in row 2, we can update the X coordinate with =F2 + CHOOSE(E3+1, 0, C3, 0, -C3) and the Y coordinate with =G2 + CHOOSE(E3+1, C3, 0, -C3, 0).
Replicating those formulas down leads to:
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| 1 | Data | Direction | Distance | Rotation | Heading | X | Y |
| 2 | 0 | 0 | 0 | ||||
| 3 | R5 | R | 5 | 1 | 1 | 5 | 0 |
| 4 | L5 | L | 5 | -1 | 0 | 5 | 5 |
| 5 | R5 | R | 5 | 1 | 1 | 10 | 5 |
| 6 | R3 | R | 3 | 1 | 2 | 10 | 2 |
Now all that's left to solve the puzzle is to compute the taxicab distance of each X/Y coordinate from the starting point.
Well, that's just the magnitude of the X coordinate added to the magnitude of the Y coordinate and that can be expressed using the ABS function: =ABS(F3) + ABS(G3).
Replicating that down gives the following, final, table and the answer to the sample puzzle:
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| 1 | Data | Direction | Distance | Rotation | Heading | X | Y | Taxicab Distance from Start |
| 2 | 0 | 0 | 0 | |||||
| 3 | R5 | R | 5 | 1 | 1 | 5 | 0 | 5 |
| 4 | L5 | L | 5 | -1 | 0 | 5 | 5 | 10 |
| 5 | R5 | R | 5 | 1 | 1 | 10 | 5 | 15 |
| 6 | R3 | R | 3 | 1 | 2 | 10 | 2 | 12 |
Sure enough, the taxicab distance after the final move (cell H6) is 12 - just like the sample said it should be!
And we figured that out without writing any "code" at all - we simply came up with few small formulas to methodically break the problem down into little pieces we could solve with a spreadsheet.
That may not quite be coding (in the usual sense), but it sure is programming!
PS - Having definitively established that you are 1337 with a spreadsheet, you might be looking for other challenges... Good news: Part 2 of the Advent of Code taxicab problem has been left as an exercise for the reader! :)