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.

  • @zogwarg
    link
    English
    3
    edit-2
    1 year ago

    Day 8: Haunted Wasteland

    https://adventofcode.com/2023/day/8

    Not so easy at least for part two.

    spoiler

    Do you remember high school math, like lowest common multiple, part 2 electric boogaloo.

    • @zogwarg
      link
      English
      21 year ago

      Cleaned up version of code used to solve part 2 in jq.

      Spoiler code section
      #!/usr/bin/env jq -n -R -f
      
      # Get LR instructions
      ( input / "" | map(if . == "L" then 0 else 1 end )) as $LR |
      ( $LR | length ) as $l |
      
      # Make map {"AAA":["BBB","CCC"], ...}
      (
        [
          inputs | select(.!= "") | [ scan("[A-Z]{3}") ] | {(.[0]): .[1:]}
        ] | add
      ) as $map |
      
      # List primes for GCM test / factorization
      [
        2, 3, 5, 7, 11, 13, 17, 19,
        23, 29, 31, 37, 41, 43, 47,
        53, 59, 61, 67, 71, 73, 79,
        83, 89, 97
      ] as $primes |
      
      reduce (
        $map | keys[] | select(test("..A")) | { s: 0, i: 0, c: .} |
      
        # For each "..A" starting position
        # Produce visited [ "KEY", pos mod $l ], until loop is detected
        until (.i as $i | .[.c] // [] | contains([$i]);
          .s as $s | .i as $i | .c as $c        |
          $map[$c][$LR[$i]] as $next            | # Get next KEY
          .[$c] = (( .[$c] // [ $s ] ) + [$i] ) | # Append ( .s ≡ $l ) to array for KEY (first = .s non mod)
          .s = ( $s + 1 )  | .i = (.s % $l )    | # Update cursors, for next iteration
          .c = $next
        )
        | .[.c][0] as $start_loop_idx | (.s - $start_loop_idx) as $loop_size
        | [ to_entries[] | select(.key[-1:] == "Z") ]
        | if (
            length != 1                                           # Only one ..Z per loop
            or ( .[0].value[0] != $loop_size )                    # First ..Z idx = loop size
            or ( [ .[0].value[0] / $l ] | inside($primes) | not ) # loop_size = ( prime x $l )
            or ( .[0].value[0] / $l  > $l )                       # GCM(loop_sizes) = $l
          ) then "Input does not fit expected pattern" | halt_error else
            # Under these conditions, synched positions of ..Zs happen at:
            # LCM = Π(loop_size_i / GCM) * GCM
      
            # loop_size_i / GCM
            .[0].value[0] / $l
          end
      ) as $i (1; . * $i)
      
      # Output LCM = first step where, all ghosts are on "..Z" nodes
      | . * $l
      
      • @swlabr
        link
        English
        11 year ago

        Seeing you implement gcd/lcm makes me think about the people who are gunning for the AoC leaderboards. What do they have that I don’t?

        Asking out of general interest and not any sort of feelings of inadequacy (I swear, behind a face of gritted teeth and obvious seethe).

        Like, do they have cron scripts to scrape the prompt and input as soon as it comes out? Libraries of util functions accrued from years of AoC participation? That’s all I’ve thought of and honestly it doesn’t sound implausible if you are hypercompetitive. Like I imagine they just have a raiders of the lost ark warehouse of boilerplate indexed in their memory palace to draw from. And I don’t have that and I am totally not envious at all.

        • @zogwarg
          link
          English
          31 year ago

          Ah! Thanks for making my notice the GCM -> GCD typo. I’m not gunning for the leaderboards myself, it’s pretty hopeless ^^. Yes i am assuming based off of experience and utility tools.

          I myself have tools to automatically get the inputs, and submit outputs, but that’s more because it pleases me than to actually be fast: https://github.com/zogwarg/advent-of-code/blob/main/functions.sh

          (Also completely pointlessly have a functions to extract the session cookie from chrome storage from the CLI, despite being long-lived, and therefore much simpler to simply copy-paste from debugger window)

          • @swlabr
            link
            English
            31 year ago

            hey dawg, doing pointless scripting to automate things you don’t need to automate is how we grow as programmers/how the basilisk gets made

        • @geriksonOP
          link
          English
          31 year ago

          Re: LCM, I figured my favorite Perl library ntheory had it, and I was right! This a godsend for Project Euler, too.

          (The first year of AoC leaned heavily on these kinds of problems, and Python itertools utterly destroyed the puzzles.)

          Re: leaderboard participants - I believe many of them are involved in programming contests, generally, and if you do enough of these, you recognize patterns, and you have routines for a lot of stuff. Also there are tools to download the puzzle inputs automatically.

          My personal take on how to do AoC: https://gerikson.com/blog/comp/adventofcode/Howto-AoC.html (maybe already posted, I don’t care)

          • @swlabr
            link
            English
            31 year ago

            Thanks for the insight. I haven’t done much AoC, and this largely confirms the vibes I’ve been getting this time around.

            • @geriksonOP
              link
              English
              41 year ago

              Much like a high IQ score doesn’t show intelligence, but rather the aptitude to take IQ tests, being good at AoC does not show you are a good programmer, but rather that you are good at programming challenges.