Population puzzle
Kay C Lan
lan.kc.macmail at gmail.com
Mon Aug 25 02:38:36 EDT 2014
OK, well I think I can do a little better than that. I can
consistently get an answer in a sec, which I guess you could beat if
you happen to be lucky with your first selection of random cities. I
do also appreciate that Terry's code is slowed a little by counting
the iterations which mine doesn't.
I approached the problem from the opposite end. Find out which cities
add up to 29,161,818 which is the difference between the total
population of the 26 cities - 100,000,000. I figured that it would
have to involve a much smaller number of cities and therefore need
fewer iterations.
I imagine Terry & Scott, your approach would on average be faster if
you followed the same logic.
Copy and paste the following in a button script:
WATCH FOR LINE WRAPS
local lPop,lStart
on mouseUp
put the millisec into lStart
put "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, 2134411" into lPop
put sum(lPop) - 100000000 into tError
repeat for each item tA in lPop
put itemOffset(tA,lPop) + 1 into tOffset
put item tOffset to -1 of lPop into tPopB
hMoreCities tA,tPopB,tError
end repeat
end mouseUp
on hMoreCities pA,pPopC,pError
--breakpoint
repeat for each item tC in pPopC
switch
case (sum(pA) + tC < pError)
if ( the number of items of pPopC > 1) then
put itemOffset(tC,pPopC) + 1 into tOffset
put item tOffset to -1 of pPopC into tPopD
hMoreCities pA & "," & tC,tPopD,pError
else
next repeat
end if
break
case (sum(pA) + tC > pError)
next repeat
break
case (sum(pA) + tC = pError)
--we have an answer
hAnswer pA & "," & tC
break
end switch
end repeat
end hMoreCities
on hAnswer tExclude
-- we have the wrong cities so we need to remove these from the
-- list of all cities
repeat for each item tA in tExclude
replace tA with "" in lPop
end repeat
--just to cross check
if (sum(lPop) = 100000000) then
put lPop into msg
else
put "I Failed" into msg
end if
put the millisec into tEnd
put cr & "Total time " & tEnd - lStart & " ms." after msg
exit to top
end hAnswer
More information about the use-livecode
mailing list