====== Practices 05: Further Array Processing====== ==== Overview ==== In practice 05, you will create a single Python file ''main.py''. In this file you will write (or complete) the following functions, each of which solves a particular problem: * ''task01(arr)'' * ''task02(arr)'' * ''task03(L)'' * ''task04(A)'' * ''task05(arr)'' * ''task06(matrix, n)'' Both filename and names of the functions have to be exactly the same as described. When submitting your solution: - Zip the file ''main.py'' into **.zip archive** with arbitrary name. - Upload the .zip file to the [[https://cw.felk.cvut.cz/brute/|BRUTE]] evaluation system. ==== Grading ==== You can obtain maximum of **2 points**. ==== Testing Your Code Localy ==== In starter code which is provided bellow each function contains **docstring** with short desription. Docstrings also contain examples of usage. Those examples can be used for testing your functions using **doctest** module. To run those tests you can simply run the ''main'' module as main script.



import numpy as np

def task01(arr):
	"""
	Returns number of steps performed by robot when moving two types of items (represented by 1 and 2)
	from leftmost third of the list "arr" into their position.

	Detailed description:

	In this problem, ranges are denoted in python style,
	e.g. range(2, 5) spans indices 2,3,4, but not 5.
	A given input array (list) consists of 3*N consecutive cells, N > 0.
	Positions in range(0, N) are filled with N integers in radom order,
	each of those integers is either 1 or 2.
	The rest of the array is filled with 0.
	The storage area for 1's is range(N, 2*N)
	The storage area for 2's is range(2*N, 3*N).

	A robot R is moving through the array, in each steps it moves from its current cell
	to one of the adjacent cells.
	When moving from a cell with index A to a cell with index B, the robot makes |A-B| steps.
	The task of the robot is to move all values from range(0, N) to their
	corresponding storage areas.

	Robot works in cycles. In one cycle, robot
	   -  moves to the rightmost cell with a non-zero value X, in range(0, N),
	   -  stores 0 in that cell,
	   -  moves to the leftmost cell containing 0 in the storage area for X,
	   -  stores X in that cell.

	Robot starts in cell with index 0.
	Robot repeats one cycle after another, until range(0, N) contains only 0's.

	Remark: Sroring a value X in a cells means that the original value in the cell is
	overwritten by X.

	Visualisation of number of robot steps in each cycle:

	1 2 2 1 0   1 0 0 0 0   0 0 0 0 0     5
	1 2 2 0 0   1 1 0 0 0   0 0 0 0 0     5
	1 2 0 0 0   1 1 0 0 0   2 0 0 0 0     12
	1 0 0 0 0   1 1 0 0 0   2 2 0 0 0     19
	0 0 0 0 0   1 1 1 0 0   2 2 0 0 0     18

	Functions returns the number of robot steps in the whole process.

	:param arr: list containing integer values 0, 1 or 2
	:return: (int) number of robot steps

	Examples:
	>>> task01([1, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
	59
	>>> task01([2, 2, 2, 0, 0, 0, 0, 0, 0])
	32
	>>> task01([2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
	86
	>>> task01([2, 2, 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
	99
	"""
	pass


def task02(arr):
	"""
	Returns number of steps performed by robot when moving items
	from left half of list "arr" into right half.

	Detailed description:

	In this problem, ranges are denoted in python style,
	e.g. range(2, 5) spans indices 2,3,4, but not 5.
	A given input array (list) consists of 2*N consecutive cells, N > 0.
	Positions in range(0, N) are filled with N positive integers in random order,
	no two values are the same.
	The rest of the array is filled with 0.

	A robot R is moving through the array, in each steps it moves from its current cell
	to one of the ajacent cells.
	When moving from a cell with index A to a cell with index B, the robot makes |A-B| steps.
	The task of the robot is to move all values from range(0, N)
	to range(N, 2*N). When the task is finished, the values in range(N, 2*N) are
	sorted in ascending order and range(0, N) contains only 0's.

	Robot works in cycles. In one cycle, robot
	   -  moves to the cell which contains the smallest non-zero value X in range(0, N),
	   -  stores 0 in that cell,
	   -  moves to the leftmost cell containing 0 in range(N, 2*N),
	   -  stores X in that cell.

	Robot starts in cell with index 0.
	Robot repeats one cycle after another, until range(0, N) contains only 0's.

	Visualisation of number of robot steps in each cycle:


	28 18 8 11 0 19 26 13 2 12   1 0 0  0  0  0  0  0  0  0     10
	28 18 8 11 0 19 26 13 0 12   1 2 0  0  0  0  0  0  0  0      5
	28 18 0 11 0 19 26 13 0 12   1 2 8  0  0  0  0  0  0  0     19
	28 18 0  0 0 19 26 13 0 12   1 2 8 11  0  0  0  0  0  0     19
	28 18 0  0 0 19 26 13 0  0   1 2 8 11 12  0  0  0  0  0      9
	28 18 0  0 0 19 26  0 0  0   1 2 8 11 12 13  0  0  0  0     15
	28  0 0  0 0 19 26  0 0  0   1 2 8 11 12 13 18  0  0  0     29
	28  0 0  0 0  0 26  0 0  0   1 2 8 11 12 13 18 19  0  0     23
	28  0 0  0 0  0  0  0 0  0   1 2 8 11 12 13 18 19 26  0     23
	 0  0 0  0 0  0  0  0 0  0   1 2 8 11 12 13 18 19 26 28     37

	Function returns integer number of robot steps in the whole process.

	:param arr: list containing random values in left half and zeros only in right half
	:return: (int) number of robot steps

	Examples:
	>>> task02([1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0])
	61
	>>> task02([6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0])
	71
	>>> task02([2, 1, 4, 3, 6, 5, 8, 7, 0, 0, 0, 0, 0, 0, 0, 0])
	115
	>>> task02([28, 18, 8, 11, 1, 19, 26, 13, 2, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
	189
	"""
	pass


def task03( L ):
	"""Finds the number of all 3-tuples in a list L, each of which contains exactly two equal values

	An unordered k-tuple in a list L is a multiset of k values (some values may be equal),
	each of which appears at a diferent position in L. For example,
	  L = [1, 2, 3, 3, 4].  Some 3-tuples in L are {1,2,3}, {1,2,4} {2,3,3}.
	  Note that multisets {2,2,3}, {4,4,4}, {1,1,2} etc.  are not 3-tuples in L.
	The number of all unordered k-tuples in a list L of length N
	is easy to compute, it is equal to binomial coefficient(N, k) = N! // (k!*(N-k)!).
	Typically, we list the items in the k-tuple in the order in which they appear in L.

	Example
	  Input
	  [7, 7, 7, 4, 4, 1]

	  Output
	  13

	  Comment
	  All 20 unordered 3-tuples in the first list are listed below, by asterisk are marked
	  those which contain exactly two equal values :
	   1 {7,7,7}         6 {7,7,4} *      11 {7,7,4} *      16 {7,4,1}
	   2 {7,7,4} *       7 {7,7,1} *      12 {7,7,4} *      17 {7,4,4} *
	   3 {7,7,4} *       8 {7,4,4} *      13 {7,7,1} *      18 {7,4,1}
	   4 {7,7,1} *       9 {7,4,1}        14 {7,4,4} *      19 {7,4,1}
	   5 {7,7,4} *      10 {7,4,1}        15 {7,4,1}        20 {4,4,1} *

	:param L: list of integers
	:return: (int) number of all 3-tuples in a list L, each of which contains exactly two equal values

	>>> task03([7, 7, 7, 4, 4, 1])
	13
  	>>> task03([8, 1, 7, 2, 6, 3, 5, 4, 8])
  	7
  	>>> task03([1, 2, 3, 1, 2, 3, 1, 2, 3])
  	54
  	>>> task03([2, 2, 2, 2, 4, 4, 4, 4])
	48

	"""
	pass


def task04(A):
	"""
	Returns list containing significance counted for each item in list A.

	Significance of an item I in a list A is equal to
	the number of items with value I//2 located to the left of I
	plus the number of items with value I*2 located to the right of I.

	:param A: list of integer values
	:return: list if the same dimenstion as A, contains significance counted for each item in A

	>>> task04([5, 5, 5, 10, 20, 20])
	[1, 1, 1, 5, 1, 1]
	>>> task04([10, 20, 30, 40, 50, 60, 70, 80])
	[1, 2, 1, 2, 0, 1, 0, 1]
	"""
	pass


def task05(arr):
	""" Finds the shortest dense subarray in the input array

	A **subarray** S of an array A is a slice of array A.
	(The term subarray is more general then the term slice used
	mostly in scripting languages like Python, JavaScript and other.)
	A subarray S of an array A is a **dense** subarray
	when the sum of all elements in S is bigger or equal to
	the half of the sum of all elements in A.

	The task:
	Find the shortest dense subarray S in input array A.
	Print three values: The indices of the first and the last item in S
	and the sum of all items in S.
	When there are more shortest dense subarrays in A, print the output
	related only to the leftmost one.
	The entries on a line are separated by single spaces and the line contains no other symbols.

	:param arr: list of integer values
	:return: tuple containing 3 integer values (K, L, M):
		* K: index of first item in the shortest dense subarray
		* L: index of last item in the shortest dense subarray
		* M: sum of all items in the shortest dense subarray

	>>> task05([1, 0, 2, 0, 0, 0, 3, 4, 0, 1, 1, 2])
	(6, 7, 7)

	>>> task05([1, 3, 5, 7, 9, 2, 4, 6, 8, 10])
	(6, 9, 28)

	>>> task05([0, 0, 0, 39, 0, 41, 0])
	(5, 5, 41)
	"""
	pass


def task06(matrix, n):
	"""Computes a new matrix where each element is the sum of all elements of original matrix
	which are covered by n x n sliding window.

	:param matrix: 2D np.array (matrix) of size M x N
	:param n: (int) dimension of sliding window n x n; n <= min(M, N)
 	:return: 2D np.array (matrix)

	Examples:

	>>> m = np.array([
	...		[2 ,6 ,9 ,5 ,2],
	...		[6 ,2 ,9 ,6 ,7],
	...		[3 ,9 ,1 ,6 ,7],
	...		[5 ,6 ,9 ,3 ,7],
	... ])
	>>> result = np.array([
	...		[47 ,53 ,52],
	...		[50 ,51 ,55],
	... ])
	>>> np.array_equal(task06(m, 3), result)
	True

	>>> m = np.array([
	...		[2 ,6 ,9 ,5 ,2],
	...		[6 ,2 ,9 ,6 ,7],
	...		[3 ,9 ,1 ,6 ,7],
	...		[5 ,6 ,9 ,3 ,7],
	... ])
	>>> result = np.array([
	...		[87 ,94]
	... ])
	>>> np.array_equal(task06(m, 4), result)
	True

	"""
	pass