Previous writeups: 2015, 2016, 2017.

These puzzles are much harder than 2015-2017 and 2021 ones, although much easier than 2019’s.

I should learn to use Z3 Prover for Day 23 and other constrained optimization scenarios.

I found day 16 particularly funny to solve with pytorch after using regular approach.

Day 4

Reminds me of data analysis homeworks:

  • validate data, order and group when necessary
  • endless combinations of sort-by, group-by, count-frequencies
  • take final result

Day 7

Part 1 is called topological sort, some used networkx solving it.

Overthought about part 2: there is no “you” to help elves, and if I had a good guess, nor should “you” affect the final result; there will always be more workers available than candidate steps, or there are always workers watching other workers, no need to chooce steps. (simplified by puzzle creator?)

The rest is just a big loop of timing ticker:

  • keep track of current time, arranged steps and their finish time
  • record finished steps, fit new candidates into workers
  • if all steps are finished, return current time
  • else recur with next time tick(just inc by 1)

Day 8

Recursion, after some training I managed to come up with a solution. Wasted some time debugging wrong input, during which I found recursive codes are hard to debug.. at least mine are.

If optimizable tail recursion is not trivial to implement, adjusting stack size might be helpful.

Day 9

Shamelessly used C++ for part 2, still haven’t find proper library with double linked list for JVM.

I hope the C++ code looks readable.

Day 10

The description uses “HI” as example, but … input contains much more points, are they all pixelated in letters or there will be outsiders? How many pixels a letter might take? Are pixels all connected vertically or horizontally? How are curved letters like ‘O’ represented in pixels? What will happen when points are overlapped? Italic and bold letters?

On the other hand, creating a valid input seems easy:

  • generate random letters(part 1)
  • pixelate letters, assign coordinates and random speed
  • let them move for a while(part 2)
  • negate speed

Day 11

Part 2 can be generalized to rectangulars with any size. 300x300 is already too large, even using pmap.

There are many ways to reduce calculation, the one I used is not efficient:

  • pre-calculate cache map c, whose keys are [i j], values are sum of all numbers from [0 0] to the key, that is 300x300 rectangles
  • loop over each start coordinate [x y] and possible square size k
  • calculate sum by s(x, y, k)= c(x+k,y+k)-c(0,y-1)-c(x-1,0)+c(x-1,y-1), record maximum one

It definitely took longer than 15 seconds on a relative new machine. As said in FAQ, there should be a solution that requires less than 15 seconds even on old machine.

Day 12

The plants are made to spread to “right”, eventually increase result by k after each generation.

I always had some difficulty when dealing with expansion puzzles like these, padding does not work for infinite series, then I found this solution: just keep related indexes in memory instead of full data structure.

Day 13

Turning directions on / \ can be simplified as (if (= slash? horizontal?) -1 1, here 1 means turn right. Y-axis is upside-down: line 0 to line 1 is “going down”, its movement vector is [0 1](x and y respectively). Adding up these two clues, LURD directions are [[-1 0] [0 -1] [1 0] [0 1]] .

The rest is then a loop:

  • sort robots by movement order
  • record current locations as loc1
  • move all robots one step forward to new locations, flag both robots if new location is in loc1, else add new location to loc1, for case: [robot1-> space <-robot2]
  • remove flagged robots
  • return if only 1 left, print
  • else recur with robots left

Day 14

Finally a simple puzzle, tried part 2 with cpp to check branch prediction rate, but epyc reports 0% miss, 4800h(wsl), qemu and E5 2683v2 does not support perf tool.

Since sum can have 1 or 2 digits, it is necessary to check both s[-7:-1] and s[-6:], or will result in a 905873412 len vector, instead of “just” 22 million for my input.

Day 16

Looks like 2021-19 and other circuit building puzzles, but with more explicit hints, the opcode mapping is strictly one-to-one relationship. Part 2 can be either deduced recursively:

  • define a “correct” opcode list
  • replace opcode with all unknown opcodes, check if state fits
  • find the only possibility, add to known opcodes(wrong->correct map)
  • recur until the map contains 16 opcodes

Or load data into a neural network and overfit train it:

import re
with open("../../resources/2018/i161.txt") as f:
    c = f.read()
ic = [float(int(x)) for x in re.findall("\d+", c)]
ics = [[ic[i:i+4], ic[i+4:i+8], ic[i+8:i+12]] for i in range(0, len(ic), 12)]
train_len = int(len(ics) * 0.9)
train_data = ics[0:train_len]
test_data = ics[train_len:]

# create tensor based on state+op=after-state
# 8->4 model?
def to_tensors(data):
    r = []
    for s, op, o in train_data:
        i = s+op
        t = [torch.tensor(i), torch.tensor(o)]
        r.append(t)
    return r

train_dataloader = DataLoader(to_tensors(train_data),  shuffle=False)
test_dataloader = DataLoader(to_tensors(test_data), shuffle=False)

# replace self.linear_relu_stack with
nn.Sequential(
    nn.Linear(8, 64),
    nn.ReLU(),
    nn.Linear(64, 64),
    nn.ReLU(),
    nn.Linear(64, 64),
    nn.ReLU(),
    nn.Linear(64, 4),
)
# and loss_fn with
nn.MSELoss(reduction='sum')

After about 200 epoches, max loss is less than 0.5, means that round(x) will be the correct registry value.

Day 19

Street rumor says g++ or clang++ can help decipher these “assembly codes” of part 2 and unroll duplicated calculations in compile time, but I failed to translate input into something they understand. I’m bad at articulating with compiler backends.

The result is the sum of all factors, even numbers included, of the certain registry.

Day 22

It is possible to reach a point with the same cost but different equipment, so encode equipment with location as a key, and reuse our good old dijkstra.

(let [s->e {0 #{1 2} 1 #{0 2} 2 #{0 1}}] ;; current position state can equip
  (defn f-22
    ;; equipment: 0 neither, 1 torch, 2 climbing
    ;; location's type, 0 rocky 1 wet 2 narrow
    [m [loc e]]
    (let [s (m loc) ;; rocky or
          m1 (e->s e)
          ne (- 3 s e) ;; simplified change equip calculation
          np (for [p (adj-points loc)
                   :when (m p)]
               (if (m1 (m p))
                 [[p e] 1] ;; can just move without change
                 [[p ne] 8]))] ;; change equip 7+1move
      (into {} np))))

It is also (highly?) likely that a larger map is needed, don’t assume that the target point is some cornor, instead, try to find a path with lowest cost in an imaginary larger map.

Day 23

Checkout Z3 Prover!