Part 1 made my head hurt, I’ll tackle Part 2 in the morning. Part 2 was easier than I expected. I’m not really happy with any part of this solution, nothing feels optimal.
On part 2
I thought that the concatenation happened on the input’s digits and not on the ongoing calculation.
So I made a two-level combinator which was more complicated than the required one…
1 Like
The question is does concatenation work this way: 1 || 02 = 102. I thought it does and made the solution to work this way, but it failed. So it made me redo the code to eliminate these cases, then it works.
Well, that’s a problem that didn’t cross my mind. What are all your process times, by the way? I think I’ve seen some heavy recursion. While some recursion/back-tracking is needed, I think I got a pretty efficient solution (going backwards and only checking paths that are possible). Problem 2 on my i7-11700K takes 2ms.
I also skipped the ‘read the data from file’ bit. I wanted to try variable length arrays, so then I hard-coded the problem data in a package.
I was able to get the left-to-right recursive version down to 60ms on an i5-2500k (process creation, IO, text parsing, and both parts. flags: -O3 -gnatp -gnatn) 90ms with -Og -gnata -gnatVa. Most of the time save came from eliminating Vector and stack allocating instead.
EDIT: Down to 40ms | 70ms after eliminating copies altogether.
1 Like
I did the following optimizations:
- Removed the unnecessary
Vector.Copyin my inner recursive function - Switched to
Bounded_Vectors.Vector (Capacity => 16) - Enabled
-gnatn2 -gnatp -march=native -O3
I tried using a bare array instead of Bounded_Vectors, but this provided no measurable improvement in performance. I’d rather keep the convenience of Containers.
On my 7950X3D this solves part 2 in 205ms. Not great, not terrible.
I’m sure there are better algorithms and this problem appears to be embarrasingly parallel, so there are more opportunities for optimization, but I think this is good enough for today.
2 Likes
Are there cases in your input with 1 02? If not, how would that arise to start with?
My only optimization in part 2 was not to re-compute anything that passed in part 1. I was pretty pleased about my solution managing 1.2s for both parts, almost all of which is part 2. (This is w/alr --release.)
Then I read the various optimizations people posted to Reddit and here, and felt… well, not quite disappointed, but less pleased. 
I don’t know if anyone else tried this, but in Part 1 my only optimization was to verify that
product (operands) >= test_value >= sum(operands)
If that’s false, there’s no point continuing.
…and I somehow completely mis-reasoned concatention in exactly the same way as @zertovitch. That puts me in good company, but is kind of bad news for him 
Completed day 7, both parts. Nothing very efficient (12 seconds on my i714700K!!!), but it works.
If I have some time to spare this advent I might try an optimization on the combinations of operators 
Rookie numbers! My Ruby solution, which is pretty much as inefficient as it gets, runs for 4 mins straight. 
It monkey patches the int class, replaces spaces with different configurations of operators and just calls eval on the resulting string. Partial solution:
class Integer
# relevant ops (*, /, %) all have same precedence
def / (other) = self + other
def % (other) = (self.to_s + other.to_s).to_i
end
valid = ["*", "/", "%"].repeated_permutation(n).one? do |ops|
eval(tail.gsub(" ") { ops.shift }) == result
end
1 Like