Skip to content

Google # Hash Code 2020 Challenge in Python

License

Notifications You must be signed in to change notification settings

sbrodehl/Hashcode2k20

Repository files navigation

Google # Hash Code 2020

Solutions with code for Google # Hash Code 2020.

Hash Code 2020 Banner

Hash Code is a team programming competition, organized by Google, for students and professionals around the world. You pick your team and programming language and we pick an engineering problem for you to solve.

from # Hash Code

Online Qualification Round

Book Scanning

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

See the README.md for a full walkthrough of the problem.

Introduction

Books allow us to discover fantasy worlds and be er understand the world we live in. They enable us to learn about everything from photography to compilers ... and of course a good book is a great way to relax! Google Books is a project that embraces the value books bring to our daily lives. It aspires to bring the world's books online and make them accessible to everyone. In the last 15 years, Google Books has collected digital copies of 40 million books in more than 400 languages, partly by scanning books from libraries and publishers all around the world. In this competition problem, we will explore the challenges of setting up a scanning process for millions of books stored in libraries around the world and having them scanned at a scanning facility.

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

Task

Given a description of libraries and books available, plan which books to scan from which library to maximize the total score of all scanned books, taking into account that each library needs to be signed up before it can ship books.

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

Practice Round

More Pizza

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

See the README.md for a full walkthrough of the problem.

Introduction

You are organizing a Hash Code hub and want to order pizza for your hub’s participants. Luckily, there is a nearby pizzeria with really good pizza. The pizzeria has different types of pizza, and to keep the food offering for your hub interesting, you can only order at most one pizza of each type. Fortunately, there are many types of pizza to choose from! Each type of pizza has a specified size: the size is the number of slices in a pizza of this type. You estimated the maximum number of pizza slices that you want to order for your hub based on the number of registered participants. In order to reduce food waste, your goal is to order as many pizza slices as possible, but not more than the maximum number.

from Problem statement for the Practice Round of Hash Code 2020

Task

Your goal is to order as many pizza slices as possible, but not more than the maximum number.

from Problem statement for the Practice Round of Hash Code 2020

Getting Started

The current version requires libraries.
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

We use python to import various different methods to actually solve a given problem. In that way we can quickly iterate through different approaches and find the best way of solving the problem.

The solvers are imported from the main.py program of the corresponding round, e.g. Practice 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 imports the solver with the input parameter string, e.g. Solver(args.input). Then the solve() method is invoked, and in if an --output path is set, the write(args.output) method is called with the given output parameter string.

Therefor each solver/approach to a problem needs to inherit from the class BaseSolver in the solver directory of the corresponding round (Final, Qualification, Practice).

This base class 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.

Each solver then needs to implements at least the two following methods:

  • 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 then submit the corresponding solver file (no need to zip various random files ... Sorry Google!).

Happy coding!

Authors

Jonas Blochwitz / @lazyguyy
Sebastian Brodehl / @sbrodehl
Jan Disselhoff / @JaeD42
Daniel Franzen

License

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