Python Exercises
This is a collection of programming examples and problems in Python. These exercises are intended to develop basic algorithmic programming skills.
ciao!
how could we possibly talk about programming without the ubuquitous “Hello world!” program?
Solution: here
minmax
Write a program that reads a sequence of numbers from the standard input, with one or more numbers per line, and prints the minimum and the maximum values in the list. For example, with this input:
10 15 7 9 1 3
The output must be as follows:
min=1 max=15
Solution: here
flipline
Write a program that reads a line of text from the standard input, and prints that line on the standard output in reverse, that is, flipped right-to-left. For example, with this input:
1 2 3 ciao
The output must be as follows:
oaic 3 2 1
Solution: here
pi
Write a program that reads a positive integer \(N\) as a command-line argument, and prints the value of the function \(\pi(i)\) for every positive \(i < N\), where \(\pi(i)\) is the number of prime numbers that are less than or equal to \(i\).
For example, with the following invocation
./pi.py 10
The output must be as follows:
1 0 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 4 10 4
Solution: here
histogram
Write a program that reads a list of non-negative numbers from the standard input, with one number per line, and prints a histogram corresponding to those numbers. In this histogram, each number \(x\) is represented by a line of \(x\) characters “#”. For example, with this input:
10 15 7 9 1 3
The output must be as follows:
########## ############### ####### ######### # ###
Solution: here
vertical histogram
Write a program that reads a list of numbers \(n\) from the standard
input, with one or more numbers per line, and prints a vertical
histogram corresponding to those numbers. In this histogram, each
number \(x\) is represented by a column of \(x\) characters # starting
from a base-line of \(n\) dash characters - representing value 0.
Positive numbers are represented by a column above zero while negative
numbers are represented with a column below zero.
For example, with this input:
7 3 -2 10 5 -3 3 5 8
The output must be as follows:
#
#
# #
# # #
# # #
# ## ##
# ## ##
## ## ###
## ## ###
## ## ###
---------
# #
# #
#
Solution: here
compress
Write a program that reads a sequence of space-separated values
from the input and outputs a "compressed"; version of the input
sequence. The compression is obtained by transforming a sequence of
three or more identical elements as \(X\) * \(N\), where
\(X\) is the element and \(N\) is the number of consecutive copies of
\(X\).
For example, with this input:
-1 1 1 1 7 7 7 7 5 5 1 1 4 1
The output should be
-1 1 * 3 7 * 4 5 5 1 1 4 1
Solution: here
longest identical sequence
Given a sequence of integers \(A = a_{1},a_{2},...,a_{n}\), a maximal identical sequence is a sequence of adjacent identical values \(v=a_{i}=a_{i+1}=a_{i+2}=...= a_{i+k}\) of maximal length \(k\). Write a program that reads an input sequence \(A\), with one or more numbers per line, and outputs the value of the first (leftmost) maximal identical sequence in \(A\).
For example, with this input:
8 -2 3 3 4 4 4 2 2 2 3 -2 3 3 3 3 4 4 4 8 2 2 8 2 2 22 2 22 22 2 2 22 8
the output must be
3
Solution: here
commonword
Write a program that reads a text file from the standard input and outputs the most common word in the input. The words in the input are the maximal-length sequences of alphabetic characters. So, a word does not include spaces or punctuation characters. If two or more words appear more often, the program may print any one of them.
For example, if the input is this:
What is free software? "Free software" is a matter of liberty, not price. To understand the concept, you should think of "free" as in "free speech", not as in "free beer". Free software is a matter of the users' freedom to run, copy, distribute, study, change and improve the software.
then the output should be this:
free
Solution: here
character frequencies
Write a program that reads a text file from the standard input, and prints the list of all characters present in the input followed by the number of times the character appears in the input.
Solution: here
character frequencies 2
Write a variant of the “character frequencies” program described above that outputs all the characters in reverse order of frequency (i.e., from the highest to the lowest frequency count).
Solution: here
word frequencies
Write a program that reads a text file from the standard input and prints the list of all the words in the text file, each followed by the number of times the word occurs in the text. Words in the input are the maximal-length sequences of alphabetic characters (e.g., a-z). So, a word does not include spaces or punctuation characters.
Solution: here
shortest least common word
Write a program that reads a list of words from the standard input, with one word per line, and prints any one of the shortest words among those that appear least often.
Solution: here
largest cluster
Write a program that reads a list of numbers from the standard input, with one or more numbers per line separated by spaces on each line, and prints the largest cluster of extension \(D\). The parameter \(D\) is a number that may be given as the first command-line argument. If the parameter is not specified, the default value is \(D=10\). A cluster of extension \(D\) is a list of all the elements taken from the input list that are within a distance of at most \(D\) from each other. For example, if the input sequence is \(12, 2, 34, 7, 21, 24, 50, 45, -9, 7, 45\), and if \(D=10\), then the output should contain the numbers \(12, 2, 7, 7\) because those numbers form a cluster of extension \(10\), and no other cluster of extension \(10\) contains more than \(4\) elements.
Solution: here
count inversions
Write a program that reads a sequence of numbers from the standard input, with one or more numbers per line separated by spaces on each line, and prints the number of inversions in the sequence. In a sequence \(A=[a_{1},a_{2},...,a_{n}]\), an inversion is a pair \(a_{i},a_{j}\) such that \(i < j\) and \(a_{i} > a_{j}\).
Solution: here
roman numeral
Write a program that takes a number \(N\) (a positive integer) in decimal notation from the console, and prints its value as a roman numeral.
Solution: here
prime factors
Write a program that reads a positive integer \(n\) from the
console or from the command line, and outputs its prime factorization.
For example, for \(n=2312\), the program should output 2^3 17^2, and for
\(n=10242311\) the output should be 19 701 769.
Solution: here
maximal regular sequence
Write a program that, given \(n\) numbers read from the standard input, outputs the maximal length of a regular sequence built with those \(n\) numbers. A regular sequence \(x_1,x_2,\ldots x_k\) is such that \(x_1\le x_2\le \cdots\le x_k\) and \(x_2 - x_1 = x_3 - x_2 = \ldots x_k-x_{k-1}\). For example, with the input:
14 22 5 16 10 34 35 23 51 28 0
The program should output
5
Because there is a regular sequence of 5 elements (\(10, 16, 22, 28, 34\)) but there isn’t one of 6 or more elements.
check sudoku
Write a program that reads nine lines from the input each containing
nine numbers between 1 and 9, representing a sudoku puzzle. The
program should output Correct if the input represents a valid
sudoku.
For example, with the following input, the output should be Correct:
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8
Conversely, while with the this input, the output shoudl be Incorrect:
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 9 5 8 7 1 9 6 7 8 6 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 5 1 2 3 4 7 6 9 8
here, and whenever the given input is incorrect, the program should also indicate at least one row, or column, or 3x3 sub-matrix that violates the rules of sudoku.
Solution: here
maze
Write a program that prints a maze generated at random like this one:
/\//\////\\\\/\\\\/\\\\//\//////\/\//\//\/\\/\/\\\////\\//\\ /\\/\/\\\\\\\//\\//\\\/////\//\////\///\///\////\//\\///\/\/ /\//\\///\//\//\/\\\\\\\\\////\/\\/\\\//\\/////\\\/\\\\\\/// \\\\/\\/////\\//\//\\\//\//\//\\\//\\\\///\/\/\/\///\\\/\/\/ \\////\\\\\\/////\\\\\/\/\//\\\//\/\\//\/\\/\/\\\////\\\/\/\ /\//\//\/\//////\\/\/////////\\/\/////////\\\\/\/\\//\/\\/// /\\\\\//\\/\/\///\/\///\/\////\\//\\\\/\///\\\////\\\\\\//\\ //\//\\///\////\/\//\////\\/\/\\\\\////\///\///\////\\//\/// ///\\/\//\\/\\/\/\\\\\///\//\\/\///\/\\\\\//\///\/\\////\/\/ \//\//\\\/\///////\///\\\\////\///\\//\/\\\\//\\/\//\/\\\/\/ /\\/////\//\/\\/\\\//\\/\///\\///\\\//////\\/\//\\\/\\\\\/\\ \\/\\\\///\////\\\\\\\\\\/\\\//\//\\\\\/\/\\\///\\\\/\////\/ /\\//\\////\/\///\//\///\///\////\/\//\/\\///\\/////\/\//\\\ \//\\\//\/\\\////\////\///\////\//\/\//\/\\//\\/\\\//\/\/\\\ \/\/\//\\/\/\/\\/\\/\/\////\\/\\/\//////\///\///\//\/\///\\\ //\\//\\\\\\\///\//\\/\/\\\\\/\/\//\/\\\\\/\/\\//\\////\\\\/ //\//\/\//\\/\//\/\///\//\/\\\\/\/\/\\\\\///\\\\/////\////\/ /\\////\//\/\///\\/\/\/\\///\\\\\\//\\/\/\\\\\//\//\//\\//\\ \//\///////\/\\//\/\\\/\/\\\\///\\\\/\///\\/\/\///\\/\\///\/ //\///////\\\/\/\//\//\//\\/\//////\/\//\\/\\////\\//\\\\\/\
Solution: here
Also, write a program that, given an input maze like the one above (read from the standard input) finds and prints a complete path that enters from the top and exists from the bottom of the maze. For example, one solution for the maze above is is this one:
\\
/\\
/\//\/
//\\//
\\///
/\////
\\/\/
//
//
\\/\
\//
//
//
//
//
//
/\//
\\/
//
//
Solution: here
partition
Write a program that prints all the partitions of a given integer. A partition of \(n\) is a bag of integers \(a_{1},a_{2},...\), such that \(a_{1} + a_{2}+ ... = n\). A “bag” is like a set, in the sense that the order doesn’t matter, but it is also like a sequence in the sense that it may contain repeated elements. In this case, to make the output unambiguous, your program must print each partition in decreasing order.
For example, the result for \(n=7\) is:
7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1
Solution: here
fifteen
Write a program to play the game “fifteen”. The game shows a 4-by-4 table containing 15 numbers (or letters), plus an empty cell. The objective of the game is to arrange the numbers in order. A move amounts to moving a cell into the adjacent empty cell. Or, in other words, a move exchanges the empty cell with an adjacent one. For example, starting from this initial state:
+--+--+--+--+ |11| 3|12|15| +--+--+--+--+ | 7| 4| 6| | +--+--+--+--+ | 8| 2|10|14| +--+--+--+--+ | 9| 5| 1|13| +--+--+--+--+
The player may move number 6 into the empty cell, obtaining this configuration:
+--+--+--+--+ |11| 3|12|15| +--+--+--+--+ | 7| 4| | 6| +--+--+--+--+ | 8| 2|10|14| +--+--+--+--+ | 9| 5| 1|13| +--+--+--+--+
Solution: here
tree
Write a program that reads a tree and prints it. The program reads trees in two different formats:
a text file in which each line contains two strings: node parent-node.
For example:
ciao root miao root mamma ciao gatto miao cane gatto topo gatto bimbo mamma bambina mamma bambini mamma
a text file in which each line contains a sequence of strings separated by the character “/”. For example:
/usr/share/texmf-texlive /usr/share/texmf-texlive/dvips /usr/share/texmf-texlive/dvips/pst-text /usr/share/texmf-texlive/dvips/hfbright /usr/share/texmf-texlive/dvips/tetex /usr/share/texmf-texlive/metapost /usr/share/texmf-texlive/metapost/venn /usr/share/texmf-texlive/metapost/makecirc /usr/share/texmf-texlive/metapost/frcursive /usr/share/texmf-texlive/metapost/nkarta /usr/share/texmf-texlive/fonts /usr/share/texmf-texlive/fonts/map /usr/share/texmf-texlive/fonts/map/dvips /usr/share/texmf-texlive/fonts/map/dvips/eurosym /usr/share/texmf-texlive/fonts/map/dvips/hfbright /usr/share/texmf-texlive/fonts/map/dvips/updmap /usr/share/texmf-texlive/fonts/map/dvips/tetex /usr/share/texmf-texlive/fonts/map/dvips/iwona /usr/share/texmf-texlive/fonts/map/dvips/phaistos /usr/share/texmf-texlive/fonts/ofm /usr/share/texmf-texlive/fonts/ofm/public /usr/share/texmf-texlive/fonts/ofm/public/oinuit /usr/share/texmf-texlive/fonts/ofm/public/ocherokee /usr/share/texmf-texlive/fonts/ofm/public/cm-lgc /usr/share/texmf-texlive/fonts/tfm /usr/share/texmf-texlive/fonts/tfm/cg /usr/share/texmf-texlive/fonts/tfm/cg/albertus /usr/share/texmf-texlive/fonts/tfm/cg/courier /usr/share/texmf-texlive/fonts/tfm/cg/lettrgth /usr/share/texmf-texlive/fonts/tfm/cg/coronet /usr/share/texmf-texlive/fonts/tfm/cg/atqolive /usr/share/texmf-texlive/fonts/tfm/cg/times /usr/share/texmf-texlive/fonts/opentype /usr/share/texmf-texlive/fonts/opentype/public /usr/share/texmf-texlive/fonts/opentype/public/iwona /usr/share/texmf-texlive/fonts/opentype/public/antt /usr/share/texmf-texlive/fonts/truetype /usr/share/texmf-texlive/fonts/truetype/public /usr/share/texmf-texlive/fonts/truetype/public/belleek /usr/share/texmf-texlive/fonts/enc /usr/share/texmf-texlive/fonts/enc/dvips /usr/share/texmf-texlive/fonts/enc/dvips/hfbright /usr/share/texmf-texlive/bibtex /usr/share/texmf-texlive/bibtex/bst /usr/share/texmf-texlive/bibtex/bst/directory /usr/share/texmf-texlive/bibtex/bst/adrconv /usr/share/texmf-texlive/bibtex/bst/hc /usr/share/texmf-texlive/xdvi /usr/share/texmf-texlive/xdvi/pixmaps /usr/share/texmf-texlive/omega /usr/share/texmf-texlive/omega/ocp /usr/share/texmf-texlive/omega/ocp/oinuit /usr/share/texmf-texlive/omega/ocp/misc /usr/share/texmf-texlive/omega/ocp/ocherokee /usr/share/texmf-texlive/omega/otp /usr/share/texmf-texlive/omega/otp/misc /usr/share/texmf-texlive/omega/otp/ocherokee /usr/share/texmf-texlive/source
The program must print the resulting tree in one of three formats selected through a command-line argument. If no command-line argument is given, then the program should print the output in all three output format. The formats are defined as follows:
- indentation
represents a tree by indenting each element under its parent element. For example, in the case of the first example, the risult should be:
root ciao mamma bimbo bambina bambini miao gatto cane topo- simple
represents a tree with the textual connectors “+” “-” and “|” in a simple way. For example, the output for the first example tree should be this:
+-root +-ciao | +-mamma | +-bimbo | +-bambina | +-bambini +-miao +-gatto +-cane +-topo- pretty
represents the tree with textual connectors in a richer and more expressive format. For example, the second example should produce this output:
•┬share └┬texmf-texlive ├┬metapost │├─venn │├─makecirc │├─nkarta │└─frcursive ├┬fonts │├┬ofm ││└┬public ││ ├─oinuit ││ ├─ocherokee ││ └─cm-lgc │├┬enc ││└┬dvips ││ └─hfbright │├┬tfm ││└┬cg ││ ├─courier ││ ├─lettrgth ││ ├─atqolive ││ ├─coronet ││ ├─albertus ││ └─times │├┬map ││└┬dvips ││ ├─hfbright ││ ├─updmap ││ ├─eurosym ││ ├─tetex ││ ├─iwona ││ └─phaistos │├┬opentype ││└┬public ││ ├─iwona ││ └─antt │└┬truetype │ └┬public │ └─belleek ├┬bibtex │└┬bst │ ├─directory │ ├─adrconv │ └─hc ├─source ├┬dvips │├─pst-text │├─hfbright │└─tetex ├┬xdvi │└─pixmaps └┬omega ├┬ocp │├─oinuit │├─misc │└─ocherokee └┬otp ├─misc └─ocherokee
Solution: here
maxlines
Write a program that reads a text file from standard input and outputs all the lines in the input that have maximal length. For example, if the input is
italy switzerland germany sweden austria netherlands belgium france
then the output should be
switzerland netherlands
Solution: here
program-x
Examine this python program. Write another Python program that does the same thing, but with a better complexity. Test your program with the following input files (passed through standard input).
- points10
- points100
- points1000
- points10000
- points20
- points200
- points2000
- points50
- points500
- points5000
Solution: here
tst
Write a program that reads a list of words from the standard input, constructs a ternary search trie (TST) by inserting each word in the TST in the given order, and then prints the TST on the standard output, which is a textual output stream.
The output of your program must conform exactly to a specific format defined as follows. This format can be best described through a series of examples.
Solution: here
plusminus
Write a program that reads a string of digits \(S\) as a command-line
argument, and inserts plus (+) and minus signs (-) in the sequence
of digits so as to create an expression that evaluates to zero. The
program should output a resulting expression, if one such expression
exists, or None if no such expressions exist.
For example, if \(S\) is 201015900001, then the program could output
+2+0+10+1-5-9+0+0+0+0+1. Instead, if \(S\) is 200015800001, then the
program should output None.
Optimization: Write a variant of this program that produces
expressions with the least number of plus or minus signs. For
example, an input value \(S\) 2391222918889 could produce an output
expression +2+3+9+1+2-2-29-1+8+8+8-9. However, a better expression
would be +239-122-29+1-88+8-9, since the first one has 12 elements
while the second one has only 7, and the minimum size is 6 (e.g.,
+239-12-229+1-88+89).
As another example, consider \(S =\) 3821248612902302283289922. There
exists an expression of only 7 elements, which is minimal:
24-8612-9023+022832-8992-2
Use your program to find the minimal expressions for
- \(S =\)
7492657830552204845644393 - \(S =\)
92374381610287463001735516 - \(S =\)
382104861250230228328992253 - \(S =\)
4692836501182824552131283782 - \(S =\)
46928365011828245521312837821
Solution: here