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:

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: 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:

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.

Grading

Grading: 8 points for correctly running code. 2 points for well-written code. A programming assignment count equally with a problem set in computing the overall grade.

Late policy

Programming assignments due at the beginning of class on the due date. I will accept assignments late with a penalty of 1 point out of 10 for each week late (fractions of a week are rounded up.)