## Programming Assignment 1

Assigned: Sep. 7.
Due: Sep. 28

#### The Post correspondence problem

The POST CORRESPONDENCE PROBLEM is defined as follows: You are given a collection of dominos. Each domino has a string of characters on top and another string on the bottom. (Both strings are non-empty.) You can make as many copies of the dominos as you need. The problem is to place the dominos side by side so that the combination of the strings on the top is the same as the combination of the strings on the bottom.

Example: Domino D1 has string ``aa'' on top and string ``aaa'' on bottom; domino D2 has strings ``bba'' and ``b''; and domino D3 has strings ``a'' and ``abba''. Then the string of dominos D2, D2, D3, D1 spells out the same string ``bbabbaaaa'' on both top and bottom.

The Post correspondence problem is, surpringly, only semi-decidable. If there is an answer then, obviously, one can find it by exhaustive search; however, there is no algorithm that always terminates and that always answers correctly whether or not an instance of the problem has a solution. The problem can be characterized in terms of the following state space:

• A state is a sequence of dominos where either the top string is a prefix of the bottom string or the bottom string is a prefix of the top. For example, the sequence D2,D2 is a state since the bottom "bb" is a prefix of the top "bbabba". The sequence D2,D1 is not a state because the top is "bbaaa" and the bottom is "baaa" and neither is a prefix of the other.
• The successors to D1 ... Dk are constructed by adding another domino at the end, if that leads to a legitimate state.
• The start state is the empty sequence of dominos.
• The goal state is a non-empty sequence of dominos where the top string and bottom string are equal.

#### Assignment

Write a program that solves the Post correspondence problem using iterative deepening through the state space of problem 2.

#### Input

Your code should accept the following inputs:
• A. A maximum depth to search.
• B. The set of dominos.
Both A and B must be settable at run-time; there will be a deduction of 4 points out of 10 for any program that hard codes them.

You may use an input file (or terminal input) of the following form:
First line: Maximum depth to search.
Second line: Number of dominos.
Remaining lines: 1 line per domino; each line contains the domino number and the two strings. You may assume a maximum of 20 characters per domino and a maximum of 20 dominos. You may assume that the input is correctly formatted and conforms to the maximums; you need not do error checking.

For instance, consider the following problem: domino D1 has string ``bb" on top and string ``b'' on bottom; domino D2 has strings ``a'' and ``aab'' and domino D3 has strings ``abbba'' and ``bb''. The input for this problem might be

```10
3
1 bb b
2 a aab
3 abbba bb
```

#### Output

The output consists of two parts:

Part 1: The number of states generated at each successive level of the search space.

Part 2: The solution. This has one of the following three forms:

• The sequence of dominos that solve the problem.
• The message "No solution exists."
• The message "No solution was found within the limits of search."
For instance, the state space for the above problem has the following form:
```empty -----> D1 -----> D1,D1 -----> D1,D1,D1 -----> D1,D1,D1,D1
|    bb        bbbb    |   bbbbbb      |   bbbbbbbb
|    b         bb      |   bbb         |   bbbb
|                      |               |
|                      |               |--> D1,D1,D1,D3
|                      |                    bbbbbbabbba
|                      |                    bbbbb
|                      |
|                      |--> D1,D1,D3  Fails
|                           bbbbabbba
|                           bbbb
|
|--> D2 -----> D2,D2  Fails
a    |    aa
aab  |    aabaab
|
|--> D2,D3 -----> D2,D3,D2 -----> D2,D3,D2,D1 Succeeds
aabbba       aabbbaa         aabbbaabb
aabbb        aabbbaab        aabbbaabb
```
The output is therefore:
```Level 0:  1 state
Level 1:  2 state
Level 2:  3 states
Level 3:  3 states
Level 4:  3 states
Solution: D2,D3,D2,D1. aabbbaabb.
```
At the last level, the count should be the number of states up to and including the solution state, but should not include states on the bottom level to the right of the solution state.

If the maximum depth of search were specified as 2 on the first line of the input file, then the output would be

```Level 0:  1 state
Level 1:  2 state
Level 2:  3 states
No solution was found within the limits of search.
```

#### Alternative format for I/O

If you want to use another format for I/O --- e.g. you want to use window-based input or you want to set up a little GUI with pictures of dominos --- that's OK, as long as you explain it clearly to the grader.

#### Coding

Programs will be accepted in C, C++, or Java. If you wish to write programs in other languages, you should discuss that with the grader. Be sure that the program runs either on the department Sun system or on the University PC system.

#### Submit

The source code and a README file explaining how to compile and run your code.