When I started looking into the Google Hashcode challenges, the first suggestion I received from Google Team was to try solving the pizza problem… just to make practice.
I learnt that solving this problem really helps to find a solution to the challenges that Google has proposed during these years to pass the qualification process (and maybe the final qualification too).
In addition, it is a good opportunity to check your coding skills and improve them to implement your own algorithm in a limited amount of time.
Finding the solution to this problem might be really challenging.
For people loving solving puzzles and logic problems, it might be really funny.
The first step is obviously to read the description of the problem.
The pizza practice problem
The pizza is a matrix of size R x C. Each element of this matrix can be a tomato (T) or a mushroom (M).
The goal is to divide the pizza into multiple slices so that the total score is maximized.
The score is the sum of the area of all slices.
Unfortunately, the pizza cannot be divided into slices of custom size. In fact, the slices must have an area that belongs to the range [2*L,H], where L is the minimum required number of tomatoes and mushroom in each slice.
All slices having an area lower than 2*L or larger than H are not valid and they cannot be considered part of the final solution.
The input files
The Google Hashcode team has provided four input text files.
The first line of each input file contains the following information:
- R: number of matrix rows
- C: number of matrix columns
- L: the minimum number of each ingredient required for each slice
- H: the maximum area of the slice
The following lines contain the matrix of ‘T’ and ‘M’ characters.
Since there are two ingredients, then a valid slice has an area belonging to the range [ 2*L, H ], where both extremes are included.
The following table summarizes the parameters values for each input file:
| Filename | R | C | L | H |
|---|---|---|---|---|
| Example.in | 3 | 5 | 1 | 6 |
| Small.in | 6 | 7 | 1 | 5 |
| Medium.in | 200 | 250 | 4 | 12 |
| Big.in | 1000 | 1000 | 6 | 14 |
Solutions for two first input files
For the input files example.in and small.in, the choice of the slices that maximize the score is straightforward.
My algorithm takes no more than 200ms for the small pizza challenge (including some basic configuration steps ).
The maximum scores for these two input files are 15 and 42 respectively.
These solutions might be calculated almost instantly every time and almost independently of the configuration parameters used for my algorithm.
If you are interested to learn about my algorithm and how I achieved these results and the solutions for the medium and the big pizza, then subscribe to my blog or follow my free updates on the social networks. I’m planning to publish soon the explanation of my algorithm.
