GetInIT Coding Challenge

The Task

The task of the coding challenge was to drive two trucks to a location in Bonn and only have a limited capacity to deal with different devices as effectively as possible. The devices differ in “utility” value, weight and the required number in Bonn. The “utility” value indicates how urgently a certain device is needed. The devices and their values can be viewed here: https://www.get-in-it.de/imgs/it/codingCompetition/bwi/code_for_bwi.pdf 
The weight of the driver, must be deducted from the total capacity of the truck. 

Underlying Problem

This task is based on the so-called “bagpack” problem, which is one of the most complicated in computer science. In order to really get the most effective loading, an algorithm with a very long runtime is required, which also depend on the number of elements that have to be sorted. In this algorithm all possible combinations are checked and then the most effective is returned. I can recommend this solution for tasks with a small number of elements. 

My Algorithm

In order to load the trucks as effectively as possible, I used a heuristic approach and implemented a simple variant of the greedy algorithm. The greedy algorithm is characterized by its short runtime and comparatively good results. 

First, the devices are sorted in descending order according to their effectiveness (in database.py): 

data = self.fetchall('SELECT * FROM devices ORDER BY weight/benefit')

The effectiveness of a device is determined by the ratio between weight and utility. The formula for this is:effectiveness = weight / utility value

After sorting, the devices are packed into the truck, starting with the most effective. Depending on how much space is still available in the truck, not all units of a device are packed, or the algorithm jumps to the next element. 
This results in the following loading lists:

TRANSPORTER NR.1	TRANSPORTER NR.2
DeviceUnitsMobiltelefon Outdoor157Mobiltelefon Heavy Duty220Mobiltelefon Büro60Tablet outdoor groß283total utility value: 44764 free capacity: 724 g	DeviceUnitsTablet outdoor groß87Tablet Büro klein599total utility value: 29876 free capacity: 445 g

The Program

Installation

After you have downloaded the project you have to install all required packages with: 

pip install -r requirements.txt

The program is written in Python, so make sure you have Python3 installed. 
Enter the following command to start the program:

python main.py

Description

My application basically consists of two areas. One is the area for editing the database entries for devices, transporter and drivers, as well as creating the loading lists. And secondly, the delivery game area in which the user has the task of collecting the packages with his truck. The second area (game area) was not part of the requirements.

GUI first area:

After pressing on “Geräte bearbeiten” (edit devices) you see this: 

When you click on “Ladeliste erstellen”. The button “Ausliefern” (deliver) becomes visible. This leads you to …

The Delivery Game

The delivery game wasn’t part of the task. 
The aim of the game is to collect all the packages from the loading list and not cause an car accident. The counters above show how many units of the various devices have already been collected. Once all the packages have been collected, you can switch to the next transporter.

Controls

Key	Function
Left / A	steer truck one lane to the left
Right / D	steer truck one lane to the right
Up /W	increase the speed of the truck
Down / S	decreace the speed of the truck

In the info box

Key	Function
Left/A	Move one button to the left
Right/D	Move one button to the right
Space/Enter	Press the selected button

class Device:
    def __init__(self, device_id, name, units, weight, benefit):
        self.id = device_id
        self.name = name
        self.units = units
        self.weight = weight
        self.benefit = benefit

    # returns the database ID
    def get_id(self):
        return self.id

    # returns the name
    def get_name(self):
        return self.name

    def set_name(self, n):
        self.name = n

    # returns the available units
    # this is not the database value
    # if a device gets packet on the transporter,
    # the available units will decrease
    def get_units(self):
        self.units = int(self.units)
        return self.units

    def set_units(self, u):
        self.units = u

    # returns the weight in g
    def get_weight(self):
        return self.weight

    def set_weight(self, w):
        self.weight = w

    # returns the benefit ("Nutzwert")
    def get_benefit(self):
        return self.benefit

    def set_benefit(self, b):
        self.benefit = b

    # sets the available units,
    # after the devices were packed
    # on the transporter
    def pack(self, units):
        self.units = self.units-units

    # returns the type of the device
    def get_type(self):
        name = self.get_name()
        if 'Mobiltelefon' in name:
            return 'smartphone'
        if 'Tablet' in name:
            return 'tablet'
        return 'notebook'

    # returns an emoji that matches the device type
    def get_emoji(self):
        if self.get_type() == 'smartphone':
            return '📱'
        return '💻'