Announcement

Collapse
No announcement yet.

Euler problem 59

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

  • 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

  • #2
    ...or a library for linked lists using strings?
    stanthemanstan~gmail
    Dead Theory Walking
    Range Trie Tree
    HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

    Comment


    • #3
      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

      Comment


      • #4
        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

        Comment


        • #5
          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

          Comment


          • #6
            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

            Comment

            Working...
            X