Advent of Code 2016 - Day 7: Internet Protocol Version 7

Part 1

Description

A message is sent repeatedly, but noise garbles it, so every copy is a bit different. The input has one copy per line, all eight letters long. Reading down each column of letters, the most frequent letter is the right one. Part 1 asks for the corrected message. 

Solution

I pasted the 546 lines into A5:A550. The first step is to split every line into its eight letters, one per column. SEQUENCE(,8) makes the numbers 1 to 8 across a row, and MID takes that character of every message:

C5: =LET(a,A5:A550,MID(a,SEQUENCE(,8),1))        ← fills C5:J550

Now each column holds all the copies of one letter of the message. For one column, COUNTIF(C5:C550,C5:C550) tells, for every cell, how many times its letter appears in the column. Comparing that with the largest count gives TRUE for the most common letter. MATCH finds the first TRUE and INDEX returns the letter:

=LET(c,C5:C550,n,COUNTIF(c,c),INDEX(c,MATCH(MAX(n),n,0)))

This is an array formula (in older versions of Excel, enter it with Ctrl+Shift+Enter). I filled it to the right, up to J4. The message is the eight letters joined together:

B2: =CONCAT(C4:J4)

I tried the puzzle’s example (16 short lines) and it gives the message from the puzzle text.

Part 2

Description

The repetition code turns out to work differently: the original message is made of the least common letter in each column.

Solution

That is the same formula with MIN in place of MAX. I put it in L4 and filled it to the right, up to S4. Each cell still looks at its own column (L4 looks at column C, M4 at column D, and so on):

L4: =INDEX(C5:C550,MATCH(TRUE,COUNTIF(C5:C550,C5:C550)=MIN(COUNTIF(C5:C550,C5:C550)),0))
D2: =CONCAT(L4:S4)

A caveat. If two letters tie for the most (or least) common, these formulas quietly pick the first one in the list. In my input every column has a clear winner, so it doesn’t matter, but the margin is small, so it is worth checking that your own columns have no ties.

Read More

Advent of Code 2016 - Day 5: How About a Nice Game of Chess?

Part 1

Description

My puzzle input is a door ID, a short piece of text. To find the password, I append a number to the door ID, starting at 0 and counting up, and take the MD5 hash of the result. A hash that starts with five zeros is interesting, and its sixth character is the next character of the password. Part 1 asks for the password made from the first eight interesting hashes.  

Solution

Excel has no MD5 function, so I used VBA. I didn’t write the MD5 calculation myself: I added a ready-made class module called clsMD5 (I modify this from Day 4 AoC 2015, source and credit goes there) and a small function around it:

Public Function MD5Hash(ByVal strText As String) As String
    Dim cMD5 As New clsMD5
    MD5Hash = cMD5.MD5(strText)
    Set cMD5 = Nothing
End Function

The door ID is in B3. Hashing tens of millions of numbers takes a while, so a macro does the searching and writes the interesting numbers into column C. It keeps a hash only when it is useful: one of the first eight (Part 1), or one that fills a new password position (Part 2, which I explain below). It stops when both parts are complete:

Public Sub FindHits()
    Dim ws As Worksheet, md5 As clsMD5, door As String
    Dim filled(0 To 7) As Boolean, nFilled As Long
    Dim hits As Long, rowOut As Long, i As Long
    Dim h As String, p As String, useful As Boolean

    Set ws = ActiveSheet
    Set md5 = New clsMD5
    door = ws.Range("B3").Value
    ws.Range("C5:C40").ClearContents
    rowOut = 5

    Do
        h = md5.MD5(door & i)
        If Left$(h, 5) = "00000" Then
            hits = hits + 1
            useful = (hits <= 8)                       ' needed for Part 1
            p = Mid$(h, 6, 1)
            If p >= "0" And p <= "7" Then              ' a valid position for Part 2
                If Not filled(CLng(p)) Then
                    filled(CLng(p)) = True
                    nFilled = nFilled + 1
                    useful = True
                End If
            End If
            If useful Then
                ws.Cells(rowOut, 3).Value = i
                rowOut = rowOut + 1
            End If
            If hits >= 8 And nFilled = 8 Then Exit Do
        End If
        i = i + 1
    Loop
End Sub

On the sheet, each row of the list has a few columns. B repeats the door ID and C holds the number the macro found. D joins them and hashes them, E takes the sixth character (as a number when it is a digit, which Part 2 needs) and F takes the seventh:

