code

Maximum sum of a contiguous subsequence

# ( Part of BE5B33PGE course, FEL CTU, 2019 )
#
#    MAXIMUM SUM OF A CONTIGUOUS SUBSEQUENCE
#
# This a notorious problem in programming because
# it is simple and it illustrates in a dramatic way
# the relative efficiency of a cubic, quadratic
# and linear solutions.
#
# The task is easy to formulate:
# Given a sequence of N numbers find a contiguous
# subsequence which sum of elements is maximum possible.
#
# When the sequence contains only non-negative numbers
# the solution to the problem is obviously the whole original sequence.
# When the sequence contains some negative values
# the solution is not obvious and a suitable algorithm
# has to be applied.
 
 
import random
import time
import sys
 
def printf(format, *args):
    sys.stdout.write(format % args)
 
# ----------------------------------------------------------------------------------
# Cubic, quadratic and linear solution of the problem
# Suppose the sequence is stored in a usual list [...]
 
 
# Naive brute force solution
#   Cubic complexity
# Compute the sums of all countiguous subsequences,
# compare them and return the maximum one.
 
def maxSumCubic( aList ):
    ##  start value
    mmax = aList[0]
    ## search
    for i1 in range( 0, len(aList)-1 ):
        for i2 in range( i1, len(aList)):
            iSum = sum( aList[i1:i2] )
            if iSum > mmax:
                mmax = iSum
                besti1, besti2 = i1, i2
    return  besti1, besti2, mmax
 
# Less naive  solution
#   Quadratic complexity
# For each possible start X of a countiguous subsequence
# set sum to 0 and then scan the sequence from X to the right
# updating the sum by each subsequent element.
# Return the maximum sum found.
 
def maxSumQuadratic( aList ):
    ##  start value
    mmax = aList[0]
    ## search
    for i1 in range( 0, len(aList)-1 ):
        iSum = 0
        for i2 in range( i1, len(aList)):
            iSum  += aList[i2]
            if iSum > mmax:
                mmax = iSum
                besti1, besti2 = i1, i2+1
    return  besti1, besti2, mmax
 
 
# Fast (standard)  solution
#   Linear complexity
# Set the sum to 0. Scan the sequence once, update the sum by the current element.
# Whenever the sum becomes negative, reset it to zero.
# Return the maximum sum found.
 
def maxSumLinear( aList ):
    ##  start value
    mmax = aList[0]; besti1 = 0; besti2 = 0
    ## search
    sum = 0; starti = 0
    for i1 in range( 0, len(aList) ):
        sum += aList[i1]
        if sum < 0:
            sum = 0
            starti = i1+1
        elif sum > mmax:
            mmax = sum
            besti1, besti2 = starti, i1+1
    return  besti1, besti2, mmax
 
# ----------------------------------------------------------------------------------
# Manage sum function calls, aggregate more calls into a single method
 
def runMaxSum( speed, aList ):
    t_start = time.time()
    if   speed == 1:
        besti, bestj, mmax = maxSumLinear( aList )
    elif speed == 2:
        besti, bestj, mmax = maxSumQuadratic( aList )
    elif speed == 3:
        besti, bestj, mmax = maxSumCubic( aList )
    t_end = time.time()
    allTime = t_end - t_start
    return besti, bestj, mmax, allTime
 
def runAllSpeedsOnList(  aList ):
    besti, bestj, mmax, runTimeLinear = runMaxSum( 1, aList )
    besti, bestj, mmax, runTimeQuadratic = runMaxSum( 2, aList )
    besti, bestj, mmax, runTimeCubic = runMaxSum( 3, aList )
    print("Sequence length =", len(aList))
    print("Times   linear, quadratic, cubic")
    printf(" %12.2f %6.2f    %6.2f\n", runTimeLinear, runTimeQuadratic, runTimeCubic )
 
def runLinQuadOnList(  aList ):
    besti, bestj, mmax, runTimeLinear = runMaxSum( 1, aList )
    besti, bestj, mmax, runTimeQuadratic = runMaxSum( 2, aList )
    print("Sequence length =", len(aList))
    print("Times   linear, quadratic ")
    printf(" %12.2f %6.2f \n", runTimeLinear, runTimeQuadratic )
 
def runLinearOnList(  aList ):
    besti, bestj, mmax, runTimeLinear = runMaxSum( 1, aList )
    print("Sequence length =", len(aList))
    print("Time   linear ")
    printf(" %12.2f \n", runTimeLinear )
 
 
# ----------------------------------------------------------------------------------
# Crerate example data and run maxSum functions on the data
 
random.seed( 830 )
 
