Half a dozen of greedy problems

A small collection of greedy problems, as found in week three of edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

Kind of disappointing this third week of the course, since they removed the access to their online problem verifier for the unregistered user. Besides, these kind of problems loose large part of their appeal if you already know they could be solved following a greedy approach. The spoiler is too big, you just have to verify the greedy step is safe. Still, let's have a look of them. As usual, I provide my full python code on GitHub.

Changing Money

Task: Find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Solution: Start from considering the higher denomination, it is safe to remove that value from the input until we can, since obviously that leads to the minimum possible result.

This is the core loop of the algorithm:

for coin in DENOMINATIONS:
    counter = leftover // coin  # 1
    if counter > 0:
        result += counter
        leftover %= coin   # 2

    if leftover == 0:
        break

1. It would be boring subtracting one coin after the other till we can, better to integer-divide the amount for the current denomination.
2. The modulo of the above division gives the amount that still have to be reduced to coins.

Maximizing the Value of a Loot

Task: Implement an algorithm for the fractional knapsack problem

Solution: Sort the input values, a list of tuples of value and weight, accordingly to their value per unit. Then get the required quantity from it.

There is a simple way to sort it in that way when python is you implementing language:

loot = sorted(items, key= lambda item: item[0]/item[1])

Notice that I'm keeping the natural ordering, form smallest to greater, so I would check the values from right to left.

Maximizing Revenue in Online Ad Placement

Task: Given two same sized integer sequences, partition them into pairs such that the sum of their products is maximized, and return such value.

Solution: There is no trick with negative values, you could just sort both sequences and multiply the items with the same index between them. Conceptually, we should start from the highest values down to the lowest one. Actually, it is all the same.

To extract the same-index components from two (or more) iterables in python we could use the handy zip() function:

for p, c in zip(profits, clicks):
    result += p * c

Collecting Signatures

Task: Given a list of 2-tuples representing segments, find the minimum number of points such that each segment contains at least one point.

Solution:

segments.sort(key=lambda item: item[1])  # 1

results = [segments[0][1]]  # 2
for segment in segments:
    if segment[0] > results[-1]:
        results.append(segment[1])  # 3

1. Sort the segments in natural order for the ending point of each segment. Notice the python way of specifying which component has to be used to sort the list.
2. Initialize the result list with the first point, ending of the first (sorted) segment.
3. When we find an ending point of a segment that is more to the right of the last one, we add it to the result list. We can easily prove that this is a safe move, so our greedy algorithm is OK.

Maximizing the Number of Prize Places in a Competition

Task: Given a positive integer, find the sum of integers largest in size equals to the given input and containing only unique values.

Solution: The simpler case is when we can use the natural sequence until the input value is reached. This approach works for 6

6 = 1 + 2 + 3

but it doesn't work, for instance, for 2 or 8

2 = 2
8 = 1 + 2 + 5

The key point is that, before adding an element to the result list, we should ensure we keep enough space for another element that should be bigger that the current one.
So, for instance. We get 2 in input, we would like to put 1 in the result list, but if we do that we are left with another 1 that we can't add, since no duplicated are allowed, so we skip it and add 2 instead, completing our job.
In case of 8, 1 and 2 could be safely added to the result list. When we consider 3, our leftovers are 5, if we put 3 in the list, we are left with a 2, that is useless, so we discard 3 and put in the result list 5 instead.

So we modify our pushing in the result list of all the elements in the natural sequence with this check:

if unassigned - i <= i:
    results.append(unassigned)
    break

When we enter the "if", we have reached the last element in the result list.

Maximizing Your Salary

Task: Compose the largest number out of a set of integers.

Solution: The trick is that the integers in input could be 1, 2, or 3 digits wide. If they were all one-digit numbers, the job would have been easy, just sort them in reversed natural order, and join them up.

Here we have to sort them in a way that '2' is to the left of '21', so that the input ['21', '2'] would lead to a result of 221.

My idea was to compare the numbers in the input list as all of them had 3 digits, extending the shorter ones duplicating the rightmost digit as required. So, I would think of the previous example as ['211', '222'], and that would lead to the expected result.

To that in python, I have created a filler function and used it in sorting in this way:

def filler(token):
    while len(token) < 3:
        token += token[-1]
    return token

# ...

tokens.sort(key=filler, reverse=True)

Again, please have a look on GitHub for details.