Qbasicnews.com
February 21, 2020, 03:12:21 PM
 Pages: [1] 2 3 ... 5
 Author Topic: Challenge: Validate a code  (Read 17824 times)
Moneo
Na_th_an

Posts: 1971

 « on: July 26, 2003, 09:15:24 PM »

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.
*****
 Logged
Meg
Ancient QBer

Posts: 483

 « Reply #1 on: July 26, 2003, 10:57:14 PM »

I like this one

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

*peace*

Meg.
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #2 on: July 27, 2003, 12:00:05 AM »

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

Posts: 1328

 « Reply #3 on: July 27, 2003, 12:46:21 AM »

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
 Logged
Meg
Ancient QBer

Posts: 483

 « Reply #4 on: July 27, 2003, 02:54:42 AM »

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.
 Logged
Sterling Christensen
Na_th_an

Posts: 1328

 « Reply #5 on: July 27, 2003, 04:06:13 AM »

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.
 Logged
Blitz
I hold this place together

Posts: 853

 « Reply #6 on: July 27, 2003, 06:28:31 AM »

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.
''

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

'' :::::::::
'' 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 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

close #1
end sub
 Logged

oship me and i will give you lots of guurrls and beeea
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #7 on: July 27, 2003, 08:00:43 AM »

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

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
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
 Logged

Antoni
Blitz
I hold this place together

Posts: 853

 « Reply #8 on: July 27, 2003, 08:14:26 AM »

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.
 Logged

oship me and i will give you lots of guurrls and beeea
Blitz
I hold this place together

Posts: 853

 « Reply #9 on: July 27, 2003, 08:21:51 AM »

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

oship me and i will give you lots of guurrls and beeea
seph
Na_th_an

Posts: 1915

 « Reply #10 on: July 27, 2003, 06:05:33 PM »

I won this challenge.
 Logged

earn.
Moneo
Na_th_an

Posts: 1971

 « Reply #11 on: July 27, 2003, 08:54:56 PM »

MEG and STERLING:
Both your solutions assumed that the user was only going to enter one code per each running of the program. Actually the whole idea of the challenge is to store the 20,000 valid codes into memory somehow, and then validate each code entered by the user. Sorry if I wasn't more explicit. Blitz and Antoni did assume the user would enter multiple codes. Please enhance your solutions to take this into consideration.

BLITZ and ANTONI:
I'm in the process of compiling and testing your solutions.

BLITZ:
Regarding your questions about "why all the challenges", no I'm not a teacher nor a student. I just enjoy challenges. You get to learn different ways of doing things from other people.
*****
 Logged
Blitz
I hold this place together

Posts: 853

 « Reply #12 on: July 27, 2003, 09:30:02 PM »

Moneo, the one i did assumes a binary file. Just so you know.
 Logged

oship me and i will give you lots of guurrls and beeea
Moneo
Na_th_an

Posts: 1971

 « Reply #13 on: July 27, 2003, 09:33:56 PM »

Here's the results of tests on BLITZ and ANTONI programs.

P.S.: I created the VALID.TXT file with 20,000 records, and each record containing a 5 byte code number, with leading zeros.

BLITZ:
1) You had a line up front with OPTIONS EXPLICIT. I had to comment this out since QuickBasic does not like it.
2) You used filename VALID.DAT instead of VALID.TXT.  I fixed it.
3) Program compiles, but issues a "Subscript out of range" error on the line:

ANTONI:
1) You used filename VALIDATE.TXT. I changed to VALID.TXT.
2) Program compiles, but issues a "Subscript out of range" error on the line:
FOR I = LBOUND(CODES) TO UBOUND(CODES)
*****
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #14 on: July 27, 2003, 09:39:28 PM »

BLITZ,

Any type of file there is can be treated like a binary file and read as a binary file accordingly.

However, the file VALID.TXT is in fact a text file with 20,000 records. Each record has 5 numeric bytes for each of the codes.
You can go ahead and read it in binary if you like, but it's just a lot more work. However, reading it as a binary file is faster because you can read in a 16k chunk at a time and then deblock the records in memory. Most utility programs read text files in binary this way to speed up the access.
*****
 Logged
 Pages: [1] 2 3 ... 5