list10 = [random.randint(-9, 9) for k in range(10) ]
list100 = [random.randint(-9, 9) for k in range(100) ]
list200 = [random.randint(-9, 9) for k in range(200) ]
list400 = [random.randint(-9, 9) for k in range(400) ]
list600 = [random.randint(-9, 9) for k in range(600) ]
list1000 = [random.randint(-9, 9) for k in range(1000) ]
list10000 = [random.randint(-9, 9) for k in range(10000) ]
list100000 = [random.randint(-9, 9) for k in range(100000) ]
#list1000000 = [random.randint(-9, 9) for k in range(1000000) ]
#list10000000 = [random.randint(-9, 9) for k in range(10000000) ]
 
runAllSpeedsOnList( list10 )
runAllSpeedsOnList( list100 )
runAllSpeedsOnList( list200 )
runAllSpeedsOnList( list400 )
runAllSpeedsOnList( list600 )
runAllSpeedsOnList( list1000 )
runLinQuadOnList( list10000 )
runLinearOnList( list100000 )
 
 
# ---------------------------------------------------------------------------------- 
# Determine (without running the program!) how long would it take to
# 1. process the list of length  5 000 by the cubic procedure,
# 2. process the list of length 10 000 by the cubic procedure,
# 3. process the list of length 100 000 by the cubic procedure,
# 4. process the list of length 1 000 000 by the cubic procedure,
# 5. process the list of length 100 000 by the quadratic procedure,
# 6. process the list of length 1 000 000 by the quadratic procedure,
#

Hi-Lo game and 1D battleships game, with variants

# ( Part of BE5B33PGE course, FEL CTU, 2019 )
#
#     The Hi-Lo (meaning High-Low) game
#
# The program chooses an integer unknown to the user.
# The user has to determine the number by inputting her guesses
# to each of which the program reacts in three possible ways:
# It informs the user that her guess is either too hig or too low
# or, maybe, spot-on. In the latter case, the user "wins" the game.
#
# The task is to determine the number by minimum number of guesses.
#
 
import random
import time
 
# initialize the random number generator by a random value - system time.
random.seed(time.time())
 
def hilo( minval, maxval ):
    print("Guess a hidden number between", minval,"and", maxval)
    guesses = 0
    hidden = random.randint( minval, maxval )
    while True:
        print("Your guess: ", end = "")
        guess = int( input())
        guesses += 1
        if guess < hidden:
            print(" too low! ")
        elif guess > hidden:
            print(" too high! ")
        else:
            print( "Got it in", guesses, "guesses.")
            break
 
 
# An "extended" version of the High-Low game.
# The program chooses TWO numbers which are unknown
# to the user and which have to be determined.
# User repeatedly inputs ONE number as a guess  and the program
# initally reacts in three possible ways: It informs the user that
# her guess is either greater than both unknown number or it is smaller
# than both numbers or it is between the numbers or, maybe, it is spot-on
# one of the unknown numbers. When the user determines one of the numbers
# the program continues as in the simple case until the user
# determines the second number and this "wins" the game.
 
def hilo2( minval, maxval ):
    print("Guess TWO hidden numbers between", minval,"and", maxval)
    print("Input always a SINGLE value as a guess.")
    guesses = 0
    # generate hidden values
    while True:
        hidden1 = random.randint( minval, maxval )
        hidden2 = random.randint( minval, maxval )
        if hidden1 < hidden2: break
    # state of the game
    found1 = False
    found2 = False
    while True:
        print("Your guess: ", end = "")
        guess = int( input())
        guesses += 1
        if not(found1) and not(found2):
            if guess < hidden1:
                print(" too low! ")
            elif guess == hidden1:
                print("Got one value correct! Now for another one:")
                found1 = True
            elif guess < hidden2:
                print(" somewhere in between!")
            elif guess == hidden2:
                print("Got one value correct! Now for another one:")
                found2 = True
            else:
                print(" too high! ")
        elif found1:
            if guess < hidden2:
                print(" too low! ")
            elif guess > hidden2:
                print(" too high! ")
            else:
                print( "Got it all in", guesses, "guesses.")
                break
        elif found2:
            if guess < hidden1:
                print(" too low! ")
            elif guess > hidden1:
                print(" too high! ")
            else:
                print( "Got it all in", guesses, "guesses.")
                break
 
# ----------------------------------------------------------------------------------
# Run the game
 
