# Assignment 18 - Post's Correspondence Problem

1. Getting Started

Please refer to this page for information on how to work on your assignment.

2. 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 JavaScript 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.

3. What has to be done in detail

The `searchcorrespondence()` function has to be implemented. It obtains three 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 `printcorrespondence(firstarray, secondarray, indexarray)` function 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 `subsearch()` function 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 `subsearch()` function should call itself with all possible values inserted at `indexarray[k]`. It means that 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 a lot.

JavaScript Starts Here.
JavaScript Ends Here.