A friend of mine was asked the following at a job interview for junior python dev.

A building has one elevator. Employees wait in an ordered line to take the lift up. The elevator has a maximum mass capacity. How many trips is the elevator going to do? The masses of the passengers are provided in an (ordered) list.

The following C-style loop will do the job, true, but isn't there a concise (hopefully a one-liner) for such a canonical problem?

#!/usr/bin/env python3

MAX_MASS = 280  # kg

def how_many(masses):
    trips = 0
    total_mass = 0
    for m in masses:
        if total_mass   m > MAX_MASS:
            trips = trips   1
            total_mass = 0

        total_mass = total_mass   m

    return trips


if __name__ == '__main__':
    passangers = [19, 22, 34, 33, 82, 91, 77, 31, 87]  # ordered!
    trips = how_many(passangers)
    print(trips)

A low-level language like C would use std::accumulate() to do it in a couple of lines. I would be truly surprised if python doesn't support some list comprehension or have a math library providing the solution in a single invocation.

CodePudding user response：

I guess you could abuse textwrap.

from textwrap import wrap

def how_many(masses):
    return len(wrap(' '.join('.' * (m-1) for m in masses), MAX_MASS-1))

(Might produce a wrong result when there's an employee with mass 1 kg, but that seems rather unlikely.)

CodePudding user response：

You can use itertoosl.accumulate to shorten this a bit:

from itertools import accumulate as acc

def trips(masses, mm):
    i = res = 0
    while i < len(masses):
        res  = 1
        i = next((i for i, a in enumerate(acc(masses[i:]), i) if a > mm), len(masses))
    return res
    

Algorithmically, the slices are a bother (O(K) in time and space), but you can replace masses[i:] with islice(masses, i, None).

If you allow recursion, you can get this down to:

def trips(masses, mm):
    if not (n := len(masses)):
        return 0
    return 1   trips(masses[next((i for i, a in enumerate(acc(masses)) if a > mm), n):], mm)

trips([19, 22, 34, 33, 82, 91, 77, 31, 87], 280)
# 3

Some docs:

• itertools.accumulate
• enumerate
• next
• itertools.islice

CodePudding user response：

Here's a solution using reduce:

from functools import reduce

def how_many(masses, MAX_MASS):
    def my_func(acc, m):
        trips, tmp = acc
        return (trips   1, m) if tmp   m > MAX_MASS else (trips, tmp   m)

    return reduce(my_func, masses, (1, 0))[0]

The call to reduce returns a tuple, so we take the first element which is the number of trips.

CodePudding user response：

Using split_before from module more_itertools to split when the mass becomes too much; and using ilen from the same module to count the splits.

from more_itertools import split_before, ilen

def count_trips(seq, max_mass):
    def acc(x):
        if acc.mass   x <= max_mass:
            acc.mass  = x
            return False
        else:
            acc.mass = 0
            return True
    acc.mass = 0
    return ilen(split_before(seq, acc))

print(count_trips([19, 22, 34, 33, 82, 91, 77, 31, 87], 280))
# 2   ( [[19, 22, 34, 33, 82], [91, 77, 31, 87]] )