Challenge: Validate a code

[Moneo]

Write a program to validate a user inputted code.

GIVEN:
* The range of possible numeric codes is from 0 to 99999.
* A text file called VALID.TXT contains 20,000 valid codes.

PROCESS:
Input the user provided code, and validate it against the 20,000 valid codes. Result is valid or invalid.

CHALLENGE:
Write the program in the most efficient manner possible, WITHOUT USING ANY ADDITIONAL FILES.
*****

[Meg]

I like this one

expect my code within the next 24 hrs. or so.

*peace*

Meg.

[Moneo]

Meg, Can't wait to see your approach. I bet it won't be recursive this time.
*****

[Sterling Christensen]

I'll try to come up with something original. Each valid code in the file is on it's own line, right?

EDIT: ok, here it is. Optimized for speed :)

Code:

DECLARE FUNCTION valid% (c&)
DEFINT A-Z

' Uncomment for stress testing:
'dummyStringToUseUpStringSpace$ = SPACE$(20000)
'anotherStringToUseUpStringSpace$ = SPACE$(20000)

PRINT
INPUT "Enter a number from 0 to 99999: ", c&

PRINT "That number is ";
IF NOT valid(c&) THEN PRINT "not ";
PRINT "listed as a valid code."

END

'
' Returns true if the code c& is found in valid.txt
'
FUNCTION valid (c&)

CONST true = -1, false = NOT true

c$ = LTRIM$(STR$(c&))
lenOfC = LEN(c$)
buffer$ = " "

' Use as much string memory as possible for temporary file access buffer,
'  using a minimum of 16 bytes and a maximum of 16384 bytes:
fileStep = FRE("") \ 3 - 64
SELECT CASE fileStep
CASE IS < 16:     fileStep = 16
CASE IS > 16384:  fileStep = 16384
END SELECT

found = false

OPEN "valid.txt" FOR BINARY AS #1

DO
   temp$ = INPUT$(fileStep, #1)
   IF LEN(temp$) < 1 THEN EXIT DO  ' Reached the end of the file?

   ' One step at a time to prevent string space overflow:
   buffer$ = RIGHT$(buffer$, 8)
   buffer$ = buffer$ + temp$
   temp$ = ""

   lenOfBuffer = LEN(buffer$)

   p = 1
   DO
      p = INSTR(p, buffer$, c$)
      IF p < 1 THEN EXIT DO
    
      IF p > 1 AND p + lenOfC <= lenOfBuffer THEN

         found = true
        
         ' The real thing will have either a space, or an enter (13 or 10)
         '  on both sides of it.
         ' The buffer$ = " " above makes it so we can always assume this
         '  even for the first code in the file.
         ' Let's say were're searching for 1234, for example:

         ' Make sure it isn't 12341, or 12349, etc:
         IF ASC(MID$(buffer$, p + lenOfC, 1)) > 32 THEN found = false

         ' Make sure it isn't 11234, or 91234, etc:
         IF ASC(MID$(buffer$, p - 1, 1)) > 32 THEN found = false

         IF found THEN GOTO validExitBothLoops

      END IF

      p = p + lenOfC

   LOOP

LOOP

validExitBothLoops:

CLOSE #1

valid = found

END FUNCTION

[Meg]

that looks really complicated, which probably means it blows mine out of the water in terms of speed. I went really basic on this one, no machiavellian formulas for you, Moneo!

Code:

DECLARE FUNCTION ValidateCode% (UserCode&)
CLS
DO
     INPUT "Enter Code: ", UserCode&
     IF UserCode& >= 0 AND UserCode& <= 99999 THEN EXIT DO
     PRINT "Invalid Code.  Must be between 0 and 99999."
LOOP

IF ValidateCode%(UserCode&) THEN PRINT "Valid." ELSE PRINT "Invalid."

FUNCTION ValidateCode% (UserCode&)

OPEN "VALID.TXT" FOR INPUT AS #1
     DO
          INPUT #1, FileCode&
          IF FileCode& = UserCode& THEN ValidateCode% = 1: EXIT DO
          IF EOF(1) THEN ValidateCode% = 0: EXIT DO
     LOOP
CLOSE #1

END FUNCTION

*peace*

Meg.

[Sterling Christensen]

Yeah, but mine won't work if the codes are separated by commas - yours will. And I forgot to make sure the number the user entered really was between 0 and 99999.

[Blitz]

Alright, here's my entry. It should be quite fast. I'd use a binary search tree but i won't bother with that without pointer. This is good enough.

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.
''
''
defint a-z
option explicit


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 keyToCheck as long    
  
    ''
    '' This is not part of the main program
    '' it's just setup.
    ''
    loadKeyTable "valid.dat"
    
    
    do
        input "Enter a key or -1 to exit: ", keyToCheck
        
        if ( checkKey( keyToCheck ) = 0 ) then
            print "Invalid key, quiting"
            exit do
        else
            print "Valid key"
        end if
    loop





'' :::::::::
'' name: checkKey
'' desc: Checks if a key is valid
''
'' :::::::::
defint a-z
function checkKey% ( keyToCheck as long ) static
    dim indxa as integer
    dim indxb as integer    
    
    ''
    '' Check range
    ''
    if ( (keyToCheck < KEYMIN) or (keyToCheck > KEYMAX) ) then
        checkKey% = 0
        exit function
    end if
    
    ''
    '' Check key
    ''    
    indxa = keyToCheck  \  16384&
    indxb = keyToCheck and 16383&
    checkKey% = keyTable( indxa, indxb )
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
    
    
    open filename for binary as #1
    
    ''
    '' Calculate the number of they in the file
    ''
    keysInFile = lof( 1 ) \ 4&        
    if ( keysInFile < 1 ) then
        print "Error: Key file empty..."
        end
    end if
    
    
    ''
    '' Clear table and load keys
    ''
    for  i = 0 to KEYMAX \ 16384&
        for  j = 0 to 16383
            keyTable( i, j ) = 0
        next j
    next i
    
    
    for  keysRead = 0 to keysInFile-1
        get #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
    next keysRead
        
    close #1
end sub

[Antoni Gual]

Maybe the fastest one..Works all in memory.

Code:

'user password validation using a hash table
'by Antoni Gual 2003
'uses linear re-hashing only
'Load qb with /ah


DECLARE FUNCTION funFirstPrime% (threshold%)
DEFINT A-Z
CONST empty = -1&
CONST QBOFFSET = 16636
'-----------------------------setup------------------------------------
filename$ = "validate.txt"
OPEN filename$ FOR INPUT AS #1
codecnt = 0
WHILE NOT EOF(1)
codecnt = codecnt + 1
LINE INPUT #1, A$
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)
LINE INPUT #1, A$
CODE& = VAL(A$)
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-------------------------------------

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
     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
     IF CODES(KEYINDEX - QBOFFSET) = CODE& THEN
        PRINT "Valid code"
     ELSE
        PRINT "Invalid code. Try again"
     END IF

    LOOP
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

[Blitz]

I'm pretty sure mine is faster, look at the search function.
But you never know

Though those long operation worries me. qb suxs, if it atleast had inline asm you could do the same thing in 2 clocks.

[Blitz]

So moneo? Why all the challenges? Your home assignments? I bet you're the teacher favorite student now.