Announcement

Collapse
No announcement yet.

Programming Problem

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Ronald Fuerst
    replied
    Lottery Distribution

    Hello Neil,
    The real name of the probability distribution that you described is
    the hypergeometric probability distribution. It is very much like the
    binomial distribution except that it is sensitive to the no replacement condition. { If the population is large then replacement has little effect and the "lottery distribution" converges to the binomial distibution"
    It is a problem involving combinations. I have included the code for both the combinations function and the hypergeopmf function.

    I hope this helps.

    Best regards

    Ron


    FUNCTION combinations( BYVAL n AS INTEGER , r AS INTEGER ) AS_ DOUBLE
    REM there are 'n' items that are taken 'r' at a time.
    DIM combo AS DOUBLE , k AS INTEGER
    combo = 1.0#
    IF r <= n AND r > 0 THEN
    FOR k = 1 TO r
    combo = (n-k +1)/k*combo
    NEXT k
    END IF

    combinations = combo
    END FUNCTION

    FUNCTION HYPERGEOPMF BDECL ALIAS "hypergeopmf" (BYVAL samp_sz AS INTEGER, _
    BYVAL nrsucess AS INTEGER, _
    BYVAL nrfail AS INTEGER, _
    BYVAL k AS INTEGER) AS DOUBLE

    REM samp_sz is the number in the sample ie. 6 in your case
    REM nrsucess is the number of successes in the total population ie. 6 in
    REM nrfail is the number of failures 49 - 6 , in your case
    REM k is the number of matches that you get with successes , ie 2

    FUNCTION = combinations(nrsucess, k) * _
    combinations(nrfail, samp_sz - k)/ _
    combinations( nrsucess+nrfail, samp_sz)
    END FUNCTION

    Leave a comment:


  • Paul Dixon
    replied
    Neil,
    if you like solving puzzles just as a mental work out and to enhance your programming then look here: http://projecteuler.net/

    Paul.

    Leave a comment:


  • Neil Croft
    replied
    Tom,

    I wish I could understand half the paper you posted a link to but I understand enough of it to go look for a new "problem". Still, not a total loss. I've used pointers and bit arrays for the first time. These puzzles should promote us to work outside of our confort zone somehow. Hopefully they make us better programmers.

    Leave a comment:


  • Rodney Hicks
    replied
    A set of 6 --1,2,3,4,5,6

    There are 6 choices for the first digit* 5 choices for the second digit=30 digits.
    Since we are using 2 at a time, we divide by 2 to get 15
    Each number will appear 5 times in the 15 sets of 2
    Code:
    1,2  1,3  1,4  1,5  1,6
         2,3  2,4  2,5  2,6
              3,4  3,5  3,6
                   4,5  4,6
                        5,6
    Therefore in 19 sets, there ar 19 *15= 285.
    If you look at the 19 sets from that first link in this thread you'll find there are duplicates.
    The 248 discreet pairs could be divided by 15 to show the absolute minimum number of 6 number sets required. (17)
    Those 17 sets of 6 would still leave you with 7 duplicates.

    Rod
    Last edited by Rodney Hicks; 1 Jun 2008, 02:29 AM. Reason: bad grammar, she was supposed to be in the kitchen.

    Leave a comment:


  • StanHelton
    replied
    Originally posted by Rodney Hicks View Post
    In each set of 6 there are 15 unique pairs so the last line above should read:
    18 sets x15 unique pairs=270 unique pairs

    In the original group of 19 sets of 6 there were 285 number pairs, with some duplication, however there are in that 19 sets of 6 248 discreet pairs which means that there are 37 duplicates. Those 37 duplicates are the key to reducing 19 to 18( or time willing 17) sets of 6.

    Rod
    I stand corrected.

    My math is not as strong as yours. How do you arrive at 285 number pairs in the 19 sets of 6?

    Stan

    Leave a comment:


  • Rodney Hicks
    replied
    18 sets of 6 -> maximum number of unique sets of six
    OR
    18 sets x 3 unique pairs per set = 54 unique pairs
    In each set of 6 there are 15 unique pairs so the last line above should read:
    18 sets x15 unique pairs=270 unique pairs

    In the original group of 19 sets of 6 there were 285 number pairs, with some duplication, however there are in that 19 sets of 6 248 discreet pairs which means that there are 37 duplicates. Those 37 duplicates are the key to reducing 19 to 18( or time willing 17) sets of 6.

    Rod

    Leave a comment:


  • StanHelton
    replied
    Originally posted by Neil Croft View Post
    ....
    Forget the lottery. Imagine 49 germs of which 6 are present in any person and you can only give them 18 antibiotics of which there are 13983816 different varieties and you want to kill at least 2 germs in every person and each antibiotic can kill 6 different germs. Whatever gets your programming juices flowing.

    The exercise is to find an algorithm that proves or disproves the solution can be calculated in less than a planet's lifetime, not win the lottery.
    Okay.


    My first attempt:

    Total # of infected persons = unlimited
    Total # of antibx that kill 6 germs = 13 million plus
    Total # of germs = 49
    Total # of germs in each infected person = 6
    Max # of vacinations = 18

    Goal: kill at least 2 germs in every infected person without exceeding the max # of vacinations

    49 Cr 6 = >13.98E+6
    49 Cr 2 = 1,176 unique pairs of germs

    18 sets of 6 -> maximum number of unique sets of six
    OR
    18 sets x 3 unique pairs per set = 54 unique pairs

    Conclusion: solution is not possible as it will miss 1,122 unique pairs of germs.


    My second attempt:

    given 49 germs
    given 13 million plus antibx that kill 6 germs

    solution:
    select 8 antibx with completely unique sets of 6 (48 germs killed)
    AND
    a 9th antibx that includes at least one instance of germ #49


    Code:
    DEFLNG a-z
    %False = 0
    %True = NOT %False
     
    
    FUNCTION KillThoseNastyGerms() AS LONG
    
    'initialize the germs
    DIM GermSet(48) AS LONG
    FOR x = 0 TO 48
       GermSet(x) = x
    NEXT x
    
    'randomize the antibx
    DIM AntibxSet(13983815, 5) AS LONG
    FOR x = 0 TO 13983815
       FOR y = 0 TO 5
          AntibxSet(x, y) = RND(0, 48)
       NEXT y
    NEXT x
    
    'solution set
    DIM VacinationSet(1 TO 9) AS GLOBAL LONG
    
    VacAntibx = 0
    GermsKilled = 0
    Success = %False
    
    FOR x = 0 TO 13983815   'checking each antibx in turn
       FOR y = 0 TO 5           'find unique antibx
          IF GermSet(AntibxSet(x, y)) >= 0 THEN INCR UniqueFlag
       NEXT y
    
       IF UniqueFlag = 6 _
       AND GermsKilled < 48 THEN              'add unique antibx to vacination list
          VacinationSet(AntibxIndexNo) = x
          INCR AntibxIndexNo
          FOR y = 0 TO 5
             GermSet(AntibxSet(x, y)) = -1
          NEXT y
          GermsKilled = GermsKilled + 6
       ELSEIF UniqueFlag > 0 _
       AND GermsKilled = 48 THEN               'select 9th antibx
          VacinationSet(AntibxIndexNo) = x
          GermsKilled = GermsKilled + 1
       END IF
       UniqueFlag = 0
    
       IF GermsKilled = 49 THEN
          'double check the solution
          FOR y = 0 TO 48
             IF GermSet(y) < 0 THEN
                GermsKilled = GermsKilled + GermSet(y)
             END IF
          NEXT y
          IF GermsKilled <> 0 THEN
             Success = %False
          ELSE
             Success = %True
             EXIT FOR
          END IF
       END IF
    NEXT x
    
    IF ISTRUE Success THEN
       'do whatever with the VacinationSet()
    ELSEIF ISFALSE Success THEN
       'research more antibx!
    END IF
    
    FUNCTION = Success
    END FUNCTION
    It won't win the lottery, but it might save the poor patient 9 injections... AND it kills all 6 germs in every patient.

    Stan
    Last edited by StanHelton; 31 May 2008, 08:51 PM. Reason: Clarify solution - add DEFLNG to make compilable

    Leave a comment:


  • Tom Ulrich
    replied
    http://www.cs.umanitoba.ca/~vanrees/Lotto.pdf

    Lemma 4.19 L(49,6,6,2)=19

    "Lotto Designs" by J.A. Bate & G.H.J. van Rees, J. Comb. Math. & Comb. Computing, V28 (1998) 15-39.

    Unless the professors at University of Manitoba and the reviewers blundered, 19 is the best one can get.

    Leave a comment:


  • Tom Ulrich
    replied
    Another approach:

    Think of it as a tree... Try to reduce the branches.

    1 to 49 pick 6 results in 49!/(6! 43!)=13,983,816 possible.

    In the 19 tickets there are tickets 1,8,15 and 19 with consecutive numbers.
    ticket 1:1,2,3,4,5,6
    ticket 8:15,16,17,18,19,20
    ticket 15:29,30,31,32,33,34
    ticket 19:44,45,46,47,48,49

    Take ticket 1: 1,2,3,4,5,6
    If I did my math correctly...(used hypergeometric formula)
    matches of 2 or more =2,111,733

    This now reduces the 13,983,816 possible to:
    13,983,816-2,111,733=11,872,043

    The next ticket will have some overlap and give less than 2,111,733 matches.

    If an array held all the possible then trim out the matches for the 1st ticket. With this now trimmed array take out the next matches.

    See if a different ticket reduced it more or not. Once a 2nd ticket is chosen, repeat for the next tickets.
    Last edited by Tom Ulrich; 30 May 2008, 09:12 AM. Reason: 2,073,848 should have been 2,111,733

    Leave a comment:


  • Rodney Hicks
    replied
    You might choose the Brute Force method because:

    Most of the work has been done for you

    19 combinations give you 19*15=285
    18 combinations give you 18*15=270

    There are 19*6=114 numbers in the 19 combinations.
    Therefore some numbers appear twice, others thrice. Perhaps others once.

    Derive all combinations from each set of numbers, store in an array
    sets(19,15,2) or sets$(19,15)
    Once array sets() is full, parse the array to find all duplicate twosomes.

    Count the number of duplicated twosomes. If less that 15 you will not be able to find an 18 piece subset to satisfy your needs or curiosity.

    However a quick look at the set of 19 tells me that there should be in excess of 15 twosomes that are duplicated.

    So if you count the different numbers in the duplicates and see if there is a preponderance of any certain numbers, ie, that the numbers are not evenly distributed, which I've already shown you that they aren't, you can then try to fashion your 18 piece subset by removing instances of the numbers with a higher count.

    Any 18 piece subset is going to include the numbers of the 19 piece subset, therefore making millions of calculation on all possible combinations seems redundant. You have fewer than 300 comparisons to make.

    Rod

    Leave a comment:


  • Neil Croft
    replied
    John,

    I can see where you're heading with that and it's an interesting visualisation concept. I need to get my head around how I can go further with that.

    Michael,

    Well noted. Force of habit is to declare the lower bound 'cos usually I don't need the speed and have been burned before when doing array sorts.

    Now I need to go and look at some pointer examples.

    Leave a comment:


  • Michael Mattias
    replied
    For better performance, use zero-based arrays instead of one-based arrays - "as documented in the help file."

    But yes you are correct, by using pointer variables you could moot the perfomance benefits of zero-based arrays.

    Leave a comment:


  • John Gleason
    replied
    Just a start, but there is a kind of pattern. I haven't figured out the verify proof logic yet tho.
    Code:
    #COMPILE EXE
    #DIM ALL
    
    FUNCTION PBMAIN () AS LONG
        LOCAL ii, ii2, x, x2 AS LONG, tots AS STRING
        DIM comb(1 TO 1176) AS LONG, ticket(1 TO 19) AS QUAD
        DIM ticket2comb(285) AS LONG
    
    '*********************************************************************************************************************
                        'enter ticket numbers left-zero-padded (this is the current record holder)
    ticket(1) = &h010203040506
    ticket(2) = &h010207080910
    ticket(3) = &h010211121314
    ticket(4) = &h030407081314
    ticket(5) = &h030409101112
    ticket(6) = &h050607081112
    ticket(7) = &h050609101314
    ticket(8) = &h151617181920
    ticket(9) = &h151621222324
    ticket(10) = &h151625262728
    ticket(11) = &h171821222728
    ticket(12) = &h171823242526
    ticket(13) = &h192021222526
    ticket(14) = &h192023242728
    ticket(15) = &h293031323334
    ticket(16) = &h353637383940
    ticket(17) = &h414243444546
    ticket(18) = &h414243474849
    ticket(19) = &h444546474849
    
    '*********************************************************************************************************************
    FOR ii = 1 TO 19    'this loop converts the 6-number tickets above into all their possible 2 number combos.
       ii2 = (ii - 1) * 15 + 1
       ticket2comb(ii2+00) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h00ff00000000) \ &h000100000000
       ticket2comb(ii2+01) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h0000ff000000) \ &h000001000000
       ticket2comb(ii2+02) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
       ticket2comb(ii2+03) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
       ticket2comb(ii2+04) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h0000000000ff)
    
       ticket2comb(ii2+05) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h0000ff000000) \ &h000001000000
       ticket2comb(ii2+06) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
       ticket2comb(ii2+07) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
       ticket2comb(ii2+08) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h0000000000ff)
    
       ticket2comb(ii2+09) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
       ticket2comb(ii2+10) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
       ticket2comb(ii2+11) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h0000000000ff)
    
       ticket2comb(ii2+12) = (ticket(ii) AND &h000000ff0000) \ &h000000000100 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
       ticket2comb(ii2+13) = (ticket(ii) AND &h000000ff0000) \ &h000000000100 + (ticket(ii) AND &h0000000000ff)
    
       ticket2comb(ii2+14) = (ticket(ii) AND &h00000000ff00)                  + (ticket(ii) AND &h0000000000ff)
    
    NEXT
    '*********************************************************************************************************************
                        'this section sorts the ticket 2-digit combos, then removes dupes
    ARRAY SORT ticket2comb()
    x = 0
    FOR ii = 1 TO 285
       IF ticket2comb(x) <> ticket2comb(ii) THEN
          INCR x
          ticket2comb(x) = ticket2comb(ii)
       END IF
       
    NEXT
    '*********************************************************************************************************************
                        'finally this part compares the ticket array to all 1176 possible combos, and prints the
                        'result to a file. The file should be viewed with word-wrap OFF to see the pattern. You can
                        'use WordPad for example to do this.
        x = 0
        x2 = 1
        FOR ii = 1 TO 49
           FOR ii2 = ii + 1 TO 49
              INCR x
              comb(x)  = VAL("&h" & FORMAT$(ii * 100 + ii2, "0000"))
    
              IF comb(x) = ticket2comb(x2) THEN
                 comb(x) = &h08888
                 INCR x2
              END IF
              tots = tots & HEX$(comb(x), 4) & ","
    
           NEXT
              tots = tots & $CRLF
        NEXT
                          
        REPLACE "8888" WITH "####" IN tots
        OPEN "c:\totsCombinatrixFile2.txt" FOR BINARY AS #1
        PUT #1, ,tots
        CLOSE
       ? "Data saved in: c:\totsCombinatrixFile2.txt"
    
    END FUNCTION

    Leave a comment:


  • Neil Croft
    replied
    10/second was a conservative estimate but given the truly vast number of tests required you'd have to go some. Still, along those lines....

    Just to loop through the 6 options per line for 18 lines would require 108 nested loops which blows the stack and, as I've seen elsewhere in answers on here, if you're blowing the stack on nested loops it's time to reconsider the algorithm. Still, 18 loops is doable so the logic of my brute force program is basically the following. There's a small piece of code that saves progress every 10k iterations and loads up the data first time around so as not to completely start from scratch each run but I've taken that out for clarity. I suspect using the P&() array directly instead of transposing into W&() would save me a bunch of cycles and that's my current task.

    Note, using the big P&() array saves the stack but uses 330k of RAM when running. Not for the faint hearted or those with smaller machines.

    Code:
    #INCLUDE "win32api.inc"
    FUNCTION PBMAIN () AS LONG
        ' Use spare cyles so we don't kill the machine
        ff&=SetPriorityClass(GetCurrentProcess, %IDLE_PRIORITY_CLASS)
        ' Name the console so we know what's running
        CONSOLE NAME "18 lines - 2 from 49"
        ' save some time
        REGISTER f&
        REGISTER g&
        '
        ta&=13983816
        '
        ' store all possibilities
        DIM p&(1 TO ta&,1 TO 6)
        '
        ta&=0
        '
        ' set the possibilities array
        FOR a&=1 TO 44
            FOR b&=a&+1 TO 45
                FOR c&=b&+1 TO 46
                    FOR d&=c&+1 TO 47
                        FOR e&=d&+1 TO 48
                            FOR f&=e&+1 TO 49
                                INCR ta&
                                p&(ta&,1)=a&
                                p&(ta&,2)=b&
                                p&(ta&,3)=c&
                                p&(ta&,4)=d&
                                p&(ta&,5)=e&
                                p&(ta&,6)=f&
                            NEXT
                        NEXT
                    NEXT
                NEXT
            NEXT
        NEXT
        '
        'current set array
        DIM w&(1 TO 18,1 TO 49)
        '
        ' if a solution exists it will have 1,2,3,4,5,6 as first line
        l1&=1
        w&(1,1)=1
        w&(1,2)=1
        w&(1,3)=1
        w&(1,4)=1
        w&(1,5)=1
        w&(1,6)=1
        FOR l2&=2 TO 13983799
            w&(2,p&(l2&,1))=1
            w&(2,p&(l2&,2))=1
            w&(2,p&(l2&,3))=1
            w&(2,p&(l2&,4))=1
            w&(2,p&(l2&,5))=1
            w&(2,p&(l2&,6))=1
        FOR l3&=l2&+1 TO 13983800
            w&(3,p&(l3&,1))=1
            w&(3,p&(l3&,2))=1
            w&(3,p&(l3&,3))=1
            w&(3,p&(l3&,4))=1
            w&(3,p&(l3&,5))=1
            w&(3,p&(l3&,6))=1
        FOR l4&=l3&+1 TO 13983801
            w&(4,p&(l4&,1))=1
            w&(4,p&(l4&,2))=1
            w&(4,p&(l4&,3))=1
            w&(4,p&(l4&,4))=1
            w&(4,p&(l4&,5))=1
            w&(4,p&(l4&,6))=1
        FOR l5&=l4&+1 TO 13983802
            w&(5,p&(l5&,1))=1
            w&(5,p&(l5&,2))=1
            w&(5,p&(l5&,3))=1
            w&(5,p&(l5&,4))=1
            w&(5,p&(l5&,5))=1
            w&(5,p&(l5&,6))=1
        FOR l6&=l5&+1 TO 13983803
            w&(6,p&(l6&,1))=1
            w&(6,p&(l6&,2))=1
            w&(6,p&(l6&,3))=1
            w&(6,p&(l6&,4))=1
            w&(6,p&(l6&,5))=1
            w&(6,p&(l6&,6))=1
        FOR l7&=l6&+1 TO 13983804
            w&(7,p&(l7&,1))=1
            w&(7,p&(l7&,2))=1
            w&(7,p&(l7&,3))=1
            w&(7,p&(l7&,4))=1
            w&(7,p&(l7&,5))=1
            w&(7,p&(l7&,6))=1
        FOR l8&=l7&+1 TO 13983805
            w&(8,p&(l8&,1))=1
            w&(8,p&(l8&,2))=1
            w&(8,p&(l8&,3))=1
            w&(8,p&(l8&,4))=1
            w&(8,p&(l8&,5))=1
            w&(8,p&(l8&,6))=1
        FOR l9&=l8&+1 TO 13983806
            w&(9,p&(l9&,1))=1
            w&(9,p&(l9&,2))=1
            w&(9,p&(l9&,3))=1
            w&(9,p&(l9&,4))=1
            w&(9,p&(l9&,5))=1
            w&(9,p&(l9&,6))=1
        FOR l10&=l9&+1 TO 13983807
            w&(10,p&(l10&,1))=1
            w&(10,p&(l10&,2))=1
            w&(10,p&(l10&,3))=1
            w&(10,p&(l10&,4))=1
            w&(10,p&(l10&,5))=1
            w&(10,p&(l10&,6))=1
        FOR l11&=l10&+1 TO 13983809
            w&(11,p&(l11&,1))=1
            w&(11,p&(l11&,2))=1
            w&(11,p&(l11&,3))=1
            w&(11,p&(l11&,4))=1
            w&(11,p&(l11&,5))=1
            w&(11,p&(l11&,6))=1
        FOR l12&=l11&+1 TO 13983810
            w&(12,p&(l12&,1))=1
            w&(12,p&(l12&,2))=1
            w&(12,p&(l12&,3))=1
            w&(12,p&(l12&,4))=1
            w&(12,p&(l12&,5))=1
            w&(12,p&(l12&,6))=1
        FOR l13&=l12&+1 TO 13983811
            w&(13,p&(l13&,1))=1
            w&(13,p&(l13&,2))=1
            w&(13,p&(l13&,3))=1
            w&(13,p&(l13&,4))=1
            w&(13,p&(l13&,5))=1
            w&(13,p&(l13&,6))=1
        FOR l14&=l13&+1 TO 13983812
            w&(14,p&(l14&,1))=1
            w&(14,p&(l14&,2))=1
            w&(14,p&(l14&,3))=1
            w&(14,p&(l14&,4))=1
            w&(14,p&(l14&,5))=1
            w&(14,p&(l14&,6))=1
        FOR l15&=l14&+1 TO 13983813
            w&(15,p&(l15&,1))=1
            w&(15,p&(l15&,2))=1
            w&(15,p&(l15&,3))=1
            w&(15,p&(l15&,4))=1
            w&(15,p&(l15&,5))=1
            w&(15,p&(l15&,6))=1
        FOR l16&=l15&+1 TO 13983814
            w&(16,p&(l16&,1))=1
            w&(16,p&(l16&,2))=1
            w&(16,p&(l16&,3))=1
            w&(16,p&(l16&,4))=1
            w&(16,p&(l16&,5))=1
            w&(16,p&(l16&,6))=1
        FOR l17&=l16&+1 TO 13983815
            w&(17,p&(l17&,1))=1
            w&(17,p&(l17&,2))=1
            w&(17,p&(l17&,3))=1
            w&(17,p&(l17&,4))=1
            w&(17,p&(l17&,5))=1
            w&(17,p&(l17&,6))=1
        FOR l18&=l17&+1 TO 13983816
            w&(18,p&(l18&,1))=1
            w&(18,p&(l18&,2))=1
            w&(18,p&(l18&,3))=1
            w&(18,p&(l18&,4))=1
            w&(18,p&(l18&,5))=1
            w&(18,p&(l18&,6))=1
            '
            'so that's 18 (17 really) loops picking out each line from the possibilities
            co&=0
            FOR a&=1 TO 44
                FOR b&=a&+1 TO 45
                    FOR c&=b&+1 TO 46
                        FOR d&=c&+1 TO 47
                            FOR e&=d&+1 TO 48
                                FOR f&=e&+1 TO 49
                                    ok&=0
                                    FOR g&=1 TO 18
                                        s&=w&(g&,a&)+w&(g&,b&)+w&(g&,c&)+w&(g&,d&)+w&(g&,e&)+w&(g&,f&)
                                        'if it got a 2 match thn we can proceed
                                        IF s&>1 THEN ok&=1:EXIT
                                    NEXT
                                    ' if we didn't get a match then that set of 18 is no good. Move on.
                                    IF ok&=0 THEN EXIT,EXIT,EXIT,EXIT,EXIT,EXIT
                                    INCR co&
                                    '
                                NEXT
                            NEXT
                        NEXT
                    NEXT
                NEXT
            NEXT
            '
            ' show some progress
            IF co&>bco& THEN
                bco&=co&
                PRINT DATE$;" ";TIME$;bco&;ta&-bco&;FORMAT$(bco&/ta&,"##.00000%")
                FOR e&=1 TO 18
                    FOR f&=1 TO 49
                        IF w&(e&,f&)=1 THEN PRINT f&;
                    NEXT
                    IF e&=1 THEN PRINT "",1
                    IF e&=2 THEN PRINT "",l2&
                    IF e&=3 THEN PRINT "",l3&
                    IF e&=4 THEN PRINT "",l4&
                    IF e&=5 THEN PRINT "",l5&
                    IF e&=6 THEN PRINT "",l6&
                    IF e&=7 THEN PRINT "",l7&
                    IF e&=8 THEN PRINT "",l8&
                    IF e&=9 THEN PRINT "",l9&
                    IF e&=10 THEN PRINT "",l10&
                    IF e&=11 THEN PRINT "",l11&
                    IF e&=12 THEN PRINT "",l12&
                    IF e&=13 THEN PRINT "",l13&
                    IF e&=14 THEN PRINT "",l14&
                    IF e&=15 THEN PRINT "",l15&
                    IF e&=16 THEN PRINT "",l16&
                    IF e&=17 THEN PRINT "",l17&
                    IF e&=18 THEN PRINT "",l18&
                NEXT
                PRINT
                '
            END IF
            '
            ' if we get a solution then save it to disk.
            IF co&=ta& THEN
                ff&=FREEFILE
                OPEN "result.txt" FOR OUTPUT AS ff&
                FOR a&=1 TO 18
                    FOR b&=1 TO 49
                        IF w&(a&,b&)=1 THEN PRINT# ff&,b&;
                    NEXT
                    PRINT# ff&,""
                NEXT
                CLOSE
            END IF
            '
            w&(18,p&(l18&,1))=0
            w&(18,p&(l18&,2))=0
            w&(18,p&(l18&,3))=0
            w&(18,p&(l18&,4))=0
            w&(18,p&(l18&,5))=0
            w&(18,p&(l18&,6))=0
        NEXT
            w&(17,p&(l17&,1))=0
            w&(17,p&(l17&,2))=0
            w&(17,p&(l17&,3))=0
            w&(17,p&(l17&,4))=0
            w&(17,p&(l17&,5))=0
            w&(17,p&(l17&,6))=0
        NEXT
            w&(16,p&(l16&,1))=0
            w&(16,p&(l16&,2))=0
            w&(16,p&(l16&,3))=0
            w&(16,p&(l16&,4))=0
            w&(16,p&(l16&,5))=0
            w&(16,p&(l16&,6))=0
        NEXT
            w&(15,p&(l15&,1))=0
            w&(15,p&(l15&,2))=0
            w&(15,p&(l15&,3))=0
            w&(15,p&(l15&,4))=0
            w&(15,p&(l15&,5))=0
            w&(15,p&(l15&,6))=0
        NEXT
            w&(14,p&(l14&,1))=0
            w&(14,p&(l14&,2))=0
            w&(14,p&(l14&,3))=0
            w&(14,p&(l14&,4))=0
            w&(14,p&(l14&,5))=0
            w&(14,p&(l14&,6))=0
        NEXT
            w&(13,p&(l13&,1))=0
            w&(13,p&(l13&,2))=0
            w&(13,p&(l13&,3))=0
            w&(13,p&(l13&,4))=0
            w&(13,p&(l13&,5))=0
            w&(13,p&(l13&,6))=0
        NEXT
            w&(12,p&(l12&,1))=0
            w&(12,p&(l12&,2))=0
            w&(12,p&(l12&,3))=0
            w&(12,p&(l12&,4))=0
            w&(12,p&(l12&,5))=0
            w&(12,p&(l12&,6))=0
        NEXT
            w&(11,p&(l11&,1))=0
            w&(11,p&(l11&,2))=0
            w&(11,p&(l11&,3))=0
            w&(11,p&(l11&,4))=0
            w&(11,p&(l11&,5))=0
            w&(11,p&(l11&,6))=0
        NEXT
            w&(10,p&(l10&,1))=0
            w&(10,p&(l10&,2))=0
            w&(10,p&(l10&,3))=0
            w&(10,p&(l10&,4))=0
            w&(10,p&(l10&,5))=0
            w&(10,p&(l10&,6))=0
        NEXT
            w&(9,p&(l9&,1))=0
            w&(9,p&(l9&,2))=0
            w&(9,p&(l9&,3))=0
            w&(9,p&(l9&,4))=0
            w&(9,p&(l9&,5))=0
            w&(9,p&(l9&,6))=0
        NEXT
            w&(8,p&(l8&,1))=0
            w&(8,p&(l8&,2))=0
            w&(8,p&(l8&,3))=0
            w&(8,p&(l8&,4))=0
            w&(8,p&(l8&,5))=0
            w&(8,p&(l8&,6))=0
        NEXT
            w&(7,p&(l7&,1))=0
            w&(7,p&(l7&,2))=0
            w&(7,p&(l7&,3))=0
            w&(7,p&(l7&,4))=0
            w&(7,p&(l7&,5))=0
            w&(7,p&(l7&,6))=0
        NEXT
            w&(6,p&(l6&,1))=0
            w&(6,p&(l6&,2))=0
            w&(6,p&(l6&,3))=0
            w&(6,p&(l6&,4))=0
            w&(6,p&(l6&,5))=0
            w&(6,p&(l6&,6))=0
        NEXT
            w&(5,p&(l5&,1))=0
            w&(5,p&(l5&,2))=0
            w&(5,p&(l5&,3))=0
            w&(5,p&(l5&,4))=0
            w&(5,p&(l5&,5))=0
            w&(5,p&(l5&,6))=0
        NEXT
            w&(4,p&(l4&,1))=0
            w&(4,p&(l4&,2))=0
            w&(4,p&(l4&,3))=0
            w&(4,p&(l4&,4))=0
            w&(4,p&(l4&,5))=0
            w&(4,p&(l4&,6))=0
        NEXT
            w&(3,p&(l3&,1))=0
            w&(3,p&(l3&,2))=0
            w&(3,p&(l3&,3))=0
            w&(3,p&(l3&,4))=0
            w&(3,p&(l3&,5))=0
            w&(3,p&(l3&,6))=0
        NEXT
            w&(2,p&(l2&,1))=0
            w&(2,p&(l2&,2))=0
            w&(2,p&(l2&,3))=0
            w&(2,p&(l2&,4))=0
            w&(2,p&(l2&,5))=0
            w&(2,p&(l2&,6))=0
        NEXT
        '
        PRINT "Done"
        WAITKEY$
        '
    END FUNCTION
    A better way of storing the P&() array (maybe 13983816x49 bytes and some clever memory reading using pointers) would be a better way forward but is a bit beyond my programming skills. Just doing a test on the 18 loops with nothing more than an incrementing counter displaying the time every 500,000,000 passes puts the time out just about every 6 seconds on my 3.6GHz xeon :goodboy: That suggests there's huge scope for improvement on my brute force method. Maybe time to go back to the drawing board there.

    Leave a comment:


  • John Gleason
    replied
    Neil, would it be of benefit to increase the number of tests per second you can run? Ten per second is not too many. A 2Ghz processor translates to 200 million ticks per test. Oof. I have to believe I can improve on that. I count 1176 combos on 18 or 19 lines of 15 combos each or say 285 combos. Thats 335,000 tests on a 1 to 1 basis or 600 ticks per test. Maybe I can get it down to like 60, or yow, 6. hehheh

    Leave a comment:


  • Eddy Van Esch
    replied
    Neil,

    If you would like to experiment with some kind of brute-forcing method, I can possibly get you in touch with a guy who has developed a client-server application for distributed calculations (a SETI-like setup).
    Last time I talked to him he was looking for an experiment to put his system to the test.

    Drop me a private mail if you think this could be of use to you.

    Kind regards

    Leave a comment:


  • Neil Croft
    replied
    Chris,

    With hindsight re-expressing the problem before posting may have avoided the "L word" associations. It's quite scary the number of people who exert extreme amounts of effort to try and predict the unpredictable although it's also interesting to see how people approach solving that "problem".

    It's interesting (and slightly related) to hear relatives at family gatherings asking why computers can't do X yet, where X is curing cancer (BOINC, they do), Answer the meaning of life (SETI?), make a cup of tea (I'm sure I could modify a water CPU cooler ), etc. As a home computer owner since 1982 (Sinclair Spectrum Yay!) I've always been more interested in programming and the algorithms rather than the end use albeit the end use indirectly pays my mortgage (I'm an IT security consultant).

    This particular conundrum should be eminently calculable though. It's simple pattern matching for goodness sake. Even good suggestions of ways to parallelize the code to share it around the heap of tin around the house would be welcome. I looked at BOINC but my C skills are poor to say the least. Just tracking the problem space is vast and so just trying to track what 10 or so CPUs had checked made my brain pop.

    Leave a comment:


  • Chris Holbrook
    replied
    Originally posted by Neil Croft View Post
    Every Lottery site... beat the lottery...pick winning lottery ...Forget the lottery... not win the lottery.
    Neil, in these forums such nuances of meaning are best avoided unless they can be expressed in code.

    I liked the one about the germs though.

    Leave a comment:


  • Neil Croft
    replied
    Donald, you've missed the line that says
    Note this is a problem in combinatrics, not a lottery problem.
    . Like the Travelling Salesman problem doesn't actually require us to hop in the car and drive around loads of strange town and note the mileage. The exercise is to find a better algorithm. Every Lottery site I've seen concentrates on "beating the odds" and I'm a man of logic and will quite happily use a pin to pick numbers to beat the lottery with equal success to any software.

    Regardless of any logic people who buy that stuff should conside this. If I did write a program that could pick winning lottery numbers, 1) why would I want to share it? 2) Why would I need to share it?

    Forget the lottery. Imagine 49 germs of which 6 are present in any person and you can only give them 18 antibiotics of which there are 13983816 different varieties and you want to kill at least 2 germs in every person and each antibiotic can kill 6 different germs. Whatever gets your programming juices flowing.

    The exercise is to find an algorithm that proves or disproves the solution can be calculated in less than a planet's lifetime, not win the lottery.

    Leave a comment:


  • Donald Darden
    replied
    This is one of the most popular themes on the Internet. The odds and the algorythms for projecting those odds are posted many places. I suggest you look for lottery calculator, lottery odds, or lottery odds calculator in your search.

    I actually have working programs in Excel and in PowerBasic for making my own determinations, and I found it an interesting subject at one time. But megalottos have put the odds of winning to such a remote extreme that I gave up an active interest in playing many years ago. Calculating the odds is just a waste of time after that.

    Note, that I also found that the lotteries themselves post the odds of winning, And there are books written about playing strategies, such as the art of Wheeling. Wheeling is taking a group of numbers, say your 9 favorite numbers, then playing them in arrangements of six numbers each. How many lines would you have to play to maximize your potential of winning on any combination of those 9 numbers? The idea is that if you can narrow the probabilities to the best 8 or 9 numbers, and say five of six numbers that are drawn actually are among those numbers you pick, then one of those lines may have 4 or 5 of those numbers on it.

    It's still a risk, of course, but it only depends on whether you are able to pick numbers that have a better chance of coming up. That's where people hope to get lucky or use a process of elemination.

    There are different strategies for Wheeling, which depend on the number of preferred numbers you want to play, how many numbers you want combined minimum per line, and how many lines you want to play. You might want to try your hand at programming a Wheeling program that works this out for you. And of course you can find lottery wheels and lottery wheeling systems on the Internet as well.

    Everybody believes that they can play and eventually beat the odds. If you take comfort in this, then I suggest you ignore the odds altogether. They are not encouraging, and for megagames, they are the absolute pits.

    Leave a comment:

Working...
X