# 1D array problems


# --------------------------------------------------------------------
#     ADDITIONAL   1D/2D  list/array problems  for individual training
# --------------------------------------------------------------------

'''

[1] (**complexity!**)
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, ...11... bad )
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] (**complexity!**)
Write a  function H(aa) which will substitute some elements in the array aa by the minimum
value of the array aa. An element, say E, should be substituted
when its value is bigger than the value of all elements which index is bigger
than the index of E. (In other words, E is bigger than all elements to the right of E.)
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] (**complexity!**)
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)). Note that containing same values does not necessarily
means that the lists are identical, see the example:
Ex.: aa = (1,1,1,4,7,7,12), bb = (1,4,4,4,4,7,12,12,12), result = true

[5]  (**complexity!**)
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]  (**complexity!**)
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]  (**complexity!**)
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 parameters 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] (**complexity!**)
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 occurrences of 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] (**complexity!**)
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 elements between  indices 2 and 8 are smaller than min(A[2], A[8]).

# 2D array problems


# --------------------------------------------------------------------
#     ADDITIONAL     2D  list/array problems  for individual training
# --------------------------------------------------------------------

# ( Part of BE5B33PGE course, FEL CTU, 2023 )
#
#     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.
#
#   Some tasks are marked with (**complexity!**) label.
#   Explain in a few sentences, how the size of the input data
#   affects the execution time of the code.
#   "Can the code process the data of size 10^3, 10^4, 10^6,
#   in about one second? Why?"

'''
[1]  (**complexity!**)
Write a function which will check a 2d array. 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]  (**complexity!**)
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]  (**complexity!**)
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]  (**complexity!**)
Write a function which generates 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
The values of M and N are the input parameters of the function.
The function returns the generated array.

[5] (**complexity!**)
Write a function which flips 2D array horizontally.
Example:
2 0 6 5        5 6 0 2
4 1 7 2   -->  2 7 1 4
8 4 4 1        1 4 4 8

[6]
Write a function which creates a 2D square array of size NxN
and fills it with values 1,2,3,...,N in the following way:
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

[7]
Write a function which creates a 2D square array of size NxN
and fills it with values 1,2,3,...,N in the following way:
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

[8A]
Write a function which prints all diagonals of a given 2D array.
A diagonal starts at the left or at the top of the table representing the
array and then it runs in the south-east direction.
Ex:
Input:
-1   0   8   1   3
1  -2   4  -3  -3
6   1  -2   1   0
1  -3   4   5  12
Output:
1
6 -3
1 1 4
-1 -2 -2 5
0 4 1 12
8 -3 0
1 -3
3

[8B]
Write a function which prints all antidiagonals of a given 2D array.
An antidiagonal starts at the left or at the bottom of the table representing the
array and then it runs in the north-east direction.
Ex:
Input:
-1   0   8   1   3
1  -2   4  -3  -3
6   1  -2   1   0
1  -3   4   5  12
Output:
-1
1 0
6 -2 8
1 1 4 1
-3 -2 -3 3
4 1 -3
5 0
12

[9] (**complexity!**)
Write a function which finds in a 2D array a partial diagonal with
maximum sum. The diagonal may run in in "north-west" or in "north-east"
direction. The diagonal 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
The maximum is attained at the main diagonal or main antidiagonal (in SW - NE direction)
-1, 6, -1, taking only the central item 6.

