Problem difficulty so far (up to day 16)

  1. Day 15 - Warehouse Woes: 30m00s
  2. Day 12 - Garden Groups: 17m42s
  3. Day 14 - Restroom Redoubt: 15m48s
  4. Day 09 - Disk Fragmenter: 14m05s
  5. Day 16 - Reindeer Maze: 13m47s
  6. Day 13 - Claw Contraption: 11m04s
  7. Day 06 - Guard Gallivant: 08m53s
  8. Day 08 - Resonant Collinearity: 07m12s
  9. Day 11 - Plutonian Pebbles: 06m24s
  10. Day 04 - Ceres Search: 05m41s
  11. Day 02 - Red Nosed Reports: 04m42s
  12. Day 10 - Hoof It: 04m14s
  13. Day 07 - Bridge Repair: 03m47s
  14. Day 05 - Print Queue: 03m43s
  15. Day 03 - Mull It Over: 03m22s
  16. Day 01 - Historian Hysteria: 02m31s
  • @swlabr
    link
    English
    3
    edit-2
    9 days ago

    Day 19! (the cuervo gold…)

    disc and code

    Ok so my path to this answer was circuitous and I now hate myself a little.

    P1: Ok, a repeated dfs on suffixes. that shouldn’t be too hard. (it was not hard)

    P2: Ok, a repeated dfs is a little too slow for me, I wonder how I can speed it up?

    forgets about memoisation, a thing that you can do to speed this sort of thing up

    I guess the problem is I’m doing an O(mn) match (where m is the number of towels, n is the max towel length) when I can do O(n). I’ll build a prefix tree!

    one prefix tree later

    Ok that still seems to be quite slow. What am I doing wrong?

    remembers that memoisation exists

    Oh I just need to memoise my dp from part 1. Oops.

    Anyway posting the code because I shrunk it down to like two semicolons worth of lines.

    (

    List<String> input = getLines();
    Set<String> ts = Set.from(input.first.split(', '));
    Map<String, int> dp = {};
    
    int dpm(String s) => dp.putIfAbsent(
        s,
        () => s.isNotEmpty
            ? ts
                .where((t) => t.matchAsPrefix(s) != null)
                .map((t) => dpm(s.substring(t.length)))
                .fold(0, (a, b) => a + b)
            : 1);
    
    void d19(bool sub) {
      print(input
          .skip(2)
          .map((s) => dpm(s))
          .map((i) => sub
              ? i
              : i > 0
                  ? 1
                  : 0)
          .reduce((a, b) => a + b));
    }