Using the new PriorityQueue from .NET 6

.NET 6 has brought along a lot of new features. Among these is a new collection type: the PriorityQueue. A PriorityQueue contains pairs of elements and priorities. It then keeps track of the min value of the priorities. This is useful if you need to keep track of a min value in a collection that is continuously updated. In this project, we will show how to use a PriorityQueue in practice by solving a problem from open.Kattis.com.

The problem

First, let's go through the basics of the problem that we are going to solve.
The full description of the problem can be found here: open.kattis.com/problems/flightcollision.

The problem states that there are some drones flying with packages from Iceland to mainland Europe. The drones normally try not to hit each other but because of an error, this system doesn't work. So the problem is given a number of drones (n) that are placed along a straight line at coordinates (x) with a velocity (v). Which drones will survive if all drones keep flying forever? Note that both drones die if they collide and can therefore not hit any other drones.

The input is given through the command line like so:

The first line is the number of drones (n). After that, there are n lines. Each line has two integers that are separated with a space. First, the start position of the drone (x) and then its velocity (v).

We then need to output how many drones are alive at the end (first line) and which ones in a space separated list (second line):

2
1 6

Prerequisites

PriorityQueue's were first introduced in .NET 6 preview 2 so to use this feature you need to install this version of .NET 6 or newer. It can be downloaded following this link: Download .NET 6

For the best developer experience, you also need the newest preview version of Visual Studio. Visual Studio Preview can be downloaded here: Download Visual Studio Preview

Reading input

In a new Console Application we first need to read our input. For this we create a class for the Drones to encapsulate the information relevant to each Drone.

class Drone
{
    public Drone(int x, int v)
    {
        this.x = x;
        this.v =v;
    }
    public int x { get; set; }
    public int v { get; set; }
    public bool dead { get; set; } // This is false by default.
}

Then we start reading from the console in our Main method.

var n = int.Parse(Console.ReadLine());

var drones = new List<Drone>();

for (int i = 0; i < n; i++)
{
    var line = Console.ReadLine().Split();
    drones.Add(new Drone(int.Parse(line[0]), int.Parse(line[1])));
}

First, we read a single line and convert the string that we read to an integer. Then we create a list of Drones and start a loop that will run n times. In the for-loop, we read a single line that we split into an array of strings. We then add a new Drone to the drones list with the two parts of the line converted to integers.

Initial Collision Queue

In order to find which Drones are going to collide, we will need to find the first drones that will collide and remove those and then repeat continuously until no drones collide. We know that it is initially only possible for two drones that are just after each other to collide. So we can simply loop over all adjacent pairs and add them to a PriorityQueue of collisions. This PriorityQueue will then keep track of whatever pair of drones will collide next if we use the time of the collision as the priority.

var collisionQueue = new Queue<(int drone1, int drone2), double>();

for (int i = 0; i < n - 1; i++)
{
    if (drones[i].v > drones[i + 1].v) // Will they ever collide?
    {
        collisionQueue.Enqueue((i, i + 1), CollisionTime(drones[i], drones[i + 1]));
    }
}

When we initialize the PriorityQueue we have to give it two types. First the type of the element in the PriorityQueue and secondly the type we will use for the priority. We use a tuple of int's to identify two drones colliding and a double to hold the time that the drones would collide. We could have used any type that implements the IComparable interface for the priority. Then we make a loop that runs n-1 times. In each round of the for-loop, we first check if the two drones will ever collide. The drones are given in sorted order of their start position (x) so we just have to check if the first of the two drones is faster than the second. If it is then we can Enqueue this pair of drones in our PriorityQueue. And for the priority, we will calculate the time of the collision, which we have split into a separate method.

static double CollisionTime(Drone drone1, Drone drone2)
{
    return (drone2.x - drone1.x) / (drone1.v - drone2.v);
}

The method simply takes the initial distance between the two drones. We divide this by their difference in speed. This gives how long it will take for the first drone to catch up with the second.

Consuming the PriorityQueue