'''

# 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.

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.

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.

-----------------------------------------------------------------------------
1. Write out all longest words in the file. Solve cases A. and B. separately

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.

-----------------------------------------------------------------------------
2. Create a list of sentences in the file

A plain sentence is a string which starts with capital letter
and ends with a dot, a question mark or an exclamation mark.
A sentence is either a plain sentence or a plain sentence enclosed in
double quotation marks.


### Plain text -- list of topics

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

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:
cycle finding (Floyd's cycle finding algorithm)
negative (positive) cycles


# String manipulation

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.

1.99:
You can use and modify the given example to produce your own random lists:
# produce a randomly generated list of 1000 values in the range 50, 90
randList = [ random.randint( 50, 90) for foo in range (1000) ]

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 when it is 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.

The function header may look like:
def moveValuesToBegin( myList, rangeMin, rangeMax): # suspicious range is [rangeMin ... rangeMax]
...

3.
You must find E = 1000 most expensive items
in 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
Ex: L = ["xybcaz", "zbcaxyyy", "cccbcahh", "uuxbcazy"]
return "bca"

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

Example 1:
L = ["abcdy", "dcba", "xbcde", "ycdxy", "aabcdx" ], K = 2
solution: string "abcd", it is a substring of K = 2 strings: "abcdy" and "abcdx".
Example 2:
L = ["abcdy", "dcba", "xbcde", "ycdxy", "aabcdx" ], K = 3
solution: string "bcd", it is a substring of K = 3 strings: "abcdy" and "xbcde" and "abcdx".

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

Solutions

Upload your working solution of a problem below to the form PGE Practices 06 _ basic recursion.

Try to upload at least one solution in each of the sections [A], [B], [C], [D].

shared solutions: onlinegdb.com

The problems 01., 02., 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 part of your training, you may consider also the problems listed in the “Output based practice problems for beginners” section (scroll down the page).

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

-- Problem 01. --

Take a recursive function in the lecture file  recursive1.py
and modify in such way that instead of printing the values
the function only returns a list of values without printing anything.
Use functions  rec_seq_down, rec_seq_up, rec_seq_updown.

An example of modification is below:
# original function
# -----------------
def rec_seq_downup( N ):
if N < 4:
print( " bottom reached ", end = '' )
return
print( N, end = ' ' )
rec_seq_downup( N-1 )
print( N, end = ' ' )

# modified function and its usage
# -------------------------------
def rec_list_downup( N ):
if N < 0:
return []
partial_list = rec_list_downup( N-1 )
result_list = [N] + partial_list + [N]
return result_list

downup = rec_list_downup( 12 )
print(downup)

-- Problem 02. --
Take a recursive function in the lecture file  recursive1.py
and modify in such way that instead of printing all values
the function only prints even numbers and each printed number
is followed by an underscore.
Use functions  rec_seq_down, rec_seq_up, rec_seq_updown.

An example of modification is below:
# modified function
# -----------------

def rec_even_downup( N ):
if N < 0:
print( " bottom reached ", end = '' )
return
if N%2 == 0: print( str(N)+"_ ", end = '' )
rec_even_downup( N-1 )
if N%2 == 0: print( str(N)+"_ ", end = '' )

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

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
========

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

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

-- Problem 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    [C]
----------------------------------------------------------------------------------------

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

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

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

-- Problem 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    [D]
----------------------------------------------------------------------------------------

-- Problem 7. --
Determine the return value of the call f7(100).
Executing this call on an usual notebook would take about 10 000 000 000 000 000 years.
However, with little analysis, the exact return value can be easily found
without running the function.

def f7( N ):
if N < 1: return 2
return f7( N-1 ) + f7( N-1 )

Hint:  Calculate f7(1), f7(2), f7(3), f7(4), etc. Observe the pattern and make a conclusion.

-- Problem 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)
#
##
###
####
#####

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

-- Problem 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.

-- Problem 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.

-- Problem 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.)

-- Problem 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.

-- Problem 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.

-- Problem 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


'''
A string is made of two characters, 'o' and 'I'.
Let us call them base character and selected character.
Two non-negative integers N and K are given, K <= N.
The task is to generate a list of all strings
which length is N and which contain exactly K selected characters.

The input is given by values N and K on a single line.
The output consists of two lines. The first line contains all
generated strings, separated by spaces, and no other characters,
the second line contains the length of the list
and the number of calls of the recursive function which generated the list.

To count the number of recursive calls, your implementation has to
follow precisely the description of the recursive function  given below.

Examples

Input
3 1
Output
Ioo oIo ooI
3 5

Input
4 1
Output
Iooo oIoo ooIo oooI
4 7

