Recently, I learned (via HN) that prime numbers are the magical building blocks of numbers.
By using that fact (without understanding it), I was able to beat the author's scores slightly by only including prime coins in the list of candidates.
Oh, after some thought, I think I understand my intuition: prime coins are good choices for the same reason prime numbers are good choices when you are resizing images or changing the sample rate on audio. What do you call that, when you avoid Moiré patterns (or something like that) by using primes?
The score calculation is incorrect, due to rounding in the calculations. For example (assuming 53-bit precision as usual), Floor(0.29 / 0.01) is not 29 as one would hope. This is because those values (0.29, 0.01) are not exactly representable. Instead, the corresponding representable values are 0.289999999999999980015985556747182272374629974365234375 and 0.01000000000000000020816681711721685132943093776702880859375. The result of the division is thus less than 29, and is floored to 28.
When run, the script currently produces these values:
2 coins is: [0.13,0.01] with a score of 886 -- should be 934
3 coins is: [0.25,0.06,0.01] with a score of 526 -- should be 542
4 coins is: [0.4,0.13,0.03,0.01] with a score of 400 -- should be 422
5 coins is: [0.45,0.2,0.08,0.03,0.01] with a score of 329 -- should be 345
6 coins is: [0.7,0.45,0.2,0.08,0.03,0.01] with a score of 305 -- should be 320
To avoid this issue, use integers instead (which you can think of as working in cents) -- adjust each value in candidates and amounts to be the corresponding integer (and the 0.01 in the denom function to be 1) and correct scores will be calculated.
Incidentally, the optimal scores for the first few sets are:
2 coins is 910 from [1, 10] or [1, 11]
3 coins is 521 from [1, 12, 19]
4 coins is 393 from [1, 5, 18, 25]
5 coins is 333 from [1, 5, 16, 23, 33]
6 coins is 296 from [1, 4, 6, 21, 30, 37] or [1, 4, 9, 24, 31, 45] or [1, 5, 8, 20, 31, 33]
7 coins is 269 from [1, 4, 9, 11, 26, 38, 44]
(Computed with a quick-and-dirty C backtracking search.)
4 comments
[ 3.0 ms ] story [ 20.4 ms ] threadBy using that fact (without understanding it), I was able to beat the author's scores slightly by only including prime coins in the list of candidates.
http://jsfiddle.net/JY648/
Oh, the author still wins on the 4- and 5-coin variations.
When I try to include more than X candidates, it crashes. Help?
When run, the script currently produces these values:
2 coins is: [0.13,0.01] with a score of 886 -- should be 934
3 coins is: [0.25,0.06,0.01] with a score of 526 -- should be 542
4 coins is: [0.4,0.13,0.03,0.01] with a score of 400 -- should be 422
5 coins is: [0.45,0.2,0.08,0.03,0.01] with a score of 329 -- should be 345
6 coins is: [0.7,0.45,0.2,0.08,0.03,0.01] with a score of 305 -- should be 320
To avoid this issue, use integers instead (which you can think of as working in cents) -- adjust each value in candidates and amounts to be the corresponding integer (and the 0.01 in the denom function to be 1) and correct scores will be calculated.
Incidentally, the optimal scores for the first few sets are:
2 coins is 910 from [1, 10] or [1, 11]
3 coins is 521 from [1, 12, 19]
4 coins is 393 from [1, 5, 18, 25]
5 coins is 333 from [1, 5, 16, 23, 33]
6 coins is 296 from [1, 4, 6, 21, 30, 37] or [1, 4, 9, 24, 31, 45] or [1, 5, 8, 20, 31, 33]
7 coins is 269 from [1, 4, 9, 11, 26, 38, 44]
(Computed with a quick-and-dirty C backtracking search.)