Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: Moneo on July 26, 2003, 09:15:24 PM



Title: Challenge: Validate a code
Post by: Moneo 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.
*****


Title: oooh
Post by: Meg on July 26, 2003, 10:57:14 PM
I like this one :)

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

*peace*

Meg.


Title: Challenge: Validate a code
Post by: Moneo 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.
*****


Title: Challenge: Validate a code
Post by: Sterling Christensen 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


Title: yikes.
Post by: Meg 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.


Title: Challenge: Validate a code
Post by: Sterling Christensen 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.


Title: Challenge: Validate a code
Post by: Blitz 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


Title: Challenge: Validate a code
Post by: Antoni Gual 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


Title: Challenge: Validate a code
Post by: Blitz on July 27, 2003, 08:14:26 AM
I'm pretty sure mine is faster, look at the search function.
But you never know :P

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


Title: Challenge: Validate a code
Post by: Blitz 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.


Title: Yeah you see
Post by: seph on July 27, 2003, 06:05:33 PM
I won this challenge.


Title: Challenge: Validate a code
Post by: Moneo 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.
*****


Title: Challenge: Validate a code
Post by: Blitz on July 27, 2003, 09:30:02 PM
Moneo, the one i did assumes a binary file. Just so you know.


Title: Challenge: Validate a code
Post by: Moneo 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?
*****


Title: Challenge: Validate a code
Post by: Moneo 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.
*****


Title: Challenge: Validate a code
Post by: Blitz on July 27, 2003, 10:46:50 PM
Sure, you can treat a transvestite as a real women too. But that doesn't mean it is :p

My code reads binary files where each 4 bytes represents a long and the next 4 bytes another one etc etc. However, i with little modification it works with ASCII files as well. So here you go. Oh and i thought it was obvious that you have to use the /ah option. Well if it wasn't, now you know.

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&
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.txt"
   
   
    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 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


Title: Challenge: Validate a code
Post by: Moneo on July 27, 2003, 10:59:36 PM
BLITZ,
Got the same "subscript out of range" error in the same place as before.
P.S.: I'm compiling using BC without any switches. Is that ok?

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?
*****


Title: too lazy to make it loop and read in more values
Post by: Meg on July 27, 2003, 11:10:22 PM
meh.

*peace*

Meg.


Title: Challenge: Validate a code
Post by: Moneo on July 27, 2003, 11:17:09 PM
MEG,
The idea is not to loop and read in more values. The idea is to read in all the valid codes ONCE, and store them in memory to your liking (and obviously they have to fit). Then for each code that the user inputs, validate against what you have in memory.

Come on, the hard part is stuffing the codes into as little memory as possible. That's the whole idea of the challenge!
*****


Title: Challenge: Validate a code
Post by: Blitz on July 27, 2003, 11:51:15 PM
Ok listen, both my entry and antonis need to be compiled with the /Ah option. If you don't compile it with that option you will get subscript out of range.


Title: Challenge: Validate a code
Post by: Antoni Gual on July 28, 2003, 06:34:16 AM
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.


Title: Challenge: Validate a code
Post by: Agamemnus on July 28, 2003, 08:16:05 AM
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???!!!!


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 08:46:40 AM
the /ah switch is the same in bc. And you should compile with vbdos. It's better with LONGs.


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 08:50:31 AM
Quote from: "Moneo"
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. :)


Title: Challenge: Validate a code
Post by: Agamemnus on July 28, 2003, 08:57:34 AM
WAIT!!!!!!!!!


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 10:14:14 AM
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.


Title: Challenge: Validate a code
Post by: Antoni Gual on July 28, 2003, 10:26:00 AM
Quote from: "Moneo"

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


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 01:01:30 PM
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! :P


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 01:21:21 PM
Quote from: "Agamemnus"
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.
*****


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 01:25:41 PM
Alright, since we're playing it like that. Eat this Antoni, 36 million compared to your 24 :)

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


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 01:28:35 PM
BLITZ AND ANTONI,
I compiled your original programs using BC with /ah option, and now they run fine.

BLITZ: Excellent, yours runs perfectly. Later you can explain what the 2 dimeensional array is all about.

ANTONI: Very good, also runs well. One very minor problem, you do not alllow the user to specify a code or zero nor a code of 99999, which are within the defined limits.
*****


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 01:36:03 PM
ANTONI,
Your "bit array" is exactly my preferred solution. See my program below with a slightly simpler bit handling than yours, that is, no need for a pwrsof2 array.
Code:

REM Code validation program by Edward F. Moneo
DEFINT A-Z
CONST BT.MAXSIZE = 99999
DIM BT.TAB ( 0 TO ((BT.MAXSIZE+1)\16) ) AS INTEGER
DIM BT.BIT  AS LONG
DIM BT.LOC  AS INTEGER
DIM BT.ARG  AS LONG
DIM BT.TRUE AS INTEGER

open "valid.txt" for input as #1
do while not eof(1)
   line input #1,d$
   bt.arg=val(d$)
   gosub bt.set
loop

do
  input "Enter code to be validated (X=exit)";z$
  if ucase$(z$)="X" then system
  gosub validate
  if valid=0 then
     print "ERROR: Non-numeric or out or range input code"
  else
     bt.arg=val(z$)
     gosub bt.test
     if bt.true=0 then print "ERROR: code invalid" else print "ok, code valid"
  end if
loop

'******************************************************************************

BT.SET:
  GOSUB BT.GET
  BT.TAB(BT.LOC) = BT.TAB(BT.LOC) OR BT.BIT
RETURN

BT.TEST:
  GOSUB BT.GET
  BT.TRUE = ( BT.TAB(BT.LOC) AND BT.BIT )    
RETURN

BT.GET:
  BT.BIT = BT.ARG MOD 16
  BT.BIT = 2^BT.BIT
  BT.LOC = BT.ARG\16
RETURN

'BT.RESET:  '(Not used by this program)
'  GOSUB BT.GET
'  BT.TAB(BT.LOC) = BT.TAB(BT.LOC) AND (NOT(BT.BIT))
'RETURN
'  *************************************************************************

'*** CHECK FOR STRICTLY NUMERIC AND LESS/EQUAL TO BT.MAXSIZE.
VALIDATE:
  VALID=0         'Init to False
  IF Z$="" THEN RETURN '-------------------->
  FOR X = 1 TO LEN(Z$)
      A=ASC(MID$(Z$,X,1))
      IF A<48 OR A>57 THEN RETURN '--------->
  NEXT X
  IF VAL(Z$)<=BT.MAXSIZE THEN VALID=-1
RETURN

*****


Title: Challenge: Validate a code
Post by: Antoni Gual on July 28, 2003, 01:52:29 PM
Blitz:
OK, you won!

Moneo:
I use the array of Pwrsof2 just for speed. In this case this is not an issue but when doing real time graphics (p.e. scaling a font) it is.


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 02:15:21 PM
Ok, Antoni, what you say makes sense for speed. Once you learn to do something considering speed, you get in the habit of always doing it that way.

P.S.: It's hard to consider Blitz as having won. His last posted program is incomplete. Also, he abandoned his original approach and adopted yours.
*****


Title: Challenge: Validate a code
Post by: Blitz on July 28, 2003, 02:55:53 PM
Eh, that was my orginal aproatch. My original one used a huge array of integers which had 100,000 elements. The one antoni wrote the second time was the same as mine but with a bit array instead. My second one same as my first, except with a bit array. So i don't see how it is ME who has abboned their original aproach.

The two dimensional array is bascially the same principal as real mode memory. It's split up into segments. In this case each segment is 16384 integers. That times 13 gives us over 100,000 elements to work with.  To calculate the element index as a two dimensional array we do this indxa = element \ 16384, indxb = element mod 16384.


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 03:01:38 PM
Ok, sorry, Blitz. It's just that you've posted several versions including benchmark versions, so I'm a little confused as to which is your lastest working version. Would you please post your latest, running version so I can try it again.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 28, 2003, 06:21:36 PM
i'm gonna try this, now that Moneo has explained what it's all about.

And, stop spamming, Blitzilla.


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 06:35:02 PM
Aga,

Your right, I didn't explain everything up front this time, like I usually do. If I do too much explaining, then I get accused of posting a challenge with too many "constraints". I'm damned if I do, and damned if I don't.

Ok, so go ahead and try this one out, now that you know.
*****


Title: I decided to do something a little different.
Post by: Meg on July 28, 2003, 07:01:42 PM
How's this for cramming the codes into as little memory as possible?  No arrays :)  (this outta be good for a laugh, at least!)

Code:
DECLARE FUNCTION GetCode& ()

CLS
SCREEN 11

OPEN "VALID.TXT" FOR INPUT AS #1
     FOR i% = 1 TO 20000
          INPUT #1, n&
          PSET (n& MOD 640, n& \ 640), 15
     NEXT i%
CLOSE #1