hilo( 10, 70 )
# hilo2( 10, 70 )
 
 
# ----------------------------------------------------------------------------------
# Modifications of the game
#
# 1. The program registers the sum of distances of the guesses from the
# hidden value.
# For example, if the hidden value is 24 and the user guesses are 17, 26, 24
# the program totals |17-24| + |26-24| + |24-24| = 7+2+0 = 9.
# The program also prints out the sum of the distances after each guess
# but not after the first or the second guess it would be too easy to the user
# to calculate the hidden number.
#
#
# 2. The game is played by two players who take turns.
# The player who first determines the hidden number wins.
# The program alternates between prompting one player and the other player
# to input their guesses.
#
#
# 3. After each guess, there is a 50% probability that the program will
# increase or decrease the hidden number by 1 or 2. The player has no information
# whether this had happend and still has to determine correctly the
# (final) value of the hidden number.
# For example, The hidden number is 24.
#   User guess 22, too low
#   User guess 26, too high, 24 changed to 25
#   User guess 24, too low, 25 changed to 24
#   User guess 25, too high, no change
#   User guess 24, hit 24, player "wins".
#
#
# 4.  The program chooses FIVE hidden numbers. After each guess the
# player is informed how many numbers are above her guess and how many
# numbers are bellow her quess. The game stops when the player had
# hid all hidden numbers.
#
 
# ----------------------------------------------------------------------------------
# More suggestions
#
# 5. 1D battleships
# The program chooses FIVE hidden CONSECUTIVE integers (= a battleship made of 5 pieces).
# The player's task is to determine all of them.
# After each guess the program only informs
# the player if she had or had not hit any of the hidden integers, it does
# not inform her where in the relation to the hidden numbers is her guess located.
# The game ends when all hidden integers have been hit at least once.
#
#
# 6. Modify any of the given variants to be played by two players.
#
#
# 7. Moving 1D battleships
# After each hit, the sequence of the hidden integers (a battleship)
# is moved by 1 to the left or to the right unknown to the user. The program
# remembers which parts of the battleship have been hit.
# For example, the battleship is (11,12,13,14,15) and 12 had been hit. Then
# the battleship is moved 1 to the right ad it becomes (12,13,14,15,16) and
# program registers that, in fact, 13 had been hit.
#

1D array problems

# ( Part of BE5B33PGE course, FEL CTU, 2019 )
#  
# -------------------------------------------------------------------- 
#     1D list/array problems
# -------------------------------------------------------------------- 
#
#   Guidelines:
#
#   1.  Use only arrays/lists to solve the following problems.
#   2.  Write each solution as a function and call the function in the main program
#   3.  If the problems at the top of the list are too easy to you 
#       start at the bottom of the list.
#
 
 
 
 
'''
[1]
Check if in an array the following holds:
a) the number of leading values 0 is equal to the number of
   the trailing values 0 (ex.: 001...100 -- OK, 01...0001 -- bad)
b) each value 1 is surrounded by values 0 (ex ...010... OK,
c) each value 1 is followed by at least two values 0.
 
[2]
Write a method zerosToStart(aa) which will move all zero values in the array aa
to the beginning of the array. The order of the nonzero elements will not be changed. In addition, the
function should not declare any other array and should do the task in linear time.
Ex.:  (3,0,0,2,1,0,7,5)  -->  (0,0,0,3,2,1,7,5)
 
[3]
Write a  function H(aa) which will substitute some elements by the mininum
value of the array aa. The element should be substituted when its value is bigger than the value of all elements which have grater index.
The method should do the task in linear time with respect to the length of aa.
Ex.:  (1,2,30,5,4,20,10,5,7) --> (1,2,1,5,4,1,1,5,7)
 
[4]
Write a  function  F( aa, bb) which will check if a list aa contains the same values
as a list bb. The lists aa and bb are sorted in increasing order. The task should be done in linear time
with respect to the value max(len(aa), len(bb)).
Ex.: aa = (1,1,1,4,7,7,12), bb = (1,4,4,4,4,7,12,12,12), result = true
 
[5]
Write a method with one integer parameter n which will write out all possible pairs of positive integers.
First element of the pair must be odd, the second one must be even. All elements must be smaller then n.
Ex.:
Input:  n = 5
Output: 1 2
        1 4
        3 2
        3 4
 
[6]
Write a method with one integer parameter n which will write out all possible different triples of positive integers.
Each element of the triple must be smaller then n and the first and the third element of the triple must be equal.
Ex.:
Input:  n = 3
Output: 1 1 1
        1 2 1
        2 1 2
        2 2 2
 
[7]
Verify if lengths of streaks of zeros in a sequence do not decrease, as we are moving from left to right and checking the streaks.
A streak is a contiguous subsequence of maximum length containing a repetitive single value.
Example: 5 2 0 2 3 0 0 4 0 0 2 6 1 0 0 0 3 --- Yes,  
         4 2 0 0 5 1 1 0 0 2 4 0 5 1 0 0 -- No
 
[8]
Two lists A and B are given. Decide if each element A[i] in list A is equal to the sum 
of all such elements in array B which are smaller than A[i].
 
[9]
Find sum of all perfect squares in the interval [a, b]. The values a and b will be the input parametres of the function.
# Perfect squares are integers 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...
# For example, there are 5 perfect squares in the interval[50, 150].
 
[10]
Find sum of all perfect cubes in the interval [a, b]
# Perfect cubes are integers 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ...
# For example, there are 10 perfect cubes in the interval[500, 5000].
 
[11]
In array A, the element A[0] is given. For each next element A[i+1] (i >= 0) it holds that
A[i+1] is equal to the number of occurences ot the value A[i] among all elements A[0], A[1], ..., A[i-1].
Ex: A[0] = 2, A = [2 0 0 1 0 2 1 1 2 2 3 0 3 1 ... ]
Generate array A with length 10, 100, 1000, 10000, million.
 
[12]
Two indices i < j in an array A are called guards when each element with index
between i and j is smaller than min(A[i], A[j]). Find all guards in a given array.
Example: A = [8, 2, 7, 5, 2, 3, 4, 2, 6, 1]
Guards are 2, 8, because A[2] = 7, A[8] = 6 and all alements between  indices 2 and 8 are smaller than min(A[2], A[8]).

2D array problems

some basic reference for beginners

# ( Part of BE5B33PGE course, FEL CTU, 2019 )
#
#     2D array problems
#
# Use only arrays/lists to solve the following problems
# if the problems at the top of the list are too easy for you
# start at the bottom of the list.
 
 
'''
[1]
Write a function which will check a 2d array and it will return
-1 ... if there are more odd values than even values in the array
 1 ... if there are more even values than odd values in the array
 0 ... if the number of odd and even values in the array is the same
 