D5: =MD5Hash(B5&C5)
E5: =IFERROR(VALUE(MID(D5,6,1)),MID(D5,6,1))
F5: =MID(D5,7,1)

I filled these down for every row of the list (rows 5 to 15). The Part 1 password is the sixth characters of the first eight rows:

B2: =CONCAT(E5:E12)

With the puzzle’s example door ID, abc, the same steps should give 18f47a30 for Part 1.

Part 2

Description

Solution

The rule changes. The sixth character of an interesting hash is now a position in the password, from 0 to 7, and the seventh character is the letter that goes there. Hashes with an invalid position (8, 9 or a letter) are ignored, and only the first hash for each position counts.

That’s why the macro keeps some hashes after the first eight: only the ones that fill a position not yet filled matter, and they are in order in the list. For each position 0 to 7, XLOOKUP finds the first row whose sixth character equals that position and returns its seventh character. COLUMN()-8 makes the position 0 in H, 1 in I, and so on to 7 in O:

H3: =XLOOKUP(COLUMN()-8,$E$5:$E$15,$F$5:$F$15,,0)       ← fill right to O3
D2: =CONCAT(H3:O3)

For the example door ID abc, the answer is 05ace8e3.

Read More

Advent of Code 2016 - Day 4: Security Through Obscurity

Part 1

Description

Each line of the input is an encrypted room name: groups of letters separated by hyphens, then a sector ID, then a checksum in square brackets, like aaaaa-bbb-z-y-x-123[abxyz]. A room is real if its checksum is the five most common letters in the name, most common first, with ties broken alphabetically. Part 1 asks for the sum of the sector IDs of the real rooms.  

Solution

I pasted the 1,066 lines into A5:A1070. One formula per row does all the work. I used LET to give each piece a name:

C5: =LET(a,$A5,
        b,--TEXTAFTER(TEXTBEFORE(a,"["),"-",-1),
        c,TEXTAFTER(TEXTBEFORE(a,"]"),"["),
        n,TEXTBEFORE(a,"["),
        d,CHAR(SEQUENCE(26,,97)),
        e,LEN(n)-LEN(SUBSTITUTE(n,d,"")),
        f,TAKE(SORTBY(d,e,-1),5),
        N(CONCAT(f)=c)*b)

