I thought about it for 15 mins, but couldn’t think of any mathematical tricks. I thought of lots of minor tricks, like comparing the number to the result and not adding any more multiplications if it’s over, things that would cut 10%-20% here and there, but nothing which fundamentally changes big O running time.
For reference, here’s my solution for part 2 in smalltalk. I just generated every possible permutation and tested it. Part 1 is similar, mainly I just used bit magic to avoid generating permutations.
(even if you haven’t used it, smalltalk is fairly readable, everything is left to right, except in parens)
day7p2: in
| input |
input := in lines collect: [ :l | (l splitOn: '\:|\s' asRegex) reject: #isEmpty thenCollect: #asInteger ].
^ (input select: [ :line |
(#(1 2 3) permutationsWithRepetitionsOfSize: line size - 2)
anySatisfy: [ :num | (self d7addmulcat: line ops: num) = (line at: 1)]
]) sum: #first.
d7addmulcat: nums ops: ops
| final |
final := nums at: 2.
ops withIndexDo: [ :op :i |
op = 1 ifTrue: [ final := final * (nums at: i + 2) ].
op = 2 ifTrue: [ final := final + (nums at: i + 2) ].
op = 3 ifTrue: [ final := (final asString, (nums at: i+2) asString) asInteger ]
].
^ final
I am not sure how much the formal complexity changes, but the pruning that occurs when working from right to left and bailing early when inverse multiplication or concatenation fails seriously cuts down on the number of combinations that you need to explore. With this pruning, the average fraction of the times (relative to the average 3^(n-1) / 2 times necessary for a naive brute force) that my code actually ended up checking whether the full inverted equation was equal to the target, was only 2.0% for equations that did not have solutions. Interestingly, the figure rose for equations that did have solutions to 6.6%.
How about the overall number of checks you did? String cat is heavy, but addition and multiplication are absurdly fast, probably faster than the branches needed for early escape.