# Bruteforcing PCP's in Python

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


• Could you explain what a PCP is? – 200_success Jan 28 '17 at 18:39
• 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 – userlip Jan 28 '17 at 18:45
• You should edit the question to include that information. Comments are not supposed to be permanent. – Graipher Jan 28 '17 at 20:56
• So does your program actually work ? – Josay Jan 29 '17 at 10:40
• Yes it does i just had to make some little changes regarding the leading zeroes – userlip Jan 29 '17 at 10:42

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.

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!")

• 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) – userlip Jan 29 '17 at 11:15
• I would definitely use either str.format or the fact that print can take multiple arguments for that final print... – Graipher Jan 29 '17 at 20:55