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
Probably the easiest optimization (which admittedly I didn’t think of myself) is to work backwards: you can eliminate multiplication and concatenation early if you start with the answer and check terms from the right.
Call it optimization and people will assume it is magic. Instead I call this a simple algebra challenge.(With part two having that quirky concatenation operation)
It is like solving for x. Let’s take an example:
3267: 81 40 27If you change it to equations:
81 (+ or *) 40 (+ or *) 27 = 3267Which effectively is:
81 (+ or *) 40 = x (+ or *) 27 = 3267So what is the x that either add or multiply would need to create 3267? Or solve for x for only two equations.
x + 27 = 3267->x = 3267 - 27 = 3240x * 27 = 3267->x = 3267 / 27 = 121(Special note since multiplying and adding will never make a float then a division that will have a remainder(or float) is impossible for x, we can easily remove multiplying as a possible choice)
Now with our example we go plug in x:
81 (+ or *) 40 = (3240 or 121) (+ or *) 27 = 3267So now we see if either 40 or 81 can divide or subtract from x to get the other number. Since it is easier to just program to use the next number in the list, we will use 40.
81 + 40 = 3240->x = 3240 - 40 = 3200 != 8181 * 40 = 3240->x = 3240 / 40 = 8181 + 40 = 121->x = 121 - 40 = 8181 * 40 = 121->x = 121 / 40 = 3.025 != 81This particular example from the website has two solutions.
For the concatenation operation, you simply check if the number ends with the number in the list. If not then a concatenation cannot occur, and if true remove the number from the end and continue in the list.
Call it pruning tree paths but it is simply algebraic.