DO
     UserCode& = GetCode&
     PRINT UserCode&; "is ";
     IF POINT(UserCode& MOD 640, UserCode& \ 640) THEN
          PRINT "Valid.              "
     ELSE
          PRINT "Invalid.            "
     END IF
LOOP

FUNCTION GetCode&
   
     LOCATE 12, 1: PRINT SPC(79);
     LOCATE 12, 1: PRINT "Enter Code: ";

     Code& = 0
     DO
          LOCATE 12, 13: PRINT Code&; " "
          DO
               c$ = INKEY$
          LOOP UNTIL c$ <> ""
          IF c$ = CHR$(27) THEN SYSTEM
          IF c$ = CHR$(13) THEN EXIT DO
          IF c$ = CHR$(8) THEN Code& = Code& \ 10
          IF c$ >= "0" AND c$ <= "9" THEN
               IF Code& <= 9999 THEN Code& = Code& * 10 + VAL(c$)
          END IF
     LOOP

     GetCode& = Code&

END FUNCTION



*peace*

Meg.


Title: Challenge: Validate a code
Post by: Antoni Gual on July 28, 2003, 07:22:52 PM
Fine idea, Meg!

This reminds me old times. I once used screen memory to run an assembler program in a Sinclair ZX Spectrum, back in 1985.... The idea was to leave all conventional memory to load a game (from an audio cassette), then my program made an (illegal) copy of it..


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 09:28:55 PM
Ok, Meg, your approach sounds ingenious. I've never used PSET and POINT commands, so I don't really understand how it's supposed to work.

The fact is, however, that it doesn´t work. It only likes small code numbers less than 500. I made several versions of the VALID.TXT file but any valid number greater than 400 is marked as invalid by your program. Must be a minor coding error. Or maybe I need to add some switch to the BC compiler.
*****


Title: Fixed
Post by: Meg on July 28, 2003, 10:45:06 PM
Yeah I had a "480" instead of a "640"; just a typo.  All fixed, now.  You don't need any fancy switches or anything.  It just uses the screen to store the information, which means you don't need to create any additional arrays.

The code is pretty straightforward.  Open up the data file, read in the values, and plot points on the screen:

i.e.

if the number read in = 0, plot a point at (0, 0)
if the number read in = 1, plot a point at (1, 0)
if the number read in = 639, plot a point at (639, 0)
if the number read in = 640, plot a point at (0, 1)


and so forth..

then, when the user enters codes, it just uses the POINT command to see whether the pixel which corresponds to that number has been lit up or not.

*peace*

Meg.


Title: Challenge: Validate a code
Post by: Moneo on July 28, 2003, 11:17:40 PM
MEG:
Fantastic, It works 100%. Congratulations. Brilliant idea.

I think we'll wait a day to see if Aga comes up with a solution, and then we'll declare a winner, which will be tough.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 01:09:06 PM
Signed integers are so much nicer sometimes...

Blah.. I might not post anything... if i convert my array to LONG, it won't go as fast....


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 02:32:09 PM
Aga, don't be concerned with speed for this. We're looking for design and simplicity.

