One-liner in Python


  • 11

    Solution

    def minimumTotal(self, t):
        return reduce(lambda a,b:[f+min(d,e)for d,e,f in zip(a,a[1:],b)],t[::-1])[0]
    

    Explanation

    Starting with the bottom row, I move upwards, always combining the current row and the next upper row. At the end, I have combined everything into the top row and simply return its only element. Here's a longer version with meaningful variable names:

    def minimumTotal(self, triangle):
        def combine_rows(lower_row, upper_row):
            return [upper + min(lower_left, lower_right)
                    for upper, lower_left, lower_right in
                    zip(upper_row, lower_row, lower_row[1:])]
        return reduce(combine_rows, triangle[::-1])[0]

  • 1
    K

    It's awesomly cool! Python's simplicity is why I love it.


  • 1
    S

    This literally makes no sense.

    Do you mind expand it and provide an explanation of what is going on?


  • 1

    I have added some explanation and more understandable code. Is it clear now?


  • 0

    @sidazhang I can give ur an example so that it helps ur understand this code better.

    we start with the list [ [-1], [2,3], [1, -1, -3] ]

    the last line reduce(combine_rows, triangle[::-1])[0]
    tells you to reverse the list to [ [1, -1, -3], [2,3], [-1] ]
    so that [1, -1, -3] and [2,3] will be lower_row and upper_low for the reduce function correspondingly.
    Then, combine_rows function will create a list of tuple ( [2,3], [ 1,-1,-3], [-1,-3] ) in zip(upper_row, lower_row, lower_row[1:])
    and the next step we use list comprehension to reduce list to [ [2-1,3-3 ] [-1]].
    at the end reduce will advance and return result from it last iteration , [ [1,0 ], [-1] ].


  • 1
    O

    Slightly longer 1-liner. Well, pretty close if you don't rename triangle with t and stuff :-)

    I think this one is easier to understand because it keeps the DP structure better.

    class Solution(object):
        def minimumTotal(self, triangle):
            return reduce(lambda a, b:[min(a[i], a[i+1])+n for i, n in enumerate(b)], triangle[::-1])[0]
    

    Which is equivalent to:

    class Solution(object):
        def minimumTotal(self, triangle):
            dp = triangle[-1][:]
            for i in range(len(triangle)-2, -1, -1):
                for j in range(i+1):
                    dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
            return dp[0]
    

  • 0

    @o_sharp What do you mean with "it keeps the DP structure better"?


  • 0
    O

    @StefanPochmann Sorry for the confusion! I mean the induction thing, like dp[j] = min(dp[j], dp[j+1]) + triangle[i][j] stuff is still intact. No big deal.


  • 0

    @o_sharp Ah, ok. I guess if you're coming from there, then your oneliner might be easier. I just probably didn't come from there but wrote mine directly like that. I don't see the need/point to think in meaningless indexes, and I'm very used to zipping like that.


  • 0
    O

    @StefanPochmann In this case, I believe I had a good reason of coming from that angle, because it takes O(1) space like this:

    class Solution(object):
        def minimumTotal(self, triangle):
            dp = triangle[-1]
            for i in range(len(triangle)-2, -1, -1):
                for j in range(i+1):
                    dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
            return dp[0]
    

    Or do dp = triangle[-1][:] if I wanna avoid changing the input data. Too bad 1-liners lose that advantage. They take O(n^2) space.


  • 0

    @o_sharp Yeah, I don't mean your angle is bad, I just mean I had a different one and find it just as easy :-)

    I understand your view that our one-liners take O(n^2) space, but I don't share it. Because they only ever hold two extra rows, the current accumulated row and the next accumulated row. And I see it as similar to for example a usual recursive traversal of a balanced binary tree, which I think you'd say takes O(log n) space, not just O(n) space.


  • 0
    O

    @StefanPochmann I think I have an important question: does this code take O(n) space or O(mn) space?

    l = [x for x in range(n)]
    for i in range(m):
        l2 = [x*2 for x in l]
        l = l2
    

    I used to think it was worst-case O(mn) space because objects never get destroyed until gc kicks in, but after looking at your reply, I can't say I'm sure. Do you have a definitive answer?


  • 0

    @o_sharp That's definitely not O(n) space. Because you build n-1 ints with at least m bits each. I don't think Python optimizes them, so it's Ω(mn) space. But that's not what you meant, right? Only shows that one shouldn't over-complicate their examples? :-P

    But about what you probably meant: Note that id gives me an object's memory address:

    >>> help(id)
    Help on built-in function id in module __builtin__:
    
    id(...)
        id(object) -> integer
        
        Return the identity of an object.  This is guaranteed to be unique among
        simultaneously existing objects.  (Hint: it's the object's memory address.)
    

    And now let's track the ids, i.e., the memory addresses, of l in your example:

    >>> from collections import Counter
    >>> ids = Counter()
    >>> n, m = 10, 1000
    >>> l = [x for x in range(n)]
    >>> for i in range(m):
            l2 = [x*2 for x in l]
            l = l2
            ids[id(l)] += 1
    
    >>> ids
    Counter({40450688: 500, 51567832: 500})
    

    You can see that in the 1000 iterations, l was only ever at one out of two addresses. Switching between them because you're switching it to l2. So if I'm not mistaken, I actually did use only O(n) space (for the lists) because Python did reuse the same space over and over again.

    Overall I think both viewpoints are valid, but I don't know what others think. Quickly googling didn't find me anything. Might be a good question for the appropriate stack exchange site or so. Maybe I'll do that.

    Btw, why do you use the list comprehension in [x for x in range(n)]?


  • 0

    @o_sharp Oh, or maybe you did mean the ints as well (ignoring their sizes, but considering their number)? Here's another experiment:

    from collections import Counter
    with open('test_space_management.txt', 'w') as f:
        i = 1000
        while i < 1000000:
            f.write('%d ' % id(i))
            i += 1
    with open('test_space_management.txt') as f:
        ctr = Counter(f.read().split())
    print ctr.most_common()
    

    That gave me:

    [('50272932', 428390), ('41689012', 367095), ('41689108', 203514), ('50272800', 1)]
    

    So Python quickly reused space for those ints as well.

    (I went with writing the ids into a file because storing them in a dict didn't allow this great reuse, I guess because the dict entries kept occupying the memory spots previously used by obsolete int objects, preventing the new int objects to take them.)


  • 0
    O

    @StefanPochmann Thanks for introducing id! It's such a great tool, but it just blew my mind.

    Under Python 3.4,

    n = 1000
    a = 0
    d = {}
    for i in range(n):
        a += 1
        d[id(a)] = True
    print(len(d))
    

    gave me:

    1000
    

    This simple a+=1 loop takes O(n) space? I thought operator.iadd was in place. It is in place for adding lists, but not for integers?

    Actually, it takes exactly min(n,32770) different addresses. Maybe 32770 is the point when gc kicks in.


  • 0

    @o_sharp What do you get when you run my version, where I write the ids into a file?


  • 0
    O

    @StefanPochmann

    I have the same result with yours if I do a while-loop.

    But if I do a for-loop:

    from collections import Counter
    with open('test_space_management.txt', 'w') as f:
        n = 1000000
        a = 0
        for i in range(n):
            f.write('%d ' % id(a))
            a += 1
    with open('test_space_management.txt') as f:
        ctr = Counter(f.read().split())
    print(ctr)
    

    it gave me:

    Counter({'35801712': 483616, '24647416': 483615, '36296688': 10838, '36296736': 10837, '36296848': 10837, '1463013904': 1, '1463015392': 1, '1463014448': 1, '1463017904': 1, '1463016944': 1, '1463015936': 1, '1463015424': 1, '1463017200': 1, '1463016288': 1, '1463014080': 1, '1463015584': 1, '1463014544': 1, '1463014208': 1, '1463014368': 1, '1463017056': 1, '1463016800': 1, '1463016144': 1, '1463016080': 1, '1463016352': 1, '1463014576': 1, '1463016656': 1, '1463016416': 1, '1463014816': 1, '1463015120': 1, '1463015072': 1, '1463016896': 1, '1463017824': 1, '1463015648': 1, '1463014304': 1, '1463017136': 1, '1463015776': 1, '1463017120': 1, '1463014272': 1, '1463014048': 1, '1463016704': 1, '1463014880': 1, '1463017792': 1, '1463017568': 1, '1463016512': 1, '1463015200': 1, '1463014752': 1, '1463015488': 1, '1463015520': 1, '1463017376': 1, '1463014976': 1, '1463015744': 1, '1463015296': 1, '1463015472': 1, '1463017872': 1, '1463015952': 1, '1463017664': 1, '1463017696': 1, '1463016272': 1, '1463015872': 1, '1463015856': 1, '1463017536': 1, '1463017744': 1, '1463013936': 1, '1463016112': 1, '1463014768': 1, '1463014496': 1, '1463014848': 1, '1463015600': 1, '1463016368': 1, '1463014096': 1, '1463015632': 1, '1463013984': 1, '1463017488': 1, '1463016032': 1, '1463014432': 1, '1463015088': 1, '1463017472': 1, '1463016576': 1, '1463017840': 1, '1463013840': 1, '1463015680': 1, '1463017504': 1, '1463014016': 1, '1463014560': 1, '1463015552': 1, '1463017712': 1, '1463017424': 1, '1463013872': 1, '1463015040': 1, '1463013824': 1, '1463016304': 1, '1463017680': 1, '1463014112': 1, '1463015248': 1, '1463017632': 1, '1463016448': 1, '1463016480': 1, '1463013888': 1, '1463017264': 1, '1463016496': 1, '1463017856': 1, '1463016192': 1, '1463017440': 1, '1463017776': 1, '1463015904': 1, '1463016592': 1, '1463017328': 1, '1463016880': 1, '1463017008': 1, '1463016960': 1, '1463015376': 1, '1463015888': 1, '1463014960': 1, '1463017920': 1, '1463014160': 1, '1463015920': 1, '1463016720': 1, '1463015152': 1, '1463015616': 1, '1463016624': 1, '1463014528': 1, '1463014288': 1, '1463017296': 1, '1463014864': 1, '1463016832': 1, '1463017088': 1, '1463015504': 1, '1463014704': 1, '1463014736': 1, '1463014320': 1, '1463015136': 1, '1463015568': 1, '1463017600': 1, '1463017888': 1, '1463014144': 1, '1463014832': 1, '1463014592': 1, '1463017408': 1, '1463016160': 1, '1463016672': 1, '1463017104': 1, '1463017344': 1, '1463014256': 1, '1463014512': 1, '1463017456': 1, '1463016992': 1, '1463014656': 1, '1463016816': 1, '1463017728': 1, '1463017760': 1, '1463016976': 1, '1463015808': 1, '1463014192': 1, '1463017552': 1, '1463016640': 1, '1463014352': 1, '1463015360': 1, '1463015536': 1, '1463016240': 1, '1463013952': 1, '1463015440': 1, '1463014064': 1, '1463015264': 1, '1463017616': 1, '1463016048': 1, '1463014464': 1, '1463014688': 1, '1463016256': 1, '1463015728': 1, '1463014608': 1, '1463017584': 1, '1463014784': 1, '1463017248': 1, '1463015344': 1, '1463014640': 1, '1463013856': 1, '1463015184': 1, '1463016688': 1, '1463017072': 1, '1463015792': 1, '1463014720': 1, '1463015232': 1, '1463017808': 1, '1463015840': 1, '1463016560': 1, '1463014896': 1, '1463014624': 1, '1463016016': 1, '1463016864': 1, '1463017168': 1, '1463014672': 1, '1463016464': 1, '1463017216': 1, '1463014400': 1, '1463015168': 1, '1463015312': 1, '1463014224': 1, '1463016912': 1, '1463016176': 1, '1463016528': 1, '1463014480': 1, '1463017232': 1, '1463017360': 1, '1463016128': 1, '1463014912': 1, '1463015056': 1, '1463016432': 1, '1463015008': 1, '1463017280': 1, '1463016544': 1, '1463016096': 1, '1463014384': 1, '1463015328': 1, '1463017184': 1, '1463014416': 1, '1463015280': 1, '1463016736': 1, '1463015824': 1, '1463015984': 1, '1463015216': 1, '1463014928': 1, '1463014336': 1, '1463015712': 1, '1463015024': 1, '1463016000': 1, '1463016336': 1, '1463016384': 1, '1463017152': 1, '1463015456': 1, '1463014128': 1, '1463017040': 1, '1463014992': 1, '1463014800': 1, '1463016848': 1, '1463016400': 1, '1463015408': 1, '1463013920': 1, '1463014032': 1, '1463016224': 1, '1463014944': 1, '1463017024': 1, '1463015968': 1, '1463016784': 1, '1463017520': 1, '1463014000': 1, '1463016064': 1, '1463016320': 1, '1463017312': 1, '1463015760': 1, '1463017392': 1, '1463016768': 1, '1463015104': 1, '1463013968': 1, '1463015664': 1, '1463016208': 1, '1463015696': 1, '1463016928': 1, '1463017648': 1, '1463016608': 1, '1463014240': 1, '1463016752': 1, '1463014176': 1})
    

    I hope it doesn't mean range() is bad for memory consumption.


  • 0

    @o_sharp Yeah, no idea what range does under the hood, but apparently it blocks some memory spots as well or so. I wouldn't worry about it, the Python makers probably know what they're doing.


  • 0

    Nice solution! I was inspired by your bottom-up one-liner to create a top-bottom one-liner:

    def minimumTotal(self, triangle):
        return min(reduce(lambda a, b: [c+min(d,e) for c,d,e in zip(b,['']+a,a+[''])], triangle, [0]))
    

    This has the advantage of not having to duplicate the reversed triangle in memory in order to process it.

    I used the Python2 hack that for any integer n:
    '' > n

    I'm not sure how to fix the one-liner for Python3 without making that 1 line extremely long. But anyway I would typically write it in the more traditional form, even if it's a bit longer :-). This is how I had originally written it:

    def minimumTotal(self, triangle):
        r = [0]
        for row in triangle:
            r = [row[i] + min (r[max(i-1,0)], r[min(i,len(r)-1)]) for i in range(len(row))]
        return min(r)
    

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.