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:

Public Sub Day25Check()
    Dim code As Double, i As Long, n As Long
    n = Range("B4").Value              ' the position computed above
    code = 20151125#
    For i = 2 To n
        code = code * 252533# - Int(code * 252533# / 33554393#) * 33554393#
    Next i
    Debug.Print code
End Sub

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

Advent of Code 2015 - Day 24: It Hangs in the Balance

Part 1

Description

Solution

The packages must be split into three groups of equal weight. The first group should have as few packages as possible, and among those, the smallest product of weights (the puzzle calls it quantum entanglement). 

Setting up

I pasted the weights into A4:A31 and turned them into a row, which is easier for the VBA function to use. I also worked out the size of one group for three groups (Part 1) and for four groups (Part 2):

B3: =SUM(A4:A31)/3
D3: =SUM(A4:A31)/4

Listing every group that has the right weight

I wrote a macro that tries the weights one after another and gives up on a branch as soon as the sum gets too big. Since the weights are sorted, one that is too big means all the later ones are too big too. It collects the results in memory and writes them to a new sheet in chunks of 50,000 rows, which is much faster than writing cell by cell:

Option Explicit
Private nums() As Long
Private target As Long
Private buffer() As String
Private bufCount As Long, outRow As Long
Private outSheet As Worksheet
Private Const BUFFER_SIZE As Long = 50000

Public Sub ListCombinationsPart1()
    ListCombinations ThisWorkbook.Worksheets("2015").Range("B3").Value, "Combinations_Output"
End Sub

Public Sub ListCombinationsPart2()
    ListCombinations ThisWorkbook.Worksheets("2015").Range("D3").Value, "Combinations_Output_2"
End Sub

Private Sub ListCombinations(ByVal t As Long, ByVal sheetName As String)
    Dim src As Worksheet, i As Long, n As Long, startTime As Double
    startTime = Timer
    Set src = ThisWorkbook.Worksheets("2015")
    n = Application.WorksheetFunction.CountA(src.Range("A4:A31"))
    ReDim nums(0 To n - 1)
    For i = 0 To n - 1
        nums(i) = src.Cells(4 + i, 1).Value
    Next i
    target = t
    Set outSheet = ThisWorkbook.Worksheets.Add
    outSheet.Name = sheetName
    ReDim buffer(1 To BUFFER_SIZE, 1 To 1)
    bufCount = 0: outRow = 1
    Application.ScreenUpdating = False
    SearchSheet 0, 0, ""
    Flush
    Application.ScreenUpdating = True
    MsgBox "Done: " & (outRow - 1) & " combinations in " & Round(Timer - startTime, 1) & " s"
End Sub

Private Sub SearchSheet(ByVal startIdx As Long, ByVal total As Long, ByVal chosen As String)
    Dim i As Long
    If total = target Then
        bufCount = bufCount + 1
        buffer(bufCount, 1) = chosen
        If bufCount = BUFFER_SIZE Then Flush
        Exit Sub
    End If
    For i = startIdx To UBound(nums)
        If total + nums(i) > target Then Exit For
        SearchSheet i + 1, total + nums(i), chosen & IIf(Len(chosen) = 0, "", ",") & nums(i)
    Next i
End Sub

Private Sub Flush()
    If bufCount = 0 Then Exit Sub
    outSheet.Cells(outRow, 1).Resize(bufCount, 1).Value = buffer
    outRow = outRow + bufCount
    bufCount = 0
End Sub

I filled C4 and B4 down for every combination.

Can the rest be split too?

A small first group only counts if the other packages can still make the other groups. I tried this on the puzzle’s example in Sheet1 (weights in C2:L2, target 20 in B2). For each first group, the remainder is the weights that aren’t in it, and a function looks for subsets of the remainder that add up to 20:

C4: =LEN(D4)-LEN(SUBSTITUTE(D4,",",""))+1
C3: =MIN(C4:C1048576)
B4: =IF(C4=$C$3,PRODUCT(VALUE(TEXTSPLIT(D4,","))),0)
B2: =MINIFS(B4:B211833,B4:B211833,">0")

I filled F4 down for every candidate.

Can the rest be split?

A small first group only counts if the other packages can still make the other groups. For each candidate, P asks whether the packages that are not in it can make a second group of the same weight. This function stops at the first one it finds, so it is fast:

