Population puzzle

[Kay C Lan]

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