Tutorial 4: Crossword puzzles

Exercise 1: Split off the type

Let us now start writing a program that reads in files of the form described above. As a first step, we want to split off the type of a line from the rest and return both parts as a tuple. For both parts of this tuple your function should eliminate leading and trailing spaces ' '.

Copy the following function stub into your file and complete it:

def split_type(line):
    """Splits off the first word in the line and returns both parts in a tuple.
    Also eliminates all leading and trailing spaces.
    Example:
        split_type('ROW ##.##') returns ('ROW', '##.##')
        split_type('CLUE (0,1) down: Of or pertaining to the voice (5)') returns
            ('CLUE', '(0,1) down: Of or pertaining to the voice (5)')
        split_type('  ROW    ##.##   ') returns ('ROW', '##.##')

    """
    pass # remove this line and replace with your own code

Hints

• you can find the starting position of the first occurence of a string m inside a string s by calling s.index(m).
• s.strip() returns a copy of the string in which all chars given as the argument have been stripped from the beginning and the end of the string. If no argument is given, as a default all whitespace characters at the beginning and the end are stripped, for example:

In [1]: s = 'aabbabbaaa'

In [2]: s.strip('a')
Out[2]: 'bbabb'

Testing

Now, test your function split_type() in the console, for example as follows:

In [3]: split_type('ROW ##.##')
Out[3]: ('ROW', '##.##')

In [4]: split_type('CLUE (0,1) down: Of or pertaining to the voice (5)')
Out[4]: ('CLUE', '(0,1) down: Of or pertaining to the voice (5)')

In [5]: split_type('  ROW    ##.##   ')
Out[5]: ('ROW', '##.##')

In [6]: split_type('  CLUE (3,4) down: Not off (2)   ')
Out[6]: ('CLUE', '(3,4) down: Not off (2)')

Note: It is important to test your function in the console before submitting your file on the automatic grader system because in the practical exam, this will be your only way to test your code, as you will not have access to the grader system and hence you will not get live feedback after your submit your code.

Once your function is behaving correctly, you can upload your file crossword.py:

Exercise 2: Reading Rows

In a next step, you will write a function read_row() that interprets an individual line of the type 'ROW'. We assume that the type has already been split off by split_type() as above, and thus there are also no leading or trailing spaces.

Copy the following function stub into your file and complete it:

def read_row(row):
    """Reads a row of a crossword puzzle and construct the corresponding
    list of boxes.
    Each '#' represents a blocked box.
    Letters 'A', ..., 'Z' and 'a', ..., 'z' correspond to filled boxes
    (all letters are capitalized before inserting into boxes).
    All other characters stand for empty boxes, which are represented
    by a single space ' ' in the list.
    Examples:
        read_row('#.#') gives ['#', ' ', '#']
        read_row('C.T') gives ['C', ' ', 'T']
        read_row('cat') gives ['C', 'A', 'T']
    """
    pass # remove this line and replace with your own code

Hints:

• You can test if a string s is a letter of the alphabet using its method s.isalpha(), which returns True iff s is non-empty and all its characters are letters.
• Note that read_row() should capitalize all letters it finds. Remember that the capitalized version of a string can be computed using the .upper() method: e.g. 'a'.upper() returns 'A'.
• Remember that you can iterate over the characters in a string just as you iterate over the entries of a list. For example, you can do the following in the console:

In [7]: for c in 'xyz':
    ...:     print(c)
    ...:     
x
y
z

Testing

When you have completed your function read_row(), test it in the console, for example as follows:

In [8]: read_row('#.#')
Out[8]: ['#', ' ', '#']

In [9]: read_row('C.T')
Out[9]: ['C', ' ', 'T']

In [10]: read_row('d_g:')
Out[10]: ['D', ' ', 'G', ' ']

In [11]: read_row('  ')
Out[11]: [' ', ' ']

Once your function looks correct, upload your file crossword.py:

Exercise 3: Reading coordinates

We are going to start parsing clues. As a stepping stone, you are going to write function coord_to_ints() converting a string containing coordinates to a pair of integers.

Copy and complete the following function stub:

