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.

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

  • 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)].

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

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

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.