Practices 05: Further Array Processing

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:

1. Zip the file main.py into .zip archive with arbitrary name.
2. Upload the .zip file to the BRUTE evaluation system.

You can obtain maximum of 2 points.

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