4 ms·
I made a python program to check every possible combination. It should run for 1 more hour and then should spit "no solution found". Is there any smarter way t
by joss82 15y ago
I made a python program to check every possible combination. It should run for 1 more hour and then should spit "no solution found".
Is there any smarter way to do it (in software) without brute forcing?
- anonymoushn 15y agoThe answer to this problem is not zero. To the best of my knowledge all of the smarter ways to do it are just smarter ways to brute force it.
- joss82 15y agoYou are right, I mistakenly thought that it was about a Golomb ruler, which it is not. EDIT: Found 7555794 solutions, took my 2GHz P4 30 minutes.
- fferen 15y agoGot the same answer with a slightly improved brute force search, in about 3 minutes. I spent more time than that trying to find a "clever" way to do it, lol.
- eLod 15y agobarnabas:btch pota$ time python btch.py found: 7555794 real 1m18.464s user 1m18.417s sys 0m0.031s (i5 2500k)
- joss82 15y agoNice! Would you show us the source?
- anonymoushn 15y agoIt might be similar to mine: http://pastie.org/2007710 http://pastie.org/2007710 Run on 2.4Ghz Core 2 Duo: $time python oranges.py 7555794 real 1m24.252s user 1m23.841s sys 0m0.144s You can still get this to be much faster if you stuff this information into bitmasks, especially if you do it in one of the other languages. You can also get a lot of speedup out of more clever pruning if you're willing to precompute a bunch of stuff. Edit: It seems like a lot of the function calls this program makes are unnecessary. This version runs about 37 seconds faster without any of the trickery I mentioned: http://pastie.org/2007699 http://pastie.org/2007699