copy pasting the rules from last year’s thread:

Rules: no spoilers.

The other rules are made up aswe 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
    2
    ·
    edit-2
    17 days ago

    Day 7

    1 and 2

    On reflection, it was a pretty fun little problem to solve. There wasn’t much of a difference between the two parts. I ran into some bugs with my recursion termination conditions, but I got them in the end.

    Part 1. A quick look at the data showed that the input length was short enough to perform an O(2n) search with some early exits. I coded it as a dfs.

    Part 2. Adding concatenation just changes the base from 2 to 3, which, while strictly slower, wasn’t much slower for this input.

    code
    void d7(bool sub) => print(getLines()
        .map((l) => l.split(RegExp(r':? ')).map(int.parse).toList())
        .fold<int>(
            0, (p, ops) => test(ops, ops[0], ops[1], 2, sub) ? ops[0] + p : p));
    
    bool test(List<int> l, int cal, int cur, int i, bool sub) =>
        cur == cal && i == l.length ||
        (i < l.length && cur <= cal) &&
            (test(l, cal, cur + l[i], i + 1, sub) ||
                test(l, cal, cur * l[i], i + 1, sub) ||
                (sub && test(l, cal, cur.concat(l[i]), i + 1, sub)));
    
    • gerikson@awful.systems
      link
      fedilink
      English
      arrow-up
      2
      ·
      edit-2
      17 days ago
      Re: day 7 parts 1 and 2

      same here, I was dicking around with combinatorics to get all combos of plus and multiply but realized before I got to the end it was gonna take too long. Then I figured that a DFS was the way to go.

      I tried to optimize a bit by exiting early if the cumulative result became too large, but for some reason that gave me incorrect (too low) answers. Part 2 runs in around 1 min anyway.

      https://github.com/gustafe/aoc2024/blob/main/d07-Bridge-Repair.pl

      • swlabr@awful.systems
        link
        fedilink
        English
        arrow-up
        2
        ·
        17 days ago
        re: branch cutting

        IDK if this is what your issue was, but one thing I ran into was that if you do something like if (current_total >= target) prune(), this can be problematic because if the tail end of the data is 0s and 1s, you exit too early. Basically I would prune strictly when the current total > target.