Input
4 2
Output
IIoo IoIo IooI oIIo oIoI ooII
6 11

Input
5 3
Output
IIIoo IIoIo IIooI IoIIo IoIoI IooII oIIIo oIIoI oIoII ooIII
10 19

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
The solution is based on the recursive idea:
Let us suppose, N = 5, K = 3.
To generate the list of all strings of length 5, with 3 selected characters,
Let us suppose we already have at our hands two lists L1 and L2:
L1 contains all strings of length 4 with 2 selected characters.
L2 contains all strings of length 4 with 3 selected characters.

L1 = IIoo IoIo IooI oIIo oIoI ooII
L2 = IIIo IIoI IoII oIII

Now, we prepend  one selected character to each string in L1.
In this way we obtain all strings of length 5, with 3 selected characters,
which begin with selected character

Next, we prepend  one base character to each string in L2.
In this way we obtain all strings of length 5, with 3 selected characters,
which begin with base character.

L1 = IIIoo IIoIo IIooI IoIIo IoIoI IooII
L2 = oIIIo oIIoI oIoII ooIII

Finally, we just merge L1 and L2 into a single list, because
now we have all demanded strings of length 5.

To obtain a general solution, we just substitute N for 5, N-1 for 4,
K for 3, and K-2 for 2 in the description above.

------------------------------------------------------------------
Another example
------------------------------------------------------------------

Let us suppose N = 4, K = 2.

First,
L1 contains all strings of length 3 with 1 selected character.
L2 contains all strings of length 3 with 2 selected characters.

L1 = Ioo oIo ooI
L2 = IIo IoI oII

Next after prepending selected character to strings in L1 and
base character to each string in L2 we obtain:

L1 = IIoo IoIo IooI
L2 = oIIo oIoI ooII

FInally, L1 + L2 is the solution for N=4, K=2.
------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------

Recursive function F

Parameters of F are N and K

First, F checks if it is time to stop and return from recursion.
If K is equal to 0, F immediately returns string consisting of N base characters.
If K is equal to N, F immediately returns string consisting of N selected characters.

When neither of the previous cases happens, F performs two recursive calls
and returns the combined result of both calls.
The first call returns list L1 of all strings,
which Length is N-1 and which contain K-1 selected characters.
The second call returns list L2 of all strings,
which Length is N-1 and which contain K selected characters.
Now, the function prepends each string in L1 with selected character
and each string in L2 with base character.
Finally, it returns the concatenation of L1 and  L2.

----------------------------------------------------------------

More examples

Input
7 0
Output
ooooooo
1 1

Input
7 1
Output
Ioooooo oIooooo ooIoooo oooIooo ooooIoo oooooIo ooooooI
7 13

Input
7 2
Output
IIooooo IoIoooo IooIooo IoooIoo IooooIo IoooooI oIIoooo oIoIooo oIooIoo oIoooIo oIooooI ooIIooo ooIoIoo ooIooIo ooIoooI oooIIoo oooIoIo oooIooI ooooIIo ooooIoI oooooII
21 41

Input
7 3
Output
IIIoooo IIoIooo IIooIoo IIoooIo IIooooI IoIIooo IoIoIoo IoIooIo IoIoooI IooIIoo IooIoIo IooIooI IoooIIo IoooIoI IooooII oIIIooo oIIoIoo oIIooIo oIIoooI oIoIIoo oIoIoIo oIoIooI oIooIIo oIooIoI oIoooII ooIIIoo ooIIoIo ooIIooI ooIoIIo ooIoIoI ooIooII oooIIIo oooIIoI oooIoII ooooIII
35 69

Input
7 4
Output
IIIIooo IIIoIoo IIIooIo IIIoooI IIoIIoo IIoIoIo IIoIooI IIooIIo IIooIoI IIoooII IoIIIoo IoIIoIo IoIIooI IoIoIIo IoIoIoI IoIooII IooIIIo IooIIoI IooIoII IoooIII oIIIIoo oIIIoIo oIIIooI oIIoIIo oIIoIoI oIIooII oIoIIIo oIoIIoI oIoIoII oIooIII ooIIIIo ooIIIoI ooIIoII ooIoIII oooIIII
35 69

