Euler problem 59

[Volker Vanoni]

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

[Stanley Durham]

...or a library for linked lists using strings?

[John Gleason]

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.

#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

[Volker Vanoni]

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

[Manuel Valdes]

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,

 
#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

[John Gleason]

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)

#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