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.

  • @swlabr
    link
    English
    31 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
      link
      English
      31 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
        link
        English
        31 year ago

        Now this is content

      • @swlabr
        link
        English
        31 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);
          }));
        }