The provided solution starts by sorting the locations by weight in ascending order and the drones are sorted in descending order by weight and converted into a data structure called a queue. Then the first drone is obtained from the queue which will be the most weight capacity, with this drone, a greedy algorithm that maximizes the number of packages delivered on each trip concerning weight will select the best trip and sum each weight.
If the sum is lower or equal to the second drone with the most weight capacity, this will be assigned to the second drone and it will come out from the queue. The process mentioned before will be repeated until no location remains by assignment.
The solution created with Visual Studio 2022 consists in three .NET 6 projects built which are the following:
-
DroneDelivery: It has a domain driven design (DDD) architecture folder structure:
- Domain: Folder with the application entities.
- Common: Only contains a class (DataFormatter.cs) with its interface to process input and output for the application.
- Application: Contains classes with its interfaces with business logic to find best trip.
- NuGet Dependencies: None.
-
DroneDelivery.Console: Console app where the dependencies are injected by IHost container in the Startup.cs file. Command usage can be obtained executed the following:
drone-delivery -h
ordrone-delivery --help
Also it has a parameterless execution where it will ask you for the input file path.
The output will print out and an output file gonna be created with the date time execution append with the file name. If OS execution platform is Windows, automatically it will open the file with
Notepad
- NuGet Dependencies:
- Microsoft.Extensions.Hosting (7.0.0)
- NuGet Dependencies:
-
DroneDelivery.Test: Project with five unit test for the class
DeliveryService
,TripService
andDataFormatter
. This program was tested with 100 drones and 1000 locations, with a duration of 17 seconds on average in a Ryzen 5 processor as the image below shows.In the command line, you can run the following:
dotnet test DroneDelivery.Test
- NuGet Dependencies:
- coverlet.collector (3.1.2)
- FluentAssertions (6.9.0)
- xunit (2.4.1)
- xunit.runner.visualstudio (2.4.3)
- Microsoft.NET.Test.Sdk (17.1.0)
- NuGet Dependencies: