Announcement

Collapse
No announcement yet.

Euler problem 59

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • John Gleason
    replied
    Yep, I probably pulled out a few too many stops there in the code above. Ok, below is your code with several key optimizations explained, giving much speed improvement. Note especially: AVOID additive string concatenation like t += CHR$(z)
    Code:
    #COMPILE EXE
    #DIM ALL
    
    FUNCTION PBMAIN () AS LONG
       LOCAL passwLong AS LONG 'added
        DIM passw AS STRING
        DIM a AS STRING
        DIM b AS STRING
        DIM c AS STRING
        DIM i AS INTEGER
        DIM j AS INTEGER
        DIM k AS INTEGER
        FOR i = 97 TO 122
            FOR j = 97 TO 122
                FOR k = 97 TO 122
    '               passw = CHR$(i)+CHR$(j)+CHR$(k)         'rather than string concatenation, use CHR$() once.
                    passW = CHR$(i,j,k)
                    decipher(passw)
                    NEXT k
    
                NEXT j
            NEXT i
            SLEEP 16000
    END FUNCTION
    FUNCTION decipher(passw AS STRING) AS LONG 'INTEGER  (make functions LONG for more speed where feasible)
    'FUNCTION decipher(passwLong AS long) AS long           'make all LONG's that you can, LONG's are fastest
        STATIC encryptBase AS STRING, oneTimeOnly AS LONG
        LOCAL passWpos, ii AS LONG
        LOCAL z AS LONG 'DIM z AS INTEGER (again, LONG's are best)
    '    DIM t AS STRING
    '    t =""
         LOCAL encrypt AS STRING
    '    DIM s1 AS STRING
    '    DIM s2 AS STRING
    '    DIM s3 AS STRING
    '    DIM s4 AS STRING
    '    DIM s5 AS STRING
    '    DIM s6 AS STRING
    '    DIM s7 AS STRING
    '    DIM s8 AS STRING
    '    DIM s9 AS STRING
    '    DIM s10 AS STRING
    '    DIM s11 AS STRING
    '    DIM s12 AS STRING
    '    DIM s13 AS STRING
    '    DIM s14 AS STRING
    '    DIM s15 AS STRING
    '    DIM s16 AS STRING
    '    DIM s17 AS STRING
    '    DIM s18 AS STRING
    '    DIM s19 AS STRING
    '    DIM s20 AS STRING
    '    DIM s21 AS STRING
    '    DIM s22 AS STRING
    '    DIM s23 AS STRING
    '    DIM s24 AS STRING
    '    DIM s25 AS STRING
    '    DIM s26 AS STRING
    '    DIM s27 AS STRING
    '    DIM s28 AS STRING
    IF oneTimeOnly = 0 THEN 'only make the base encrypted string once
       oneTimeOnly = 1
    'make s an array rather than a bunch of numbered s variables:
    DIM s(1 TO 28) AS STRING
        'turn base encrypted string into bytes without commas, so we don't have to find the next encrypted byte using
        'the INSTR function in every iteration of the main loop:
        s(1) = CHR$(79,59,12,2,79,35,8,28,20,2,3,68,8,9,68,45,0,12,9,67,68,4,7,5,23,27,1,21,79,85,78,79,85,71,38,10,71,27,12,2)
        s(2) = CHR$(79,6,2,8,13,9,1,13,9,8,68,19,7,1,71,56,11,21,11,68,6,3,22,2,14,0,30,79,1,31,6,23,19,10,0,73,79,44,2,79,19,6)
        s(3) = CHR$(28,68,16,6,16,15,79,35,8,11,72,71,14,10,3,79,12,2,79,19,6,28,68,32,0,0,73,79,86,71,39,1,71,24,5,20,79,13,9,79)
        s(4) = CHR$(16,15,10,68,5,10,3,14,1,10,14,1,3,71,24,13,19,7,68,32,0,0,73,79,87,71,39,1,71,12,22,2,14,16,2,11,68,2,25,1,21)
        s(5) = CHR$(22,16,15,6,10,0,79,16,15,10,22,2,79,13,20,65,68,41,0,16,15,6,10,0,79,1,31,6,23,19,28,68,19,7,5,19,79,12,2,79,0)
        s(6) = CHR$(14,11,10,64,27,68,10,14,15,2,65,68,83,79,40,14,9,1,71,6,16,20,10,8,1,79,19,6,28,68,14,1,68,15,6,9,75,79,5,9,11)
        s(7) = CHR$(68,19,7,13,20,79,8,14,9,1,71,8,13,17,10,23,71,3,13,0,7,16,71,27,11,71,10,18,2,29,29,8,1,1,73,79,81,71,59,12,2,79)
        s(8) = CHR$(8,14,8,12,19,79,23,15,6,10,2,28,68,19,7,22,8,26,3,15,79,16,15,10,68,3,14,22,12,1,1,20,28,72,71,14,10,3,79,16,15)
        s(9) = CHR$(10,68,3,14,22,12,1,1,20,28,68,4,14,10,71,1,1,17,10,22,71,10,28,19,6,10,0,26,13,20,7,68,14,27,74,71,89,68,32,0,0)
        s(10) = CHR$(71,28,1,9,27,68,45,0,12,9,79,16,15,10,68,37,14,20,19,6,23,19,79,83,71,27,11,71,27,1,11,3,68,2,25,1,21,22,11,9,10)
        s(11) = CHR$(68,6,13,11,18,27,68,19,7,1,71,3,13,0,7,16,71,28,11,71,27,12,6,27,68,2,25,1,21,22,11,9,10,68,10,6,3,15,27,68,5,10)
        s(12) = CHR$(8,14,10,18,2,79,6,2,12,5,18,28,1,71,0,2,71,7,13,20,79,16,2,28,16,14,2,11,9,22,74,71,87,68,45,0,12,9,79,12,14,2,23)
        s(13) = CHR$(2,3,2,71,24,5,20,79,10,8,27,68,19,7,1,71,3,13,0,7,16,92,79,12,2,79,19,6,28,68,8,1,8,30,79,5,71,24,13,19,1,1,20,28)
        s(14) = CHR$(68,19,0,68,19,7,1,71,3,13,0,7,16,73,79,93,71,59,12,2,79,11,9,10,68,16,7,11,71,6,23,71,27,12,2,79,16,21,26,1,71,3,13)
        s(15) = CHR$(0,7,16,75,79,19,15,0,68,0,6,18,2,28,68,11,6,3,15,27,68,19,0,68,2,25,1,21,22,11,9,10,72,71,24,5,20,79,3,8,6,10,0,79,16)
        s(16) = CHR$(8,79,7,8,2,1,71,6,10,19,0,68,19,7,1,71,24,11,21,3,0,73,79,85,87,79,38,18,27,68,6,3,16,15,0,17,0,7,68,19,7,1,71,24,11,21)
        s(17) = CHR$(3,0,71,24,5,20,79,9,6,11,1,71,27,12,21,0,17,0,7,68,15,6,9,75,79,16,15,10,68,16,0,22,11,11,68,3,6,0,9,72,16,71,29,1,4,0)
        s(18) = CHR$(3,9,6,30,2,79,12,14,2,68,16,7,1,9,79,12,2,79,7,6,2,1,73,79,85,86,79,33,17,10,10,71,6,10,71,7,13,20,79,11,16,1,68,11,14)
        s(19) = CHR$(10,3,79,5,9,11,68,6,2,11,9,8,68,15,6,23,71,0,19,9,79,20,2,0,20,11,10,72,71,7,1,71,24,5,20,79,10,8,27,68,6,12,7,2,31,16,2)
        s(20) = CHR$(11,74,71,94,86,71,45,17,19,79,16,8,79,5,11,3,68,16,7,11,71,13,1,11,6,1,17,10,0,71,7,13,10,79,5,9,11,68,6,12,7,2,31,16,2)
        s(21) = CHR$(11,68,15,6,9,75,79,12,2,79,3,6,25,1,71,27,12,2,79,22,14,8,12,19,79,16,8,79,6,2,12,11,10,10,68,4,7,13,11,11,22,2,1,68,8,9)
        s(22) = CHR$(68,32,0,0,73,79,85,84,79,48,15,10,29,71,14,22,2,79,22,2,13,11,21,1,69,71,59,12,14,28,68,14,28,68,9,0,16,71,14,68,23,7,29)
        s(23) = CHR$(20,6,7,6,3,68,5,6,22,19,7,68,21,10,23,18,3,16,14,1,3,71,9,22,8,2,68,15,26,9,6,1,68,23,14,23,20,6,11,9,79,11,21,79,20,11,14)
        s(24) = CHR$(10,75,79,16,15,6,23,71,29,1,5,6,22,19,7,68,4,0,9,2,28,68,1,29,11,10,79,35,8,11,74,86,91,68,52,0,68,19,7,1,71,56,11,21,11,68)
        s(25) = CHR$(5,10,7,6,2,1,71,7,17,10,14,10,71,14,10,3,79,8,14,25,1,3,79,12,2,29,1,71,0,10,71,10,5,21,27,12,71,14,9,8,1,3,71,26,23,73,79)
        s(26) = CHR$(44,2,79,19,6,28,68,1,26,8,11,79,11,1,79,17,9,9,5,14,3,13,9,8,68,11,0,18,2,79,5,9,11,68,1,14,13,19,7,2,18,3,10,2,28,23,73,79)
        s(27) = CHR$(37,9,11,68,16,10,68,15,14,18,2,79,23,2,10,10,71,7,13,20,79,3,11,0,22,30,67,68,19,7,1,71,8,8,8,29,29,71,0,2,71,27,12,2,79,11)
        s(28) = CHR$(9,3,29,71,60,11,9,79,11,1,79,16,15,10,68,33,14,16,15,10,22,73)
    
        encryptBase = BUILD$(s(1),s(2),s(3),s(4),s(5),s(6),s(7),s(8),s(9),s(10),s(11),s(12),s(13),s(14),s(15),s(16),s(17),s(18),s(19),s(20),s(21),s(22),s(23),s(24),s(25),s(26),s(27),s(28))
     END IF
        encrypt = encryptBase
    '    encrypt = s1+s2+s3+s4+s5+s6+s7+s8+s9+s10+s11+s12+s13+s14+s15+s16+s17+s18+s19+s20+s21+s22+s23+s24+s25+s26+s27+s28
    
       'now we can use a FOR/NEXT loop instead of WHILE INSTR(encrypt... because we know exactly the string length
    '    WHILE INSTR(encrypt, ",") > 0
       passWpos = 1   'this will keep track of which of the 3 letter positions of password to XOR
       FOR ii = 1 TO LEN(encrypt)
    '     z =  VAL(LEFT$(encrypt,INSTR(encrypt,",")-1))XOR ASC(LEFT$(passw,1))
    
        'no longer need to do above VAL conversions because they were done all at once making encrypBase, so:
         z =  ASC(encrypt, ii) XOR ASC(passW, passWpos)
    
    !'--------------------------------------------------------------------------------------------------------------
    !'OK here is the red flag: additive string concatenation. Try to avoid whenever possible, which is almost always.
    '     t += CHR$(z) << try never to do this because it gets VERY slow VERY fast
    '     rather than that, try this for example: use the string var encrypt which has already been made:
          ASC(encrypt, ii) = z
    '     note: the two lines above could be combined to ASC(encrypt, ii) = ASC(encrypt, ii) XOR ASC(passW, passWpos)
    !'OK end of the red flag: additive string concatenation.  Try to avoid whenever possible, which is almost always.
    !'--------------------------------------------------------------------------------------------------------------
    
    '    encrypt =RIGHT$(encrypt,LEN(encrypt)- INSTR(encrypt,",")) << also very slow, but not needed now because
                                                                     'ii counter keeps track of position on encrypt.
    
    '    passw = RIGHT$(passw,LEN(passw)-1)+ LEFT$(passw,1)
         INCR passWpos
         IF passWpos = 4 THEN passWpos = 1 'reset to 1 if it exceeds 3
    
       NEXT
    '    WEND
    '     z = VAL(encrypt)XOR ASC(LEFT$(passw,1)) << done already above
    '     t+=CHR$(z)
         IF INSTR(encrypt," the ")> 0 THEN
            PRINT "The password is '" + passw+"'"
            PRINT "The original text was "
            PRINT encrypt
            PRINT "The sum of the ASCII values in the original text is "+ STR$(sum(encrypt))
            WAITKEY$
         ELSE
             decipher = 0
         END IF
         END FUNCTION
    FUNCTION sum(st AS STRING) AS LONG
        DIM c AS LONG
        DIM i AS INTEGER
        c = 0
        FOR i = 1 TO LEN(st)
            c+= ASC(MID$(st,i,1))
        NEXT i
        sum = c
    END FUNCTION

    Leave a comment:


  • Manuel Valdes
    replied
    Volker:

    It's quite easy to read a complete .TXT as shown below. Also, you can add a flag, to exit the process once the password was found.

    Best regards,


    Code:
     
    #COMPILE EXE
    #DIM ALL
    
    GLOBAL FLG AS INTEGER
     
    FUNCTION PBMAIN () AS LONG
     DIM passw AS STRING, a AS STRING, i AS LONG, j AS LONG, k AS LONG
     FLG=0
     FOR i = 97 TO 122
      FOR j = 97 TO 122
       FOR k = 97 TO 122
        passw = CHR$(i)+CHR$(j)+CHR$(k)
        decipher(passw)
        IF FLG=1 THEN EXIT FOR
       NEXT k
       IF FLG=1 THEN EXIT FOR
      NEXT j
      IF FLG=1 THEN EXIT FOR
     NEXT i
     WAITKEY$
    END FUNCTION
     
    FUNCTION decipher(passw AS STRING) AS INTEGER
     DIM z AS LONG, t AS STRING, encrypt AS STRING
     t =""
     OPEN "CIPHER1.TXT" FOR BINARY AS #1
      GET$ #1,LOF(1),encrypt
     CLOSE 1
     WHILE INSTR(encrypt, ",") > 0
      z =  VAL(LEFT$(encrypt,INSTR(encrypt,",")-1))XOR ASC(LEFT$(passw,1))
      t += CHR$(z)
      encrypt =RIGHT$(encrypt,LEN(encrypt)- INSTR(encrypt,","))
      passw = RIGHT$(passw,LEN(passw)-1)+ LEFT$(passw,1)
     WEND
     z = VAL(encrypt) XOR ASC(LEFT$(passw,1))
     t+=CHR$(z)
     IF INSTR(t," the ")> 0 THEN
      PRINT "The password is '" + passw+"'"
      PRINT "The original text was "
      PRINT t
      PRINT "The sum of the ASCII values in the original text is "+ STR$(sum(t))
      FLG=1
     ELSE
      decipher = 0
     END IF
    END FUNCTION
     
    FUNCTION sum(st AS STRING) AS LONG
     DIM c AS LONG, i AS LONG
     c = 0
     FOR i = 1 TO LEN(st)
      c+= ASC(MID$(st,i,1))
     NEXT i
     sum = c
    END FUNCTION

    Leave a comment:


  • Volker Vanoni
    replied
    Re: problem59

    your code is very instructive but "heavy duty" for a newcomer. For example, I never have touched assembler code and pointers. There is a lot to do. The code is very fast!
    I like Euler problems,too. To solve some of them with my modest tools is meaningful for me and there is much fun and learning by doing.
    Thank you.
    Volker

    Leave a comment:


  • John Gleason
    replied
    I kind of enjoy these Euler problems. Below I do it with LONG's rather than strings. It could be made much faster by just decoding a small part of the encrypted string, and looking for unprintable chrs, then if found, move on without decoding the whole 1200 chrs.
    Code:
    #COMPILE EXE
    #DIM ALL
    
    FUNCTION PBMAIN () AS LONG
    
       GOTO byStr
       encryptedStr: '!db is easiest way to enter the below data as it was formatted given to us
         !db 79,59,12,2,79,35,8,28,20,2,3,68,8,9,68,45,0,12,9,67,68,4,7,5,23,27,1,21,79,85,78,79,85,71,38,10,71,27,12,2
         !db 79,6,2,8,13,9,1,13,9,8,68,19,7,1,71,56,11,21,11,68,6,3,22,2,14,0,30,79,1,31,6,23,19,10,0,73,79,44,2,79,19,6
         !db 28,68,16,6,16,15,79,35,8,11,72,71,14,10,3,79,12,2,79,19,6,28,68,32,0,0,73,79,86,71,39,1,71,24,5,20,79,13,9,79
         !db 16,15,10,68,5,10,3,14,1,10,14,1,3,71,24,13,19,7,68,32,0,0,73,79,87,71,39,1,71,12,22,2,14,16,2,11,68,2,25,1,21
         !db 22,16,15,6,10,0,79,16,15,10,22,2,79,13,20,65,68,41,0,16,15,6,10,0,79,1,31,6,23,19,28,68,19,7,5,19,79,12,2,79,0
         !db 14,11,10,64,27,68,10,14,15,2,65,68,83,79,40,14,9,1,71,6,16,20,10,8,1,79,19,6,28,68,14,1,68,15,6,9,75,79,5,9,11
         !db 68,19,7,13,20,79,8,14,9,1,71,8,13,17,10,23,71,3,13,0,7,16,71,27,11,71,10,18,2,29,29,8,1,1,73,79,81,71,59,12,2,79
         !db 8,14,8,12,19,79,23,15,6,10,2,28,68,19,7,22,8,26,3,15,79,16,15,10,68,3,14,22,12,1,1,20,28,72,71,14,10,3,79,16,15
         !db 10,68,3,14,22,12,1,1,20,28,68,4,14,10,71,1,1,17,10,22,71,10,28,19,6,10,0,26,13,20,7,68,14,27,74,71,89,68,32,0,0
         !db 71,28,1,9,27,68,45,0,12,9,79,16,15,10,68,37,14,20,19,6,23,19,79,83,71,27,11,71,27,1,11,3,68,2,25,1,21,22,11,9,10
         !db 68,6,13,11,18,27,68,19,7,1,71,3,13,0,7,16,71,28,11,71,27,12,6,27,68,2,25,1,21,22,11,9,10,68,10,6,3,15,27,68,5,10
         !db 8,14,10,18,2,79,6,2,12,5,18,28,1,71,0,2,71,7,13,20,79,16,2,28,16,14,2,11,9,22,74,71,87,68,45,0,12,9,79,12,14,2,23
         !db 2,3,2,71,24,5,20,79,10,8,27,68,19,7,1,71,3,13,0,7,16,92,79,12,2,79,19,6,28,68,8,1,8,30,79,5,71,24,13,19,1,1,20,28
         !db 68,19,0,68,19,7,1,71,3,13,0,7,16,73,79,93,71,59,12,2,79,11,9,10,68,16,7,11,71,6,23,71,27,12,2,79,16,21,26,1,71,3,13
         !db 0,7,16,75,79,19,15,0,68,0,6,18,2,28,68,11,6,3,15,27,68,19,0,68,2,25,1,21,22,11,9,10,72,71,24,5,20,79,3,8,6,10,0,79,16
         !db 8,79,7,8,2,1,71,6,10,19,0,68,19,7,1,71,24,11,21,3,0,73,79,85,87,79,38,18,27,68,6,3,16,15,0,17,0,7,68,19,7,1,71,24,11,21
         !db 3,0,71,24,5,20,79,9,6,11,1,71,27,12,21,0,17,0,7,68,15,6,9,75,79,16,15,10,68,16,0,22,11,11,68,3,6,0,9,72,16,71,29,1,4,0
         !db 3,9,6,30,2,79,12,14,2,68,16,7,1,9,79,12,2,79,7,6,2,1,73,79,85,86,79,33,17,10,10,71,6,10,71,7,13,20,79,11,16,1,68,11,14
         !db 10,3,79,5,9,11,68,6,2,11,9,8,68,15,6,23,71,0,19,9,79,20,2,0,20,11,10,72,71,7,1,71,24,5,20,79,10,8,27,68,6,12,7,2,31,16,2
         !db 11,74,71,94,86,71,45,17,19,79,16,8,79,5,11,3,68,16,7,11,71,13,1,11,6,1,17,10,0,71,7,13,10,79,5,9,11,68,6,12,7,2,31,16,2
         !db 11,68,15,6,9,75,79,12,2,79,3,6,25,1,71,27,12,2,79,22,14,8,12,19,79,16,8,79,6,2,12,11,10,10,68,4,7,13,11,11,22,2,1,68,8,9
         !db 68,32,0,0,73,79,85,84,79,48,15,10,29,71,14,22,2,79,22,2,13,11,21,1,69,71,59,12,14,28,68,14,28,68,9,0,16,71,14,68,23,7,29
         !db 20,6,7,6,3,68,5,6,22,19,7,68,21,10,23,18,3,16,14,1,3,71,9,22,8,2,68,15,26,9,6,1,68,23,14,23,20,6,11,9,79,11,21,79,20,11,14
         !db 10,75,79,16,15,6,23,71,29,1,5,6,22,19,7,68,4,0,9,2,28,68,1,29,11,10,79,35,8,11,74,86,91,68,52,0,68,19,7,1,71,56,11,21,11,68
         !db 5,10,7,6,2,1,71,7,17,10,14,10,71,14,10,3,79,8,14,25,1,3,79,12,2,29,1,71,0,10,71,10,5,21,27,12,71,14,9,8,1,3,71,26,23,73,79
         !db 44,2,79,19,6,28,68,1,26,8,11,79,11,1,79,17,9,9,5,14,3,13,9,8,68,11,0,18,2,79,5,9,11,68,1,14,13,19,7,2,18,3,10,2,28,23,73,79
         !db 37,9,11,68,16,10,68,15,14,18,2,79,23,2,10,10,71,7,13,20,79,3,11,0,22,30,67,68,19,7,1,71,8,8,8,29,29,71,0,2,71,27,12,2,79,11
         !db 9,3,29,71,60,11,9,79,11,1,79,16,15,10,68,33,14,16,15,10,22,73,0,0,0,0,0,0,0,0  ;add padding 0's for extra POKE room
        byStr:
    
        LOCAL ii, ii2, ii3, ii4, wsPtr AS LONG, encrypStr, workString AS STRING
        DIM passWord(17575) AS LONG '26^3 - 1
    
        encrypStr = PEEK$(CODEPTR(encryptedStr), 1200) 'make a string out of the above data
    
        'make permutations now of all lowercase XOR passwords
        FOR ii = &h61 TO &h7a '<<26 lowercase letters
           FOR ii2 = &h61 TO &h7a
              FOR ii3 = &h61 TO &h7a
                 passWord(ii4) = ii + &h100 * ii2 + &h10000 * ii3
                 INCR ii4
              NEXT
           NEXT
        NEXT
    
        'decrypt string now with each password then check for " the "
        FOR ii2 = 0 TO 17575
           workString = encrypStr
           wsPtr = STRPTR(workString)
           FOR ii = 0 TO 399                  'string is 1200 chrs long, so 400 * 3 will decode it
              POKE LONG, wsPtr + 3 * ii, PEEK(LONG, wsPtr + 3 * ii) XOR password(ii2)
           NEXT
           IF INSTR(workString, " the ") THEN
              ? MKL$(password(ii2))
              ? workString
              WAITKEY$
           END IF
        NEXT
    
    END FUNCTION

    Leave a comment:


  • Stanley Durham
    replied
    ...or a library for linked lists using strings?

    Leave a comment:


  • Volker Vanoni
    started a topic Euler problem 59

    Euler problem 59

    Hello,
    attached there is a brute force solution of Problem 59- Project Euler.net .
    The result is correct. I worked with strings which surely are seldom used to solve such problems. It would be nice to show me another way. In addition I am not able to read in "cipher1.txt" using PowerBasic .
    Is anybody interested to work with me on Euler problems or a library for linked
    lists using strings? If I am not allowed to ask this, simply ignore it.
    greetings
    Volker
    Attached Files
Working...
X