Population puzzle
Mick Collins
mickclns at mac.com
Thu Sep 25 15:15:24 EDT 2014
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 <mikedoub at gmail.com>
> To: How To use LiveCode use LiveCode <use-livecode at lists.runrev.com>
> Subject: Population puzzle
> Message-ID: <23AF2370-8161-458A-91C6-22153C15F895 at 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
More information about the use-livecode
mailing list