Advent of Code 2024 Week 2: this time it's all grids, all the time

Day 11

Some hacking required to make JQ work on part 2 for this one.

::: spoiler Part 1, bruteforce blessedly short

#!/usr/bin/env jq -n -f

last(limit(1+25;
  [inputs] | recurse(map(
    if . == 0 then 1 elif (tostring | length%2 == 1) then .*2024 else
      tostring | .[:length/2], .[length/2:] | tonumber
    end
  ))
)|length)

:::

::: spoiler Part 2, some assembly required, batteries not included

#!/usr/bin/env jq -n -f

reduce (inputs|[.,0]) as [$n,$d] ({};     debug({$n,$d,result}) |
  def next($n;$d): # Get next           # n: number, d: depth  #
      if $d == 75                    then          1
    elif $n == 0                     then [1          ,($d+1)]
    elif ($n|tostring|length%2) == 1 then [($n * 2024),($d+1)]
    else #    Two new numbers when number of digits is even    #
      $n|tostring| .[0:length/2], .[length/2:] | [tonumber,$d+1]
    end;

  #         Push onto call stack           #
  .call = [[$n,$d,[next($n;$d)]], "break"] |

  last(label $out | foreach range(1e9) as $_ (.;
    # until/while will blow up recursion #
    # Using last-foreach-break pattern   #
    if .call[0] == "break" then break $out
    elif
      all( #     If all next calls are memoized        #
          .call[0][2][] as $next
        | .memo["\($next)"] or ($next|type=="number"); .
      )
    then
      .memo["\(.call[0][0:2])"] = ([ #                 #
          .call[0][2][] as $next     # Memoize result  #
        | .memo["\($next)"] // $next #                 #
      ] | add ) |  .call = .call[1:] # Pop call stack  #
    else
      #    Push non-memoized results onto call stack   #
      reduce .call[0][2][] as [$n,$d] (.;
        .call = [[$n,$d, [next($n;$d)]]] + .call
      )
    end
  ))
  # Output final sum from items at depth 0
  | .result = .result + .memo["\([$n,0])"]
) | .result

:::

Day 11!

::: spoiler discussion p1 + 2 I'd say this was pretty easy. My instinct was that 64 bit ints were big enough for this problem, and that memoising would also be a good idea. I didn't experiment with a control though, so I don't know if memoisation was truly necessary. Either way, my initial solution for 1. was performant enough for part 2.

:::

// F# as usual
// fst and snd are tuple deconstruction helpers

[<TailCall>]
let rec blink (idx:int) (maxIdx:int) (pebbles : (int64*int64) list) =
    if idx = maxIdx
    then pebbles |> List.sumBy snd
    else
        pebbles
        // Expand array
        |> List.collect (fun (pebbleId, pebbleCount) -> 
            let fpb = float pebbleId
            let digitCount = Math.Ceiling(Math.Log(fpb + 1.0,10))      
            match pebbleId with
            | 0L -> [ 1L, pebbleCount ]
            | x when digitCount % 2.0 = 0.0 -> 
                let factor = Math.Pow(10,digitCount/2.0)
                let right = fpb % factor
                let left = (fpb - right) / factor
                [int64 left, pebbleCount; int64 right,pebbleCount]   
            | x -> [ x * 2024L, pebbleCount ])
        // Compress array
        |> List.groupBy fst
        |> List.map (fun (pebbleId, pebbleGroup) -> pebbleId, pebbleGroup |> List.sumBy snd)
        |> blink (idx+1) maxIdx


"./input.example"
|> Common.parse
|> List.map (fun pebble -> pebble,1L)
|> blink 0 25 
|> Global.shouldBe 55312L

"./input.actual"
|> Common.parse
|> List.map (fun pebble -> pebble,1L)
|> blink 0 75 
|> printfn "Pebble count after 75 blinks is %d" 

Day 14, got very lucky on this one, but too tired to think about why part 2 still worked.

::: spoiler spoiler

#!/usr/bin/env jq -n -R -f

#     Board size     # Our list of robots positions and speed #
[101,103] as [$W,$H] | [ inputs | [scan("-?\\d+")|tonumber] ] |

