Dinner Delivery Cleanup Problem

Dinner Delivery Cleanup Problem – Problem Setup

A company offers dinner for its employees who are working late. The dinner is ordered via delivery.

One day, the admin noticed that the plastic bag for packing and extra condiments were not thrown away after people have taken their food.

Who should be doing the cleanup? The admin suggested the following approach when taking food:

The person taking the last packet of food should clean up the plastic bag and extra condiments.

This seems to be a reasonable approach at first glance. However, if we treat this as an algorithm problem, we can find out the issue with this approach.

Analyzing the Admin Solution

Translating the above approach naively into pseudo code, we have:

procedure take-food(people-taking-food, food-packets):
  person = first(people-taking-food)
  for food-packet in food-packets:
    take-food(person, food-packet)
    if is-last(food-packet, food-packets):
      cleanup(person);
    endif
    person = next(people-taking-food)
  end
end

procedure take-food(people-taking-food, food-packets):

person = first(people-taking-food)

for food-packet in food-packets:

take-food(person, food-packet)

if is-last(food-packet, food-packets):

cleanup(person);

endif

person = next(people-taking-food)

end

On surface, everything looks fine, we will always have someone to cleanup because the for loop would reach the last element of the array.

However, there might be a case where it would fail when executing person = next(people-taking-food) if there are less people than food packets.

In fact, the pseudo code does not model our setup very well. We should not be iterating through the food, but rather, we should be iterating through the people who are taking the food.

Hence, a better pseudo code would be:

procedure take-food(people-taking-food, food-packets):
  food-packet = first(food-packets)
  for person in people-taking-food:
    if food-packet exists:
      take-food(person, food-packet)
      if is-last(food-packet, food-packets):
        cleanup(person)
      endif
    endif
    food-packet = next(food-packets)
  end
end

procedure take-food(people-taking-food, food-packets):

food-packet = first(food-packets)

for person in people-taking-food:

if food-packet exists:

take-food(person, food-packet)

if is-last(food-packet, food-packets):

cleanup(person)

endif

food-packet = next(food-packets)

end

Now the issue with the approach is quite obvious. If people taking the food is less than the number of food packets ordered, we will never hit the condition for clean up.

Mapping the edge case back to real life, it means that someone orders food but forgets to collect, there will be leftover food after everyone has collected. Hence the trash would not be cleared.

Luckily for us, this rarely happens in because usually people who are hungry but didn’t order the food will go and collect leftover food.

A Deterministic Solution

Is there a better algorithm to solve this problem? Yes. One of the ways I can think of is to assign the person beforehand in a deterministic manner when signing up for food order:

last-person = null
procedure sign-up(person-signing-up):
  sign-up(person-signing-up)
  last-person = person-signing-up
end

procedure take-food(people-taking-food, food-packets):
  ...
  cleanup(last-person)
end

last-person = null

procedure sign-up(person-signing-up):

sign-up(person-signing-up)

last-person = person-signing-up

end

procedure take-food(people-taking-food, food-packets):

...

cleanup(last-person)

end

Of course, there might be cases where the last person who sign up never showed up during food collection. However, it would be a people management issue instead of an algorithm issue. For an algorithm’s perspective, it has achieved its goal for always having a person assigned to do the cleanup (when at least one person orders, of course).

Cover photo from: https://www.broadsheet.com.au/melbourne/food-and-drink/article/lunch-comes-you-delivery

More interesting pieces like this: Opinion Pieces

Dinner Delivery Cleanup Problem