You must take into consideration that this program has a user interface. So, the user is not going to notice the difference of a few microseconds.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 02:41:04 PM
:|


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 03:16:06 PM
My entry. Uses longs! I know, BAD! :(

Code:

'Is this BLITZTASTIC OR WHAT??!?!?

DECLARE FUNCTION validate.all% (file1$)
DECLARE FUNCTION num.exists% (n&)
DECLARE SUB load.valid.nums (file1$)
DIM SHARED num.max AS LONG, num.max2 AS LONG: num.max = 100000: num.max2 = num.max \ 16
DIM SHARED huge.array(1 TO num.max2) AS LONG
DIM SHARED bit2(0 TO 15) AS LONG
DIM SHARED num.amount AS INTEGER: num.amount = 20000
FOR I% = 0 TO 15: bit2(I%) = 2 ^ I%: NEXT I%

CLS

'OPEN "valid.txt" FOR OUTPUT AS #1
'FOR I% = 1 TO 20000
'a$ = LTRIM$(STR$(INT(RND * 100000)))
'PRINT #1, a$
'NEXT I%
'CLOSE
'SYSTEM

load.valid.nums ("valid.txt")

t1# = TIMER
PRINT validate.all%("valid.txt")
t2# = TIMER: PRINT "Time for"; num.amount; "values to be processed:"; t2# - t1#; "seconds."

'use num.exists%(n&) for individual numbers..
DO
INPUT n&
IF n& > 99999 THEN PRINT "Number bigger than 99999..."
IF n& < 0 THEN PRINT "Number smaller than 0..."
IF num.exists%(n&) THEN PRINT "Number exists!" ELSE PRINT "Number doesn't exist.."
LOOP

SUB load.valid.nums (file1$)
enter.char$ = CHR$(13): a1$ = " ": a2$ = "  ": num1$ = "": num2% = 0
OPEN file1$ FOR BINARY AS #1
j% = 1: FOR I% = 1 TO num.amount
num1$ = ""
GET #1, , a1$: IF a1$ = enter.char$ THEN GOTO v2
IF INSTR("0123456789", a1$) = 0 THEN GET #1, , a1$: GOTO v2
FOR j% = 1 TO 4
num1$ = num1$ + a1$
GET #1, , a1$: IF a1$ = enter.char$ THEN GOTO v1
IF INSTR("0123456789", a1$) = 0 THEN GET #1, , a1$: GOTO v2
NEXT j%
num1$ = num1$ + a1$
GET #1, , a1$
v1: IF a1$ <> enter.char$ THEN GET #1, , a1$: GOTO v2
num2& = VAL(num1$)
k% = num2& MOD 16
j% = num2& \ 16 + 1
temp& = huge.array(j%)
IF (temp& AND bit2(k%)) = 0 THEN huge.array(j%) = temp& + bit2(k%)
v2: GET #1, , a1$
NEXT I%
CLOSE
END SUB

FUNCTION num.exists% (n&)
k% = n& MOD 16
j% = n& \ 16 + 1
IF (huge.array(j%) AND bit2(k%)) THEN num.exists% = -1
END FUNCTION

FUNCTION validate.all% (file1$)
is.valid% = -1
enter.char$ = CHR$(13): a1$ = " ": a2$ = "  ": num1$ = "": num2% = 0
OPEN file1$ FOR BINARY AS #1
j% = 1: FOR I% = 1 TO num.amount
num1$ = ""
GET #1, , a1$: IF a1$ = enter.char$ THEN GOTO v2b
IF INSTR("0123456789", a1$) = 0 THEN GET #1, , a1$: GOTO v2b
FOR j% = 1 TO 4
num1$ = num1$ + a1$
GET #1, , a1$: IF a1$ = enter.char$ THEN GOTO v1b
IF INSTR("0123456789", a1$) = 0 THEN GET #1, , a1$: GOTO v2b
NEXT j%
num1$ = num1$ + a1$
GET #1, , a1$
v1b: IF a1$ <> enter.char$ THEN GET #1, , a1$: GOTO v2b
num2& = VAL(num1$)
k% = num2& MOD 16
j% = num2& \ 16 + 1
temp& = huge.array(j%)
IF (temp& AND bit2(k%)) = 0 THEN is.valid% = 0
v2b: GET #1, , a1$
NEXT I%
CLOSE
validate.all% = is.valid%
END FUNCTION


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 03:33:53 PM
Aga, Congratulations, it works!
However, it looks a bit complicated.

One small observation. On user input it allows leading, embedded, and trailing blanks on the numbers. Not exactly "clean", but that's my opinion.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 03:37:24 PM
Arr! I thought we already discussed that it removes all of that? aRr!!!!


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 03:53:08 PM
CODE VALIDATION CHALLENGE FINAL RESULTS:

First Place: MEG.  Brilliant solution and concise implementation.

Tied for Second: ANTONI and BLITZ. Excellent solutions and implementations.

Third: AGA. Very good, working solution.

Fourth: STERLING. Participated.

*****


Title: Challenge: Validate a code
Post by: Blitz on July 29, 2003, 03:53:50 PM
Jesus christ, that code will give me nightmares for weeks....

And reading from video ram is around 100 times slower then sys ram. And writing to it is around 10 times slower then sys ram. It's faster then files, but a huge array would have been faster. So if it was performance you were after...

Why do i get the feeling that meg won cuz she's the only girl here?


Title: Let's mutiny..
Post by: Agamemnus on July 29, 2003, 04:06:56 PM
Quote from: "Moneo"

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



Efficiency is equal to SPEED, not source code length, as Moneo thinks.. :)

BTW, Mr. Blitz, could you compare yours to mine...? Mine reads in 20,000 numbers, then reads them in again and searches for them. Also checks that they are numbers and proper format.

I could do this myself, but you see, if I keep looking at YOUR code (50% whitespace..), *I* might have nightmares for weeks..  :bounce:


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 04:10:55 PM
Blitz,
Speed was not an issue here. Speed is seldom an issue when a program has a user interface. The user can't telll the difference  waiting for 100ms or 200ms between his input and a response from the program.

