# COSC345 Assignment 4 — Cracker U

## Student number:

Code Cracker is a puzzle that appears in the Otago Daily Times. It is like a crossword, in that it is a rectangular area with words running horizontally and vertically, which you have to recover from clues. There is a mapping from the integers 1–26 to the letters A–Z which you have to recover. You are given the answer for some of the numbers.

This program works by using a large dictionary of English words. It takes each clue in turn, and finds all the dictionary words of the right length that are consistent with that clue and with what's already been solved. If there are no such words, we're out of luck. (This can happen because the word you need is not in the dictionary.) If there's exactly one such word, we've solved that clue completely and can cross it off. If there's more than one such word, we glean what we can (e.g., if it could be CLANGER or CLINGER then at least it's CL-NGER, but we'll have to finish it later.

• Is this the first, second, or third program you looked at? (Put a circle around one.)
• Write the time:

• Read the Cracker listing until you feel that you have a rough idea of what is going on.
• Write the time:

• Take a break if you like.
• Write the time:

• The input to the program has three parts. What are they, and in what order?
1.

2.

3.

• There is a magic number in this program. What is its value, what does it signify, and do you think it is big enough?
1.

2.

3.

• Is this program certain to terminate in a finite time? If so, can you give a simple bound in terms of the sizes of the inputs. If not, can you explain why?

• Write the time:

• Take a break if you want one.
• Write the time:

• There are supposed to be two mistakes in this program. What are they?

• Write the time: