DEV Community

Andrei Visoiu
Andrei Visoiu

Posted on

Divide pizzas with a Greedy approach & Python

Consider that you are having 10 friends over and have ordered 7 pizzas. How can you divide those pizzas fairly? One way is for everyone to get half a pizza and a fifth of a pizza. (for example, by splitting 2 pizzas in fifths and the other 5 in halves).

If we were to represent our problem as fractions:

fraction1

This way of writing a fraction as a sum of distinct unit fractions (fractions that have a numerator equal to 1 and the denominator a positive integer) was used as a serious notation for the rational numbers by ancient Egyptians and is called an Egyptian fraction.

We can use the computer to find the Egyptian notation for any fraction using a fairly simple greedy approach: in short, for any given fraction M/N, find the least integer greater than or equal to N/M, let it be x, and then recur for M/N - 1/x until the result is 0.

Alright, let's code a solution! Firstly, we have to read our M and N. Let's make the user give it as M/N:

M, N = [int(x) for x in input("M/N = ").split('/')]
Enter fullscreen mode Exit fullscreen mode

Now, let's write a function that prints the sum:

def egyptian_fraction(m, n):
    while m > 0: # we recur until m is 0
        x = n // m
        if n % m != 0: # if n is not divisible by m, we have to add 1 in order to respect the 'greater than or equal' part.
            x += 1
        m = m * x - n # when calculating, M/N - 1/x = (M*x - N) / N
        n *= x
        print("1/{0}".format(x), " + " if m != 0 else "", sep = "") # print the numbers like: 1/2 + 1/5
Enter fullscreen mode Exit fullscreen mode

In the end, our program could look like this:

def egyptian_fraction(m, n):
    while m > 0:
        x = n // m
        if n % m != 0:
            x += 1
        m = m * x - n
        n *= x
        print("1/{0}".format(x), " + " if m != 0 else "", sep = "")

M, N = [int(x) for x in input("M/N = ").split('/')]
egyptian_fraction(M, N)
Enter fullscreen mode Exit fullscreen mode

So, in the end, we have a program capable of dividing pizzas equally among our guests! As a matter of fact, this approach can be used to divide any object in equal shares.
Do you have any thoughts about this approach or code? Let me know in the comments!

Discussion (0)