Qbasicnews.com

Full Version: Challenge: Validate a code
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3 4 5 6 7
Moneo:
My program uses huge (more than 64K) arrays, as does Blitz's. In the IDE they are activated with /AH, don't know what is the equivalent switch in BC.
Preprocessing is cheating!

Question!!!!!! QUESTION!!!!!!! The user inputs 20,000 numbers and tests if any of them exist out of the other 20,000 numbers in the file?!?!?!?!

Wouldn't it be better just to use TWO files, then???!!!!
the /ah switch is the same in bc. And you should compile with vbdos. It's better with LONGs.
Quote:BTW: I don't understand why you set up a two dimensional array, and why you use the values 16384 and 16383. What are you trying to do?
*****

End the challenge first and i'll explain. Smile
WAIT!!!!!!!!!
I did a benchmark between mine and antonis, i think he'll agree that they're very fair. Here they are.


Code:
defint a-z

const KEYMIN&   = 0&
const KEYMAX&   = 99999&
const VALIDKEY  = -1

declare sub loadKeyTable   ( filename as string )
declare function checkKey% ( keyToCheck as long )


'$dynamic
dim shared keyTable( KEYMAX \ 16384&, 16383 ) as integer
'$static


    ''
    '' Entry point
    ''
    dim result as integer  
    dim keyToCheck as long    
    dim indxa as integer, indxb as integer
    dim tmrIni as single, tmrEnd as single
    
  
    ''
    '' This is not part of the main program
    '' it's just setup.
    ''
    loadKeyTable "valid.txt"    
    keyToCheck = 13
    
    tmrIni = timer
    for  i = 0 to 31999
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )

        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )

        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
        
        indxa = keyToCheck  \  16384&
        indxb = keyToCheck and 16383&
        result = keyTable( indxa, indxb )
    next i
    tmrEnd = timer
    
    
    print "Blitz code does" + str$(clng( 32000#*10# / (tmrEnd-tmrIni) )) + " searches per second"



'' :::::::::
'' name: loadKeyTable
'' desc: Loads a bunch of valid keys
'' note: This is to be run BEFORE starting to time
''
'' :::::::::
defint a-z
sub loadKeyTable ( filename as string ) static
    dim currKey as long
    dim keysRead as long
    dim keysInFile as long
    
    dim i as integer, j as integer
    dim indxa as integer, indxb as integer
    
    
    open filename for input as #1    
    
    ''
    '' Clear table and load keys
    ''
    for  i = 0 to KEYMAX \ 16384&
        for  j = 0 to 16383
            keyTable( i, j ) = 0
        next j
    next i    

    while ( not eof( 1 ) )
        input #1, currKey
        
        if ( (currKey < KEYMIN) or (currKey > KEYMAX) ) then
            print "Error: Invalid key in file..."
            end
        end if
        
        ''
        '' Put key in table
        ''        
        indxa = currKey  \  16384&
        indxb = currKey and 16383&
        keyTable( indxa, indxb ) = VALIDKEY
    wend
        
    close #1
end sub


And Antonis
Code:
DECLARE FUNCTION funFirstPrime% (threshold%)
DEFINT A-Z
CONST empty = -1&
CONST QBOFFSET = 16636
'-----------------------------setup------------------------------------
filename$ = "valid.txt"
OPEN filename$ FOR INPUT AS #1
codecnt = 0
WHILE NOT EOF(1)
codecnt = codecnt + 1
INPUT #1, CODE$
WEND

TABLESIZE = funFirstPrime(codecnt)

REDIM SHARED CODES(-QBOFFSET TO TABLESIZE - QBOFFSET) AS LONG
FOR I = LBOUND(CODES) TO UBOUND(CODES)
   CODES(I) = empty
NEXT

SEEK 1, 1

WHILE NOT EOF(1)
INPUT #1, CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> empty
   IF CODES(KEYINDEX - QBOFFSET) = CODE& THEN PRINT "Repeated code in input": END
   IF KEYINDEX = TABLESIZE THEN
      KEYINDEX = 0
   ELSE
      KEYINDEX = KEYINDEX + 1
   END IF
WEND
CODES(KEYINDEX - QBOFFSET) = CODE&
WEND
CLOSE

'--------------------------main loop-------------------------------------
    dim result as integer  
    dim tmrIni as single, tmrEnd as single

    CODE& = 13
        
    tmrIni = timer
    for  i = 0 to 31999
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&
        
        KEYINDEX = (CODE& MOD TABLESIZE)
        
        WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
          IF KEYINDEX = TABLESIZE THEN
             KEYINDEX = 0
          ELSE
             KEYINDEX = KEYINDEX + 1
          END IF
        WEND
        result = CODES(KEYINDEX - QBOFFSET) = CODE&

    next i
    tmrEnd = timer
    
    print "Antonis code does" + str$(clng( 32000#*10# / (tmrEnd-tmrIni) )) + " searches per second"



END

FUNCTION funFirstPrime (threshold)

tp30 = INT((threshold * 1.3))
IF tp30 / 2 = tp30 \ 2 THEN
   tp30 = tp30 + 1
END IF
c = tp30 - 2
IF c < 1 THEN
   c = 1
END IF
t2& = threshold * 2&
DO
   c = c + 2
   FOR z = 3 TO SQR(c)
      ind = -1
      IF c / z = c \ z THEN
         ind = FALSE
         EXIT FOR
      END IF
   NEXT z
   IF ind THEN
      IF (c - 3) / 4 = INT((c - 3) / 4) OR c > t2& THEN
         funFirstPrime = c
         EXIT DO
      END IF
   END IF
LOOP
END FUNCTION


After running each 8 times during the exact same conditions my best was 6301538 and Antonis was 2925714.
Quote:Come on, the hard part is stuffing the codes into as little memory as possible. That's the whole idea of the challenge!

Oh, well, so you were asking for this!:

Code:
'user password validation using a bit array
'Antoni Gual 2003
'-----------------------------setup------------------------------------
DEFINT A-Z
DIM pwrsof2(15)
FOR i = 0 TO 14: pwrsof2(i) = 2 ^ i: NEXT: pwrsof2(15) = &H8000
filename$ = "valid.txt"
OPEN filename$ FOR INPUT AS #1
DIM codes(16636)

WHILE NOT EOF(1)
LINE INPUT #1, A$
code& = VAL(A$)
byte = code& \ 16
bit = code& MOD 16
codes(byte) = codes(byte) OR pwrsof2(bit)
WEND
CLOSE

DO
DO
        INPUT "enter your code"; usr$
        IF usr$ = "" THEN END
        code& = VAL(usr$)
        IF code& > 0 AND code& < 99999 THEN EXIT DO
        PRINT "code must be in range 0 to 99999"
    LOOP
    byte = code& \ 16
    bit = code& MOD 16
    IF codes(byte) AND pwrsof2(bit) THEN
        PRINT "Accepted"
    ELSE
        PRINT "Rejected"
    END IF
    LOOP
END


Blitz:
I agree Your code was faster. Maybe as fast than this new one Big Grin
Yeah, that one is much much faster. Although it's basically the same as my code except you used a bit array to be able to use a static array. If you put dynamic before it runs the same speed as mine. But yeah, it's faster then mine now. cheeeataarr! Tongue
Quote:Preprocessing is cheating!

Question!!!!!! QUESTION!!!!!!! The user inputs 20,000 numbers and tests if any of them exist out of the other 20,000 numbers in the file?!?!?!?!

Wouldn't it be better just to use TWO files, then???!!!!

AGA,
In the range of 0 to 99999 there are 100,000 possible codes, of which there are 20,000 identified as valid in the VALID.TXT file. The idea is to read the valid codes and store them in memory somehow for later validation for each of the user input codes.

Yes, that's pre-processing, but it saves you from having to scan the entire VALID.TXT file everytime the user gives you a code.
*****
Alright, since we're playing it like that. Eat this Antoni, 36 million compared to your 24 Smile

Code:
''
'' If i had to chose i'd use a number in the range
'' 0 to 32767 for effciency. If the number was
'' bigger then that i wouldn't use qb.
'' Use the /ah option or you won't be able to compile
'' or run.
''
''
defint a-z

const KEYMIN&   = 0&
const KEYMAX&   = 99999&

declare sub loadKeyTable   ( filename as string )
declare function checkKey% ( keyToCheck as long )

dim shared PowerOf2( 15 ) as integer
dim shared keyTable( (KEYMAX+1) \ 16 ) as integer


    ''
    '' Entry point
    ''
    dim indx as integer
    dim result as integer  
    dim keyToCheck as long
    dim tmrIni as single, tmrEnd as single
    
  
    ''
    '' This is not part of the main program
    '' it's just setup.
    ''
    loadKeyTable "valid.txt"    
    keyToCheck = 13
    
    tmrIni = timer
    for  j = 0 to 99
        for  i = 0 to 31999        
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
            result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
        next i
    next j
    tmrEnd = timer
    
    
    print "Blitz code does" + str$(clng( 32000#*10#*100# / (tmrEnd-tmrIni) )) + " searches per second"


'' :::::::::
'' name: checkKey
'' desc: Checks if a key is valid
''
'' :::::::::
defint a-z
function checkKey% ( keyToCheck as long ) static

    checkKey% = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
    
end function



'' :::::::::
'' name: loadKeyTable
'' desc: Loads a bunch of valid keys
'' note: This is to be run BEFORE starting to time
''
'' :::::::::
defint a-z
sub loadKeyTable ( filename as string ) static
    dim currKey as long
    dim keysRead as long
    dim keysInFile as long
    
    dim i as integer, j as integer
    dim indxa as integer, indxb as integer
    
    for  i = 0 to 14
        PowerOf2( i ) = 2^i
    next i
    PowerOf2( i ) = &h8000    
    
    open filename for input as #1    
    
    ''
    '' Clear table and load keys
    ''
    for  i = 0 to KEYMAX \ 16&
        keyTable( i ) = 0
    next i    

    while ( not eof( 1 ) )
        input #1, currKey
        
        if ( (currKey < KEYMIN) or (currKey > KEYMAX) ) then
            print "Error: Invalid key in file..."
            end
        end if
        
        ''
        '' Put key in table
        ''        
        keyTable( currKey \ 16& ) = keyTable( currKey \ 16& ) or PowerOf2( currKey and 15& )
    wend
        
    close #1
end sub
Pages: 1 2 3 4 5 6 7