5
\$\begingroup\$

I'm given a list of strings and a length limit N. I have to write a function to accumulate consecutive strings in the list until the next string would exceed the N limit. I have to return a list of lists, where each list is the largest consecutive substring not to exceed N characters total. See the test case below for an example. Also, if any single string in the list is longer than N, I have to print a useful message and return.

My attempt to solve the problem has been this one:

def break_lst(lst, size):
    def len_lst(l):
        return len("".join(l))

    err = "Error: use a bigger size than " + str(size)
    result = []
    sublst = []

    for v in lst:
        sublst.append(v)
        ls = len_lst(sublst)

        if ls == size:
            result.append(sublst)
            sublst = []
        elif ls > size:
            prev_sublst = sublst[:-1]
            if not prev_sublst or len_lst(prev_sublst) > size:
                raise Exception(err)
            else:
                result.append(prev_sublst)
                sublst = [v]

    if sublst:
        if len_lst(sublst) > size:
            raise Exception(err)
        else:
            result.append(sublst)

    return result

if __name__ == "__main__":
    lst = ["1", "22", "333", "4444", "55555", "666666", "7777777", "88888888"]

    for i in range(17):
        try:
            print(i, break_lst(lst, size=i))
        except Exception as e:
            print(e)

Output:

Error: use a bigger size than 0
Error: use a bigger size than 1
Error: use a bigger size than 2
Error: use a bigger size than 3
Error: use a bigger size than 4
Error: use a bigger size than 5
Error: use a bigger size than 6
Error: use a bigger size than 7
8 [['1', '22', '333'], ['4444'], ['55555'], ['666666'], ['7777777'], ['88888888']]
9 [['1', '22', '333'], ['4444', '55555'], ['666666'], ['7777777'], ['88888888']]
10 [['1', '22', '333', '4444'], ['55555'], ['666666'], ['7777777'], ['88888888']]
11 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
12 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
13 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
14 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
15 [['1', '22', '333', '4444', '55555'], ['666666', '7777777'], ['88888888']]
16 [['1', '22', '333', '4444', '55555'], ['666666', '7777777'], ['88888888']]

Problems with the function:

  • The proposed algorithm is really ugly and unpythonic
  • The fact it's handling an special case when the loop has finished makes it even uglier

How would you proceed in order to make a cleaner algorithm out of it?

\$\endgroup\$
  • 1
    \$\begingroup\$ I wonder if there is any nice way of using itertools.accumulate() for this problem.. \$\endgroup\$ – alecxe Nov 21 '17 at 4:26
  • 1
    \$\begingroup\$ @alecxe I don't think accumulate would be good here in the slightest. groupby however is worse than not using groupby. \$\endgroup\$ – Peilonrayz Nov 21 '17 at 9:38
4
\$\begingroup\$

You can greatly reduce the size of your code by using a total integer and one result list. You can access the last item in the list by using result[-1]. Additionally, you can reduce the number of times you raise an error by just checking the size of each grouping.

def break_lst(lst, size):
    total = 0
    result = [[]]
    for v in lst:
        total += len(v)
        if total <= size:
            result[-1].append(v)
        else:
            total = len(v)
            if total > size:
                raise Exception("Error: use a bigger size than {}".format(size))
            result.append([v])
    return result
\$\endgroup\$
3
\$\begingroup\$

a variation of nfn neil's answer, but with a generator so it could handle larger files too

def break_lst(lst, size):
    result = []
    total = 0
    for word in lst:
        if len(word) > size:  # easiest case first
            msg = f"Error: use a bigger size than {size}"  #python 3.6 ftw
            raise ValueError(msg)
        total += len(word)
        if total <= size:
            result.append(word)
        else:
            yield result
            result = [word]
            total = 0
    if result:
        yield result

Exception

Instead of raising a generic Exception, it would be better to raise a more specific one, so your try-except clause doesn't catch exceptions other parts may raise. Check the documentation for the most suited type

\$\endgroup\$
2
\$\begingroup\$

Instead of checking for invalid input while doing your computation, you could compute the minimum acceptable length first and then splitting into sublists. This will also help to improve the error message; but it has the drawback of limiting the inputs to iterable that are not iterators as they will be exhausted when computing the size:

def break_lst(array, size):
    min_size = max(map(len, array))
    if size < min_size:
        raise ValueError('size too small (required at least {}, got {})'.format(min_size, size))

    ...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.