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.

  • gerikson@awful.systemsOP
    link
    fedilink
    English
    arrow-up
    3
    ·
    1 year ago

    Day 9: Mirage Maintenance

    My solution: https://github.com/gustafe/aoc2023/blob/main/d09-Mirage-Maintenance.pl

    discussion

    What can I say. Shockingly simple.

    I just literally followed the instructions, and got a solution in 20ms. This despite literally creating each intermediate array yet only using the ends. I’m sure I used way to much memory but you know? I’m using a $5/mo VPS for everything and unless I’m barking totally up the wrong tree I’ve never exceeded its memory limits.

    On the subreddit I see people discussing recursion and “dynamic programming” (which is an empty signifier imho) but I really don’t see the need, unless you wanna be “elegant”

    • swlabr@awful.systems
      link
      fedilink
      English
      arrow-up
      3
      ·
      1 year ago
      spoiler

      DP to me is when you use memoisation and sometimes recursion and you want to feel smarter about what you did.

      I also struggle to think of the need for DP, even in a more “elegant” approach. Maybe if you wanted to do an O(n) memory solution instead of n^2, or something. Not saying this out of derision. I do like looking at elegant code, sometimes you learn something.

      I feel like there’s an unreadable Perl one line solution to this problem, wanna give that a go, @gerikson?

      • zogwarg@awful.systems
        link
        fedilink
        English
        arrow-up
        3
        ·
        1 year ago
        spoiler

        Part 2 only, but Part 1 is very similar.

        #!/usr/bin/env jq -n -R -f
        [
          # For each line, get numbers eg: [ [1,2,3] ]
          inputs / " " | map(tonumber) | [ . ] |
        
          # Until latest row is all zeroes
          until (.[-1] | [ .[] == 0] | all;
           . += [
             # Add next row, where for element(i) = prev(i+1) - prev(i)
             [ .[-1][1:] , .[-1][0:-1] ] | transpose | map(.[0] - .[1])
            ]
          )
          # Get extrapolated previous element for first row
          |  [ .[][0] ] | reverse | reduce .[] as $i (0; $i - . )
        ]
        
        # Output sum of extapolations for all lines
        | add
        

        I’m pretty sure you could make this one line and unreadable ^^.

        • swlabr@awful.systems
          link
          fedilink
          English
          arrow-up
          3
          ·
          1 year ago

          Here’s where I landed in dart

          no comments
          d9(bool s) {
            print(getLines().fold(0, (p, e) {
              int pre(List h, bool s) {
                return h.every((e) => e == 0)
                    ? 0
                    : (pre(List.generate(h.length - 1, (i) => h[i + 1] - h[i]), s)) *
                            (s ? -1 : 1) +
                        (s ? h.first : h.last);
              }
          
              return p + pre(stois(e), s);
            }));
          }