3
\$\begingroup\$

I am trying to Bruteforce a PCP that is supposed to be up to the length 300.

I wrote a little Python program that is doing just that but it could take forever until my program finds the right PCP.

import sys

x1 = "aba"
x2 = "a"
x3 = "bab"
y1 = "a"
y2 = "ab"
y3 = "abaa"

def ternary(n):
    if n == 0:
        return ''
    else:
        e = n//3
        q = n%3
        return ternary(e) + str(q)

x = 1; 

while True:
    ter = ternary(x)
    ter = ("%01d" % (float(ter),))
    #print("ter = " + str(ter))
    wordx = ""
    wordy = ""
    for i in range(0, len(str(ter))):
        if(str(ter)[i] == '0'):
            wordx = wordx + x1
        if(str(ter)[i] == '1'):
            wordx = wordx + x2
        if(str(ter)[i] == '2'):
            wordx = wordx + x3
    for j in range(0, len(str(ter))):
        if(str(ter)[j] == '0'):
            wordy = wordy + y1
        if(str(ter)[j] == '1'):
            wordy = wordy + y2
        if(str(ter)[j] == '2'):
            wordy = wordy + y3

    print(ter)


    if wordx == wordy:
        print("Wordx = " + wordx + " and wordy = " + wordy + " and the decimal number is = " + str(x) + " and the ternary number is = " + str(ter))
        sys.exit("Yes!")
    x+=1

Useful Information about PCP's: https://en.wikipedia.org/wiki/Post_correspondence_problem

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you explain what a PCP is? \$\endgroup\$ – 200_success Jan 28 '17 at 18:39
  • \$\begingroup\$ Sure! See I have these variables at the top (x1,x2,x3,y1,y2,y3). So the Turing Machine that is running a PCP like that only accepts inputs, that generate the same input with my x and my y variables. So for example I type 112 into my Turing Machine the word produced by my x's would be: abaabaa And my word produced by the y's would be: aaab Which are not the same. So my task is it to find a PCP (number of inputs for that Turing Machine) that is accpetable (in this case the PCP is somewhere below 300) Hope u dont mind the link: en.wikipedia.org/wiki/Post_correspondence_problem \$\endgroup\$ – userlip Jan 28 '17 at 18:45
  • \$\begingroup\$ You should edit the question to include that information. Comments are not supposed to be permanent. \$\endgroup\$ – Graipher Jan 28 '17 at 20:56
  • \$\begingroup\$ So does your program actually work ? \$\endgroup\$ – Josay Jan 29 '17 at 10:40
  • \$\begingroup\$ Yes it does i just had to make some little changes regarding the leading zeroes \$\endgroup\$ – userlip Jan 29 '17 at 10:42
2
\$\begingroup\$

Many thing can be improved to make your code faster and clearer:

Multiple useless calls to str

You keep calling str on ter which is a string already. You can replace every occurence of "str(ter)" by "ter".

The 2 loops with (apparently) different loop indices can be written in a single loop

Unless I am missing something, the 2 loops could be written with a single loop.

Loop like a native

I highly recommend watching Ned Batchelder's excellent talk "Loop like a native". In a nutshell, any time you use range and len together, there is a better way to do it.

In your case, after taking the comment above, the code becomes :

for c in ter:
    if c == '0':
        wordx = wordx + x1
    if c == '1':
        wordx = wordx + x2
    if c == '2':
        wordx = wordx + x3
    if c == '0':
        wordy = wordy + y1
    if c == '1':
        wordy = wordy + y2
    if c == '2':
        wordy = wordy + y3

Similar conditions

You have the same conditions evaluated twice. You could group them together.

elif

You could use elif between your mutually exclusive cases.

+=

You could use a += b instead of a = a+b.

Then your code becomes:

for c in ter:
    if c == '0':
        wordx += x1
        wordy += y1
    elif c == '1':
        wordx += x2
        wordy += y2
    elif c == '2':
        wordx += x3
        wordy += y3

Single value provided to %

Instead of builting a tuple with a single value via "%01d" % (float(ter),), you could directly write "%01d" % float(ter).

Loop like a native again

Instead of writing a while True to loop over integers, you could use itertools.count.

import itertools
for x in itertools.count(1):
    ter = "%01d" % float(ternary(x))

divmod

A builtin called divmod does exactly what your are doing in your ternary function.

Final code

Many things can still be improved but here is my current version of the code:

import sys
import itertools

x1 = "aba"
x2 = "a"
x3 = "bab"
y1 = "a"
y2 = "ab"
y3 = "abaa"

def ternary(n):
    if n == 0:
        return ''
    else:
        e, q = divmod(n, 3)
        return ternary(e) + str(q)

for x in itertools.count(1):
    ter = "%01d" % float(ternary(x))
    #print("ter = " + ter)
    wordx = ""
    wordy = ""
    for c in ter:
        if c == '0':
            wordx += x1
            wordy += y1
        elif c == '1':
            wordx += x2
            wordy += y2
        elif c == '2':
            wordx += x3
            wordy += y3

    if wordx == wordy:
        print("Wordx = " + wordx + " and wordy = " + wordy + " and the decimal number is = " + str(x) + " and the ternary number is = " + ter)
        sys.exit("Yes!")
\$\endgroup\$
  • \$\begingroup\$ Thank you very much! The code works really well but I still have one question :P Is there a way to add exactly 1 leading zero to the number ter ? Because as soon as the number gets bigger the "%01d" wont add a leading zero anymore (I tested) \$\endgroup\$ – userlip Jan 29 '17 at 11:15
  • \$\begingroup\$ I would definitely use either str.format or the fact that print can take multiple arguments for that final print... \$\endgroup\$ – Graipher Jan 29 '17 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.