Qbasicnews.com
August 25, 2019, 11:38:11 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1] 2 3 ... 5
  Print  
Author Topic: Challenge: Validate a code  (Read 16858 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 Smiley

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! Smiley

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



WWW
« 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.
    ''
    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
Logged

oship me and i will give you lots of guurrls and beeea
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« 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
'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
Logged

Antoni
Blitz
I hold this place together
*****
Posts: 853



WWW
« 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 Tongue

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



WWW
« 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



WWW
« 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:
loadKeyTable "valid.txt"

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)
3) You have a comment about loading QB with /ah. Should I compile your program with any special switches?
*****
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
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!