I like simplicity. Meg's program is 39% the size of yours, and accomplishes the same task.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 04:13:25 PM
Moneo, moneo..

My validation program is 3 lines of code:

Code:

FUNCTION num.exists% (n&)
k% = n& MOD 16
j% = n& \ 16 + 1
IF (huge.array(j%) AND bit2(k%)) THEN num.exists% = -1
END FUNCTION


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 04:17:29 PM
Aga, are you kidding me?
That's the validation function. You entire validation program takes 90 lines of code.
*****


Title: Challenge: Validate a code
Post by: Agamemnus on July 29, 2003, 04:24:01 PM
Er, I meant function.

Realize that I have three functions. One to test an entire file of numbers, one to load a file of numbers, one to test one number, and some code for user input.

Also realize that writing to the screen takes much more moving-around- the-computer-code (SPEED) than writing to an array.

So, if you ignore what's inside the functions, the actual program is only 3 lines, too.


Title: Challenge: Validate a code
Post by: Blitz on July 29, 2003, 04:44:20 PM
Come on man, i don't care who wins. I never even enter these callenges becuase of the people who are supose to judge it. What annoys me is that you don't actually seem to understand any of the code. For instance, if it's the shortest code you wanted you would have seen that my first one was basically this. When you remove all the dims, functions, consts, defint, comments. All the things that make clear code. You would have gotten this. Which is quite a bit smaller then megs when you count actual lines of code. So i don't think you're qualified to judge this. In my opnion Antoni should have won. Even though it was basically my code replaced with a bit array. A bit array didn't come to my mind at first. So i think he should have won. Although i would have given him less points for coding style. He would still be the winner.


Code:

'$dynamic
dim shared keyTable( 7, 16383 ) as integer

open "valid.txt" for input a #1
while ( not eof( 1 ) )
    input #1, currKey&
    keyTable( currKey& \ 16384& , currKey& and 16383&  ) = -1
wend
close #1

do
    input "Enter a key or -1 to exit: ", keyToCheck&
   
    if ( keyTable( keyToCheck& \ 16384& , keyToCheck& and 16383& ) = 0 ) then
        print "Invalid key, quiting"
        exit do
    else
        print "Valid key"
    end if
loop


Title: Challenge: Validate a code
Post by: Antoni Gual on July 29, 2003, 05:11:05 PM
Aga: Using longs is not bad, only dangerous: there are some entries at Microsoft Knowledge Base about QB45 bugs related to  longs, in particular as parameters to SUBS and FUNCTIONS.

Blitz: When I die my style of coding will be taught in schools  :rotfl:


Title: Challenge: Validate a code
Post by: Moneo on July 29, 2003, 07:33:48 PM
Blitz,
Your late entry is a beautiful piece of tight code.
However, I had the following little problems:
1) The OPEN statement had "a" instead of "as"
2) I discovered that I needed to compile with /ah switch.
3) It's supposed to exit on -1. However, it says that it's valid.
4) So, I tried some other negative numbers, like -99999 which caused a "subscript out of range" error.
5) You also allow leading, embedded and trailing blanks on the input numbers, which is not good practice. If I entered "1 3" but really meant "123" you accept the input as "13".
6) I also tried some numbers larger than 99999, like 222222, which caused the "subscript out of range" error.

With a few more minutes of work, your last entry could have been a serious contenter. However, we closed off the challenge earlier.

As far as judging is concerned, we don't have any other alternate way of judging challenges. Maybe what I've been doing is not the best way of judging, that is, having the person who posted the challenge be the judge, but it's been working up to now for my posts. Any suggestions?

Regarding my not understanding all the code, it's tough enough to get the programs to compile and then to test them thoroughly. I take a fast look at them to get a fundamental idea of how they work, but without comments of any kind, it's extremely hard to really comprhend the general algorithms of the programs and the logic of their respective functions. If you were test-driving a car, you'd start it up, put in gear and drive around a bit. You woudn't take the engine and transmission apart to see how everything works.
*****


Title: Challenge: Validate a code
Post by: Blitz on July 29, 2003, 09:03:21 PM
Oh yeah, forgot the if ( (keyToCheck& < 0) or ( keyToCheck > 99999) ) then exit do


Title: Challenge: Validate a code
Post by: Agamemnus on July 31, 2003, 11:32:26 PM
blitz, i tried the last (complete) code piece of yours but got into an infinite loop somehow....

compare my and your methods.... I believe they will be close time-wise.............