Population puzzle

[Terry Judd]

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" <mikedoub at 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 at lists.runrev.com
>Please visit this url to subscribe, unsubscribe and manage your
>subscription preferences:
>http://lists.runrev.com/mailman/listinfo/use-livecode