Challenge: Validate a code - Moneo - 07-27-2003
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.
*****
oooh - Meg - 07-27-2003
I like this one
expect my code within the next 24 hrs. or so.
*peace*
Meg.
Challenge: Validate a code - Moneo - 07-27-2003
Meg, Can't wait to see your approach. I bet it won't be recursive this time.
*****
Challenge: Validate a code - Sterling Christensen - 07-27-2003
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
yikes. - Meg - 07-27-2003
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.
Challenge: Validate a code - Sterling Christensen - 07-27-2003
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.
Challenge: Validate a code - Blitz - 07-27-2003
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
Challenge: Validate a code - Antoni Gual - 07-27-2003
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
Challenge: Validate a code - Blitz - 07-27-2003
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.
Challenge: Validate a code - Blitz - 07-27-2003
So moneo? Why all the challenges? Your home assignments? I bet you're the teacher favorite student now.
|