Input
7 5
Output
IIIIIoo IIIIoIo IIIIooI IIIoIIo IIIoIoI IIIooII IIoIIIo IIoIIoI IIoIoII IIooIII IoIIIIo IoIIIoI IoIIoII IoIoIII IooIIII oIIIIIo oIIIIoI oIIIoII oIIoIII oIoIIII ooIIIII
21 41

Input
7 6
Output
IIIIIIo IIIIIoI IIIIoII IIIoIII IIoIIII IoIIIII oIIIIII
7 13

Input
7 7
Output
IIIIIII
1 1

'''



With example solutions below.

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.

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 leaves of 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.


# Queue BFS

0.
Solve any problems in the previous tree related section(s),
as a kind of repetition and a reinforcement of your tree manipulation skills.

1.
Modify the BFS procedure in such way that it prints only the keys in the leaves of the tree,
it does not print the keys in the internal nodes of the tree.

2.
Modify the BFS procedure in such way that it prints the keys in each particular level
of the tree on a separate line. Specifically, the key of the root will be printed also on a separate line.

3.
Homework 3.1.
# ----------------------------------------------------------------------------------
Modify the BFS procedure in such way that it prints the keys in each particular level
in order from right to left.
Example:
_______24________
____12___       ____3____
13     17     __22__    8
6    1
Output:  24  3 12   8 22 17 13  1 6

Assignment text in Brute:
# ----------------------------------------------------------------------------------

4.
Modify the BFS procedure in such way that it prints the keys  in the tree
only up to a given depth D.
Example, using the tree in the previous Example:
D = 0
Output:  24
D = 1
Output:  24 12 3
D = 2
Output:  24 12 3 13 17 22 8

5.
Use BFS procedure to locate in the tree  and print all such nodes
which key is bigger then the parent key. Suppose that a reference
to the parent is not part of the node representation.

6.
Use BFS procedure to create a physical duplicate of a tree.
The shape of the duplicate will be the same as that of the original
and each node key in the duplicate will be twice as big as the key in
the corresponding original node.

7.
Use BFS to check whether the shape of two given trees is identical.
The key values in both trees may be arbitrary and should not be considered in the check.



Example solutions of problems 2. and 4. in recursive tree processing paragraph above.
The functions and the main program are an extension of the tree manipulation code presented in Lecture 7 code ADT tree 2.

# ...
# simple auxilliary function
def isLeaf(self, node):
if node == None: return True
return node.left == None and node.right == None

#2.
#The function returns sum of all keys in the leaves of the tree.
def f2(self, node):
if node == None: return 0
if self.isLeaf( node ):
return node.key
#else:
return self.f2(node.left) + self.f2(node.right)

#4.
# The function returns the number of all nodes which height
# (see definition in the lecture code) is equal to a given value H.
# Solution:
#   Each recursive call of the function returns two values:
#      -- the number of the nodes with the given property
#         in the whole sub-tree which root is in the current node,
#      -- the height of the current node
def f4(self, node, givenH ):
# (Compare the returned -1 value to the analogous approach
# in the keysToHeights function in the lecture code )
if node == None: return 0, -1

# Extract necessary information from the left and the right subtree
countL, heightL = self.f4( node.left, givenH )
countR, heightR = self.f4( node.right, givenH )

# combine the extracted information from the subtrees
# to construct the information relevant to the current node

nodeHeight = 1+ max(heightL, heightR)
if nodeHeight == givenH:
nodeCount = 1 + countL + countR
else:
nodeCount = 0 + countL + countR

return nodeCount, nodeHeight

def markNodesWithHeight(self, node, givenH):
if node == None: return -1

heightL = self.markNodesWithHeight( node.left, givenH)
heightR = self.markNodesWithHeight( node.right, givenH)
nodeHeight = 1 + max( heightL, heightR )

if nodeHeight == givenH:
node.tag = '*'

return nodeHeight

def unmarkAllNodes(self, node):
if node == None: return
self.unmarkAllNodes( node.left )
self.unmarkAllNodes( node.right )
node.tag = ' '

# ............................................................................
#                M A I N   P R O G R A M
# ............................................................................

#...

print( "sum of keys in the leaves")
print( t.f2(t.root) )

givenHeight = 2
t.markNodesWithHeight( t.root, givenHeight )
t.display()
print( "Number of nodes with the given height", givenHeight)
count, rootheight = t.f4(t.root, givenHeight)
print( count )
t.unmarkAllNodes( t.root )

#############################################################################################
turtle example(s)
b = []
posx, posy, dir, trc, penup = 0,0,2, 'o', True
ddir = [ [0,1], [-1,1], [-1,0], [-1,-1], [0,-1], [1,-1], [1,0], [1,1] ]
dirname = ["E", "NE", "N", "NW", "W", "SW", "S", "SE",  ]
def init( w, h ):
global b
b = [ ['.']*w for i in range(h) ]

def disp():
global b
b[posy][posx] = 'T'
for i in range(len(b)):
line = b[i]
for c in line:
print( ' '+c, end = '')
if i == posy:
print( " dir = " + dirname[dir], end = '' )
print()
print("-" * len(b[0]))

def setpos( x, y ):
global posx, posy
posx, posy = x,y

def fd( n ):
global posx, posy, b
for i in range( n ):
if 0<=posy<len(b) and 0<=posx<len(b[0]):
b[posy][posx] = trc
posy += ddir[dir][0]
posx += ddir[dir][1]

def lt():
global dir
dir = (dir+1) % 8

def rt():
global dir
dir = (8+dir-1) % 8

def spir( n ):
if n <= 0: return
fd(n); lt(); #lt();
spir( n-1 )

init( 40,40 )
setpos( 39,28 )
spir(14)
disp()
'''
fd(2)
lt()
fd(4)
rt()
fd( 2 )
disp()
'''



# Using Matplotlib library

Recall the climate text files in the section Climate data above.

1.
Process a climate text file.
Find the average temperature on each day in all years on record.
That is, compute the average temperature for each day separately.
There will be an average temperature of 1.1., an average temperature of 2.1.,
etc. up to average temperature on 31.12.
Thus, there will be sequence of 365 average temperatures, for each day in a year.
For simplicity, skip and do not process 29.2. in the leap years.

Display all average temperatures in a plot
using  matplotlib library.
There will be 365 data points to display in the plot.
Choose yourself visual parameters of the plot
(points shape/color, grid, etc.)

The climate file will be a parameter of your solution.

( If you want to add some more features to the display,
consult the documentation references in the lecture or search the web. )

[Apart form the lecture examples, see also another example solution at the page bottom.]

# Using CSV files

Using data from https://www.gapminder.org

Problems:

1.
Find those countries which population was between 1M and 2M in 2015.

2.
Find countries which had less than 100k internet users in 2015.

3. Find the year in which the worldwide increase
of the net user was the biggest, compared to the previous year.
(the difference of the total number of net users between two
successive years is maximized.)



# Asymptotic complexity

 Determine the asymptotic complexity of a function which solves
a problem marked by the label
(**complexity!**) in the sections 1D array problems and 2D array problems above.

You may either use some of your code solutions of those problems
or you may work completely analytically without coding.

Explain your reasoning in a single short paragraph,
sometimes even 2-3 lines of explanation are sufficient.
Send your finding to berezovs@fel.cvut.cz.

# 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.

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

# 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

file = open( fileName, "r" )

while True:
if line[0:5] == "STAID": break

dateMinTemper = 0

# to compute average
totalTemp = 0
noOfDays = 0

# process all lines
while True:
# 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\\PGE2021\\data\\"
fname = "TG_STAID000169.txt"

avg20century(path + fname)

# if the data file is in your working directory
# it is enough to set
# path = ""