Python Multiple Assignment Is a Puzzle

Re:Python Multiple Assignment Is a Puzzle by jw2013 on Sunday July 27, 2014 @02:23AM (#8092135)

The function you wrote:

    a) takes O(n*lgn) time; the method in post uses O(n) time
    b) use extra memory; the method in post uses O(1) extra memory
    c) have logical error: the problem asks to find the first missing positive (in range [1, infinity)).

So firstMissingPositive([4,100]) should return 1, instead of 5. But the problem is not stated in the post, so let's assume you are implementing the first missing positive in range(A[0], A[-1] + 1) for sorted(A), your code does not handle corner case well.

For example:

    a) your firstMissingPositive([100]) gives ValueError: min() arg is an empty sequence
    b) your firstMissingPositive([]) gives IndexError: list index out of range

It is attempting to write three-liners that seems to solve the problem, but it is far more important to solve the problem in time and space efficient way. At least, it is important to handle the corner cases well.

[ Parent | on HN ]

Re:Python Multiple Assignment Is a Puzzle by zebulanmcranahn on Sunday July 27, 2014 @01:32PM (#8093355)

  def firstMissingPositive(A):
      try:
          for x in range(1, max(A)+1):
              if x not in A: return x
      except: return A

  def firstMissingPositive(A):
      try: return next(x for x in range(1, max(A)+1) if x not in A)
      except: return A

Two above return:

  print(firstMissingPositive([4,2,5,7,1])) # 3
  print(firstMissingPositive([4,100]))     # 1
  print(firstMissingPositive([]))          # []
  print(firstMissingPositive([5]))         # 1

I wasn't sure what [5] or [] were supposed to return so maybe I'm still wrong? Had never heard of this question before, thought I'd try it out.

Thanks for the reply, very informative.

[ Parent | on HN ]

Re:Python Multiple Assignment Is a Puzzle by TheLoneWolfling on Sunday July 27, 2014 @05:11PM (#8093984)

You really should change "except" to "except ValueError" there.

Also, I suggest first converting A to a set. Just "A = set(A)" would work.

[ Parent | on HN ]

Re:Python Multiple Assignment Is a Puzzle by yeukhon on Sunday July 27, 2014 @02:55PM (#8093613)

HN is not really for code review, but why are you using try and except here??

[ Parent | on HN ]

Re:Python Multiple Assignment Is a Puzzle by TheLoneWolfling on Sunday July 27, 2014 @05:07PM (#8093972)

Python is designed for it, and it makes it cleaner, so why not?

EAFP: Easier to ask for forgiveness than permission

That being said, just a blanket except is a bad idea.

[ Parent | on HN ]

Re:Python Multiple Assignment Is a Puzzle by zebulanmcranahn on Monday July 28, 2014 @12:51AM (#8095233)

Thanks for the ValueError tip. I added it as well as a TypeError just in case the input comes in as a string. My skills are beginner level at best, tips like yours help a lot!

[ Parent | on HN ]