Splitting Chocolates, or, Minimum Partition Difference

February 05, 2020

A take-home ques­tion from some com­pa­ny’s recruit­ment process (not me apply­ing). It’s sim­i­lar to anoth­er blog post that I had in mind to write, so might as well just com­bine both of them into one.

The ques­tion (rewrit­ten by me):

There is a long bar of choco­late con­tain­ing hazel­nuts and caramel. It is orig­i­nal­ly con­tigu­ous, with grooves along the length of the bar (like with Toblerone or Kinder Bueno). Each sec­tion of the choco­late bar con­tains some number of hazel­nuts, and may also con­tain caramel.

Let’s say Alice wants to split the choco­late bar to share with k people, includ­ing her­self. She would have to break the choco­late bar at k-1 points along the bar into k pieces.

Alice is like any other person - she wants to appear gen­er­ous but secret­ly wants as many hazel­nuts in her choco­late as pos­si­ble. She devis­es a plan for break­ing the choco­late so that she gets the piece with the least hazel­nuts out of the k pieces, but yet max­i­mize the number of hazel­nuts in her own piece.

Alice also does­n’t want to break the choco­late bar such that the break­age point is in between 2 sec­tions with caramel, since that will make a mess all over the place. Caramel belongs in the stom­ach, not on the floor.

Given all of these rules, can you find out how many hazel­nuts will be in Alice’s share of the choco­late?

For exam­ple:

2 | 3 | 4 | 5
  | C | C | 

This bar of choco­late has 4 sec­tions, with 2, 3, 4, and 5 hazel­nuts in each sec­tion respec­tive­ly. The middle 2 sec­tions has caramel in it.

Given 2 people (Alice and one other friend), the answer should be 5, since Alice would have make a break in between the third and fourth sec­tion. Alice’s friend will get 9 hazel­nuts while Alice will get 5 hazel­nuts.

Anoth­er exam­ple:

4 | 3 | 6 | 2
  |   |   |

It is also pos­si­ble that the bar does not con­tain any caramel at all, in which case it is okay to break the choco­late bar in between any 2 sec­tions.

Given 3 people (Alice and two other friends), the answer should be 3, since this time Alice would have broken it between the first and second sec­tion, and between the second and third sec­tion. This yields 4 hazel­nuts for the first friend, 8 hazel­nuts for the second friend, and 3 hazel­nuts for Alice.

This ques­tion can be split into two parts. The first part involves coa­lesc­ing the caramel sec­tions togeth­er, since they can be treat­ed as a single sec­tion.

Then, it is simply an appli­ca­tion of Min­i­mum Par­ti­tion Dif­fer­ence, which I’ve writ­ten a top-down recur­sive mem­o­iza­tion ver­sion of here. This is due to the obser­va­tion that what Alice is trying to do is to min­i­mize the imbal­ance between all of the pieces. In other words, she is trying to min­i­mize the dif­fer­ence between the largest piece and the small­est piece (thus the name of the algo­rithm).

I’ve chosen to rep­re­sent the hazel­nuts in each sec­tion as a list of inte­gers. The caramel in the choco­late is rep­re­sent­ed as a list of tuples, each of which indi­cates the start and end sec­tions (inclu­sive) of the parts of choco­late bar con­tain­ing caramel. The last argu­ment we need is the number of people involved (includ­ing Alice).

from typing import List, Tuple

class memoized:
    def __init__(self, func):
        self.cache = {}
        self.func = func
    def __call__(self, *args):
        if args in self.cache:
            return self.cache[args]
        result = self.func(*args)
        self.cache[args] = result
        return result

def minimum_partition_difference(arr, k):
    def _minimum_partition_difference(l, r, k):
        if k == 1:
            return sum(arr[l:r + 1])
        maximum = float('-inf')
        for i in range(l, r):
            maximum = max(
                min(sum(arr[l:i + 1]), _minimum_partition_difference(i + 1, r, k - 1)),
        return maximum
    return _minimum_partition_difference(0, len(arr) - 1, k)

def chocolate(hazelnuts: List[int], caramel: List[Tuple[int, int]], people: int):
    if caramel:
        # sort the caramel hazelnuts
        caramel.sort(key=lambda x: x[0])
        coalesced_hazelnuts = []
        # put the first bunch of non-caramel sections first
        for i, r in enumerate(caramel):
            coalesced_hazelnuts.append(sum(hazelnuts[r[0]:r[1] + 1]))
            # put those non-caramel sections that are in between caramel sections
            if i != len(caramel) - 1:
                next_chunk = caramel[i + 1]
                coalesced_hazelnuts.extend(hazelnuts[r[1] + 1:next_chunk[0]])
        # put the last bunch of non-caramel sections
        coalesced_hazelnuts.extend(hazelnuts[caramel[-1][1] + 1:])
        coalesced_hazelnuts = hazelnuts

    return minimum_partition_difference(coalesced_hazelnuts, people)

print(chocolate([2,3,4,5], [(1,2)], 2)) # 5
print(chocolate([4,3,6,2], [], 3)) # 3
print(chocolate([6,3,2,8,7,5], [(2,4)], 2)) # 9

The time com­plex­i­ty of this solu­tion is dom­i­nat­ed by the second part, which is O(kn2), where k is the number of people, and n is the number of sec­tions in the choco­late.

This is because we are cal­cu­lat­ing (and mem­o­iz­ing) the inter­me­di­ate result for every value of i, where i varies from 1 to k, and every sub­ar­ray/​sub­sec­tion of the choco­late bar ((n2 + 1)/​2 sub­ar­rays in an array).

The time com­plex­i­ty of the first part is mainly from the sort­ing of the caramel sec­tions (assum­ing the input isn’t already sorted).

The orig­i­nal blog post I wanted to write was about one of my broth­er’s home­work assign­ment ques­tions, which goes some­thing like this (again abridged):

Given a list of jobs and their run­times, and k proces­sors, we want to dis­trib­ute the jobs con­tigu­ous­ly between the proces­sors so that we min­i­mize the total run­ning time, which is count­ed as the time it takes to com­plete all the jobs.

Find the short­est pos­si­ble run­time for a given list of jobs and number of proces­sors.

This requires us to invert the ver­sion of the Min­i­mum Par­ti­tion Dif­fer­ence algo­rithm above to return the size of the largest par­ti­tion instead of the size of the small­est par­ti­tion.

def minimum_partition_difference(arr, k):
    def _minimum_partition_difference(l, r, k):
        if k == 1:
            return sum(arr[l:r + 1])
        minimum = float('inf')
        for i in range(l, r):
            minimum = min(
                max(sum(arr[l:i + 1]), _minimum_partition_difference(i + 1, r, k - 1)),
        return minimum

    return _minimum_partition_difference(0, len(arr) - 1, k)

There is an inter­est­ing way to solve MPD using “binary search” as well, which I might write about soon.