An interesting programming challenge

[Geoff Canyon]

On Thu, Apr 9, 2015 at 9:35 PM, <dunbarx at aol.com> wrote:

> 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.
>

This is stream-of-conscious code, but it produces the solution in under a
second. Spoiler returns:


















There are 2^26 possible sets, or about 64 million. On the assumption that's
too many to brute force, I do the following:

1. break the list of 26 into two sets of 13, the largest in one set, the
smallest in the other.
2. for each set, I calculate all the sums. 2^13 is 8192, which is much more
manageable.
3. I calculated the sums of the 13 largest and 13 smallest cities.
Subtracting those from 100,000,000 gave me the minimum required
contribution for the *other* set. So the big cities must sum to at least
64,133,708 (or else all the small cities won't be enough to hit the goal)
which eliminates about 85% of the possibilities from the big set; and the
small cities must sum to at least 6,704,474 which eliminates only about 100
of those possibilities.
4. I sort each set descending.
5. Then I parse through the large city sets, and in an inner loop parse
through the small city sets, checking for winners. If the sum is ever less
than 100,000,000 I exit the inner loop, because none of the small city sets
left will do the trick.


on mouseUp
   put line 1 to 13 of fld 1 into P
   split P using cr
   repeat with i = 1 to 8191
      put baseconvert(i,10,2) into B
      put char 1 to 13 - length(B) of "000000000000" before B
      repeat with j = 1 to 13
         if char j of B is 0 then next repeat
         add P[j] to S[i]
         put P[j],"" after L[i]
      end repeat
   end repeat
   repeat with i = 1 to 8191
      if S[i] > 64133708 then next repeat
      delete variable S[i]
      delete variable L[i]
   end repeat
   repeat for each key K in S
      put K into X[S[K]]
   end repeat
   put the keys of X into kList
   sort lines of kList numeric descending
   put 0 into i
   repeat for each line K in kList
      add 1 to i
      put K into FS1[i]
      put L[X[K]] into FL1[i]
   end repeat

   delete variable S
   delete variable L
   put line 14 to 26 of fld 1 into P
   split P using cr
   repeat with i = 1 to 8191
      put baseconvert(i,10,2) into B
      put char 1 to 13 - length(B) of "000000000000" before B
      repeat with j = 1 to 13
         if char j of B is 0 then next repeat
         add P[j] to S[i]
         put P[j],"" after L[i]
      end repeat
   end repeat
   repeat with i = 1 to 8191
      if S[i] > 6704474 then next repeat
      delete variable S[i]
      delete variable L[i]
   end repeat
   delete variable X
   repeat for each key K in S
      put K into X[S[K]]
   end repeat
   put the keys of X into kList
   sort lines of kList numeric descending
   put 0 into i
   repeat for each line K in kList
      add 1 to i
      put K into FS2[i]
      put L[X[K]] into FL2[i]
   end repeat
   put the keys of FL1 into K1list
   sort lines of K1list numeric
   put the keys of FL2 into K2list
   sort lines of K2list numeric
   repeat for each line K1 in K1list
      repeat for each line K2 in K2list
         if FS1[K1] + FS2[K2] = 100000000 then \
               put "winner" && FL1[K1] & FL2[K2] & cr after fld 2
         if FS1[K1] + FS2[K2] < 100000000 then exit repeat
      end repeat
   end repeat
end mouseUp