## English translation

The Martian ships assumed attack position around the Earth. Slovenian army is ready for them: it has CISSes (Completely Invisible Spaceships) that can destroy the enemy. They need a strategic plan, which is the topic of this task.

To understand what you'll be doing, watch the animation. Martian ships are represented by circles, ours by squares.

## Grade 6

Write a function

`razdalja(x, y)`

, which gets two tuples representing coordinates of points, and returns the Euclidean distance between them. To be ready for transdimensional beings, it should work with arbitrary number of dimensions. The distance is always computing as the square root of sums of squared differences,$$d(x, y) = \sqrt{\sum_{i=0}^{n-1}(x_i - y_i)^2}$$

- Call
`razdalja((5, 12), (2, 16))`

returns 5 (that is, $\sqrt{(5 - 2)^2 + (12 - 16)^2} = \sqrt{3^2 + 4^2}$). - Call
`razdalja((5, ), (8, )`

(distance on a line) returns 3 (that is, $\sqrt{(5 - 8)^2}$). - Call
`razdalja((1, 7, 4, 2, 6, -7, 4), (-1, 10, 5, 2, 6, -8, 3)`

(distance in 7-dimensional space) returns 4.

- Call
Writa a function

`najblizja(marsovec, ladje)`

, which gets a tuple representing the coordinates of Martian ship, and a list of tuples, representing the coordinates of our ships. The function must return the coordinates of our ship that is the closest to the Martian.- Call
`najblizja((1, 1), [(0, 0), (5, 2), (-8, 3)]`

returns`(0, 0)`

, because this is the closest ship to the Martian ship at`(1, 1)`

. - Call
`najblizja((-7, 2, 5, 1), [(0, 0, 5, 2), (5, 2, 5, 2), (-8, 3, 5, 2)])`

returns`(-8, 3, 5, 2)`

.

- Call
Write a function

`dodeli_ladje(marsovci, ladje)`

, which gets a list of coordinates of Martian and our ships. It must return a list of tuples of the same length as`marsovci`

: The i-th element of the result contains the coordinate of our ship that is the closes to the i-th Martian ship.- Calling
`dodeli_ladje([(1, 1), (0, 0), (-7, 2), (5, 1)], [(0, 0), (5, 2), (-8, 3)])`

returns`[(0, 0), (0, 0), (-8, 3), (5, 2)]`

.

- Calling
Write a function

`skupine_marsovcev(marsovci, ladje)`

, which returns a list of sets of tuples with coordinates of Martian ships. The list is of the same length as`ladje`

. Each element of the result is the set of coordinates of Martian ships that will be destroyed by the corresponding ship from`ladje`

.The order of elements in the result may be arbitrary.

Call

`skupine_marsovcev( [(0, 1), (2, 2), (51, 52), (100, 100), (1, 3), (4, 5), (45, 50), (103, 98)], [(0, 0), (50, 50), (100, 100)]))`

returns

`[{(0, 1), (2, 2), (1, 3), (4, 5)}, {(100, 100), (103, 98)}, {(51, 52), (45, 50)}]`

The first set is destroyed by our ship at

`(0, 0)`

, the second by our ship at`(100, 100)`

and the third by our ship at`(50, 50)`

.The function essentially returns the coordinates of the ship that are designated the same color in the animation.

Hint: although this may not be obvious at the first glance, this task is about dictionaries.

## Grade 7

Write a function

`sredisce(s)`

that gets a list of coordinates (tuples) and returns a tuple with the coordinate of the center of these points. Coordinates of the center are computed as average per each coordinate separately.`s`

can be of arbitrary length. Coordinates are of arbitrary dimensionality.- Call
`sredisce([(2, 8), (6, 10)`

returns`(4, 9)`

.

- Call
Write a function

`razpostavi_ladje(skupine)`

, which returns the optimal placement of the ships for the given groups. The argument is in the same shape as the result of function`skupine_marsovcev`

. The function must return a list of coordinates of centers of groups (sets).- Call

`razpostavi_ladje([{(0, 1), (2, 2), (1, 3), (4, 5)}, {(100, 101), (103, 98)}, {(51, 52), (45, 50)}])`

returns a list that contains

`[((0 + 2 + 1 + 4) / 4, (1 + 2 + 3 + 5) / 4), ((100 + 103) / 2, (101 + 98) / 2), ((51 + 45) / 2, (52 + 50) / 2)]`

## Grade 8

Write a function

`optimiraj_ladje(marsovci, ladje)`

, which gets the coordinates of Martian ships and some initial position of our ships. The function alternately repeats two steps:- determine the groups of Martian ships that "belong" to each or our ships (like done by
`skupine_marsovcev`

); - based on these groups, find a better placement of our ships - move each ship to the center of its designated group;
- the ships have moved, therefore the groups may have changed; compute the new groups;
- move the ships to the centers of new groups;
- reassign the groups ...

The procedure stops when nothing changes any more. The function returns the final positions of our ships.

The function essentially executes the optimization shown in the video. The video represents four calls of this function from different initial positions. Funkcija v bistvu izvaja optimizacijo, ki jo kaže video. Video, konkretno, predstavlja štiri klice funkcije.

For help when debugging, the test contains the sequence of positions in the last test. If your function prints them out, you can check that they are the same.

- determine the groups of Martian ships that "belong" to each or our ships (like done by

## Grade 9

The attack will be most effective if our ships are close to Martian ships. Write a function

`kvaliteta(marsovci, ladje)`

, which returns the sum of distances between Martian ships and the closest our ship. In other words, it returns the sum of lengths of all lines in the animation.Write a function

`nakljucna(marsovci, ladij)`

, which returns a random initial position of the given number (`ladij`

) of ships. Coordinates are randomly chosen using coordinates of Martian ships. The i-th coordinate of each of our ships is randomly drawn from i-th coordinates of all Martian ship.Call

`nakljucna([(5, 8), (2, 17), (1, 33), (4, 9)], 3)`

could return, for instance

`[(1, 8), (4, 17), (2, 8)]`

. Each coordinate x is randomly drawn frmo x-coordinates of Martian ships, and y-coordinates are drawn from y-coordinates.

## Grade 10

Write a helper function

`optimiraj_ladje_2(marsovci, ladje)`

, which is the same as`optimiraj_ladje`

, except that it returns a tuple with quality and positions, where quality is computed using function`kvaliteta`

.Assume that we start the optimization from some random position. As we can see from the third case in the video, we can be unfortunate and end up with some poorly-optimized positions. To prevent that, we run the procedure multiple times from different random positions. Write a function

`planiraj(marsovci, ladij)`

, which starts with 100 random positions and return the best final position that it encountered in any of 100 optimizations.

## About tests

Tests include fuction signatures with some documentation in one of the usual formats. Definitions also include some type annotation. Ignore if you don't understand it. If you do, this can serve as further clarification of argument types.

The order of elements of lists in results of functions is sometimes arbitrary. Tests will sort the result of your function and compare it with sorted expected result. Don't let this confuse you; you don't have to sort anything.

If your function returns a list when the tests expect a tuple, they will (usually) complain. Note the different parentheses/brackets/braces in the output.

`(3)`

is not tuple but just `3`

in parentheses. `(3, )`

is a tuple.

If test expects that the function will return `[(4 + 6) / 2, (3 + 9) / 3]`

, it, of course, expects a list with numbers `[3, 4]`

. Tests are written in this form to help you understand what you need to compute.

The test of the last function creates random sets of 20 points in the vicinity of 3 points. Then it computes the center of each set. These points are actually the centers that must be discovered and returned by your function. It is expected that the function will stumble upon those at least once (but more likely) 90 times out of 100.