I don't think it would make a large difference in runtime, but the bounds aren't quite right.
The largest possible value isn't 999,999,999, because that's not a legal value. The largest value is 987,654,321
Dividing that by 9, you get 109,739,369, but that's not a legal value either, you'd want to start with 109,738,365 for the gcd as it's a valid possible row. I don't know that all gcds would need to be a valid row, but any gcd larger than 98,765,432 would need to be used at multiples from 1-9; with that gcd or smaller, multiple 10 becomes viable and the gcd doesn't need to be valid with multiple of 1.
One more nitpick on the upper bound of the GCD: since we know that 0 is going to be in every column, one of the row numbers must start with a 0 and will be an 8-digit number (0 in the first cell). The GCD can't be larger than the smallest row number.
The GCD search should start at 098,765,432 and then go down from there.
That version counts, the 1 bit's but here we already know the number is not 0 and we want to know that the inverted number it has exactly 1 bit set, so instead of
popcnt(n) == 1
we can use
n & (n-1) == 0
Moreover, n is the inverted number
n = 0b1111111111 - s
so an alternative is to run the check in the original number, and I think that this does the trick:
For us slow kids in the back what does this mean, “[…] such that the nine 9-digit numbers formed by the rows of the grid has the highest-possible GCD over any such grid”?
All the digits in a row become a number. All nine such numbers have a greatest common denominator. The puzzle solution is the center row of the grid where the numbers have the greatest common denominator possible. I. E. None of them are prime.
It took 3 readings and a scan of some of the later words but I think this is the correct reading
So a naive program can just solve the puzzle repeatedly, differently, and ccmpute the GCD of the rows, and output the one with the highest result. There aren't infinitely many solutions to a sodoku style puzzle, so...?
I also wrote my solution in Rust. I was pleased that my approach gave me an opportunity to write a linked list and get the chance to apply some rarely used learning[0].
My solution doesn't use SIMD, but is actually takes about the same amount of time as the the solution in the article, given the same number of cores, though an glaring weakness of my approach is that it can only scale up to 7 cores as written.
Rough outline of how mine works:
- Set current best GCD to 1.
- Search through all valid board configurations.
- Bail out from the search early if the current partially generated board couldn't have a GCD greater than the current maximum found, e.g. if we've only generated two rows of the board, and the GCD of those two rows are already less than the max.
- Update the current best GCD as you find higher ones.
- Share the current best GCD value across multiple threads. That way the longer the program runs, the earlier and earlier the searches will start bailing out.
- Don't always read from the shared variable to avoid contention. Instead, each thread has its own copy of the last value it read which we compare with first before copying and caching the shared value.
- Another interesting property of this approach is that it can be used to validate the correct solution even faster than it takes to find it. Instead of initially setting the max GCD to 1, set it to `solution - 1`. That way branches in our search will bail even sooner from the beginning. This leads to the program running about 20% more quickly.
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.
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.
> My first attempt when solving this puzzle was to encode the constraints as an SMT optimization problem, and using Z3 to find the solution.
This is why choosing the right tool for the job matters. Z3 is hilariously overkill for such a problem (not to undermine how interesting and useful Z3 is, and not to accuse the author of doing anything wrong).
Z3 is only one class of solver; a finite domain constraint solver is much more suited to these sorts of tasks.
The article is not super clear, but the problem in the article has an additional requests, to maximize the GCD of the rows interpreted as "9" digits numbers, in your case:
GCD(127685439, 594137826, 836429571, ...) = 9
but the author finds one GCD with 8 digits.
Also, for this reason it's important in this version to keep the "0" as "0" instead of mapping it to "1".
Readit News
The largest possible value isn't 999,999,999, because that's not a legal value. The largest value is 987,654,321
Dividing that by 9, you get 109,739,369, but that's not a legal value either, you'd want to start with 109,738,365 for the gcd as it's a valid possible row. I don't know that all gcds would need to be a valid row, but any gcd larger than 98,765,432 would need to be used at multiples from 1-9; with that gcd or smaller, multiple 10 becomes viable and the gcd doesn't need to be valid with multiple of 1.
The GCD search should start at 098,765,432 and then go down from there.
Nitpick: that has two threes.
Also, what’s wrong with 109,738,654 from that argument’s view?
I remembered there was a trick to avoid popcount, but I didn't remember it. So I found https://stackoverflow.com/questions/51387998/count-bits-1-on...
That version counts, the 1 bit's but here we already know the number is not 0 and we want to know that the inverted number it has exactly 1 bit set, so instead of
we can use Moreover, n is the inverted number so an alternative is to run the check in the original number, and I think that this does the trick:Deleted Comment
It took 3 readings and a scan of some of the later words but I think this is the correct reading
So a naive program can just solve the puzzle repeatedly, differently, and ccmpute the GCD of the rows, and output the one with the highest result. There aren't infinitely many solutions to a sodoku style puzzle, so...?
Deleted Comment
My solution doesn't use SIMD, but is actually takes about the same amount of time as the the solution in the article, given the same number of cores, though an glaring weakness of my approach is that it can only scale up to 7 cores as written.
Rough outline of how mine works:
- Set current best GCD to 1.
- Search through all valid board configurations.
- Bail out from the search early if the current partially generated board couldn't have a GCD greater than the current maximum found, e.g. if we've only generated two rows of the board, and the GCD of those two rows are already less than the max.
- Update the current best GCD as you find higher ones.
- Share the current best GCD value across multiple threads. That way the longer the program runs, the earlier and earlier the searches will start bailing out.
- Don't always read from the shared variable to avoid contention. Instead, each thread has its own copy of the last value it read which we compare with first before copying and caching the shared value.
- Another interesting property of this approach is that it can be used to validate the correct solution even faster than it takes to find it. Instead of initially setting the max GCD to 1, set it to `solution - 1`. That way branches in our search will bail even sooner from the beginning. This leads to the program running about 20% more quickly.
Source: https://gist.github.com/lazytype/35b45f3ea81b5c1c5555546fe6f...
[0] https://rust-unofficial.github.io/too-many-lists/
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.
This is why choosing the right tool for the job matters. Z3 is hilariously overkill for such a problem (not to undermine how interesting and useful Z3 is, and not to accuse the author of doing anything wrong).
Z3 is only one class of solver; a finite domain constraint solver is much more suited to these sorts of tasks.
https://gist.github.com/Qix-/3580f268e2725848971703e74f6b26b...
GCD(127685439, 594137826, 836429571, ...) = 9
but the author finds one GCD with 8 digits.
Also, for this reason it's important in this version to keep the "0" as "0" instead of mapping it to "1".