Skip to content

HashCode 2021 practice question solution with 727,667,236 points. It is a clean and readable 4 hours solution written in Python.

Notifications You must be signed in to change notification settings

mozanunal/hashcode2021-even-more-pizza

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Hashcode 2021 Even More Pizza

It is our implementation for Hashcode 2021 practice question. It is a clean and readable 4 hours solution writen in Python.

Data Scores
A – Example 65 points
B – A little bit of everything 12,029 points
C – Many ingredients 708,861,140 points
D – Many pizzas 7,946,557 points
E – Many teams 10,847,445 points
Total 727,667,236 points

Solution

This is a brief explanation of the solution process. Please see the code for the details. We have created 2 classes:

Pizza Class

Stores ingredients as set and index to create submission file.

class Pizza(object):
    def __init__(self, index, ings):
        self.index = index
        self.ings = set(ings)
        self.count = len(self.ings)
        self.selected = False
        self.score = {}

Team Class

Team class stores the pizzas which are sent to the team. Add function of team class handles:

  • adds unique ingridient with union function
  • adds pizza to pizzas
  • marks pizza as selected
  • checks the capacity and already selected pizza error states
class Team():
    def __init__(self, cap):
        self.cap = cap
        self.pizzas = []
        self.ings = set()

    def calcSc(self, pizza):
        comm = self.ings.intersection(pizza.ings)
        uniq = self.ings.union(pizza.ings)
        total = pizza.count
        for p in self.pizzas:
            total += p.count
        sc = len(uniq) / (total)
        return sc

    def add(self, pizza):
        assert 1 + len(self.pizzas) <= self.cap
        self.pizzas.append(pizza)
        assert pizza.selected == False
        pizza.selected = True
        self.ings = self.ings.union(pizza.ings)
    
    def __repr__(self):
        return '[{}-{}-{}]'.format(self.cap, [p.index for p in self.pizzas], self.ings)

    @property
    def is_full(self):
        return len(self.pizzas) == self.cap

Solver

Solver takes a list of teams and a list of pizzas as argument. The pizzas should already be sorted with count of ingredients. PART_SIZE is used to shorten the calculation process. When checking the potential pizza candidates how many sample will be check is determined with this size in enumerate(pizzas[0:PART_SIZE]).

PART_SIZE=256

def solve(teams, pizzas):
    for team in tqdm(teams):
        if len(pizzas) < 1:
            print('done--------------')
            break
        for i in range(team.cap):
            maxScore = 0
            maxScoreIdx = 0
            for i, pizza in enumerate(pizzas[0:PART_SIZE]):
                score = team.calcSc(pizza)
                if score > maxScore:
                    maxScore = score
                    maxScoreIdx = i
            team.add(pizzas[maxScoreIdx])
            pizzas.pop(maxScoreIdx)
            

Solving Process

Solving start with 4 member teams. Since the score is calculated the square of the unique ingredients, filling 4 member teams first gives better result.

nPizza, n2, n3, n4, pizzaL, teamL2, teamL3, teamL4 = readF(filename)
pizzaLSorted = sorted(pizzaL, key=operator.attrgetter('count'), reverse=True)
#### initial add start ########
solve(teamL4, pizzaLSorted)
solve(teamL3, pizzaLSorted)
solve(teamL2, pizzaLSorted)

outF( filename.replace('data/','')+'.out', teamL2, teamL3, teamL4 )

My Other HashCode Repos

Team

About

HashCode 2021 practice question solution with 727,667,236 points. It is a clean and readable 4 hours solution written in Python.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published