Advent of Code 2016 - Day 1: No Time for a Taxicab

Part 1

Description

You start at a corner facing north and follow a list of instructions such as R2 or L3: turn 90° right or left, then walk that many blocks. Part 1 asks how many blocks away from the start you end up.

Solution

I pasted the instructions into B3 as one line. A6 cuts the line into instructions at every comma and space, and spills them down as a list (A6:A181). A6# in the formulas below means “the whole spilled list”:

A6: =TOCOL(TEXTSPLIT(B3,", "))
B6: =LEFT(A6#,1)                          ← the turn, L or R
C6: =RIGHT(A6#,LEN(A6#)-1)                ← the number of blocks

Every turn is exactly 90°, so the walk alternates between east/west and north/south. Column D says which one each step is. 

D6: =IF(MOD(ROW(),2)=0,"X","Y")

Column E holds each step as a signed number (east and north are positive, west and south negative). The sign depends on the previous step and the turn:

• After an east/west step, turning right flips the sign (east becomes south, west becomes north).
• After a north/south step, turning right keeps the sign (north becomes east, south becomes west).
• A left turn is the opposite in both cases.

I start by pretending my previous step was north, so I typed 1 in E5:

E6: =IF(MOD(ROW(),2)=1,IF(E5<0,IF(B6="R",0+C6,0-C6),IF(B6="R",0-C6,0+C6)),IF(E5<0,IF(B6="R",0-C6,0+C6),IF(B6="R",0+C6,0-C6)))

The final position is the sum of the steps on each axis, and the distance is the two sums without their signs:

B2: =ABS(SUMIF(D6:D181,"X",E6:E181))+ABS(SUMIF(D6:D181,"Y",E6:E181))

I checked the sign rule on the puzzle’s examples: R2, L3 gives 5, R2, R2, R2 gives 2 and R5, L5, R5, R3 gives 12.

Part 2

Description

Solution

Now I need the first location I walk onto twice, so I need every block I pass through and not only the corners.

First, the position after each step. F5 holds the start, (0,0), as text. F6 adds the step to the previous position, and G and H split the text back into the x and y numbers:

F6: ="("&IF(D6="X",E6+MID(F5,2,(FIND(",",F5)-2)),MID(F5,2,(FIND(",",F5)-2)))&","&
        IF(D6="X",MID(F5,FIND(",",F5)+1,(LEN(F5)-1-FIND(",",F5))),
           E6+(MID(F5,FIND(",",F5)+1,(LEN(F5)-1-FIND(",",F5)))))&")"
G6: =VALUE(IF(D6="X",E6+MID(F5,2,(FIND(",",F5)-2)),MID(F5,2,(FIND(",",F5)-2))))
H6: =VALUE(IF(D6="X",MID(F5,FIND(",",F5)+1,(LEN(F5)-1-FIND(",",F5))),
             E6+(MID(F5,FIND(",",F5)+1,(LEN(F5)-1-FIND(",",F5))))))

Next, every block walked during each step. J6 builds a list of locations from the previous position to the new one, one row per instruction:

J6: =IF(D6="X",
        TOROW("("&SEQUENCE((MAX(G5:G6)-MIN(G5:G6)),1,IF(G6>G5,G5+1,G5-1),IF(G6>G5,1,-1))&","&H6&")"),
        TOROW("("&G6&","&SEQUENCE((MAX(H5:H6)-MIN(H5:H6)),1,IF(H6>H5,H5+1,H5-1),IF(H6>H5,1,-1))&")"))

The rows have different lengths, so I joined everything into one text and split it again. That gives one long list of locations in walking order (I6, 988 locations for my input):

I6: =TOCOL(TEXTSPLIT(TEXTJOIN(":",TRUE,J6:GQ181),":",,,0))

The answer is the first location in the list that appears more than once, and its distance from the start:

D2: =INDIRECT(ADDRESS(5+MATCH(TRUE,COUNTIF(I$6:I$993,I$6:I$993)>1,0),9))
E2: =ABS(MID(D2,2,(FIND(",",D2)-2)))+ABS(MID(D2,FIND(",",D2)+1,(LEN(D2)-1-FIND(",",D2))))

A caveat. D2 finds the first location that is repeated somewhere later. That is the same as the first location reached twice on my input, and on the puzzle’s example, but not always: another location could be revisited sooner. A safe version counts how often each location has appeared so far, in a free column next to the list (I used GU), and takes the first row where the count reaches 2:

GU6: =COUNTIF(I$6:I6,I6)                      ← fill down
D2:  =INDEX(I6:I993,MATCH(2,GU6:GU993,0))

My path never returns to the start. If yours does, add (0,0) at the top of the list, because the start counts as visited.