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@awful.systems
    link
    fedilink
    English
    arrow-up
    3
    ·
    11 months ago
    4 a

    Not so bad today. I bit the bullet and tried to see if dart has tuples or similar. It does, by the name of “records”. Now instead of pretending I’m writing in C/C++, I can pretend I’m writing in python.

    Anyway, a) is a pretty straightforward job-interview style question, except AoC doesn’t care about efficiency. Still, we all have our own versions of pride, so I did it with a set (Though whether or not dart’s native Set is tree or hash based is not known to me right now).

    code
    int matches(String line) {
      ({List wn, List n}) card = getNumbers(line);
      Set wn = Set.from(card.wn);
    
      return card.n.fold(0, (prev, e) => prev + (wn.contains(e) ? 1 : 0));
    }
    
    void day4a(List lines) {
      print(lines.fold(0, (acc, line) {
        int m = matches(line);
        return acc + (m != 0 ? (1 << (m - 1)) : 0);
      }));
    }
    
    4b

    b) was a little harder, and definitely a possible trap for overthinking. I think the easiest way to think about solving this is as if it is a dynamic programming problem (though it kinda isn’t).

    So the general approach is to formulate it like this:

    T_n(total cards won by card n) = M_n(total matches for card n) + CW_n(total cards won by the copies that card n wins).

    and

    CW_n =

    • 0 if M_n = 0
    • sum of T_i, where i = n + 1 … n + M_n

    Caching T_n is the DP trick to making this performant (though once again, it does not need to be)

    Anyway, the above approach is the top-down version of the DP; the bottom-up version is what I actually started with in my head. I gave up on that approach because I felt like the logic was too hard for me to figure out.

    code:
    void day4b(List lines) {
      List totalMatches = lines.map((e) => matches(e)).toList();
    
      // total copies won, including copies won from copies.
      List cachedWins = List.filled(totalMatches.length, -1);
      int totalWins(int i) {
        // return cached result if it exists
        if (cachedWins[i] > 0) {
          return cachedWins[i];
        }
    
        int count = totalMatches[i];
        // count the copies won from the subsequent copied cards
        for (int j = 1; j <= totalMatches[i]; j++) {
          count += totalWins(i + j);
        }
    
        // cache the result
        cachedWins[i] = count;
        return count;
      }
    
      int totalCards = totalMatches.length; // count all the originals
      // count all the wins
      for (int i = 0; i < totalMatches.length; i++) {
        totalCards += totalWins(i);
      }
      print(totalCards);
    }