From hours to 360ms: over-engineering a puzzle solution

Re:From hours to 360ms: over-engineering a puzzle solution by amyres on Saturday February 08, 2025 @10:39PM (#42988254)

Since we're over-engineering here, one more optimization is to skip all potential GCDs that are divisible by 2 or 5.

Suppose the GCD was divisible by 2, then all rows would be even. Since the last digit of an even integer is in {0,2,4,6,8} and we need 9 unique numbers in the final column, we know that 4 or 5 of the row numbers must be odd. So the GCD can't be even.

Similarly, the GCD can't be divisible by 5. If it were, all rows numbers would need a 0 or 5 in the final digit.

[ Parent | on HN ]

Re:From hours to 360ms: over-engineering a puzzle solution by lern_too_spel on Sunday February 09, 2025 @12:51AM (#42988777)

We know that the GCD is divisible by 9 because the sum of the digits for every row is 45.

[ Parent | on HN ]

Re:From hours to 360ms: over-engineering a puzzle solution by Jtsummers on Sunday February 09, 2025 @01:36AM (#42988928)

Not necessarily. The sum of the digits ranges from 36-45, there are 10 possible digits of which 9 will be used. If, say, 5 were the unused number then it would not be divisible by 9.

[ Parent | on HN ]

Re:From hours to 360ms: over-engineering a puzzle solution by amyres on Sunday February 09, 2025 @11:13AM (#42991531)

Exactly. The actual solution to the puzzle in question has a GCD not divisible by 9.

[ Parent | on HN ]

Re:From hours to 360ms: over-engineering a puzzle solution by lern_too_spel on Sunday February 09, 2025 @11:28AM (#42991644)

You're right. I misread the question. It's 9 of the 10 digits 0-9 instead of all 9 digits 1-9 as in sudoku.

[ Parent | on HN ]