/leistungsnachweis-ride-distributor

Solution for the online qualification round of Google HashCode 2018

Primary LanguageC++

Ride distributor

Build status

Solution to the Self-driving rides problem statement for the Online Qualification Round of Hash Code 2018.

Getting Started

Use CMake to generate a Visual Studio project, after cloning this repo. From then on use ".build/RideDistributor.sln" to work on the project.

Installing

Create Workspace

cmake . -B".build" -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DCMAKE_BUILD_TYPE=Debug

Create Executable

cmake --build .build --target all

Debug informations are printed to the console by default. They can be deactivated by defining "NDEBUG".

Create Documentation

cmake --build .build --target doc

Unit Tests (create executable first)

cd .build && ctest -VV

Usage

RideDistributor takes two parameters. The first one is the path to the input file, the second one the path to the output file.

Example for the a_example.in file given by Google

RideDistributor.exe ..\..\resources\a_example.in ..\..\resources\a_example.out

The score of the output file can be checked using nikosk93/hashcode2018_grader.

Results

The following table shows benchmarks from all versions of this project: (each of the columns links to the commit of that version)

Heuristic Beam Search Best-first search (using points) Best-first search (using times left + points)
a_example.in 10 8 10
b_should_be_easy.in 124373 168815 176877
c_no_hurry.in 8747443 9133444 14825711
d_metropolis.in 1708208 4403978 3015856
e_high_bonus.in 2503182 3363963 21465945
Total 13,083,216 17,070,208 39,484,399

Built With

Authors

Acknowledgments