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!