def coord_to_ints(coordstring):
    """Reads a string in the form '(x,y)' (where x and y are strings
    representing integer values) and return the corresponding pair
    of integers (x, y).
    Example: coord_to_ints('(0,1)') returns (0, 1)
    """
    pass # remove this line and replace with your own code

You can use the following guarantees on the input to your coord_to_ints function:

1. there are no spaces between the parentheses;
2. the numbers are integers (not floats);

Note: both x and y can be integers of arbitrary size (in particular, they may both have several digits).

Testing

When you have finished your function coord_to_ints, test it in the console. You should see the following behavior:

In [12]: coord_to_ints('(0,1)')
Out[12]: (0, 1)

In [13]: coord_to_ints('(1135,17005)')
Out[13]: (1135, 17005)

In [14]: coord_to_ints('(8,800)')
Out[14]: (8, 800)

Can you think of some original tests yourself?

Once your function looks correct, upload your file crossword.py for further automatic testing:

Exercise 4: Reading clues

Having read the rows of the crossword puzzle, in the next step we want to read the clues. They are given in the following form:

• first the starting position (i,j) as a pair of integers,
• then, after a space, the direction given as the string across or down,
• then :, followed by the question, and
• finally, after another space, the length as an integer in parentheses ( and ).

Copy and complete the following function stub:

def read_clue(cluestring):
    """Reads a clue into a tuple in the following way:
    The input is of the form
        '(x,y) direction: question (length)'
    where x, y and length are integers, direction is 'across' or 'down'
    and question is the text of the clue.
    The output should then be
        ((x, y), direction, length, question)
    where (x, y) is a tuple of ints and length is an int.
    Example:
        read_clue('(0,1) down: Of or pertaining to the voice (5)') returns
        ((0, 1), 'down', 5, 'Of or pertaining to the voice')
    There may be arbitrarily many spaces in the input.
    """
    pass # remove this line and replace with your own code

You can use the following guarantees on the input to your function cluestring:

1. there is only one colon (which might be helpful to split the input);
2. there are no parentheses except those containing the starting position and those containing the length;

Note that both x, y, and length can be arbitrary-sized integers (in particular, they may all have several digits).

Hint: There are many ways to solve this exercise, but the possibly simplest is just to use str.index() to find the relevant parts of the string, one by one, and then slice the string as you go along.

Hint: Remember, you can split a string with respect to any separator of your choosing and not just spaces. str.split('bunny') is a valid call:

In [15]: s = 'dogbunnycat'

In [16]: s.split('bunny')
Out [16]: ['dog', 'cat']

Testing

When you have finished your function read_clue, test it in the console. You should be able to reproduce the following behavior:

In [17]: read_clue('(0,1) down: Of or pertaining to the voice (5)')
Out[17]: ((0, 1), 'down', 5, 'Of or pertaining to the voice')

In [18]: read_clue('(1135,17005)   across:    Longest English word    (45)')
Out[18]: ((1135, 17005), 'across', 45, 'Longest English word')

Once your function looks correct, upload your file crossword.py:

Exercise 5: Reading input files

We now have all the functions we need to be able to read input files. It essentially only remains to open a file and give each of its lines to the function corresponding to the line’s type. We want the output to be a tuple consisting of two elements:

• first a list rows containing the rows of the puzzle described in the files as read by read_row(),
• second a list clues containing the clues as read by read_clue().

Copy and complete the following function stub:

def read_file(filename):
    """Open the puzzle file with the given filename and create a pair
    consisting of a puzzle grid (a list of rows) and a list of clues.
    The rows and clues may be interleaved arbitrarily in the file.
    """
    pass # remove this line and replace with your own code

Testing

Test your function in the console using the provided test puzzle files. You should get the following behavior:

In [19]: read_file('tinypuzzle.txt')
Out[19]: ([[' ']], [((0, 0), 'down', 1, 'A')])

In [20]: read_file('smallpuzzle.txt')
Out[34]:
([[' ', '#'], ['#', ' ']], [((0, 0), 'down', 1, 'A'), ((1, 1), 'across', 1, 'B')])

Also test your function on puzzle1.txt, puzzle2.txt, and puzzle7x7.txt.

Once your function looks correct, upload your file crossword.py:

Exercise 6: Creating clue strings

