Algorithm

This algorithm finds all best (in most cases) paths and move ants from the start room to the end room in an optimal way (with the least amount of turns).

Step I: Parse map file and validate received data

Requirements for map:

1. Map must have a valid number of ants: 1 <= number of ants <= INT_MAX.

2. Map must have the start and the end rooms.

3. Map must have no rooms with the same names. Each room name must be unique.

4. Map must have no rooms with the same coordinates.

5. Map must have one or more links.

6. Each link must have valid names of the start and the end rooms. It means that rooms with these names are present in map file.

7. Map must have no duplicates of links. There are no links that connect the same points.

Seventh requirement means that map file cannot have the following lines:

dining_room-living_room
// a few other links
living_room-dining_room

Also these lines are not possible in map file too:

dining_room-living_room
// a few other links
dining_room-living_room

To help understand created algorithm some steps have images with example of map, that display it after current part of algorithm work. For example, we received the following map after parsing and validation:

Step II: BFS (Breadth-first search)

At this step I use BFS algorithm. But my point is not to find out the shortest path. My point is to find out levels that this algorithm assigns to rooms.

Rooms are called vertices in a graph theory. Links are called arcs.

If you know Russian, you can check this video about how BFS algorithm works. It provides a good explanation.

I use BFS algorithms as it is, but with one little change — end room will get MAX_INT as BFS level.

It is important for correct algorithm work.

Step III: Delete useless links

At this step I have to delete useless links on the map.

Which links are useless?

• Peer-to-peer links. (Links that connect rooms with the same BFS level)
• Links which connect rooms with no BFS level. If one of the room, which this link connects, has no BFS level, link is useless. (BFS level assigned to -1 during initialization).

Step IV: Align links

At this step we have to align remaining links. It means that all links have to have the following structure:

room with BFS level N-room with BFS level M, where N < M.

So at this step each link will receive direction.

I use this step to prepare received data to the next step.

Step V: Count input and output links for each rooms

Using links directions that were found out at the previous step, we have to calculate how many input and output links has each room.

Step VI: Delete dead ends

At this step we have to delete all links to the rooms that have no one link of one type, but have one or more links of another type. Exception is the start and the end rooms. For example, all links to room, that has 2 input links and 0 output links, will be deleted. (Obviously, if it is not the end room)

Step VII: Delete input forks

We have to iterate over rooms at each BFS level. (Except BFS levels of the start and the end rooms). In the current example we have to iterate over rooms from 1st BFS level to 4th BFS level.

If we find the room that have more than one input links we have to select one best suitable input link and delete all others.

How we will know which link is the best?

It is so easy.

If all paths from the start room to the current room contain room with output fork (room has more than one output links), it means that all links are bad. And it is not important which link of them we will keep for room. We can left anyone input link and delete all other input links for this room.

But, if there is path from the start room to the current room, that was build with this link, has no rooms with output fork, it means that this link is the best. And we have to delete all others.

Note that we check, if room has output fork, only for rooms between the start and the current rooms. (The start and the current rooms can have output forks. Now it is not important).

At our example we have input fork at the room_4.

And we have to find out which one of two input links we will keep for room_4 and which input link will be deleted.

Let's build paths with each link.

Path with [room_4] <- [room_1] input link

[room_4] <- [room_1] <- [room_0]

This path contains room_1. Thus room has output fork. So [room_4] <- [room_1] link is bad.

Path with [room_4] <- [room_2] input link

[room_4] <- [room_2] <- [room_0]

There are no rooms with output fork between the start room and the current room. So [room_4] <- [room_2] is the best link.

Now we have to delete [room_4] <- [room_1] link to remove input fork at the room_4.

Step VIII: Delete output forks

We have to iterate over rooms at each BFS level. (Except BFS levels of the start and the end rooms). But now in descending order. In the current example we have to iterate over rooms from 4th BFS level to 1st BFS level.

If room has more than one output links, we have to select one of them and delete all others.

How to select the best one link?

We have to build path from the current room to the end room with each link. Link which was part of the shortest path is the best.

Let's check our example. We have output fork at room_3.

With these room we will have the following paths:

Path with [room_3] -> [room_6] link

[room_3] -> [room_6] -> [room_8] -> [room_9]

This path's length is 3.

Path with [room_3] -> [room_7] link

[room_3] -> [room_7] -> [room_9]

This path's length is 2.

So we have to keep [room_3] -> [room_7] link and delete [room_3] -> [room_6] link.

Step IX: Form paths

At this step we have to form paths. It is not difficult, because we have no forks. Our task is only form paths and sort them by length in ascending order.

Step X: Perform turns (Move ants from start to end room)

It is only one step in this algorithm description, but it is also very important part. It is mini algorithm which help to select path for each ant.

To make decision we have to know how many ants remain at the start and sum of differences between length of current path and lengths of shorter paths.

For example we have three paths:

1. Length of Path #1 is 1.

2. Length of Path #2 is 7.

3. Length of Path #3 is 10.

Number of ants at the start is 20.

At each step we will iterate over paths by their length in ascending order and make decision — move ant by this path or not.

First step

Ants at the start	Current path	Expression	Move ant by this path
20	Path #1	20 > 0	Yes
19	Path #2	19 > (7 - 1)	Yes
18	Path #3	18 > ((10 - 1) + (10 - 7))	Yes

Second step

Ants at the start	Current path	Expression	Move ant by this path
17	Path #1	17 > 0	Yes
16	Path #2	16 > (7 - 1)	Yes
15	Path #3	15 > ((10 - 1) + (10 - 7))	Yes

Third step

Ants at the start	Current path	Expression	Move ant by this path
14	Path #1	14 > 0	Yes
13	Path #2	13 > (7 - 1)	Yes
12	Path #3	12 > ((10 - 1) + (10 - 7))	No

...