#     Making the assumption that the easter egg occurs when   #
#           When the quandrant product is minimized           #
def sig:
  reduce .[] as [$x,$y] ([];
    if $x < ($W/2|floor) and $y < ($H/2|floor) then
      .[0] += 1
    elif $x < ($W/2|floor) and $y > ($H/2|floor) then
      .[1] += 1
    elif $x > ($W/2|floor) and $y < ($H/2|floor) then
      .[2] += 1
    elif $x > ($W/2|floor) and $y > ($H/2|floor) then
      .[3] += 1
    end
  ) | .[0] * .[1] * .[2] * .[3];

#           Only checking for up to W * H seconds             #
#   There might be more clever things to do, to first check   #
#       vertical and horizontal alignement separately         #
reduce range($W*$H) as $s ({ b: ., bmin: ., min: sig, smin: 0};
  .b |= (map(.[2:4] as $v | .[0:2] |= (
    [.,[$W,$H],$v] | transpose | map(add) 
    | .[0] %= $W | .[1] %= $H
  ))) 
  | (.b|sig) as $sig |
  if $sig < .min then
    .min = $sig | .bmin = .b | .smin = $s 
  end | debug($s)
)

| debug(
  #    Contrary to original hypothesis that the easter egg    #
  #  happens in one of the quandrants, it occurs almost bang  #
  # in the center, but this is still somehow the min product  #       
  reduce .bmin[] as [$x,$y] ([range($H)| [range($W)| " "]];
    .[$y][$x] = "█"
  ) |
  .[] | add
)

| .smin + 1 # Our easter egg step

And a bonus tree: :::

Day 13, day 13 of shirking other responsibilities.

::: spoiler p1 Ok. So, I overthought this a little. Ultimately, this problem boils down to solving a system of 2 linear equations aka inverting a matrix.

Of course, anyone who has done undergraduate linear algebra knows to look to the determinant in case some shit goes down. For the general problem space, a zero determinant means that one equation is just a multiple of the other. A solution could still exist in this case. Consider:

a => x+1, y+1
b => x+2, y+2
x = 4, y = 4 (answer: 2 tokens)

The following has no solution:

a => x+2, y+2
b => x+4, y+4
x = 3, y = 3

I thought of all this, and instead of coding the solution, I just checked if any such cases were in my input. There weren't, and I was home free. :::

::: spoiler p2 No real changes to the solution to p1 aside from the new targets. I wasn't sure if 64 bit ints were big enough to fit the numbers so I changed my code to use big ints.

I'm looking at my code again and I'm pretty sure that was all unnecessary. :::

Day 12:

::: spoiler P1 Ok. I have been traumatised by computational geometry before, so I was initially spiralling. Luckily, there wasn't too much comp geo stuff to recall.

My solution was a lot simpler than I initially thought: no need for union-find, accounting for regions inside regions, etc. Just check every square for a given region, and if it touches a square in the same region that you've seen before, subtract the common edge. This is linear in the area of the problem, so it's fast enough. :::

::: spoiler P2 It took a moment to figure out that I could modify the above perimeter counting to mark the squares containing the perimeter and walk along it afterwards, counting each edge. This is also linear in area. :::

This morning I felt a bit burned out on AoC but thought I might as well just do some noodling around on breaks. Turns out it was

::: spoiler day 10

pretty dang easy

:::

So far this is the current standing according to the finishing times of the 1st 100 answers on the global leaderboard

1. Day 09 - Disk Fragmenter: 14m05s
2. Day 06 - Guard Gallivant: 08m53s
3. Day 08 - Resonant Collinearity: 07m12s
4. Day 04 - Ceres Search: 05m41s
5. Day 02 - Red Nosed Reports: 04m42s
6. Day 10 - Hoof It: 04m14s
7. Day 07 - Bridge Repair: 03m47s
8. Day 05 - Print Queue: 03m43s
9. Day 03 - Mull It Over: 03m22s
10. Day 01 - Historian Hysteria: 02m31s

Day 15

::: spoiler p1 Pretty easy. Just check in the direction you want to push if you have space. :::

::: spoiler p2 DNF Currently debugging with test cases from the subreddit. I’ve also created a shitty visualiser for it, stay tuned! :::