• b is the sector ID: the text before the [, then whatever comes after the last hyphen (-- turns it into a number).
• c is the checksum between the brackets.
• n is the name part of the line, before the [.
• d is the letters a to z, and e counts how many times each letter appears in the name.
• f sorts the letters by count, largest first, and keeps the first five. Because d is already in alphabetical order and SORTBY keeps the original order for ties, ties come out alphabetically, as the puzzle wants.
• The last line compares those five letters with the checksum, and gives the sector ID if they match and 0 if not.

B5 is the same formula but ends with (CONCAT(f)=c), so it shows TRUE or FALSE for each room. The answer is the total of column C:

B2: =SUM(C5:C1070)

The puzzle’s examples agree: aaaaa-bbb-z-y-x-123[abxyz] and not-a-real-room-404[oarel] are real, and totally-real-room-200[decoy] is not.

Part 2

Description

Solution

Now the real rooms must be decrypted. Each letter is shifted forward in the alphabet by the sector ID, wrapping from z back to a, and the hyphens become spaces. I need the sector ID of the room where the North Pole objects are stored.

The shift is the sector ID modulo 26. E5 turns the name into single letters, shifts each one, and joins them again:

E5: =LET(a,A5,
        b,SUBSTITUTE(TEXTBEFORE(a,"-",-1),"-"," "),
        c,MOD(--TEXTAFTER(TEXTBEFORE(a,"["),"-",-1),26),
        e,MID(b,SEQUENCE(LEN(b)),1),
        f,IF(c+CODE(e)>122,96+MOD(c+CODE(e),122),c+CODE(e)),
        SUBSTITUTE(CONCAT(CHAR(f)),CHAR(32+c)," "))

• CODE(e) is the number of each letter (a is 97 and z is 122). If the shifted number goes past 122, 96+MOD(…,122) wraps it around to the start of the alphabet.
• The spaces get shifted too, because a space is code 32, and become the character with code 32 + shift. The last line changes exactly those characters back into spaces. That works because they are symbols or digits, never letters.

The sector ID of each row is in column F:

F5: =--TEXTAFTER(TEXTBEFORE(A5,"["),"-",-1)

Then G marks the rows whose decrypted name contains “north”, and the answer is the sector ID in the first marked row:

G5: =IF(ISNUMBER(SEARCH("north",E5:E1070)),1,0)
D2: =INDEX(F5:F1070,MATCH(1,G5#,0))

Only one room matches (the “northpole object storage” one). The puzzle’s example, qzmt-zixmtkozy-ivhz-343, decrypts to “very encrypted name”, as it should.

Read More

Advent of Code 2016 - Day 3: Squares With Three Sides

Part 1

Description

Each row of the input holds three numbers, the side lengths of a triangle. A triangle is possible only if the sum of any two sides is larger than the third. Part 1 asks how many of the listed triangles are possible. 

Solution

I pasted the input into A5:C1915, one triangle per row (1,911 rows).

To test a triangle, it is enough to compare the two shorter sides with the longest one. So I first sorted the three sides in every row. SMALL(A5:C5,SEQUENCE(3)) gives the smallest, the middle and the largest side, and TOROW lays them out in a row (E5:G5):

E5: =TOROW(SMALL(A5:C5,SEQUENCE(3)))       ← fill down to row 1915

Now the triangle is possible when the first two sorted sides add up to more than the third. SUMPRODUCT counts the rows where that is true:

B2: =SUMPRODUCT(--(E5:E1915+F5:F1915>G5:G1915))

The puzzle’s example, a triangle with sides 5, 10 and 25, is correctly rejected, because 5 + 10 is not more than 25.

Part 2

Description

Solution

The numbers should have been read down the columns instead: each group of three rows in a column makes one triangle. So there are the same number of triangles, but made from different numbers.

Rows 5 to 7 of column A are the first triangle, rows 5 to 7 of column B the second and rows 5 to 7 of column C the third. In H5, I5 and J5 I test each of those three groups: the smallest number plus the second smallest must be more than the largest, and the cell shows 1 if so, otherwise 0:

H5: =IF(MIN(I5:I7)+SMALL(I5:I7,2)>MAX(I5:I7),1,0)
I5: =IF(MIN(J5:J7)+SMALL(J5:J7,2)>MAX(J5:J7),1,0)
J5: =IF(MIN(K5:K7)+SMALL(K5:K7,2)>MAX(K5:K7),1,0)

The next group is rows 8 to 10, so the next formulas are in H8, I8 and J8, and so on. I copied the block down, so there is a formula in every third row (5, 8, 11 and so on down to 1913), and the rows in between stay empty. The answer is the number of 1s:

D2: =COUNTIF(M5:O1915,1)

By the way, there is an option to use this formula to check if a triangle is valid: =IF(SUM(A5:C5)>2*MAX(A5:C5),1,0).

Read More

Advent of Code 2016 - Day 2: Bathroom Security

Part 1

Description

A keypad has nine buttons in a 3 × 3 square. You start on the 5 and read a line of instructions made of U, D, L and R. Each letter moves your finger one button up, down, left or right, unless that would leave the keypad. At the end of each line you press the button you are on, and the next line continues from there. Part 1 asks for the code made of the buttons pressed.  

Solution

I treated the keypad as coordinates. The 5 in the middle is (0, 0), so x goes right and y goes down. I laid the buttons out with =SEQUENCE(3,3) in I1:K3, which makes 1 to 9 with the 5 in J2. Next to it is a small table of the four letters and the step each one makes (L1:N4):

L	M (x)	N (y)
U	0	-1
D	0	1
R	1	0
L	-1	0

I pasted the five lines of input into A16:A20. For each line, one formula takes the position where the last line ended (B15:C15 holds the start, 0 and 0) and goes through the line letter by letter. MID(D,SEQUENCE(LEN(D)),1) cuts the line into single letters, and REDUCE walks through them. Each step adds the letter’s movement to the position, and the new position is kept only if it is still on the keypad, meaning x and y are both between -1 and 1:

B16: =LET(D,A16,
        REDUCE(B15:C15,MID(D,SEQUENCE(LEN(D)),1),
          LAMBDA(A,V,
            LET(B,A+XLOOKUP(V,$L$1:$L$4,$M$1:$N$4),
                IF(MAX(ABS(B))<2,B,A)))))

This spills into B16:C16 (x and y). The next line, B17, is the same formula starting from B16:C16, and so on down to B20.

The button for each line is found by moving from the 5:

D16: OFFSET($J$2,C16,B16)

The code is the five buttons joined together:

B2: =TEXTJOIN(,,D16:D20)

To test it, I used the puzzle’s example in A11:A14, with the same formulas in rows 11 to 14. It gives 1985, as in the puzzle text.

Part 2

Description

Solution

The keypad turns out to be a diamond: a 1 at the top, then 2 3 4, then 5 to 9, then A B C, and a D at the bottom. You still start on the 5.

I laid the new keypad out in Q1:T5. This time the 7 is in the middle, so it is (0, 0) and the 5 (where I start) is (-2, 0), which I typed in E10:F10. A move is allowed if the position stays inside the diamond, meaning |x| + |y| is at most 2. It’s the same formula as before with a different test:

E16: =LET(A,A16,
        REDUCE(E15:F15,MID(A,SEQUENCE(LEN(A)),1),
          LAMBDA(K,L,
            LET(XY,XLOOKUP(L,$L$1:$L$4,$M$1:$N$4),
                IF(SUM(ABS(K+XY))>2,K,K+XY)))))
G16: =OFFSET($R$3,F16,E16)
D2:  =TEXTJOIN(,,G16:G20)

Again, E16 starts from E15:F15, and so on down. The example lines give 5DB3, as in the puzzle text.

Read More

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.

Read More

Advent of Code 2015 - Day 25: Let It Snow

Part 1

Description

Solution

The codes are written into a huge grid along diagonals, and each code comes from the one before it: multiply by 252533, then keep the remainder after dividing by 33554393. The first code is 20151125. I need the code at one row and column. 

Checking the order on a small grid

First I recreated the first seven diagonals in Sheet1 and compared them with the puzzle’s example table. All 29 numbers matched.

Why I didn’t fill the grid

My cell is on a diagonal numbered above 6,000, which makes it roughly the 18-millionth code. No sheet can fill 18 million cells by hand, so I computed the position and then the code directly.

Finding the position

The code in row r and column c is on diagonal d = r + c − 1. All the earlier diagonals hold 1 + 2 + … + (d − 1) codes, and within the diagonal the code is number c. So the position is n = (d − 1)·d/2 + c, and I need to apply the rule n − 1 times from the first code, which means:

code = 20151125 × 252533^(n−1) mod 33554393

In Sheet2:

B1: my row            B2: my column
B3: =B1+B2-1                       ← diagonal
B4: =(B3-1)*B3/2+B2                ← position n
B5: =B4-1                          ← exponent
B6: 33554393     B7: 252533     B8: 20151125

Raising to a big power

 252533 to a power of millions is far too large for Excel, but I can use square-and-multiply. Take the exponent in binary. Row k of a table holds 252533^(2^k) mod 33554393, found by squaring the row above. When bit k of the exponent is 1, that row’s value is multiplied into a running result:

A11: 0                      A12: =A11+1       (fill down to A40)
B11: =$B$7                  B12: =MOD(B11*B11,$B$6)
C11: =MOD(INT($B$5/2^A11),2)
D11: =IF(C11=1,MOD(B11,$B$6),1)
D12: =IF(C12=1,MOD(D11*B12,$B$6),D11)
B9:  =MOD($B$8*D40,$B$6)    ← the code

I filled the formulas down to row 40, which covers exponents up to about a billion. B9 is the answer.

This stays exact because every product is below 2^53 (the biggest here is about 9.7×10^14, and Excel is exact up to 9×10^15). I think older Excel versions also need the quotient inside MOD to stay under 2^27 (about 134 million), and here it never goes past about 29 million.

To test it, row 1, column 1 gives 20151125, row 2, column 1 gives 31916031, and row 6, column 6 gives 27995004, as in the puzzle’s example.

A second check with VBA

To be sure, I also ran the sequence the slow way. It’s only about 18 million steps, a couple of seconds in VBA. The values stay below 2^53, so Double arithmetic is exact:

A11: 0                      A12: =A11+1       (fill down to A40)
B11: =$B$7                  B12: =MOD(B11*B11,$B$6)
C11: =MOD(INT($B$5/2^A11),2)
D11: =IF(C11=1,MOD(B11,$B$6),1)
D12: =IF(C12=1,MOD(D11*B12,$B$6),D11)
B9:  =MOD($B$8*D40,$B$6)    ← the code

Both ways gave the same code, and that’s the answer I submitted.

Part 2

Description

There is no puzzle to solve for Part 2 of Day 25. The second star is given once you have collected all the other stars.

Read More