Problem 156 (Luhn algorithm) - Checker not catching an reconstruction ambiguity
Back to General discussions forum
Well, together with the other thread, I've spend more time on this problem than on the last ten combined! :)
Anyway, I've found a discrepancy in the solution checker, more precisely the part checking the reconstructed numbers:
If you have a number of the form '19?9', even with the missing digit, the Luhn checksum is correct: 9 + (?)*2 + 9 + 2*1 = 20, which is divisible by 10.
Now there is an ambiguity: Both 0 and 5 are allowed missing digits, since they contribute either 0 or 10 to the checksum because of the factor of 2 (caused by the position).
My algorithm replaced the missing digit in these occurrences with a 5, but the checker really, really wants to see a 0 there. A simple if-statement makes my code checker-compliant, but I feel both cases should be allowed here.
Hm... yes, I think I've missed this when creating the problem, thanks :)
The checker for it was created when our site only allowed to check whether result is equal to expected or not. This problem seemingly requires more intellectual check. We have necessary features long ago, but I should just pull my brains into single heap and rewrite the checker.
People already have found several issues with this problem - and you another one. I think it's time - thanks :)
I'll try to take care of it in a few days, hopefully.
52=10 - it's more then 9 according to Lunh's algorithm if digit>9 then 9 substract of porduct 5 and 2 --> 52=10-9=1 checksum: 9+12+9+12=22 5 cannot be a missing number
Hi grey,
you are of course right, I really did not see that I made an error there. So the ambiguity I described above is not existent.
What caused the error on my part was that I tried really hard to make the reconstruction with as few checks for (10 - checksum_without_'?') as possible, but it seems you really need three: One if the difference is 0, one if it is odd and one if it is even, but not zero.
If you want to force the case of 0 into the even one, you can see that there is an elegance to (10 - checksum) / 2... Too bad it is plain wrong ;-)
Sorry for the confusion.