Algorithm

This algorithm finds all best paths (in most cases) 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

Requirement for map:

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

2. Map must have start and 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 start and 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 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:

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 have start or end room with no BFS level (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 have each room.

Step VI: Delete dead ends

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

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 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 left 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 contains 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 left for room. We can left anyone input link and delete all other input links for this room.

But, if 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 consider, if room has output fork, only rooms between the start and the current rooms. (The start and the current rooms can have output forks. Now it is not important).

At this example we have input fork at the room_4.

And we have to find out which of two input links we will left 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 with output fork. So [room_4] <- [room_1] 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 current room and the start 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

Step IX: Form paths

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