I’ve been working on this one for a few minutes, a few there and finally got it, a month later. Great puzzle, Michael, thanks!
> From: Michael Doub <miked...@gmail.com> > To: How To use LiveCode use LiveCode <use-livecode@lists.runrev.com> > Subject: Population puzzle > Message-ID: <23af2370-8161-458a-91c6-22153c15f...@gmail.com> > Content-Type: text/plain; charset=windows-1252 > > 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? > le live, assuming the census estimates are exactly >> right? > > This was in the mongodb certification, if I remember correctly, and > the python code was fun to write. > I worked on this using a reduced set of smaller numbers You can see them in the code. This finds ALL sets of numbers adding to the goal With the small group, there were 6 groups of numbers adding to 100 (instantaneous) 1 29 70 1 4 8 19 68 13 19 68 1 8 19 21 22 29 1 8 21 70 8 22 70 I wasn’t sure this was working for the original sum (100 M) so I tried a number around 30M that I had constructed from some of the given numbers. In about 3 or 4 seconds it came up with: 02149127 02543482 03279833 04296250 05582170 12828837 That gave me more confidence so I went back to 100M and after about 10 minutes it gave me 02134411 02142508 02226009 02543482 02812896 03095313 03279833 04224851 04296250 04335391 04552402 05268860 05582170 05946800 06371773 09461105 12828837 18897109 The reason it took relatively so long was that any sums larger than the goal are thrown away before combining them and with the larger goal few of those were tossed so there were many more to work with. So, here’s the code: global goalSum, GSmod1, GSmod2 -- the mods in above and below lines are used -- to cut down on computation, the sum of the -- mods for lower and upper part are added. -- if not equal to mods of goalSum, then -- that combo is not used constant modulus1=31, modulus2=7 on doTest put 100000000 into goalSum put 30679699 into goalSum put \ "18897109, 12828837, 09461105, 06371773, 05965343, 05946800, 05582170, 05564635, " & \ "05268860, 04552402, 04335391, 04296250, 04224851, 04192887, 03439809, 03279833, " & \ "03095313, 02812896, 02783243, 02710489, 02543482, 02356285, 02226009, 02149127, " & \ "02142508, 02134411" into theNums -- put 100 into goalSum put goalSum mod modulus1 into GSmod1 put goalSum mod modulus2 into GSmod2 -- put "1,4,8,13,19,21,22, 29, 68, 70" into theNums replace " " with empty in theNums -- so the sort will work sort items of theNums ascending numeric put the number of items in theNums into nNums -- put sumsOfAllIndex(theNums,nNums,0,5) into bottomGroup put sumsOfAllIndex(theNums,nNums,0,10) into bottomGroup sort lines of sumAllTo5 numeric by (10 * (word 3 of each) + word 4 of each) -- put sumsOfAllIndex(theNums,nNums,5,10) into topGroup put sumsOfAllIndex(theNums,nNums,10,26) into topGroup sort lines of topGroup numeric by (10 * (word 3 of each) + word 4 of each) put 0 into lineNum put empty into goodSums repeat for each line L1 in topGroup put word 3 of L1 into mod1_1 put word 4 of L1 into mod1_2 if GSmod1 >= mod1_1 then put GSmod1 - mod1_1 into mod1LookFor else put GSmod1+modulus1 - mod1_1 into mod1LookFor end if if GSmod2 >= mod1_2 then put GSmod2 - mod1_2 into mod2LookFor else put GSmod2+modulus2 - mod1_2 into mod2LookFor end if repeat for each line L2 in bottomGroup if word 3 of L2 = mod1Lookfor then if word 4 of L2 = mod2Lookfor then put word 2 of L1 into w1 put word 2 of L2 into w2 if w1 + w2 = GoalSum then add 1 to lineNum put word 5 of L1 && word 5 of L2 into line lineNum of goodSums end if end if end if end repeat end repeat put unpack(goodSums, theNums, nNums) into goodSums2 replace "," with space in goodSums2 put goodSums2 & cr & cr & cr & cr & cr before fld "Content" end doTest function sumsOfAllIndex theNums,nNums,nL,nH -- nL and nH are the exponents of the Low and High -- repeat limits -- -- for a given number (which is a sum), each of the -- 26 given numbers used in the sum -- is represented by a bit in a binary number -- called i2 (i base 2) a few lines below put empty into theSums put 0 into lineNum put 2^nL into twoTonL put 1024 * twoTonL into Ltimes1024 put 2^nH into twoTonH repeat with i = twoTonL to twoTonH step twoTonL put baseConvert(i,10,2) into i2 put sumConstruct(theNums,nNums, i2) into thisSum if thisSum <= goalSum then add 1 to lineNum put i && thisSum && (thisSum mod modulus1) && (thisSum mod modulus2) && i2 into thisLine put thisLine into line lineNum of theSums end if end repeat return theSums end sumsOfAllIndex function sumConstruct theNums,nNums, i2 -- constructs the sum of the numbers represented -- by the string of bits, i2 put len(i2) +1 into leni2p1 put 0 into theSum repeat with i = 1 to len(i2) if char leni2p1-i of i2 = 1 then add item i of theNums to theSum end if end repeat return theSum end sumConstruct function unpack goodSums, theNums, nNums -- turns a list of lines, each with two bit strings into list -- of lines, each with numbers summing to the goal sum put empty into toGoodSums repeat with i =1 to the number of lines in goodSums put unpackone(line i of goodSums, theNums, nNums) into line i of toGoodSums end repeat return toGoodSums end unpack function unpackone theLine,theNums,nNums -- unpacks a line of two (bit strings), one from the upper -- group and one from the lower, constructing a concatenation -- of numbers from the original list which will sum -- to the goal sum put empty into lineOfNums repeat with i12 = 1 to 2 put word i12 of theLine into wordBase2 put len(wordBase2) +1 into lenWB2p1 repeat with i = 1 to lenWB2p1 -1 if char lenWB2p1-i of wordBase2 = 1 then put (item i of theNums) & comma after lineOfNums end if end repeat end repeat delete last char of lineOfNums sort items of lineOfNums numeric ascending return lineOfNums end unpackone _______________________________________________ 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