[2]
Write a function which will detect, in a 2d array, all columns
which contain an ascending sequence of values (the values should ascend
from top to bottom). The function will return a new 1D array containing
indices of all columns with ascending sequences.
 
[3]
Write a function which decides whether a 2D array contains so called
"saddle point". A saddle point is an element X in the array with the property
 that it is the maximum value of all elements in its column and also
 it is the minimum value of all elements in its row.
 
[4]
Write a function which fills a 2D array of size MxN with
values 1,2,3,...,M+N, diagonally in the following manner:
1   2   3   4 ...   N
2   3   4   5 ... N+1
3   4   5   6 ... N+2
. ... ... ... ... ...
M M+1 M+2 M+3 ... M+N
 
[5]
Write a function which will flip 2D array horizontally
 
[6]
Write a function which will fill a 2D square array of size NxN
with values 1,2,3,...,N in the following way:
A:
1 2 3 4 5 ... N
2 2 3 4 5 ... N
3 3 3 4 5 ... N
4 4 4 4 5 ... N
5 5 5 5 5 ... N
. . . . . ... .
N N N N N ... N
 
B:
1 1 1 1 1 ... 1
1 2 2 2 2 ... 2
1 2 3 3 3 ... 3
1 2 3 4 4 ... 4
1 2 3 4 5 ... 5
. . . . . ... .
1 2 3 4 5 ... 5
 
 
[7]
Write a function which will rotate a 2D array left by 90 degrees.
The array will be the input parameter of the function
Example with 3x3 array:
1 2 3        3 6 9
4 5 6  -->   2 5 8
7 8 9        1 4 7
If the input array is a square array do not create a new array,
otherwise(= height is not equal to width) create a new array
 
[2]
Write a function which will find in a 2D array a diagonal with
maximum sum. The diagonal may run in in "north-west" or in "north-east"
direction. Also the diagonal may be only partial, i.e. it may
contain just a few elements from the entire diagonal, nonetheless,
the diagonal cannot be split into two or more separate, non-contiguous pieces.
Note that the diagonal need not to be aligned with the corners of the array,
it may be located anywhere in the array.
The array is not necessarily square, it may be rectangular.
A single element is considered to be a diagonal as well.
Ex1:
 4   7  -2  -3  
-1   0   2   1
-2   3  -4  -2
-1   0   8   1
 1  -2   4  -3
 6   1  -2   1 
 1  -3   4   5 
