Lab session 5: Imperative Programming
This is the 5th lab of a series of weekly programming labs. You are required to solve these
programming exercises and submit your solutions to the automatic assessment system Themis.
The system is 24/7 online. Note that the weekly deadlines are very strict (they are given for the
CET time zone)! If you are a few seconds late, Themis will not accept your submission (which
means you failed the exercise). Therefore, you are strongly advised to start working on the
weekly labs as soon as they appear. Do not postpone making the labs! You can find Themis via
the url https://themis.housing.rug.nl
The theme of this lab is recursion. Each problem must be solved using recursion! The
teaching assistants will (after the deadline) manually check the submissions that are accepted
by Themis. If a passed program does not make use of recursion, then the scored
points are subtracted by the teaching assistants.
Problem 1: Quadratic Sums
The number 142 can be written as a sum of squares of positive integers in 7 different ways:
142 = 12 + 22 + 42 + 112
= 12 + 42 + 52 + 62 + 82
= 12 + 42 + 52 + 102
= 22 + 32 + 42 + 72 + 82
= 22 + 52 + 72 + 82
= 32 + 42 + 62 + 92
= 52 + 62 + 92
In these sums, a square is used at most once (i.e. a sum containing a sub expression of the form
a
2 + a
2
is not allowed). Moreover, the order of the terms is irrelevant (so 2
2 + 52
and 5
2 + 22
are
considered to be the same expression).
Write a program that accepts on its input an integer n (where 1 ≤ n ≤ 1600), and outputs in
how many different ways n can be expressed as a sum of squares of positive integers.
Problem 2: Zipping Strings
The input of this exercise consists of a non-negative integer n, and three strings consisting of
uppercase letters from the alphabet (without spaces, tabs, etc.). The objective is to determine
whether the third string can be produced from the first two strings by zipping the first two strings
in such a way that the order of the letters of both strings is preserved. Moreover, it is allowed to
insert at most n auxiliary letters. The output of your program should be YES if this is possible,
and NO otherwise. You may assume that each string consists of at most 32 letters.
For example, if we are allowed to insert one auxiliary letter, then we can produce the string
PROGRAMMING from the strings PROM and GAMING as follows:
The array a is given and consists of positive integers that satisfy 1 ≤ a[i] ≤ 20 for all i.
Moreover, the given b satsifies 1 ≤ b ≤ 100. We want to know the number of solutions of the
above equation, where all x[i] are non-negative integers.
For example, the equation 5 · x[0] + 7 · x[1] + 9 · x[2] + 11 · x[3] = 42 has 9 unique solutions:
The input of this problem is a single line that starts with an integer n (the number of coeffi-
cients) folowed by a colon (:). You may assume that 1 ≤ n ≤ 10. Next, there are n coefficients
a[i]. The input is terminated with the value b (the right hand side of the equation). The output
of your program must be the number of solutions of the given equation.
Problem 4: Grid Colouring Puzzle
In this problem we consider a colouring puzzle for a 9 × 9 grid of cells. Cells must be coloured
with one of the colours RED, GREEN, BLUE, YELLOW, or WHITE. Given a grid in which
some cells have been coloured already, the puzzle is to colour the remaining cells such that no
cell has a neighbour (north, east, south, west) with the same colour. Moreover, in each row or
column no colour may appear more than twice.
The input for this problem is a grid of 9 × 9 characters. We use the letters ’R’, ’G’, ’B’,
’Y’, and ’W’ to denote coloured cells, and ’#’ to denote empty (non-coloured) cells. The
output of your program must be the solution of the puzzle, or ’NO SOLUTION’ if no solution
exists. You may assume that a puzzle has at most one solution.