Semi-decide Post's Correspondence Problem

Question

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).

Input:

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

Output:

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

Hint:

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

Answer 1

Python 3, 223 216 199 192 191 189 183 bytes

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

from itertools import*
j=''.join
def f(x):
 for l in count(1):
  for i in product(x,repeat=l):
   *b,=zip(*i);c=j(b[0])
   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

Answer 2

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')

Answer 3

Pyth - 55 43 bytes

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

Old version:

DgGH=TkV`G=+T@c@czdtvN\,H)RT;JZ.VZI>J0B#=J?qgb0gb1bJB;J

Explanation:

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?

Answer 4

Haskell, 260 253 243 230 Bytes

import Data.List
c=concat
x=concatMap
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