The previous thread has fallen off the front page, feel free to use this for discussions on current problems

Rules: no spoilers, use the handy dandy spoiler preset to mark discussions as spoilers

  • @zogwarg
    link
    English
    410 days ago

    Day 11

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

    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)
    
    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
    
  • @swlabr
    link
    English
    3
    edit-2
    9 days ago

    Day 12:

    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.

    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.

  • @geriksonOP
    link
    English
    3
    edit-2
    11 days ago

    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

    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
    • @zogwarg
      link
      English
      210 days ago

      One look day 9 and I had to leave it until after work (puzzles unlock at 2PM for me), it wasn’t THAT hard, but I had to leave it until later.

      • @Architeuthis
        link
        English
        410 days ago

        puzzles unlock at 2PM

        Almost exactly at the start of office hours for me.

  • @swlabr
    link
    English
    310 days ago

    Day 11!

    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.

    • @Architeuthis
      link
      English
      2
      edit-2
      10 days ago
      11 discussion with spoliers

      Well my pt1 solution would require something like at least 1.5 petabytes RAM to hold the fully expanded array, so it was back to the drawing board for pt2 😁

      Luckily I noticed the numbers produced in every iteration were incredibly repetitive, so I assigned a separate accumulator to each one, and every iteration I only kept the unique numbers and updated the corresponding accumulators with how many times they had appeared, and finally I summed the accumulators.

      The most unique numbers in one iteration were 3777, the 75 step execution was basically instant.

      edit: other unhinged attempts included building a cache with how many pebbles resulted from a number after x steps that I would start using after reaching the halfway point, so every time I found a cached number I would replace that branch with the final count according to the remaining steps, but I couldn’t think of a way to actually track how many pebbles result downstream from a specific pebble, but at least it got me thinking about tracking something along each pebble.

      11 code
      // 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" 
      
      • @geriksonOP
        link
        English
        310 days ago
        re: 11p2 discussion

        I was also on my way to building a multilevel memoization cache with “branches”, when I just happened to stumble on an incredibly elegant solution in the subreddit. I stole it and awarded myself only 1 point for today. Because I’m worth it.

    • @swlabr
      link
      English
      2
      edit-2
      10 days ago
      followup

      So memoisation is predictably needed for part 2 to run in time. It’s an O(en), so it takes seconds by step 39 and minutes by step 47.

      • @zogwarg
        link
        English
        3
        edit-2
        10 days ago
        re:followup

        If you somehow wanted your whole final array it would also require over 1 Peta byte ^^, memoization definetely reccomended.

        • @swlabr
          link
          English
          410 days ago
          spoiler

          It’s one AOC problem zogwarg, what could it cost? 10 PB?

  • @zogwarg
    link
    English
    37 days ago

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

    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:

    • @swlabr
      link
      English
      37 days ago

      I didn’t really know what they wanted in part 2, so…

      lol

      I made a pretty shitty animation to render the bots and paused it when the tree appeared. This took me way longer than if I had just looked at the 10000 entry text file that I had already made. If I have the energy I’ll make a screen recording.

    • @Architeuthis
      link
      English
      3
      edit-2
      6 days ago
      Pt2 commentary

      I randomly got it by sorting for the most robots in the bottom left quadrant while looking for robot concentrations, it was number 13. Despite being in the centre of the grid it didn’t show up when sorting for most robots in the middle 30% columns of the screen, which is kind of wicked, in the traditional sense.

      The first things I tried was looking for horizontal symmetry (find a grid where all the lines have the same number of robots on the left and on the right of the middle axis, there is none, and the tree is about a third to a quarted of the matrix on each side) and looking for grids where the number of robots increased towards the bottom of the image (didn’t work, because turns out tree is in the middle of the screen).

      I thinks I was on the right track with looking for concentrations of robots, wish I’d thought about ranking the matrices according to the amount of robots lined up without gaps. Don’t know about minimizing the safety score, sorting according to that didn’t show the tree anywhere near the first tens.

      Realizing that the patterns start recycling at ~10.000 iterations simplified things considerably.

      The tree on the terminal output

      (This is three matrices separated by rows of underscores)

    • @zogwarg
      link
      English
      17 days ago
      Updated Reasoning

      Ok it probably works because it isn’t bang center but a bit up of center, most other steps most be half half noise vertically, and the reason it doesn;t minimize on an earlier horizontal step (where every step is mostly half half), is because the middle points on the trunk, that don’t contribute to the overall product therefore minimizing it even lower.

      • @geriksonOP
        link
        English
        27 days ago
        re: day 14 part 2

        I had nfc how to solve this but someoone on the subreddit mentioned that miminizine the “safety score” was the way to go too … I guess your explanation is the correct one. Also the way the puzzle is generated is to start with the tree and go “backwards” a couple of thousand steps and use a number of of those as starting positions. Probably throw in some random robots as noise.

  • @swlabr
    link
    English
    3
    edit-2
    8 days ago

    Day 13, day 13 of shirking other responsibilities.

    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.

    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.

    • @Architeuthis
      link
      English
      3
      edit-2
      8 days ago
      13 commentary

      Solved p1 by graph search before looking a bit closer on the examples and going, oh…

      In pt2 I had some floating point weirdness when solving for keypress count, I was checking if the key presses where integers (can’t press button A five and half times after all) by checking if A = floor(A) and sometimes A would drop to the number below when floored, i.e. it was in reality (A-1).999999999999999999999999999999999999999999999. Whatever, I rounded it away but I did spend a stupid amount of time on it because it didn’t happen in the example set.

    • @zogwarg
      link
      English
      3
      edit-2
      8 days ago

      I liked day 13, a bit easy but in the right way.

      Edit:

      Spoilers

      Although saying “minimum” was a bit evil when all of the systems had exactly 1 solution (not necessarily in ℕ^2), I wonder if it’s puzzle trickiness, anti-LLM (and unfortunate non comp-sci souls) trickiness or if the puzzle was maybe scaled down from a version where there are more solutions.

      • @swlabr
        link
        English
        28 days ago
        spoiler

        Given the lack of edge cases, I feel the latter possibility is strong. I’m just glad it was easy!

  • @swlabr
    link
    English
    26 days ago

    Day 15

    p1

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

    p2 DNF

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

    • @zogwarg
      link
      English
      26 days ago
      Re: p2

      Definitely a bit tedious, I had to “play” a whole session to spot bugs that I had. It took me far longer than average. I had buggy dissepearing boxes because of update order, I would reccomend a basic test case of pushing a line/pyramid of boxes in every direction.

    • @swlabr
      link
      English
      26 days ago
      P2 complete

      The issue with my code was that I didn’t make a push atomic, i.e. I would move boxes even if their ancestors couldn’t be pushed. Making a list of candidate boxes to push solved this.

      Here’s the visualisation of the complete solution, though it doesn’t show the last 100 frames or so. Please forgive me

      https://imgur.com/a/RL50MaC