We now have everything in place to read descriptions of crossword puzzles from files. Unfortunately, the format in which we are keeping them (lists of rows and clues) is hard to read for humans, so if we actually want to solve a puzzle, having it in this format is not very helpful. So now we will write functions to better visualize the puzzles, and also to fill in words.

As a first step in this direction, we will write a function that takes a clue tuple (as we have created above) and constructs a string representation of it that we can print to the screen later, if we like. Copy and complete the following function stub:

def create_clue_string(clue):
    """ Given a clue tuple (position, direction, length, question),
    create a string in the form 'position direction: question (length)'.
    For example, given the clue
        ((2, 3), 'across', 4, 'Black bird'),
    this function will return
        '(2,3) across: Black bird (4)'
    """
    pass # remove this line and replace with your own code

Note that the clue string is not printed out, but returned.

Hint: This will be particularly easy if you use f-strings. As an example, try this in the console:

In [21]: tb = 'To Be'

In [22]: on = 'or Not'

In [23]: f'{tb}, {on} {tb}'
Out[24]: 'To Be, or Not To Be'

Testing

Test your function create_clue_string() in the console; for example, you should have the following behavior:

In [25]: create_clue_string(((2, 3), 'across', 4, 'Black bird'))
Out[25]: '(2,3) across: Black bird (4)'

(Note: there is no space in the (2,3) part of the output.)

Once your function is behaving correctly, upload your file crossword.py:

Exercise 7: Creating puzzle strings

We now want to write a function that will give a complete string representation of a puzzle that we can print out on the screen. Since visualizing the grid part is somewhat messy, we give you a function create_grid_string below which does this job.

Copy (and don’t change) the following function into your file crossword.py:

def create_grid_string(grid):
    """Return a crossword grid as a string."""
    size = len(grid)
    separator = '  +' + ('-----+')*size
    column_number_line = '   '
    column_number_line += ''.join(f' {j:2}   ' for j in range(size))
    result = f'{column_number_line}\n{separator}\n'
    for (i, row) in enumerate(grid):
        fill = '  |'
        centre_line = f'{i:2}|'
        for entry in row:
            if entry == '#':
                fill += '#####|'
                centre_line += '#####|'
            else:
                fill += '     |'
                centre_line += f'  {entry}  |'
        result += f'{fill}\n{centre_line}\n{fill}\n{separator}\n'
    return result

Now use create_clue_string() and create_grid_string() to write a function create_puzzle_string() that creates a string representing the puzzle. We expect to see the following behavior:

In [26]: grid, clues = read_file('puzzle1.txt')

In [27]: pstring = create_puzzle_string(grid, clues)

In [28]: print(pstring)
     0     1     2     3     4   
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |#####|
 0|#####|     |#####|     |#####|
  |#####|     |#####|     |#####|
  +-----+-----+-----+-----+-----+
  |     |     |     |     |     |
 1|     |     |     |     |     |
  |     |     |     |     |     |
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |#####|
 2|#####|     |#####|     |#####|
  |#####|     |#####|     |#####|
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |     |
 3|#####|     |#####|     |     |
  |#####|     |#####|     |     |
  +-----+-----+-----+-----+-----+
  |     |     |     |#####|     |
 4|     |     |     |#####|     |
  |     |     |     |#####|     |
  +-----+-----+-----+-----+-----+

(0,1) down: Of or pertaining to the voice (5)
(0,3) down: Nocturnal winged mammals (4)
(1,0) across: Colourful underwater structure formed by colonies of organisms (5)
(3,3) across: Thus (2)
(3,4) down: Not off (2)
(4,0) across: Every (3)

Copy and complete the following function stub:

def create_puzzle_string(grid, clues):
    """Return a human readable string representation of the puzzle."""
    pass # remove this line and replace with your own code

Hint: Be careful not to have a newline at the end of the returned value.

Testing

Test your function in the console and make sure that you can replicate the example above. (Note the extra line between the puzzle and the clues.)

Once your function looks correct, upload your file crossword.py:

Exercise 8: Filling in words

We can now visualize crossword puzzles on the screen that we have read from files. However, we still have no convenient way of filling in solutions. We will take care of this now.

Copy and complete the following function stub:

def fill_in_word(grid, word, position, direction):
    """Create and return a new grid (a list of lists) based on the grid
    given in the arguments, but with the given word inserted according
    to position and direction.
        - direction: is either 'down' or 'across'.
        - position: the coordinates of the first letter of the word in the grid.
    *This function may modify its grid argument!*
    """
    pass # remove this line and replace with your own code

Your function fill_in_word() does not have to check if the word you fill in is legal, i.e., that it fits the grid and that it does not contradict letters filled in before.

Your function may modify its grid argument (this will make the whole operation much simpler), but you still have to return the new/updated grid.

Testing

Test your function fill_in_word() on the console. For example, you should have the following behavior:

In [29]: grid, clues = read_file('puzzle1.txt')

In [30]: fill_in_word(grid, 'ALL', (4,0), 'across')
Out[30]:
[['#', ' ', '#', ' ', '#'],
 [' ', ' ', ' ', ' ', ' '],
 ['#', ' ', '#', ' ', '#'],
 ['#', ' ', '#', ' ', ' '],
 ['A', 'L', 'L', '#', ' ']]

In [31]: print(create_grid_string(grid))
     0     1     2     3     4   
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |#####|
 0|#####|     |#####|     |#####|
  |#####|     |#####|     |#####|
  +-----+-----+-----+-----+-----+
  |     |     |     |     |     |
 1|     |     |     |     |     |
  |     |     |     |     |     |
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |#####|
 2|#####|     |#####|     |#####|
  |#####|     |#####|     |#####|
  +-----+-----+-----+-----+-----+
  |#####|     |#####|     |     |
 3|#####|     |#####|     |     |
  |#####|     |#####|     |     |
  +-----+-----+-----+-----+-----+
  |     |     |     |#####|     |
 4|  A  |  L  |  L  |#####|     |
  |     |     |     |#####|     |
  +-----+-----+-----+-----+-----+

Can you construct some interesting tests of your own?

Once your function looks correct, upload your file crossword.py:

Exercise 9: Creating row strings

As you might have noticed, our implementation of crossword puzzles still has one annoying aspect: when playing with pen and paper, you can at any point put the puzzle aside and continue later. This is so far not possible with our puzzle program: whenever you close python, all your progress is lost. So let us improve the situation by adding a “save” feature.

As a first step, write a function create_row_string that takes as an argument a list representing a valid row and creates a string that represents this row as described for the files above. Represent empty boxes by .. Copy and complete the following function stub:

def create_row_string(row):
    """Returns a row representation of a string.
    Example:
        create_row_string(['#', 'A', ' ']) returns '#A.'
    """
    pass # remove this line and replace with your own code

Hints

• Remember you can use the separator.join() methods of strings to concatenate strings. For example separator.join([string1, string2]) == string1+separator+string2 # True
• Strings are immutable! But you can replace characters in a string by using the .replace(s1,s2) methods of strings which will replace all occurrences of s1 with s2.

Testing

Test your function on the console. For example, you should have the following behavior.

In [32]: create_row_string(['#', 'A', ' '])
Out[32]: '#A.'

Once your function looks correct, upload your file crossword.py:

Exercise 10: Writing the file

It is now time to actually print your partially solved puzzle to a file using our functions create_row_string() and create_clue_string(). To this end, copy and complete the following function stub:

def write_puzzle(filename, grid, clues):
    """Writes the puzzle given by the grid and by the clues to the specified
    file.
    """

• To have a fixed order, we make the convention that all rows should be written to the file before any clues are written.
• If you have already forgotten the file format used in today’s tutorial, re-read the Introduction part of this tutorial.

Hint: You can also use f-strings for writing to files, for example: file.write(f'ROW {row_string}')

Hint: don’t forget to use your create_row_string and create_clue_string functions!

Testing

Test your function write_puzzle in the console by doing the following:

In [33]: grid, clues = read_file('tinypuzzle.txt')

In [34]: write_puzzle('test.txt', grid, clues)

Afterwards, the two files tinypuzzle.txt and test.txt should have exactly the same content.

Now try your function also with smallpuzzle.txt and puzzle1.txt as input.

Once your function looks correct, upload your file crossword.py: