# Google HashCode 2017 Practice Problem

I made an attempt at solving the HashCode 2017 practice problem. This repository contains my workings for the problem including the exact same README. It is coded in Java and uses a Genetic Algorithm to figure out which is the fittest Pizza!

## Starting Out

The clock has struck HashCode o'clock and now you are faced with a real life problem that you must solve using your coding skills and problem solving abilities.

You've stepped up to the plate faced with the challenge of splitting a Pizza between your many friends. Simple right? Not unless you need to ensure that every friend gets a quadrliateral piece of the hot goodness no larger than `H` and with not less that `L` toppings.

As featured in the book The Hitchiker's Guide to the Galaxy by Douglas Adams, the phrase Don't Panic should help soothe your nerves. This is a big challenge and you're more than capable of solving it, you turned up and now it's your time to shine.

## Break It Down

Looking at any problem, try to break the problem down in to Classes (People, Drones, Pizza, Slices, Cats) and what functions or what variables they must store. In our case we are just looking to look at `Pizza` and their many `Slice` at different points we can dish out.

``````
public class Pizza {
public List<Slice> slices; /* Store all the slices for this Pizza cutting scenario */
}

public class Slice {
public int fromX, fromY; /* Slice is from here */
public int toX, toY; /* to here */
}
``````

Now you've represented the problem using Java objects. We can now create instances of the `Pizza` with different scenarios (selections) to `Slice` it up.

## Get Them Pizza Datas

You can pull out what our `Pizza` could look like by reading the file line by line. The first line tells us that we have `rows columns min_topping max_slice` which we store as variables for later use. The following lines will tell us where on a (Y, X) our tomatos and mushrooms live.

See `HashCodeSolver.loadFile()` for more details and `HashCodeSolver.storeFile()` for simple saving of our 'output' (arrangement).

## Determining Fitness

Genetic Algorithms are simple and nature inspired. You take a sequence that is deemed the fittest (most appropriate) and breed it with a similarly suited mate. This should mean your baby `Pizza` is more likely to be fitter and stronger than you are? Yes and no. We know that the `Pizza` must have a set number of ingredients in a `Slice`, must not be bigger than a certain slice, and that each `Slice` must not conflict with another. This is important because Barbara is definitely going to be mad if you stole her allocated mushroom! You can if you like, not divide the entire Pizza in its entirety but it is best to share most of it with you and your mates.

These restrictions will be part of your fitness calculation. `fitness = no overlap, minimum toppings provided, not too much for a single person and most of your pizza is shared`

See `Pizza.fitness()` for more details.

## How Big a Slice Exactly?

You can generate a list of factors based on a minimum and maximum number of cells per quadrliateral slice in your set row and columns sized pizza. The maximum is given for us as a value in the input file and the minimum will be `number of different ingredients * minimum number of ingredients`. Loop from the 1 to the size of the Pizza for both rows and columns, call these variables Y and X respectively. Multiply your X and Y and ensure that it is within the minimum and maximum cell bounds. If it is then add it to a list of valid factors (or pizza slice sizes).

See `Utility.factors()` for more details.

## Let's Cut!

Hold on there... are you sure that you're going to cut the `Pizza` and have the minimum number of ingredients per `Slice`? We can now loop through each possible position from X to Y and ensure that if we cut here we'd meet the minimum and we won't be cutting into pizza space that does not exist.

See `HashCode.slices()` for more details

## Right, It's Cold Now...

Tough, you've paid the Delivery Guy or Girl for the Pizza, you're just going to have to cut and reheat (or eat it cold). So create a plan for cutting your `Pizza` using a variety of `Slice` arrangements.

Once you have an initial two `Pizza` breed them to make `Pizza` children. To do this we can find a middle point on both `Pizza` (note we can have one with 5 `Slice` and another with 7 `Slice`). This will be our Cross Point to swap the `Slice` in one with the `Slice` in another after this point.

See `HashCodeSolver.breed()`.

Ensure that your children aren't 50% pappa `Pizza` and 50% mamma `Pizza` by mutating their genes. We can do this by swapping out random slices with any of the other valid `Slice` for us to maybe (just) be a fitter `Pizza`. We can also remove one or add another extra `Slice` in, if we have not explored all of the pizza space.

See `HashCodeSolver.mutate()`

So now we have the baby `Pizza` out of this generation which are like their parents but not 100% (definitely a little more rebellious). We have evolved our `Pizza` to be better or worse than our mamma or pappa `Pizza`.

## The Hunger Games

Now this is where the sad part comes. Only the fittest two can survive the `Pizza` HashCode Hunger Games.

To ensure we're betting on the top two, lets compare our baby `Pizza` using the `fitness()` to establish who our chips should be on. This isn't the same as counting cards, I swear.

Whichever `Pizza` is the fittest wins, The Hunger Games is over and Peeta & Katniss `Pizza` remain.

This generaton passes and our baby `Pizza` have all grown up. We can therefore repeat the `breed()` and `mutate()` until we reach our best possible arrangement.

## Hurray, Pizza!

This isn't 100% ideal at calculating the best arrangement (Java = slow, sorry) and is merely showing you how you can represent it. People have tried to solve it by looping left to right, top to bottom, vice versa to place large through to small until all possible positions are filled. This would be the most ideal way of going about it but that's just boring.

If you're interested in finding out more, checkout the repository or tweet me