Idego Pytech Challenge
We have prepared a contest especially for the attendees of the Pytech Summit 2022 conference! Recall our speech on the biggest event in Poland dedicated to the Python language:
Details of the challenge
You have a set of tasks that needs to be performed by a machine. Each task has the following format:
{
'name': string,
'resources': list of strings,
'payoff': float
}
Each task provides some payoff when completed, and requires a set of resources to be performed.
- If two tasks require the same resource, those are incompatible.
- If two tasks are incompatible, then the machine can’t do both at the same time.
Example of tasks:
[
{"name": "picture 1", "payoff": 2.1, "resources": ["resource 5", "resource 2"]},
{"name": "picture 2", "payoff": 4.5, "resources": ["resource 5", "resource 4", "resource 1"]},
{"name": "fsck", "payoff": 0.48, "resources": ["resource 4", "resource 2", "resource 3"]},
{"name": "clean", "payoff": 3.64, "resources": ["resource 5", "resource 6"]},
{"name": "picture 3", "payoff": 5.92, "resources": ["resource 6", "resource 3", "resource 4", "resource 1", "resource 2"]},
{"name": "backup", "payoff": 1.85, "resources": ["resource 4", "resource 6"]},
{"name": "clean", "payoff": 0.38, "resources": ["resource 3", "resource 2"]},
{"name": "clean camera", "payoff": 4.97, "resources": ["resource 6", "resource 3", "resource 4"]},
{"name": "clean motor", "payoff": 2.95, "resources": ["resource 4", "resource 6", "resource 2"]},
{"name": "picture 4", "payoff": 3.78, "resources": ["resource 5", "resource 4", "resource 2", "resource 1"]}
]
The best subtask for the example tasks is:
[
{'name': 'clean camera', 'payoff': 4.97, 'resources': ['resource 6', 'resource 4', 'resource 3']},
{'name': 'picture 1', 'payoff': 2.1, 'resources': ['resource 2', 'resource 5']}
]
Goal
Develop a system that resolves which tasks the machine has to perform to maximize the payoff. This is, find the subset of tasks in a way that the payoff is maximum and all the tasks in the resulting set are compatible.
Results
We received many very well structured answers, so we decided to reward a bit more participants. And so, using a rating system checking for correctness, efficiency, readability, complexity, stability and time, we have selected six laureates:
- Piotr K.
- Piotr M.
- Emilia M.
- Artur A.
- Paweł B.
- Marek B.
Congratulations to the winners!