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 )

mozanunal / hashcode2021-even-more-pizza Goto Github PK