Assignment 17 - Post's Correspondence Problem

You can download this homework and set the permissions with the commands

      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment17.html
      chmod 755 *.html

Outline
Post's Correspondence Problem consists of two arrays of words, the first array and the second array. Both arrays have the same length, but the words in it can be of different length. A correspondence is a list of indices which tell how to arrange the elements of the arrays such that both give the same word. Examples can be found in the last lecture, note that the indexing of arrays starts in Java Script with 0.

(a)   Position         (0)     (1)     (2)     (3)      (4)
      First Array      abb     a       bab     baba     aba
      Second Array     bbab    aa      ab      aa       a

      Correspondence 1  1, 0, 0,  3,   0,  4
      First word        a abb abb baba abb aba
      Second word       aa bbab bbab aa bbab a

      Correspondence 2  1, 0, 4
      First word        a abb aba
      Second word       aa bbab a
                        (Thanks to Ryan Flynn for finding this one)

(b)   Position        (0)     (1)     (2)     (3)      (4)
      First Array     a       aa      aba     aabb     abb
      Second Array    b       ba      bba     bbba     bba

      No correspondence exists

Since this problem is unsolvable, it is impossible to write an algorithm which checks the existence of a correspondence. Nevertheless, one can check whether there is a correspondence of a given length. This should be implemented in this exercise.

What has to be done in detail
The function searchcorrespondence has to be implemented. It obtains two inputs: firstarray, secondarray and indexarray which are the parameters defining Post's Correspondence Problem and the array which will carry the correspondence. The length of this array is already given. The implementation should cover two aspects:

It should list all existing correspondences of the given length. For example, if indexarray is (0,0,0,0) and there are five columns, then the algorithm should check for all entries (a,b,c,d) with a,b,c,d in {0,1,2,3,4} whether these values of index array define a solution. The easiest way is to go in lexicographic order through all these possibilities.
Furthermore, the search is sometimes lengthy. Therefore it should be shortened in those cases where it is obvious that one cannot generate an entry. If in the case of the first example, all entries of the form (1,2,*,*) are impossible as the first row will start with "aplanacanal" and the second with "lanacanalpa" which cannot be matched to any matching correspondence.

One can use the function printcorrespondence(firstarray,secondarray,indexarray) to print the existing solutions and also analyze this function in order to get an idea of how to test for correspondences. The function to be edited is the function "subsearch" which is called from "correspondencesearch". Here it comes with a parameter $k$ which says that indexarray[k] is now the variable which has to be set. The function subsearch should call itself with all possible values inserted at indexarray[k]. That means, for any possible choice h, the following should be done:

indexarray[k] should take the value h;
the function should be called with the value firstword+firstarray[h] instead of firstword, secondword+secondarray[h] instead of secondword, k+1 instead of k.

Furthermore, please optimize your solution. That is, do not make such a call if it can be eaisly seen that whatever will be done, it will not lead to a match. This optimization will speed up the processing of the search much.

Java Script starts here.

Java Script ends here.