P3: =VALUE(TEXTSPLIT(B3,","))
C3: =FindCombinationsFromArray2(
        TEXTJOIN(",",,FILTER($C$2:$L$2,IF(COUNTIF(P3#,$C$2:$L$2),0,1))),20)

P3# is the first group as numbers. With three groups, any subset found there is the second group, and what’s left is the third. The example gives 99, as in the puzzle text.

Part 2

Description

Solution

Now there are four groups. I ran the second macro for the new target, pasted the list into G4, and used the same formulas in columns E and F:

F4: =LEN(G4)-LEN(SUBSTITUTE(G4,",",""))+1
F3: =MIN(F4:F1048576)
E4: =IF(F4=$F$3,PRODUCT(VALUE(TEXTSPLIT(G4,","))),0)
D2: =MINIFS(E4:E211833,E4:E211833,">0")

The list is shorter, and the smallest group needs one package fewer. With four groups, a second group isn’t enough in principle, since the rest has to split into three. For my input I checked that it works.

Read More

Advent of Code 2015 - Day 23: Opening the Turing Lock

Part 1

Description

Solution

The puzzle gives a program for a small computer with two registers, a and b. The jumps make it hard to do with formulas alone, because what runs next depends on what happened before. So I put the program in the sheet and wrote a macro that walks through it. 

Preparing the input

I pasted the program into column A, starting at row 4, and split each line into the instruction (column A, for example jio a) and the number (column B, for example 18). Because every instruction sits in its own row, a jump of +18 simply means “18 rows down”.

How the macro works

The macro keeps a row number, the pointer, which is the row just above the next instruction. It reads the instruction one row below, does what it says, and moves the pointer. For hlf, tpl, inc it moves one row down, and for jmp, jie, jio it moves by the number in column B (only when the condition is true for the last two). After every instruction it writes the current values of a and b into the pointer’s row. The program ends when the pointer reaches the last row, so the final values are in the last row (row 50 for me). That’s why the answers are simply:

B2: =E50      ← Part 1, the value of b at the end
D2: =G50      ← Part 2

Option Explicit

Public Sub Day23Part1()
    RunProgram 0, 4          ' a starts at 0, trace goes to columns D:E
End Sub

Public Sub Day23Part2()
    RunProgram 1, 6          ' a starts at 1, trace goes to columns F:G
End Sub

Private Sub RunProgram(ByVal startA As Long, ByVal col As Long)
    Dim ws As Worksheet: Set ws = ActiveSheet
    Dim reg(0 To 1) As Long          ' reg(0) = a, reg(1) = b
    Dim lastRow As Long, p As Long, k As Long, off As Long
    Dim ins As String, op As String

    lastRow = ws.Cells(ws.Rows.Count, 1).End(xlUp).Row     ' last instruction
    ws.Range(ws.Cells(3, col), ws.Cells(lastRow, col + 1)).ClearContents
    reg(0) = startA
    ws.Cells(3, col).Value = startA
    p = 3                            ' the row just above the next instruction

    Do While p + 1 <= lastRow
        ins = ws.Cells(p + 1, 1).Value
        off = Val(ws.Cells(p + 1, 2).Value)
        op = Left$(ins, 3)
        k = 0
        If Mid$(ins, 5, 1) = "b" Then k = 1
        Select Case op
            Case "hlf": reg(k) = reg(k) \ 2: p = p + 1
            Case "tpl": reg(k) = reg(k) * 3: p = p + 1
            Case "inc": reg(k) = reg(k) + 1: p = p + 1
            Case "jmp": p = p + off
            Case "jie"
                If reg(k) Mod 2 = 0 Then p = p + off Else p = p + 1
            Case "jio"
                If reg(k) = 1 Then p = p + off Else p = p + 1
        End Select
        ws.Cells(p, col).Value = reg(0)
        ws.Cells(p, col + 1).Value = reg(1)
    Loop
End Sub

One thing to know when reading the result: the rows inside the loop (rows 42 to 50 for me) are visited many times, so each shows only the values from the last time the program passed through it.

Part 2

Description

Solution

It’s the same program, but register a starts at 1 instead of 0. That’s F3 = 1 and the macro Day23Part2, which fills F:G. The answer is D2 = G50.

What the program actually does

Looking at the trace, the program has two halves. The first half has no loops. It builds a starting number in a, and the two starting values of a take different paths and build two different numbers. Since the first block has no jumps for Part 1, one running formula can compute it, so I could check it without the macro. In T3 I put 0, and in T4 down to T20:

T4: =IF(LEFT(A4,3)=$M$4,T3/2,IF(LEFT(A4,3)=$M$5,T3*3,IF(LEFT(A4,3)=$M$6,T3+1,T3)))

where M4:M6 hold hlf, tpl and inc. T20 gives the starting number for Part 1.

The second half (rows 42 to 50) is the Collatz sequence. If a is even, halve it; otherwise triple it and add 1. It stops when a is 1, and register b counts the steps. So the two answers are just the number of Collatz steps for the two starting numbers, which I confirmed with a quick separate calculation.

Read More

Advent of Code 2015 - Day 22: Wizard Simulator 20XX

Part 1

Description

Solution

This puzzle is a game with many choices on every turn, so I did it in two steps. First I built a simulator in Excel where I type in the spells and see what happens. Then I used VBA to try every possible sequence. 

The layout

• The boss’s hit points and damage are in B4:B5, my hit points are in D4 and my mana is in A6.
• The spell table is in L1:S6 (cost, damage, heal, poison, shield, recharge, turns).
• From row 11 down there is one row per turn. Column A says whose turn it is, “P” for me and “E” for the boss, with one formula:

A11: =LET(a, SEQUENCE(100), IF(MOD(a,2)=1,"P","E"))

• On my rows I type the spell number (1 to 5) in column L.
• Row 10 labels the columns B (before) and A (after). The columns are boss hit points (B, C), boss damage (D), my hit points (E, F), my mana (G, H), armor (J) and mana spent (K).
• Rows 11, D10 and the starting cells B11, E11 and G11 are linked to the input: =B4, =D4, =A6 and =B5.

Effects without timers

I didn’t track timers. Instead each row asks “was this spell cast in the last few rows?” with COUNTIF over column L. Poison and shield last 6 turns, so they look back 6 rows. Recharge lasts 5, so it looks back 5:

B12: =MAX(0,C11-(COUNTIF(L6:L11,4)*$P$5))        ← poison damage
J12: =COUNTIF(L6:L11,3)*$Q$4                      ← shield armor
G12: =H11+COUNTIF(L7:L11,5)*$R$6                  ← recharge mana

The spell I cast this turn is handled in the same row:

C11: =MAX(0,B11-(COUNTIF(L11,1)*$N$2+COUNTIF(L11,2)*$N$3))     ← boss hit points after my spell
F11: =MAX(0,E11-IF(A11="E",(D11-J11),0))+COUNTIF(L11,2)*$O$3   ← boss hits me on "E" rows, Drain heals me
H11: =MAX(0,IF(A11="P",G11-IF(L11>0,INDEX($M$2:$M$6,L11),0),G11))   ← mana after the spell
K11: =IF(A11="P",IF(L11>0,INDEX($M$2:$M$6,L11),0),"")          ← mana spent

Reading the result

C8 is the first row where the boss has 0 hit points, and F8 is the first row where I do. A10 is the earlier of the two. If the boss dies first, K8 adds up the mana spent up to that row:

C8:  =IFNA(XMATCH(0,C11:C54,0),999)
F8:  =IFNA(XMATCH(0,F11:F54,0),999)
K8:  =IF(C8<=F8,SUM(TAKE(K11:K54,A10)))

The <= matters. If poison kills the boss at the start of his turn, the sheet still lets him hit me in that row, so both hit 0 on the same row.

The simulator doesn’t check that a sequence is legal. It won’t stop me from casting a spell I can’t afford, or one that’s still running. So I used it to look at a sequence, not to find one.

Trying every sequence

For the search I wrote a macro. It plays the game turn by turn and tries all five spells each turn. It skips spells I can’t afford or that are still active, and stops following any path whose mana already reaches the best total found. When it finishes, it writes the best sequence into column L, so K8 confirms the total:

Option Explicit
Private best As Long, bestLen As Long, bossDmg As Long, hardMode As Boolean
Private bestPath(1 To 200) As Long, curPath(1 To 200) As Long
Private spellCost As Variant

Public Sub Day22Part1()
    Solve False
End Sub

Public Sub Day22Part2()
    Solve True
End Sub

Private Sub Solve(ByVal hard As Boolean)
    Dim ws As Worksheet, i As Long
    Set ws = ActiveSheet
    spellCost = ws.Range("M2:M6").Value
    bossDmg = ws.Range("B5").Value
    hardMode = hard
    best = &H7FFFFFFF
    bestLen = 0
    Search ws.Range("D4").Value, ws.Range("A6").Value, ws.Range("B4").Value, 0, 0, 0, 0, 0
    ws.Range("L11:L110").ClearContents
    For i = 1 To bestLen
        ws.Cells(9 + 2 * i, 12).Value = bestPath(i)      ' L11, L13, L15, ...
    Next i
    MsgBox "Least mana: " & best
End Sub

Private Sub Record(ByVal total As Long, ByVal n As Long)
    Dim i As Long
    best = total: bestLen = n
    For i = 1 To n: bestPath(i) = curPath(i): Next i
End Sub

Private Sub Search(ByVal php As Long, ByVal mana As Long, ByVal bhp As Long, _
                   ByVal sh As Long, ByVal po As Long, ByVal re As Long, _
                   ByVal spent As Long, ByVal depth As Long)
    Dim sp As Long, c As Long, s As Long, m As Long, b As Long, ph As Long
    Dim sh2 As Long, po2 As Long, re2 As Long, armor As Long, dmg As Long

    If spent >= best Then Exit Sub

    ' my turn: hard mode, then effects
    If hardMode Then
        php = php - 1
        If php <= 0 Then Exit Sub
    End If
    If sh > 0 Then sh = sh - 1
    If po > 0 Then
        bhp = bhp - 3: po = po - 1
    End If
    If re > 0 Then
        mana = mana + 101: re = re - 1
    End If
    If bhp <= 0 Then
        Record spent, depth
        Exit Sub
    End If

    For sp = 1 To 5
        c = spellCost(sp, 1)
        If c <= mana Then
            If Not ((sp = 3 And sh > 0) Or (sp = 4 And po > 0) Or (sp = 5 And re > 0)) Then
                s = spent + c
                If s < best Then
                    curPath(depth + 1) = sp
                    m = mana - c: b = bhp: ph = php
                    sh2 = sh: po2 = po: re2 = re
                    Select Case sp
                        Case 1: b = b - 4
                        Case 2: b = b - 2: ph = ph + 2
                        Case 3: sh2 = 6
                        Case 4: po2 = 6
                        Case 5: re2 = 5
                    End Select
                    If b <= 0 Then
                        Record s, depth + 1
                    Else
                        ' boss turn: effects, then he attacks
                        armor = 0
                        If sh2 > 0 Then
                            armor = 7: sh2 = sh2 - 1
                        End If
                        If po2 > 0 Then
                            b = b - 3: po2 = po2 - 1
                        End If
                        If re2 > 0 Then
                            m = m + 101: re2 = re2 - 1
                        End If
                        If b <= 0 Then
                            Record s, depth + 1
                        Else
                            dmg = bossDmg - armor
                            If dmg < 1 Then dmg = 1
                            ph = ph - dmg
                            If ph > 0 Then Search ph, m, b, sh2, po2, re2, s, depth + 1
                        End If
                    End If
                End If
            End If
        End If
    Next sp
End Sub

On the puzzle’s two examples the same logic gives 226 and 641. Part 1 can take a little while to run, because it looks at about 700,000 positions.

Part 2

Description

Solution

On hard difficulty I lose 1 hit point at the start of each of my turns. The macro just turns that on: Day22Part2 runs the same search with hardMode = True. It gives a higher total, since some of the cheapest wins no longer survive.

To let the simulator show this too, I put a 1 in D2 as a switch and added one term to the “after” hit points formula in column F:

F11: =MAX(0,E11-IF(A11="E",(D11-J11),0)-IF(AND(A11="P",$D$2=1),1,0))+COUNTIF(L11,2)*$O$3

Then I typed the sequence from the macro into column L and K8 showed the same total.

Read More