The Post's Correspondence Problem (PCP) gives you a list of pairs of strings, P_1 ... P_n. Your task is to find a k, and some sequence of k indices such that fst(P_i1) ... fst(P_ik) = snd(P_i1) ... snd(P_ik)

We're trying to find some sequence of the pairs where the word we build from the first part is equal to the word on the second part. A solution can use any of the pairs any number of times, and in any order.

For example, if our pairs are (0,110), (11,1) and (001,100) , then one solution is the world 11001110, with the solution sequence of 2321:

11 001 11 0
1  100 1  110

Some will have no solution, such as (001, 01), (0001, 01).


An arbitrary number of words, separated by spaces. Each word is of the format seq1,seq2 where each seq1 and seq2 are strings consisting only of 0 or 1, of arbitrary length.

Example: the above examples would have the following formats:

0,110 11,1 001,110

001,01 0001,01


If there is some sequence of the pairs which solves the PCP, output the word of the solution, followed by a space, followed by the sequence. The pairs are numbered starting at 1.

If there is no such sequence, run forever. (The problem is undecidable, so this will have to do).

Example output

11001110 2321

# second example never halts


This is Turing Complete, so you're going to have to use some sort of infinite search.

  • 5
    \$\begingroup\$ The usual term is "recognize". \$\endgroup\$
    – xnor
    Commented Jul 21, 2016 at 1:04

4 Answers 4


Python 3, 223 216 199 192 191 189 183 bytes

Thanks to @KarlKastor for pointing out that I could use count

from itertools import*
def f(x):
 for l in count(1):
  for i in product(x,repeat=l):
   if c==j(b[1]):print(c,j(str(x.index(k)+1)for k in i));return

A function that takes input of a tuple of pairs of strings x in the form ((seq1,seq2),(seq1,seq2)...) and prints the output to STDOUT in the same format as the test cases.

To continuously output solutions rather than just one solution, remove the return statement.

How it works

The function generates all l-length arrangements of the string pairs using product, with l being initialised at 1. This list is then unpacked and transposed using zip; this leaves a two-element list, where the first element contains all the first strings in the pairs, and the second all the second strings in the pairs. Each element is concatenated to a string using join; if these are the same, we have a hit and the string is printed to STDOUT. The sequence of pair indices is then generated by looking up each pair in the original arrangement using index; these indices are concatenated to a string, and also printed to STDOUT. If no solution exists for that l, l is incremented and the process repeated.

Try it on Ideone

  • 2
    \$\begingroup\$ was going to post an extremly similar solution in Python3, but you beat me to it \$\endgroup\$
    – KarlKastor
    Commented Jul 21, 2016 at 13:43
  • 1
    \$\begingroup\$ damn, posted mine because it was 3 bytes shorter, but then you updated yours. btw try if you can get it shorter by using for i in count() instead of while 1:i=len(x);i+=1, also why start counting at len(x)? \$\endgroup\$
    – KarlKastor
    Commented Jul 21, 2016 at 14:07
  • \$\begingroup\$ i wrote "i" instead of "l", but meant your "l" \$\endgroup\$
    – KarlKastor
    Commented Jul 21, 2016 at 14:16
  • \$\begingroup\$ @KarlKastor Of course! I had forgotten about count. As for starting at len(x), I'm not quite sure what I was thinking. \$\endgroup\$ Commented Jul 21, 2016 at 15:35
  • 1
    \$\begingroup\$ I shouldn't have helped you, now your bytecount is lower :p \$\endgroup\$
    – KarlKastor
    Commented Jul 21, 2016 at 16:05

Python 2, 220 215 203 199 195 193 187 bytes

from itertools import*
def f(p,o="".join):
 h=lambda s:o(x[s]for x in j)
 for i in count(1):
  for j in product(p,repeat=i):
   if h(0)==h(1):print h(0),o(`p.index(k)+1`for k in j);return

example use:

>>> f([("0","110"),("11","1"),("001","100")])
('11110', '221')

Pyth - 55 43 bytes

Msm@c@cz\ tvd\,H`G;.VZI>Z0B#=Z?qgb0gb1bZB;Z

Old version:



M                           #define a function g(G,H)
 s                          #join and return the following
  m             `G;         #for each char d in str(G): 
     @cz\ tvd               #split input on " " and get the element at index int(d)-1
   @c        \,H            #split that on "," and get the element at index H    

.VZ                  ;      #for b from 0 to infinity
        #             B     #try
         =Z?       bZ       #set var Z (which defaults to 0) to b if
            qgb0gb1         #g(b,0) is equal to g(b,1)
   I>Z0B                    #if Z>0, break
                       Z    #print Z

This program iterates from 0 to infinity. Each value is split digit by digit and that sequence is checked to see if it is valid. There is a try block so any sequences that go out of range are ignored, but considering how many sequences contain indexes that go out of bounds, this algorithm is painfully inefficient. But since when is code golf about efficiency?


Haskell, 260 253 243 230 Bytes

import Data.List
l p=x(\n->sequence$replicate n[0..length p -1])[1..]
i p=map(unzip.(map(p!!)))$l p
f p=x(show.(+1))(a l)++" "++(c$fst$a i)
 where a e=e p!!((\(Just x)->x)$findIndex(\x->c(fst x)==c(snd x))$i p)

use like: f([("0","110"),("11","1"),("001","110")])

This could probably be A LOT shorter, but what the hell...

-10 bytes thanks to @jmite

-13 by replacing fromJust with lambda


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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