Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • @swlabrEnglish
    3•9 months ago

    21 Step Counter

    Starting this thread having only solved a.

    A

    Pretty straightforward. Could probably be done in a few lines with the right syntactic sugar.

    B

    This is some game of life thing that I’ve never implemented or seen an implementation of, so I am altogether lost.

    My current code (https://github.com/Fluxward/aoc2023/blob/main/21.dart) has a memoisation based approach but my current ailments are preventing me from really thinking about this properly so I am bowing out until I have the wherewithal.

    • @geriksonOPEnglish
      3•9 months ago

      This is the hardest problem of the year so far, based on leaderboard completion times. I’m busy wrapping up work for this year, and looking for a new job, so this will have to be put on the TODO pile

      • @swlabrEnglish
        2•9 months ago

        At this point I have officially given up and started looking at other people’s code. I’ll work on it after Imm fully better, it’s too much for me right now.

    • @zogwargEnglish
      3•9 months ago

      Only solved by receving heavy hints from other’s solution, and it still took me forever. By far the hardest this year.

    • @swlabrEnglish
      2•9 months ago

      Update on B:

      still no solve, however

      Through glancing at someone else’s code, I was inspired to just try simulating the A problem beyond 64 steps and seeing the result.

      Essentially it reaches a (bi stable?) steady state between two numbers, which makes sense- if you can only make single rook steps, then the reachable squares will alternate every cycle.

      Don’t know if I’ll try solve this again tonight but mentally I have now understood the solution.

    • @swlabrEnglish
      1•9 months ago

      Update to the update: now fully recovered, I am now trying to finish the last problems.

      Solved 21 B!

      I spent way too much time on this but it’s fine

      So my approach to AOC has always been to write a pure coding solution, which finally broke down here.

      First, the solve:

      I call the unrepeated garden map the “plot”. Each repetition of the plot I call a “grid”. Hope that isn’t confusing.

      1. Looking at the input data, it is a grid of 131x131 squares with the starting position in the center at 66,66 (indexed from 1)
      2. If you imagine a chessboard pattern over the whole area, on each step the possible reachable squares alternate colors.
      3. Row 66 and col 66 are unimpeded by stones, as well as the edges of each grid. This means that:
      • starting from the initial grid, it takes 66 steps to enter a new grid. You enter a new grid on all sides.
      • a grid is always initially entered from the middle of an edge, either on one or two sides based on its position relative to the grids that are currently being considered.
      • each grid is independent of every other grid, except for the step where it is entered.

      To see why that last point is true, consider that in order for another grid A to influence an adjacent grid B beyond the moment the adjacent grid is entered, there must be a reachable point further from the midpoint of the edge on the edge of A. However, because the middle row and column are free from rocks, this is never the case. Any influence from A reaches B too late, i.e. reachable squares on B from A will be reachable sooner from just travelling from the entry point on B.

      1. The number of steps is 131x100x2023 + 65.

      So putting all this together, the way I got the answer was like this:

      1. Simulate the whole area for 65 + (5*131) steps (more than necessary)
      2. Print the number of reachable squares in the grid at 65 + 131n for n = 0-5
      3. Using pen and paper, determine some coefficients for some of the numbers that come up, add everything up in a calculator, and type that answer into AOC.

      So I guess the answer I arrived at was what I’d been thinking I should be doing this whole time: a mix of simulating some of the problem and a decent amount of pen and paper work to get the solution out, rather than just pure coding. Fun!