Solution of Team uwunauten for the Informaticup 2023

This is the repository for the solution of the Team uwunauten for the Informaticup 2023 hosted by the German Society of Computer Science. You can find more information about the competition here.

Background for Task "Profit!"

This year's task was called "Profit!". The task was to place different components on a 2D-Grid to connect deposits with factories to enable the production of products. Solutions were scored by the products they were able to produce in a number of fixed timesteps of the simulation. More information can be found in the offical task description.

Solution

Our main idea was to split the task in different subproblems, and then combine these solutions into the global solution. In a Divide and Conquer fashion, we start off with determining connected components. Each connected component defines deposits that can reach other. Two connected components are shut off from each other, enabling us to split the map into multiple, independent subareas which we solve one by one. For each of the parts, we model the selection of products as a Knapsack problem and applied a greedy solving strategy. The connection between deposits and factories is done by a modified Dijkstra-Algorithm to prevent self-intersections. To evaluate the score of given connections, we modeled the available resources as piecewise linear functions, which allows us to estimate the score within constant time, without the need for the specified turn-based simulation. To allow for the fast combination and testing of the different partial solutions, we implemented our solution in modern C++20 with execution speed as a priority. Our solution aims to provide a solid setup which can be manually optimized after, rather than providing an already optimized score. More information is found in our documentation (german).

Usage

Docker

The easiest way to run our solution is using Docker with the provided Dockerfile. You can build the docker container using

docker build --tag DOCKER_TAG .

and run it using

docker run -i DOCKER_TAG < tasks/001.task.json

This prints the solution on the command line.

Build yourself

Our project uses CMake as a build system. We support to build options: RELEASE and DEBUG. You can configure them e.g., with ccmake.

To generate Makefiles:

mkdir build && cmake build 

To build, run make from the build folder

make 

We use STDIO for input and output. An example call would be:

./main < ../tasks/001.task.json > output.json

Development

Tests can be run with ctest: ctest