This course assumes that the student is familiar with imperative programming in Python.

This entails
that the student should know how to deal with variables, expressions, conditions, iterations, functions,
lists, dictionaries, and text files (and hopefully also related concepts such as recursion, sets, and
exceptions). Below are listed multiple exercises on imperative programming. Many of these exercises
are quite challenging, and students should expect to need a considerable amount of time to do them.
The students are supposed to do these exercises in the first three weeks of the course.

The exercises are not graded: the goal of the exercises is to determine how strong the knowledge of the
students is of imperative programming in Python. If the exercises show that the knowledge of students
appears to be lacking, the course can delve deeper into certain topics. It therefore makes no sense to
get solutions to these exercises from the Internet, or from another source which is not you yourself. The
purpose is to find out how far your knowledge and skills reach.
Exercise 1: Text formatting

Write a program that asks for an input text file, an output text file, and an integer to use as column size
(you can use a minimum of 10). Read the input text file, and format the text so that it uses no more
words on each line than fit the column size, e.g., if the column size is 40, no more than 40 characters are
used on each line (this includes punctuation and whitespaces, but excludes the newline character).
Words are not "broken off" (if by chance the file contains a word longer than the column width, you may
simply let that word “stick out”). Write the formatted text to the output text file.

In the input text file, paragraphs are distinguished from each other by an empty line. In the output text
file, you either do the same thing, or you simply go to a new line which you then start with four spaces
(“indent”).

For an extra challenge, try to insert spaces in a balanced way so that the column is justified (i.e., all lines
are equally long, except for those that end a paragraph). Make sure that you can handle column sizes
that are less than the maximum word length.

An example input file that you can use to experiment with is the included file “[Link].”

Concepts: Strings, Lists, Files

In the television game Lingo, the players have to guess a 5-letter word. They start with one letter given,
and then guess words of the correct length. After a guess, any letter that is correct and in the correct
place, is marked (in the television show by drawing a square around the letter). Furthermore, any of the
remaining letters that is in the sought word, which is not in the correct place, is also marked (in the
television show by drawing a circle around the letter). The players have only a limited amount of
attempts available to guess the word (usually 5, which is what will be used for this program).

Write a program that plays Lingo with the user. The program uses a dictionary of legal English words
(the file “[Link],” of which each line consists of one legal English word). The program selects a
word to guess, for instance WATER. It also randomly selects one of the letters that the user gets "for
free," for instance the A in the second spot.

The user then tries to guess the word. Every time, before the user makes a guess, the program displays
the word as far as it is known. This means that it displays the word as a sequence of dashes, one dash for
each letter, except that every letter of which the user knows that it is correct and in the correct spot, is
displayed as the actual letter. This includes the letter that is given away for free. For instance, if the
word is WATER, the A was given away for free, and the user already guessed an R in the last spot, then
the word is displayed as –A--R.

To guess, the user types in a word. The program responds by displaying the guessed word as follows:
Every letter that the word contains that is correct and in the correct place, is displayed as an uppercase
letter. Every letter of the remaining ones that is correct but not in the correct place, is displayed as a
lowercase letter. Finally, all remaining letters are displayed as dashes. For instance, if the word is WATER
and the user guesses BARGE, the program displays -Ar-e.

The guessing continues until the user guesses the word correctly, or uses up all attempts (after which
the program will give the correct answer).

Four rules should be noted: (1) if the user makes a mistake, for instance typing a word that is too long or
too short, or which contains more than only letters, the program gives an error message and the user
can enter a new guess – this does not count as one of the attempts; (2) if the user enters a word which is
not in the English dictionary, but for the rest meets the requirements, then the program gives an error
message, and this DOES count as a guess; (3) the user can enter the word in uppercase or lowercase
letters, or even a mix; (4) if the guess contains multiple copies of the same letter, and the word contains
that letter but fewer of them, only as many copies of the letter as the word contains are marked – for
instance, if the word is WATER and the user guesses APART, then only one of the two A’s is displayed in
the program’s response: a––rt; and (5) a correct letter in the correct place has precedence over a
correct letter which is not in the correct place – for instance, if the word is WATER and the user guesses
RADAR, then the program responds with –A––R (and not –––aR).

For an extra challenge, allow the user to specify the desired word length and maximum number of
guesses at the start of the program.

Concepts: Strings, Lists, Files, possibly Dictionaries

In this exercise we use a rectangular grid. In each of the cells of the grid a number is written. Your goal is
to determine a path that leads from the left of the grid to the right of the grid, of which the numbers in
the cells add up to the highest possible total for the grid.

Imagine that the left side of the grid is “west,” the right side is “east,” the top of the grid is “north,” and
the bottom is “south.” You may start the path in any of the cells at the west end of the grid. The next cell
must be either to the north-east of this cell, or to the east, or to the south-east. From the new cell, again
you may go to the north-east, east, or south-east. You may not move outside the grid. This continues
until you reach a cell at the east end of the grid.

For example, consider the following grid:

4 7 2 9 11
1 0 3 7 9
2 12 5 7 8
3 13 4 2 5

The shaded cells show a possible path through the grid. This path is actually the path that produces the
highest total for the cell values for this grid, namely 38.

Write a program which asks for an input file which contains the description of a grid. This file consists of
the following lines:

 The first line contains a number which indicates the number of rows of the grid.
 The second line contains a number which indicates the number of columns of the grid.
 Each of the next lines describes a row of the grid, from top to bottom. The line contains the
values in the cells, from left to right, with spaces between the values. All values are integers
bigger than or equal to 0.

An example (which describes the grid above) you find in the file “[Link].”

The program produces as output the sum of the values on the path with the highest total (in the
example 39).

Note: For this exercise you should spend some time thinking of a smart way to approach it. Simply
generating all the possible paths is a stupid approach (and will take far too long).

Concepts: Strings, Lists, Files

This exercise consists of a more advanced version of the previous exercise. Again, there is a grid of
numerical values, through which you must determine the path with the highest sum. You may start in
any cell of the grid. The path you must follow is given as a list of compass directions. The directions are
given as letters: E for east, W for west, N for north, and S for south. If east is given, you may move to the
east, to the north-east, or to the south-east. If west is given, you may move to the west, to the north-
west, or to the south-west. If north is given, you may move to the north, to the north-east, or to the
north-west. Finally, if south is given, you may move to the south, to the south-east, or to the south-west.
You may not move outside the grid. The path may cross itself – in that case, you may add the value of a
cell which is on the path multiple times, each time that you reach it.

For instance, consider the following grid:

8 4 5 1 2
6 1 2 4 7
9 5 4 7 6
2 1 0 7 8
9 5 8 7 4

The path is given as: E E S E N E

The optimal path starts with the 8 on the bottom row, and takes the following steps: E, NE, SW, NE, NW,
SE, for a total of 53.

Write a program which asks for an input file which contains the description of a grid. This file consists of
the following lines:

 The first line contains a number which indicates the number of rows of the grid.
 The second line contains a number which indicates the number of columns of the grid.
 Each of the next lines describes a row of the grid, from top to bottom (as many lines as there are
rows). The line contains the values in the cells, from left to right, with spaces between the
values. All values are integers bigger than or equal to 0.
 The next line contains the length of the path.
 The last line contains the compass directions for the path, with spaces in between the letters.
The compass directions are given as E, W, N, and S.

An example (which describes the grid above) you find in the file “[Link].” The program
produces as output the sum of the values on the path with the highest total (in the example 53).

A smaller example (therefore easier to debug) you find in the file “[Link]” (solution is 32). A few more
test files are “[Link]” (solution is 117), “[Link]” (solution is 85), and “[Link]” (no
solution).

Note: If you found a smart solution for the previous exercise, you can use a variation on that solution for
this exercise. However, this particular exercise is by far the hardest of the set.

Concepts: Strings, Lists, Files

The game Solo Noble consists of a board with holes, and pegs placed in the holes. At least one hole is
empty. A typical board is shown below, where each dot is a hole. The start position is usually all holes
being filled with pegs, with only the middle hole empty.
. . .
. . .
. . . . . . .
. . . . . . .
. . . . . . .
. . .
. . .

A legal move in Solo Noble consists of a peg moving to a hole two positions away in an orthogonal
(horizontal or vertical) direction, where there is another peg in the hole that is jumped. The peg which is
jumped is removed from the board. The goal is to remove all pegs (but one) from the board using legal
moves. In the standard game, the final peg is supposed to end up in the center. For instance, below you
see how from a particular start position with 4 pegs on the board, the game is solved.
. . x . . . . . . . . .
. x x . x . . x . . . .
. . . . . x . . . . . x x . . . . x . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . x . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .

Your program processes a text file which consists of exactly 33 characters. Each of these characters is
one position of the Solo Noble board, from left to right, top to bottom. The characters are either a dot,
or an x. As such, the file describes a Solo Noble position according to the examples above, whereby a dot
is a hole, and an x is a peg in a hole. The file “[Link]” is an example (which represents the
leftmost board in the solution above), but your program should be able to process other files which
have these specifications too (more files are delivered with the assignment, and you can make your own
too). The program solves the game from the position given (you may or may not require the last peg to
end up in the center), and prints the steps which comprise the solution. If there is no solution, the
program simply prints a line stating that.

Warning: Trying to solve the board from the initial standard position (which has 32 pegs on the board,
given in the file “[Link]”) might take a very long time. Don’t try it without also
implementing the speed-up indicated below.

A good speedup can be achieved if you store every position that you encounter in your search for a
solution, when you have discovered that no solution is possible for that position, in a dictionary. Then,
when you encounter a new position, first check in the dictionary whether you already know that this
one cannot be solved. For the complete board, the dictionary will grow to a length of about 11,000
entries, which easily fits in memory.

Concepts: Lists, Recursion, Files, Dictionaries