3 ms·
I'm surprised at people here suggesting that brute force is the only solution. There are better ways of searching. Let's make an assumption that we only ever d
by IanCal 11y ago
I'm surprised at people here suggesting that brute force is the only solution. There are better ways of searching.
Let's make an assumption that we only ever deal with integers.
Also, 66 is pretty small given we've got to multiply by 13 at one point and multiply by 12 at another.
Let's simplify it a little too.
a + ((13 * b) / c) + d + 12 * e - f - 11 + ((g * h) / i) - 10 == 66
a + ((13 * b) / c) + d + (12 * e) - f + ((g * h) / i) == 87
Rearrange a little for clarity
(a + d - f) + (12 * e) + ((13 * b) / c) + ((g * h) / i) == 87
What can we tell about this? Well, most of this is additive, apart from f.
That means we're going to be increasing our answer at each stage. If we set e to be 9, then we're definitely going to overshoot. In fact, it'd be probably impossible for it to be 7 (since that'd get us to 84 already). 6 would leave us with only 15 spare.
The greatest reduction would be 6 (1 + 2 - 9) so the rest of the equation can't be above 93 in total. The most we can add at the start is 16, so the rest of the equation can't be below 71. That's a fairly narrow band.
Is anything hugely constrained? Well, how about ((13 * b) / c)? If that's an integer then we've got to have b as a multiple of c. Therefore we really can only have c <= 4. c only has 4 values, and unless it's 1 then b only has a small number of possible values too.
Neither g or h can be 1 either, since then we'd never find a multiple of i.
Finally, since we know how changing our answer affects the result (up or down) we can mix up the numbers until it starts to work or get close. Maybe, like countdown, the answer isn't to simply give up but see how close you can get. In fact, we can make a further assumption that the problem is reasonably solvable, which suggests it's not actually that far from what is a reasonable first guess.
So. Start with something obvious, then lets try and tweak it until we start to pass all the conditions above.
1,2,3,4,5,6,7,8,9
b is not a multiple of c. Swap c for a.
3,2,1,4,5,6,7,8,9
Ok, so fine up through the first four. Let's leave those as they are until we have a better reason to change them.
e could be 5, yep.
f can be anything.
((g * h) / i) => 7 * 8 / 9 nope.
We can move around 5 and 6 into this. The 8 / 6 looks nice together, both even, the only one that works is 9 * 8 / 6. I can't actually see another solution without making a bigger difference elsewhere.
So
3,2,1,4,5,7,9,8,6 => 98
Pretty close! We're 11 over. We've got a fairly unrestricted "multiply by 12" in there, so let's see if we can decrease it.
e = 5 -> e = 4
All we're changing is d then, which is fine since it's another unrestricted one, and it'll change our results elsewhere by 1.
3,2,1,5,4,7,8,9,6 => 87
Let's double check that
a + ((13 * b) / c) + d + (12 * e) - f - 11 + ((g * h) / i) - 10 == 66
3 + ((13 * 2) / 1) + 5 + (12 * 4) - 7 - 11 + ((8 * 9) / 6) - 10 == 66
valid multiple valid multiple
I'm not going to pretend I hadn't already seen some answers, and I definitely think this is a hard problem, but it's certainly not something that you have to brute force. We can make clear and obvious steps towards solutions, several paths are guaranteed dead ends and there are a neat set of variables we can set to basically anything so we'll regularly actually be able to at least try our answer before tweaking it again.
Edit -
Anyone want to start a pool for when this will find its way into an interview question set?
- tempestn 11y agoI think this would be a great interview question, as it would be a signal to the applicant that they probably don't want the job. ;) Yes, there are ways to constrain things so you can work it out without trying thousands of possibilities, but it's still basically a slog doing it by hand, as you demonstrated.
- IanCal 11y ago> it's still basically a slog doing it by hand, as you demonstrated. Well, it requires some work, yes, but there's not actually that much blind trial and error.