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
    link
    English
    2
    edit-2
    13 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
      link
      English
      4
      edit-2
      13 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

      • @ArchiteuthisOP
        link
        English
        3
        edit-2
        12 days ago

        My graph search solves 7-1 and passes the example cases for 7-2, but gives too low a result for the complete puzzle input, and there’s no way I’m manually going through every case to find the false negative. On to day 8 I guess.

        7-2 Check case by simple graph search that mostly works
        // F#
        let isLegit ((total: int64), (calibration : int64 array)) = 
        
            let rec search (index : int) (acc: int64) =
                let currentValue = calibration.[index]
                
                [Add; Times; Concat] // operators - remove 'Concat' to solve for 7-1
                |> List.exists (fun op -> // List.exists returns true the first time the lambda returns true, so search stops at first true
                        match op with // update accumulator
                        | Add -> acc + currentValue
                        | Times -> acc * currentValue
                        | Concat -> int64 (sprintf "%d%d" acc currentValue)
                        |> function // stop search on current accumulator value (state) exceeding total, or being just right
                        | state when state > total -> false
                        | state when state = total && index < (calibration.Length-1) -> false // this was the problem
                        | state when state = total && index = (calibration.Length-1) -> true
                        | state -> // stop if index exceeds input length, or continue search
                            if index+1 = calibration.Length
                            then false
                            else search (index+1) state
                )
             
            // start search from second element using the first as current sum
            search 1 calibration.[0]
        

        EDIT: total && index < (calibration.Length-1) -> false – i.e. stop if you reach the total before using all numbers, well, also stops you from checking the next operator, So, removing it worked.

        Rubber ducking innocent people on the internets works, who knew.

        • @gerikson
          link
          English
          412 days ago

          this looks like the same issue I had!

      • @swlabr
        link
        English
        213 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.

        • @gerikson
          link
          English
          213 days ago
          re: branch cutting

          thanks for the tip, I looked into it again and I found I was cutting in the wrong place. Fixed now, and halves the time for part 2

          • @swlabr
            link
            English
            213 days ago

            We love to see it