how many different methods can we find for this question

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

how many different methods can we find for this question

fareastern23
Instead of just finding the answer..I wan tot see how many different ways this question can be answered. I have got one using Python. Please submit any other methods. I've seen a couple other methods but want to see what can be done! Thanks I hope you try and have fun. This is not used for a test and I will not take credit for your work and math abilities.


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? Provide the answer and code or reasoning used.
Reply | Threaded
Open this post in threaded view
|

Re: how many different methods can we find for this question

dunbarxx
Hi.

Well, one way, though it is as brute force as you can get, is to assemble (perhaps with the "combinatorial" handler in the "masterLibrary"), all the combos of all the values into a single list. Then just get the sum of each of those lines and see if it equals 100,000,000.

This may take a while on even the fastest desktop machines.

Craig Newman
Reply | Threaded
Open this post in threaded view
|

Re: how many different methods can we find for this question

dunbarxx
In reply to this post by fareastern23
I heard long ago that a little analysis is worth a million lines of code.

If you take the sum of all but the top two values (out of 26), that sum does not reach 100M. So it might be much faster, knowing that one or more of, say, the top four values are required in the final, to run the combinatorial on only the remaining lower (22!!!) values, and then run a short routine to check all those sums with the handful of larger ones. There are a lot of combinations; anything cleverer that can reduce that load is a real time saver.

Craig
Reply | Threaded
Open this post in threaded view
|

Re: how many different methods can we find for this question

dunbarxx
Houston, we have an issue with LC.

I used the "combinatorial" function in the "MasterLibrary" for 26 elements, but the process was too slow. I made a kluge, so that a shorter call to that function was then processed by an even more brute-force routine. It works fine, but it also does not work.

LC stalls if the number of elements is greater than 23. I assume this is some sort of memory issue, unless LC just gets bored with the whole thing.

The following handlers pull an arbitrary value to test, and the gadget does indeed find the appropriate components.

on mouseUp
   --FIELD 1 HAS THE LIST OF POPULATIONS
   --1,9,18 ARE AN ARBITRARY TARGET SUM
   -- THIS IS A SHORTER TEST FOR 18 LINES TO PROVE CONCEPT, AND FINISH IN A SHORT TIME

   get line 1 of fld 1 & "," & line 9 of fld 1 & "," & line 18 of fld 1
   put sum(it) into magicNumber --26978865
   
   put fld 1 into tList
   put combinatorial(12) into accum
   repeat with y = 13 to 18 --FAILS WITH A VALUE OF 26, THE ACTUAL NUMBER OF LINES IN THE LIST
      put accum into tempAccum
      repeat for each line tLine in tempAccum
         put tLine & comma & y & return after finalAccum
      end repeat
      put accum & return & finalAccum into accum
      put y after accum
      put y into fld 3
      put "" into finalAccum
   end repeat
   
   repeat for each line tLine in accum
      repeat for each item tItem in tLine
         put line tItem of tList & "," after temp
      end repeat
      if sum(temp) = magicNumber then
         answer tLine
         exit to top
      else
         put "" into temp
      end if
   end repeat
end mouseUp

function combinatorial n
   put the cursor into tCursor
   put 1 into tCursorCtr
   if n >= 15 then -- make sure you know what you're in for!
      answer n && "objects will result in" && (2^15 -1) && "subsets" with "Continue" or "Cancel"
      if it is "Cancel" then exit to top
   end if
   put 1 into subsetsVar -- initialize variable
   repeat until x = n -- this repeats (2^n - 2) times, which is one less than the numer of possible subsets
      Add 1 to tCursorCtr
      if tCursorCtr > 5000 then
         set the cursor to busy
         put 0 into tCursorCtr
      end if
      put the last line in subsetsVar into x -- each subset is used as input to compute the next subset
      put the number of items in x into noItems
      if item noItems of x = n then
         add 1 to item (noItems -1) of x -- increment 2nd to last item if last item = n
         delete the last item of x -- get rid of last item if it = n
         put return & x after subsetsVar -- add another subset to list of subsets
      else
         put ((item noItems of x) + 1) into item (noItems + 1) of x -- increment last item
         put return & x after subsetsVar -- add another subset to list of subsets
      end if
   end repeat
   set the cursor to tCursor
   return subsetsVar -- return the list of all possible subsets
end combinatorial

-- Population LIST:

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

Craig Newman
Reply | Threaded
Open this post in threaded view
|

Re: how many different methods can we find for this question

dunbarxx
In reply to this post by fareastern23
I think there is no combination that equals 100,000,000.

I could be wrong.

Craig