This problem is not about a Golomb ruler. When dealing with Golomb rulers you care about uniqueness of lengths across all pairs, while in this problem you do not.
If you had 4 oranges and 5 bowls, you could place them as follows:
1 1 0 1 1
This arrangement is not a Golomb ruler because the lengths 1 and 3 both occur more than once, but it is a valid solution to a smaller version of the problem in the OP.
Got 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.
$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
15 comments
[ 5.4 ms ] story [ 50.7 ms ] threadI would just feed this to a counting SAT, or constraint, solver.
If I wrote the constraint solver, does that count as an acceptable answer?
There are some fancy ways of doing this, involving lots of bitshifting, which are quite fun.
Edit: Remove mis-remembered bitshifting.
If you had 4 oranges and 5 bowls, you could place them as follows:
1 1 0 1 1
This arrangement is not a Golomb ruler because the lengths 1 and 3 both occur more than once, but it is a valid solution to a smaller version of the problem in the OP.
Is there any smarter way to do it (in software) without brute forcing?
To the best of my knowledge all of the smarter ways to do it are just smarter ways to brute force it.
EDIT: Found 7555794 solutions, took my 2GHz P4 30 minutes.
Run on 2.4Ghz Core 2 Duo:
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