Assignment 1 factorial_base

Assignment 1
COMP9021
1. General matters
1.1. Aims. The purpose of the assignment is to:
• let you design solutions to simple problems;
• let you implement these solutions in the form of short python programs;
• practice the use of arithmetic computations, tests, repetitions, lists, tuples, dictionnaries, deques, reading
from files.
1.2. Submission. Your programs will be stored in a number of files, with one file per exercise, of the appropriate
name. After you have developed and tested your programs, upload your files using WebCMS. Assignments can
be submitted more than once: the last version is marked. Your assignment is due by April 10, 11:59pm.
1.3. Assessment. Each of the 4 exercises is worth 2.5 marks. For all exercises, the automarking script will let
each of your programs run for 30 seconds. Still you should not take advantage of this and strive for a solution
that gives an immediate output for “reasonable” inputs.
Late assignments will be penalised: the mark for a late submission will be the minimum of the awarded mark
and 10 minus the number of full and partial days that have elapsed from the due date.
The outputs of your programs should be exactly as indicated.

2
2. Factorial base
Write a program, stored in a file named factorial_base.py, that performs the following task.
• Prompts the user to input a nonnegative integer. If the input is not a nonnegative integer, then the
program outputs an error message and exits.
• Outputs the conversion of that number in “factorial base”: a number written in factorial base is of the
form dk . . . d1 with di ≤ i for all 1 ≤ i ≤ k, and its decimal value is dk × k! + · · · + d1 × 1!. For instance,
the decimal value of 2301 read in factorial base is 2 × 4! + 3 × 3! + 0 × 2! + 1 × 1! = 67.
Here is a sample run of the program.
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : 12 a
I n c o r r e c t input , gi vi n g up . . .
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : 12 13
I n c o r r e c t input , gi vi n g up . . .
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : −3
I n c o r r e c t input , gi vi n g up . . .
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : 67
Decimal 67 r e a d s a s 2301 i n f a c t o r i a l b a se .
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : 2301
Decimal 2301 r e a d s a s 310311 i n f a c t o r i a l b a se .
$ python3 f a c t o r i a l b a s e . py
Inpu t a n o n n e g a ti v e i n t e g e r : 310311
Decimal 310311 r e a d s a s 75354211 i n f a c t o r i a l b a se .
3
3. Rubik’s rectangle
Write a program, stored in a file named rubiks_rectangle.py, that performs the following task.
• Prompts the user to input the digits 1 to 8 (with possibly whitespace inserted anywhere), in some order,
say d1 d2 d3 d4 d5 d6 d7 d8, without repetition; if the input is incorrect, then the program outputs an
error message and exits.
• Finds the minimal number of steps needed to go from the initial state, represented as
1 2 3 4
8 7 6 5
to the final state, represented as
d1 d2 d3 d4
d8 d7 d6 d5
following a sequence of transformations named row exchange, right circular shift and middle clockwise
rotation, that transform a configuration of the form
k1 k2 k3 k4
k8 k7 k6 k5
into
– for row exchange:
k8 k7 k6 k5
k1 k2 k3 k4
– for right circular shift:
k4 k1 k2 k3
k5 k8 k7 k6
– for middle clockwise rotation:
k1 k7 k2 k4
k8 k6 k3 k5
For instance, if the final configuration is 26845731 then 7 steps are sufficient (and necessary):
– Initial configuration
1 2 3 4
8 7 6 5
– followed by right circular shift
4 1 2 3
5 8 7 6
– followed by middle clockwise rotation
4 8 1 3
5 7 2 6
– followed by row exchange
5 7 2 6
4 8 1 3
– followed by right circular shift
6 5 7 2
3 4 8 1
– followed by middle clockwise rotation
6 4 5 2
3 8 7 1
– followed by middle clockwise rotation
6 8 4 2
3 7 5 1
– followed by right circular shift
2 6 8 4
1 3 7 5
which is the final configuration.
4
• Outputs the number of steps needed to reach the final configuration (this is always possible), using a
message whose grammatical form depends on whether the number of steps is 0 or 1, or at least 2.
Here is a sample run of the program.
$ python3 r u b i k s r e c t a n g l e . py
Inpu t f i n a l c o n f i g u r a t i o n : 01234567
I n c o r r e c t c o n fi g u r a ti o n , gi vi n g up . . .
$ python3 r u b i k s r e c t a n g l e . py
Inpu t f i n a l c o n f i g u r a t i o n : 12345678
0 s t e p i s needed t o r e ac h the f i n a l c o n f i g u r a t i o n .
$ python3 r u b i k s r e c t a n g l e . py
Inpu t f i n a l c o n f i g u r a t i o n : 2 6 8 4 5 7 3 1
7 s t e p s a r e needed t o r e a c h the f i n a l c o n f i g u r a t i o n .
$ python3 r u b i k s r e c t a n g l e . py
Inpu t f i n a l c o n f i g u r a t i o n : 7215 4368
16 s t e p s a r e needed t o r e ac h the f i n a l c o n f i g u r a t i o n .
$ python3 r u b i k s r e c t a n g l e . py
Inpu t f i n a l c o n f i g u r a t i o n : 1 5 3 2 4 6 7 8
18 s t e p s a r e needed t o r e ac h the f i n a l c o n f i g u r a t i o n .
Hint: Use collections.deque
5
4. A word game
Write a program, stored in a file named highest_scoring_words.py, that performs the following task.
• Prompts the user to input between 3 and 10 lowercase letters (with possibly whitespace inserted anywhere); if the input contains too few or too many lowercase letters or any character which is neither a
lowercase letter nor whitespace, then the program outputs an error message and exits.
• Finds in the file wordsEn.txt, assumed to be stored in the working directory, the words built from the
letters input by the user (with the exclusion of any other character) with highest score, if any; the score
of a word is defined as the sum of the values of the letters that make up that word, the value of each
letter being defined as follows:
a 2 b 5 c 4 d 4 e 1 f 6
g 5 h 5 i 1 j 7 k 6 l 3
m 5 n 2 o 3 p 5 q 7 r 2
s 1 t 2 u 4 v 6 w 6 x 7
y 5 z 7
• Outputs a specific message if there is no such word; otherwise, outputs the highest score and all words
with that score, one word per line, with a different introductory message depending on whether there
is a unique such word (in which case the introductory message is on the same line as the word) or at
least two such words (in which case the introductory message is on a line of its own and all words are
preceded with 4 spaces).
Here is a sample run of the program.
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : a b c 2 e f
I n c o r r e c t input , gi vi n g up . . .
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : ab
I n c o r r e c t input , gi vi n g up . . .
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : a b c d e f g hi j k
I n c o r r e c t input , gi vi n g up . . .
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : zz zz zz
No word i s b u i l t from some o f t h o s e l e t t e r s .
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : a a a
The hi g h e s t s c o r e i s 2 .
The hi g h e s t s c o r i n g word i s a
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : a e i o u
The hi g h e s t s c o r e i s 8 .
The hi g h e s t s c o r i n g words are , i n a l p h a b e t i c a l o r d e r :
i o u
o ui
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : prmgroa
The hi g h e s t s c o r e i s 2 4.
The hi g h e s t s c o r i n g word i s program
6
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : a b e o r a t
The hi g h e s t s c o r e i s 1 6.
The hi g h e s t s c o r i n g word i s ab a t o r
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : r a m m o x y
The hi g h e s t s c o r e i s 1 7.
The hi g h e s t s c o r i n g words are , i n a l p h a b e t i c a l o r d e r :
mayor
moray
moxa
oryx
$ python3 h i g h e s t s c o r i n g w o r d s . py
Enter between 3 and 10 l o w e r c a s e l e t t e r s : e ae o rtsmn
The hi g h e s t s c o r e i s 1 7.
The hi g h e s t s c o r i n g words are , i n a l p h a b e t i c a l o r d e r :
matrons
transom
7
5. Overlapping photographs
Write a program, stored in a file named perimeter.py, that performs the following task.
• Prompts the user to input the name of text file assumed to be stored in the working directory. We
assume that if the name is valid then the file consists of lines all containing 4 integers separated by
whitespace, of the form x1 y1 x2 y2 where (x1, y1) and (x2, y2) are meant to represent the coordinates
of two opposite corners of a rectangle. With the provided file frames_1.txt, the rectangles can be
represented as follows, using from top bottom the colours green, yellow, red, blue, purple, olive, and
magenta.
We assume that all rectangles are distinct and either properly overlap or are disjoint (they do not touch
each other by some of their sides or some of their corners).
• Computes and outputs the perimeter of the boundary, so with the sample file perimeter.py, the sum
of the lengths of the (external or internal) sides of the following picture.
Here is a sample run of the program with the two provided sample files.
$ python3 p e rim e t e r . py
Which data f i l e do you want t o u se ? f r am e s 1 . t x t
The p e rim e t e r i s : 228
$ python3 p e rim e t e r . py
Which data f i l e do you want t o u se ? f r am e s 2 . t x t
The p e rim e t e r i s : 9090