Skip to content

sbrodehl/Hashcode2k18

Repository files navigation

Google # Hash Code 2018

Solutions and code for the Google # Hash Code 2018 Challenge of our Team Gyrating Flibbittygibbitts.

HashCode 2018 Banner

Hash Code is a team programming competition organized by Google for students and industry professionals across Europe, the Middle East and Africa. You pick your team and programming language, we pick a Google engineering problem for you to solve.

from # Hash Code 2018

Final Round

The problem statement will be added once available. Our solution is in the Final Round folder.

Online Qualification Round

Self-driving rides

The problem statement can be found here. Our solution is in the Online Qualification Round folder.

Introduction

Millions of people commute by car every day; for example, to school or to their workplace.

Self-driving vehicles are an exciting development for transportation. They aim to make traveling by car safer and more available while also saving commuters time.

In this competition problem, we’ll be looking at how a fleet of self-driving vehicles can efficiently get commuters to their destinations in a simulated city.

from Problem statement for the Online Qualification Round of Hash Code 2018

Task

Given a list of pre-booked rides in a city and a fleet of self-driving vehicles, assign the rides to vehicles, so that riders get to their destinations on time.

For every ride that finishes on time (or early), you will earn points proportional to the distance of that ride; plus an additional bonus if the ride also started precisely on time.

from Problem statement for the Online Qualification Round of Hash Code 2018

Here is a visualization of our solution of the map High Bonus. Example Output Visualization

Practice Round

The problem statement can be found here. Our solution is in the Practice Round folder.

Did you know that at any given time, someone is cutting pizza somewhere around the world? The decision about how to cut the pizza sometimes is easy, but sometimes it’s ​really hard: you want just the right amount of tomatoes and mushrooms on each slice. If only there was a way to solve this problem using technology...

from Practice Problem for Hash Code, Hash Code 2018

Getting Started

Prerequisites

The current version requires in particular the following libraries / versions. See requirements.txt for the full list of requirements.

The easiest way to install those dependencies is by using the requirements.txt file with pip3.

pip3 install -r requirements.txt

Code & Solver Structure

The solutions are called from the main.py program of the corresponding round, e.g. Online Qualification Round/main.py, with the --solver SOLVER argument describing a solver in the solver directory and input being an input file from the input directory.

See the help below for more details.

$ python3 main.py -h
usage: main.py [-h] [--output OUTPUT] [--solver SOLVER] input

positional arguments:
  input            input file

optional arguments:
  -h, --help       show this help message and exit
  --output OUTPUT  output file
  --solver SOLVER

The main.py instantiates the solver with the input string, e.g. Solver(args.input). Then the solve() method is invoked and in case an --output path is set, the write(args.output) method is called with the given output string.

Therefor each solution/approach to a problem - let's call that a solver - needs to inherit from the class BaseSolver in the solver directory of the corresponding round (Final, Qualification, Practice).

The baseclass ensures, that the solver has a __init__ method, which has input_str as an argument, which is the the filepath of the given input. This methods needs to take care of e.g. input parsing.

The solve() method solves the problem and holds the solution in memory.

The write() method writes a correct output file which can be submitted online.

Together with the output file one can submit the corresponding solver file.
Happy coding!

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting pull requests to us.

Authors

Sebastian Brodehl / @sbrodehl
Tobias Kremer / @tbkr
Dennis Meyer / @snakebite1457
Moritz Schmidtgen / @mschmi10

License

This project is licensed under the Apache License 2.0 - see the LICENSE file for details