All Projects β†’ sagishporer β†’ hashcode-practice-even-more-pizza

sagishporer / hashcode-practice-even-more-pizza

Licence: Apache-2.0 license
Google Hash Code 2021 practice problem: "Even More Pizza". Score: 731,455,475

Programming Languages

C#
18002 projects

Projects that are alternatives of or similar to hashcode-practice-even-more-pizza

lombok-rs
Lombok port for Rust
Stars: ✭ 31 (+158.33%)
Mutual labels:  hashcode
hashcode
πŸ”‘ A javascript module for generating hashcodes of objects
Stars: ✭ 27 (+125%)
Mutual labels:  hashcode
HashKode
Kotlin hashcode utilities
Stars: ✭ 15 (+25%)
Mutual labels:  hashcode
GoogleHashCode2018
Solutions to Google HashCode 2018
Stars: ✭ 14 (+16.67%)
Mutual labels:  hashcode
hashcode-2018
Solution for Google Hash Code 2018 Qualification Round
Stars: ✭ 14 (+16.67%)
Mutual labels:  hashcode
SpookilySharp
A .NET/Mono implementation of Bob Jenkins’ SpookyHash version 2. Offers 32- 64- and 128-bit hashes of strings, char and byte arrays, streams and any type of object represented by an array of simple types.
Stars: ✭ 20 (+66.67%)
Mutual labels:  hashcode
HashCode
Google Hash Code solutions.
Stars: ✭ 17 (+41.67%)
Mutual labels:  hashcode
GoogleHashCode2017
Assignments for the Google HashCode 2017
Stars: ✭ 16 (+33.33%)
Mutual labels:  hashcode

Google Hash Code 2021 practice problem solution: Even More Pizza

Problem statement

Algorithm description:

  • Phase 1: Build a solution
  • Phase 2: Optimizations

Phase 1 - Build a solution

  1. Sort pizzas by number of ingredients.
  2. Build deliveries, first teams of 4, after that 3, after that 2:
    2.1 Select the pizza with the most ingredients.
    2.2 Select the pizza that will give the best improvement in delivery (most new ingredients, with the least overlapping ingredients).
    2.3 Repeat 2.2 until the delivery is ready.

Phase 2 - Optimization

  1. Try to swap 2 pizzas between any 2 deliveries - if it improves the score, make the swap.
  2. Try to swap 1 pizza between any 2 deliveries - if it improves the score, make the swap.
  3. Try to swap a pizza from any delivery with unused pizza - if it improves the score, make the swap.
  4. Try to move 1 pizza between 2 deliveries (# of pizza in the 2 deliveries must be -+1) - if it improves the score, make the swap.
  5. If any improvement performed in 1-4 - go to 1

Notes

  1. Phase 1 takes about 5 seconds to run.
  2. Phase 2 takes about 50 minutes to run with the current restrictions (implemented for D & E which are huge). About 1% score improvement.

Scores

Input Phase 1 Phase 1 + 2
A – Example 74 74
B – A little bit of everything 12,922 13,533
C – Many ingredients 706,624,572 712,692,751
D – Many pizzas 7,863,102 7,911,296
E – Many teams 10,789,627 10,837,821
Total 725,290,297 731,455,475
Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].