The maximum is attained at the diagonal with values 6 -2 8 -2 
(starting in the 6-th row and going upwards right) taking only
the sub-sequence 6 -2  8 which sum is 12.
Ex2:
-1 -1 -1
-1  6 -1
-1 -1 -1
[[-1 -1 -1][-1 6 -1][-1 -1 -1]]
 
 
'''

Text files

Climate data

Each of the following data files contains a sequence of daily average temperatures at some meteorological station in Europe.
These data and many more are publicly accessible at the webpage of European Climate Assessment & Dataset project (http://www.ecad.eu) In particular, we are using excerpts from Daily mean temperature blended data set(You do not have to download it, it has about 372Mb.)

The data time span is quite large, the oldest recording started in late 18th century and all of them had been carried out daily since that. The format of the files is relatively simple: First, there are few lines/paragraphs of text describing the data set and then there are uniformly structured lines, each of which contains the date of the measurement and the temperature on the date plus some (relatively neglectable) additional technical information. Open a file in your text editor and see it for yourself.

Data files: Choose any data file for your exercises and code debugging, preferably process more of them.

tg_staid005464.txt, tg_staid000027.txt, tg_staid000048.txt, tg_staid000048.txt, tg_staid000169.txt, tg_staid000173.txt, tg_staid000271.txt, tg_staid005464.txt, tg_staid005465.txt, tg_staid011744.txt.

The tasks

1. Process a climate text file.
Find the average temperature on 1.1. during the whole 20th century 
at a selected meteorological station station. 
That is, compute the average of  temperatures 
on 1.1.1901, 1.1.1902, 1.1.1903, ..., 1.1.1998, 1.1.1999, 1.1.2000.

[See an example solution at the page bottom. ]


2. Process a climate text file.
Compute the average temperature of each month in the years
1800, 1810, 1820, 1830 , ... 1990, 2000, 2010, if the measurements
for those years which data are completely present in the data file.

3. Process a climate text file.
Find the longest continguous time interval (measured in days)
in which the the temperatures were negative on each day.

4. Process a climate text file.
Find the year in which the average temperature
was the lowest.
Do not consider years with incomplete information or
with missing data for some days of the year.

Plain text -- online book

Project Gutenberg (https://www.gutenberg.org/) offers over 58,000 free eBooks in various format.

You may download and experiment with any of them, preferably start with the books in plain .txt format.

In this practice we offer The Adventures of Sherlock Holmes by Arthur Conan Doyle linked here book . If you do not like this particular author/title go to the project webpage and download any other suitable book in plain .txt format.

The tasks

Write out all longest words in the file.
A.
A word is sequence of characters which is surrounded by spaces.
Using this definition, punctuation symbols become part of a word.
For example, string "Hello, nice to see you again!"  will also contain words
"Hello," and "again!".
B.
A word is sequence of characters which is surrounded by spaces or by
punctuation marks.
Using this definition, punctuation symbols are not part of a word.
For example, string "Hello, nice to see you again!"  will contain words
"Hello", "nice", "to", "see", "you", "again".
Hint: First substitute each punctuation character by a space and then treat the
string as in case A.

In both cases A and B neglect the words which are divided at the end of the line.
Only if you want to challenge yourself include those words too in your search.  

Plain text -- list of topics

The foollowing file contains a list of various computer science topics, each topic is listed on a single line of text.

List of topics .

The tasks

1. 
Extract and print all topics (= lines in the file) related to trees. 
A topic is related to a tree
if the corresponding text line contains either word "tree" or a word "trees".

2.
Extract and print all topics (= lines in the file) containing some abbreviation.
An abbreviation is a sequence of 2, 3 or 4  capital letters.
Example:
  reconstructing tree from DFS and BFS traversal
  Fast Fourier Transform (FFT) (will get TLE)
  finding LCA in a DAG

3.
Extract and print all topics (= lines in the file)
containing some text enclosed in round brackets.
Both brackets -- the opening and the closing one must be present.
Example:
  quadratic equations (or binary search)
  cycle finding (Floyd's cycle finding algorithm)
  negative (positive) cycles

String manipulation

The tasks

1.
Write a method that interleaves two strings: 
it should take one character from the first string, then one from the second string, 
another from the first string and so on. 
Once one string has no characters left it should carry on with the other string. 
For example, interleaving the strings "anna" and "patrik" 
should give the result "apnantarik" (or "paantnraik"). 

2.
Write a function which returns a list of strings.
When the strings are printed a "picture" should appear on the output.
The picture is a square with two diagonals. The size of the square
is a parameter of the function.
Example for size 8 and 9:
xxxxxxxx
xx    xx
x x  x x
x  xx  x
x  xx  x
x x  x x
xx    xx
xxxxxxxx

xxxxxxxxx
xx     xx
x x   x x
x  x x  x
x   x   x
x  x x  x
x x   x x
xx     xx
xxxxxxxxx

Searching, Sorting

A. Finish the problems from the previous sections which you have not solved yet.

B.

1.
Modify characteristic/histogram so that they can admit also negative integers in the given array.

2. 
Write a function which will move all suspicious values in the list L to the beginning of the list.
The mutual order of the suspicious values should not change. Also, the mutual order of the unsuspicious values should not change.
A value X is suspicious if it lies in the range [10..20].
Ex: Input:  L = [ 5, 400, 11, 13, 2, 1, 15, 0, 18 ] 
    Output: L = [ 11, 13, 15, 18, 5, 400, 2, 1, 0 ] 
Demonstrate by an experiment that the task can be completed in less than 1 second when length(L) = 10^6.
    

3.
You must find E = 1000 most expensive items from an unsorted price list containing N = 10 000 000 different items. 
Two schemes of solution are as follows.
Scheme A: repeat E times the search for an item without changing order of items in the list.
Scheme B: sort the list and extract the 1000 top items.
Determine by experiment which method is more effective.


4.
Write a function which takes as an input two strings A and B.
The function will return true if B consists only of some number of repetitions of A .
Otherwise, function will return false.
Examples: A = "one",  B = "oneoneoneone" -- true
          A = "one",  B = "oneon" -- false
          A = "banana", B = "banabanana" -- false
          A = "baba", B = "bababa" -- false
          A = "baba", B = "baba" -- true
          
5.
Write a function which takes as an input a list L of strings. 
The function should return a new string B satisfying the properties:
-- B is a continguous substring of each string in L
-- The length of B is maximum possible

7.
Write a function which takes as an input a list L of strings and positive integer K. 
The function should return a new string B satisfying the properties:
-- B is a continguous substring of at least K strings in L
-- The length of B is maximum possible


8. 
There is an array A filled randomly with integers from range 0..5.
Associate with each cell (with A[i]) the following information:
D[i] .. absolute value of the difference between the two neighbours of A[i]
M[i] .. sum of S[i] and A[i], modulo 4
S[i] .. the sum of the two neighbours of A[i]
P[i] .. the product of the two neighbours of A[i]
  The neighbour of the first/last element in the array, is the last/first
  element in the array (the array is "circular")

Sort A in such way that D is the most important criterion, the next criterion is
 M, the next is S, then P and finally, the last criterion is A
The elements of A should be sorted in ascending order by all criteria.

Example:
A = [ 2, 0, 1, 1, 5, 3, 4, 2, 3 ]
D = [ 3, 1, 1, 4, 2, 1, 1, 1, 0 ]
M = [ 1, 3, 2, 3, 1, 0, 1, 1, 3 ]
S = [ 3, 3, 1, 6, 4, 9, 5, 7, 4 ]
P = [ 0, 2, 0, 5, 3,20, 6,12, 4 ]

sorted 
A = [ 3, 3, 4, 2, 1, 0, 5, 2, 1 ]

Recursion I

The tasks

The problems 1. - 13. are (hopefully!) simple introductory problems, their difficulty should not vary too much. A little bit more of challenge might be presented in problems 14. and 15., though they also belong to the very standard repository of classical recursion tasks. Try to solve them just by yourself first, and only later consult the web.

Beginners
Another recursion explanation is on GeeksForGeeks.
As a training you may consider also the problems listed in the “Output based practice problems for beginners” section.

----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [A]
----------------------------------------------------------------------------------------

Determine the output the function call WITHOUT running the program.

Example and analysis
====================

def rec1( n ):
    if n < 1: return 2
    return 1 + rec1( n-1 ) + rec1( n-2 )
# call:
rec1(5)

Each node n the tree diagram represents one function call,
the value in the node is the value of the parameter
                                  ____________________[5]____________________
                      ___________[4]____________                    _______[3]_____
           ________[3]_____             ______[2]___         ______[2]___      __[1]___
    ______[2]____      __[1]__      ___[1]___     [0]     __[1]___     [0]    [0]   [-1]
 __[1]__      [0]     [0]   [-1]   [0]    [-1]           [0]   [-1]
[0]   [-1]

The next tree scheme is based on the previous one,
the return value of the corresponding function call is appended
to each node.
                                  ____________________[5]38__________________
                      ___________[4]23__________                    _______[3]14___
           ________[3]14___             ______[2]8__         ______[2]8__      __[1]5__
    ______[2]8___      __[1]5_      ___[1]5__     [0]2    __[1]5__     [0]2   [0]2  [-1]2
 __[1]5_      [0]2    [0]2  [-1]2  [0]2   [-1]2          [0]2  [-1]2
[0]2  [-1]2

The function call rec1(5) returns value 38.

PROBLEMS
========

-- 1. --
def rec2( n ):
    if n < 1: return 1
    return 2 + rec2( n-1 ) + rec2( n-2 )
# call:
rec1(5)

-- 2. --
def rec3( n ):
    if n < 2: return 1
    return 1 + rec3( n-1 ) + rec3( n-2 )
# call:
rec1(5)

-- 3. --
def rec4( n ):
    if n < 2: return 2
    return 1 + rec4( n-2 ) + rec4( n-3 )
# call:
rec1(6)

----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [B]
----------------------------------------------------------------------------------------

Describe how the return value of the function depends on
 the value(s) of its input parameter.

Example
def rec5( x, y ):
    if x >= y: return x
    return rec5( x+1, y )

The function returns maximum of x and y.
( If x is bigger than or equal to y then it is immediately returned
  as a result.
  If, on the other hand, x is smaller then y then the function
  repeatedly calls itself and increases the value of x until
  it is equal to y, which was originally the bigger of the two.)

Functions to analyze

-- 4. --
def rec6( x, y ):
    if x < y: return rec6(x+1,y)
    return x

-- 5. --
def rec7( x, y ):
    if y > 0: return rec7(x, y-1) + 1
    return x;

-- 6. --
def rec8( x, y ):
    if y > 0: return rec8(x-1, y) - 1
    return y;

----------------------------------------------------------------------------------------
  P R O B L E M S   S E T    [C]
----------------------------------------------------------------------------------------

-- 7. --
Determine exactly the return value of the call f9(100),
provided that the function can run a return the result in some reasonable time.
def f9( N ):
    if N < 1: return 2
    return f9( N-1 ) + f9( N-1 )

-- 8. --
Write a recursive function which will print an isosceles right triangle filled with character 'x'.
The number of lines in the triangle will be the parameter of the function.
(Isosceles triangle = the length of both shorter sides is the same )
Example:
f(5)
#
##
###
####
#####

-- 9. --
Write a recursive function which will print an right triangle filled with character 'x'.
The number of x's along the longer cathetus (side) will be twice as big as the
 number of of x's along the shorter cathetus (side).
The number of lines in the triangle will be the parameter of the function.
Example
f(5)
##########
  ########
    ######
      ####
        ##


-- 10. --
Write a recursive function which will return the sum of the squares
of the first N positive integers
It holds for f:  f(1) == 1, f(2) = 1+4 = 5, f(3) = 1 + 4 + 9 = 14, f(4) = 30, etc.

-- 11. --
Write a recursive function which will return the sum of all positive integers less than or
equal to N which are not divisible by 3.
It holds for f:  f(1) == 1, f(2) = 1+2 = 3, f(3) = 1 + 2 (3 is not included, it si divisible by 3),
f(4) = 1 + 2 + 4 = 7, f(5) = 1 + 2 + 4 + 5 = 12,
f(6) = 1 + 2 + 4 + 5 = 12  (6 is not included, it si divisible by 3),
f(7) = 1 + 2 + 4 + 5 + 7 = 19, etc.

-- 12. --
Write a recursive function which will return a list of all pairs of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each pair in the output, that the sum of the pair is divisible by 3.
(You may consider implementing a loop in the body of the function.)

-- 13. --
Write a recursive function which will return a list of all triples of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each triple in the output, that the sum of the triple is positive.

-- 14. --
Write a recursive function which will return a list of tuples of the values
in a given list of integers. The list will be the input parameter of the function.
It must hold, for each tuple in the output, that the sum of the elements in the tuple
is equal to another given value K.
The tuples may be of different lengths.
Example
input: [ 2, 7, 3, 5, 11, 4, 8 ], K = 20
output:
[3, 5, 4, 8]
[7, 5, 8]
[2, 7, 3, 8]
The method you should avoid is to generate all possible tuples and only later
remove those which sum is not equal to K.

-- 15. --
Determine the value of A(4, 4). Function A(m, n) is defined:
def A( m, n ):
    if m == 0: return  n + 1
    if n == 0: return A( m-1, 1 )
    if m > 0 and n > 0: return A( m-1, A(m, n-1) )

Recursive tree processing

Write a recursive function which will process a binary tree.
Check its performance by generating few trees with depth less than 7
and applying the function to each of the trees.
If a function changes the structure or the contents of the tree
print each tree twice: before the function is applied and after the function is applied.
Visually check if the function processed the tree correctly.

Follow the example in the file ADTtreeExample.py in the lecture notes.
Optionally, copy and modify the functions from the main lecture file ADTtree2.py.


1.
The function removes from the tree all leaves with odd key value.

2.
The function returns sum of all keys in the tree.

3.
The function returns sum of all keys in all nodes which depth is equal to a given value D.

4.
The function returns the number of all nodes which height (see definition in the lecture code)
is equal to a given value H.

5.
The function returns the biggest value of the keys of the nodes in the maximum depth in the tree.

6.
The function returns the smallest value of the keys of all **leaves** in the minimum depth in the tree.

7.
The function returns the smallest value of the keys of all **leaves** in the minimum depth in the tree.

8.
The function creates a tree which contains 2*N+1 nodes and contains only two leaves, the depth
 of both leaves is N.

9.
The function creates a duplicate of the given tree.
The input parameter is the root of the original tree.

10.
The function substitutes the key value of a node
by the sum of depths of all nodes in its left and right subtrees.

11.
The function adds to the tree some number of nodes. After the operation, the depths of all
 leaves in the tree is equal and also the number of added nodes is minimum possible.

Graph processing

Write a program which processes a graph.
Use the graphs stored in the archive . Download the archive and run your program on all data.

The tasks:

Reminder: The degree of node X is the number of neighbours of X, that is, 
the number of nodes connected directly to X by a single edge.
We denote en edge connecting two nodes X and Y by symbol (X, Y)

1. An edge is a balanced edge if the degree of its both end nodes 
   is the same. 
   Print the number of balanced edges in the graph.

2. The slope of an edge is the absolute value of the difference between 
   the degrees of its and nodes. (The slope of a balanced edge is 0.)
   Count then number of edges with maximum slope in the graph.

3. Three different nodes X, Y, Z define an basic open path 
   if there are edges (X,Y) and (Y,Z) in the graph 
   and there is no edge between X and Z.
   Print the number of all basic open paths in the graph. 
   Each path is counted only once, that is, 
   consider the triples X, Y, Z and Z, Y, X  to be identical.      

4. Analogously to the previous problem, four different nodes X, Y, Z, W 
   define an open path of length 3 if there are edges (X,Y), (Y,Z), (Z,W) 
   and there is no edge (X, W) in the graph.
   Print the number of all open paths of length 3 in the graph. 
   
5. Count the number of triangles in the graph. 
    A triangle is a triple of nodes X, Y, Z, such that
   there are edges (X,Y), (Y,Z) and (Z,X) in the graph.
   
6. Calculate the distance between each two nodes in the graph using BFS. 
   Print out the maximum distance between two nodes.
   This value is called the diameter of the graph.

A graph and its picture:

10 15
4 9
5 6
5 0
6 3
8 5
0 7
4 2
2 3
1 0
8 1
9 8
3 7
7 8
7 5
1 9
 graph


Text files solved example

#  Solution of task 1 in file processing
 
def dateOfInterest( date ):
    # skip year 1900
    if date[0:4] == "1900": return False
 
    if   ( date[0:2] == "19" and date[4:8] == "0101" )\
        or date == "20000101" :
        return True
    else: return False
 
 
# -------------------------------------------------------------
# The avg20century funcion depends in all details
# on the exact format of the data.
# Check the data file visually to see how the data are organized.
 
def avg20century(fileName):
    # named constants do help
    dateColumn = 2
    temperColumn = 3
    qualityColumn = 4
    qualityValid = 0
    qualitySuspect = 1
    qualityMissing = 9
 
    # start reading
    file = open( fileName, "r" )
 
    # skip the file header
    while True:
        line = file.readline()
        if line[0:5] == "STAID": break
 
    minTemper = 10000 # start with big temperature
    dateMinTemper = 0
 
    # to compute average
    totalTemp = 0
    noOfDays = 0
 
    # process all lines
    while True:
        line = file.readline()
        # detect possible empty lines to stop
        if line == None or line.strip(" ") == "":
            break
 
        # extract info from a text line
        lineVals = line.split(",")
        date =  lineVals[dateColumn]
        #date =  lineVals[2]
 
        temper = int( lineVals[temperColumn] )
        quality = int( lineVals[qualityColumn] )
 
        # do not accept dubious data
        if quality != qualityValid:
            if dateOfInterest( date ):
                print( line, end = "" )
            continue
 
        # check 20 century
        if dateOfInterest( date ):
            totalTemp += temper
            noOfDays += 1
            #print(line, date, temper, totalTemp )
 
    file.close()
 
    print("total temp:", totalTemp)
    print("no of days:", noOfDays)
    # in data file temperatures are x 10
    print( "average ", (totalTemp/noOfDays)/10 )
 
    #end of coldestDay
 
# ------------------------------------
#   M A I N   P R O G R A M
 
path ="d:\\Iskola\\PGE2019\\data\\"
fname = "TG_STAID000169.txt"
 
avg20century(path + fname)

courses/be5b33pge/practices/code.txt · Last modified: 2020/04/03 09:10 by berezovs