Centaure sur Tore

Description

In the Alpha Centauri system, you operate a farm for centaurs located on a toroidal asteroid. The pastures are organized into square fields, separated by barriers placed at predefined locations. A centaur can move from one field to a neighboring one horizontally, vertically, or diagonally if there is no barrier blocking access. During diagonal movements, the corridor allows centaurs to move straight ahead, but it is too narrow for them to change direction (see the attached image example-directions.png for an explanation of possible movements).

You are about to manage two centaurs. However, there’s a catch - centaurs are solitary animals, and it is of paramount importance to prevent the two centaurs from meeting in the same square field. Before accommodating them, you only have time to install three additional barriers in the area: where should you place them to house the two beasts without allowing them to meet?

The square fields are identified by a coordinate system, for example, (0, 1) or (1, 2), and the locations for the barriers are identified by a pair of coordinates, for example, ((0, 1), (1, 2)).

An example in a 5x5 dimension is provided in the attached figures:

• example-empty.png: an example of a toroidal centaur farm with barriers placed between the square fields.
• example-directions.png: an example of possible directions with a given placement of barriers. In this example, from the square field located at (1, 1), a centaur can go to (2, 0), (0, 2), and (2, 2).
• example-solved.png: an example of a barrier to add to isolate the two centaurs. The program expects input like: [((1, 1), (0, 2)), ((3, 1), (4, 2)), ((3, 3), (4, 3))]. The order of square fields is not important; ((1, 1), (0, 2)) and ((0, 2), (1, 1)) represent the same barrier.

Once connected to the service below, you will need to place three barriers in 100 randomly generated farms. If you succeed within the 30-second limit for each farm, you will get the flag!