challenge for programmable calculators

[Thomas Klemm]

(12-22-2013 09:48 PM)Katie Wasserman Wrote:  

Quote:I was using the symmetry of abc(a+b+c) to bail out early for values ≥ 1000. We can do that since a ≤ b ≤ c.

Okay, I see the symmetry that you're using and the partial ordering. But I don't see why you don't need to test for the reverse digit ordering. For example, in 2 4 7 you test if 728 matches 247, but you don't test if 728 matches 742. In looking at the Python code, I don't see that test in there.

Am I still not understanding your speedup method or is there a bug in the code?

A lot of the possibilities can be excluded not because they don't match the criteria but simply because the value is too big. We use the fact that the function \(f(a, b, c) = abc(a+b+c)\) is both symmetric and monotonous. Thus instead of 729 cases we only have to check the 86 cases I've listed.

What's missing (and you may call that cheating or a bug) is that in case of 2 4 7 the value 728 should be ordered to 278 before comparing it to 247. If these two match then 728 would be a solution.
Another possibility is to split 728 into 7 2 8 and check whether (7+2+8)*7*2*8 = 1904 is the same as 728.

Since that operation is expensive we could perform it only when the difference 728 - 247 = 481 is 0 modulo 9. This reduces the set to only 15 cases:
1 1 1 : 3
1 1 4 : 24
1 1 7 : 63
1 2 5 : 80
1 2 6 : 108
1 3 5 : 135
1 4 4 : 144
1 4 7 : 336
1 7 7 : 735
2 2 5 : 180
2 2 7 : 308
2 3 4 : 216
2 4 8 : 896
3 3 3 : 243
4 4 4 : 768

In this list we can easily spot the solutions. Thus the last step may be omitted.

Cheers
Thomas