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

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

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

StackExchange Code Review Q#153850, answer score: 2