OK - I¹ll take the bait although elegant algorithms definitely aren¹t my
forte. As a result this is probably a very half-baked and inefficient
solution to the problem but it seems to work and doesn¹t have to resort to
recursion (which I can never get my head around) to generate the starting
combinations. Instead I just repeatedly randomise the order of the items
and sum them in that order until I get the required value.
Anyway, here goes (watch out for wrapped lines)
Terry...
on runIt
put the seconds into tTimer
put 100000000 into theTotal
put
"18897109,12828837,9461105,6371773,5965343,5946800,5582170,5564635,5268860,
4552402,4335391,4296250,4224851,4192887,3439809,3279833,3095313,2812896,278
3243,2710489,2543482,2356285,2226009,2149127,2142508,2134411" into
tCityPops
put empty into tKeys
put 0 into tN
repeat for each item tPop in tCityPops
add 1 to tN
put tPop into tPops[tN]
put tN & comma after tKeys
end repeat
delete last char of tKeys
put 0 into nIterations
repeat forever
add 1 to nIterations
# randomise the order of the keys
put randomiseItems(tKeys) into tX
put 0 into tTotal
repeat for each item tKey in tX
add tPops[tKey] to tTotal
if tTotal = theTotal then
# we have a winner
put itemOffset(tKey,tX) into nItem
put item 1 to nItem of tX into tY
sort items of tY ascending numeric
answer ("Items = "&tY &cr& "nIterations = "&nIterations &cr&
"Elapsed time = "&(the seconds - tTimer)&" secs")
exit to top
else
if tTotal > theTotal then
exit repeat
end if
end if
end repeat
end repeat
end runIt
function randomiseItems theItems
put empty into tItems
repeat forever
put the number of items in theItems into nItems
if nItems = 0 then exit repeat
put random(nItems) into nItem
put item nItem of theItems & comma after tItems
delete item nItem of theItems
end repeat
delete last char of tItems
return tItems
end randomiseItems
On 25/08/2014 9:52 am, "Michael Doub" <miked...@gmail.com> wrote:
>I know that some of the folks on this list enjoy puzzles. A friend sent
>me this one this afternoon and I thought it would be interesting to see
>the different approaches folks come up with and how fast it can be
>solved. enjoyŠ
>
>The 2010 Census puts populations of 26 largest US metro areas at
>18897109, 12828837, 9461105, 6371773, 5965343,5946800, 5582170, 5564635,
>5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279833,
>3095313,2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127,
>2142508, and 2134411.
>
>Can you find a subset of these areas where a total of exactly 100,000,000
>people live, assuming the census estimates are exactly right?
>_______________________________________________
>use-livecode mailing list
>use-livecode@lists.runrev.com
>Please visit this url to subscribe, unsubscribe and manage your
>subscription preferences:
>http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