Now we have the drones that could collide to start off with. Then we need to continue to dequeue pairs of drones as long as there are elements in the PriorityQueue.

while (collisionQueue.Count != 0)
{
    (int drone1, int drone2) = collisionQueue.Dequeue();
    if (!drones[drone1].dead && !drones[drone2].dead)
    {
        drones[drone1].dead = true;
        drones[drone2].dead = true;
        // Next section of code
    }
}

We make a while-loop that runs as long as there are elements in the PriorityQueue. Then we Dequeue an element from the PriorityQueue. This gives us the pair of drones that were currently going to collide the first because it takes the element with the smallest collision time. One of the two drones could already be dead due to other collisions so we check that they are both alive (not dead). Then if they are both alive we change them to being dead and continue.

Now that they are dead we need to update the collision queue. Because they are dead, then the first alive drone before the pair could potentially collide with the first alive drone after the pair. For this, we find these two drones and add them to the queue.

var previousAlive = Enumerable.Range(-1, drone1+1).Reverse().First(i => i == -1 || !drones[i].dead);
var nextAlive = Enumerable.Range(drone2 + 1, drones.Count - drone2+1).First(i => i == drones.Count || !drones[i].dead);

For the first prior alive drone, we go through all indices before the first drone backwards and then take the first drone that is not dead or if we reach the end return -1. For the first alive drone after the pair we go from index of the second drone and looks for the first drone that is not dead or return the length of the list if we reach the end. Then we just need to check that there actually were some alive drones before and after and potentially Enqueue them as we have seen before.

if (previousAlive != -1 && nextAlive != drones.Count)
{
    if (drones[previousAlive].v > drones[nextAlive].v)
    {
        collisionQueue.Enqueue((previousAlive, nextAlive), CollisionTime(drones[previousAlive], drones[nextAlive]));
    }
}

This new drone pair will then also be a part of the drones that will need to be checked before the while-loop stops. When the while loop has stopped, there are no more possible collisions and we just need to write how many drones are alive and which.

Printing Output

Console.WriteLine(drones.Sum(d => d.dead ? 0 : 1));
Console.WriteLine(string.Join(' ', Enumerable.Range(0, drones.Count).Where(i => !drones[i].dead).Select(i => i + 1)));

First, we write a line where we make a sum of all drones. For a dead drone, we add 0 to the sum and an alive drone gives 1. Next, we join a list into a space-separated string. The list is the indices of all the drones that are still alive.

Then we are done.

Disclaimer

open.Kattis.com does not use the newest preview version of .NET to run submitted C# code so you will not be able to use this solution on Kattis. Another note is that this solution is not precise enough for very big inputs. When we calculate the collision time we divide integers to get a double. This can cause rounding errors which will make it so that drones will collide in a false order. To fix this we would need to create a custom type for the priority that does not have rounding errors. Essentially, we want it to remember its difference in position and difference in velocity separately and then multiple each side of the comparison with both velocities to get clean integers that can still be compared. This could be implemented like so:

class Collision : IComparable<Collision>
{
    private int diffDistance;
    private int diffVelocity;

    public Collision(int diffDistance, int diffVelocity)
    {
        this.diffDistance = diffDistance;
        this.diffVelocity = diffVelocity;
    }

    public int CompareTo(Collision other)
    {
        if (this.diffDistance * other.diffVelocity < other.diffDistance * this.diffVelocity)
        {
            return -1;
        }
        if (this.diffDistance * other.diffVelocity > other.diffDistance * this.diffVelocity)
        {
            return 1;
        }
        return 0;
    }
}

Conclusion

In this article, we have looked at a specific problem from open.Kattis.com that can be solved using the new PriorityQueue from .NET 6. We have seen how to initialize a PriorityQueue. We have seen how to Enqueue (add) element-priority pairs to a PriorityQueue. And we have seen how to Dequeue (get) an element from a PriorityQueue. Credit and thanks to Jorke de Vlas who made this problem for the Northwestern Europe Regional Contest 2020.