What's up with this code?

[Scott David Daniels]

Gregory Petrosyan wrote:
> Hello, it's me again.
> I am trying to optimise small module for working with polynomials, and
> I have encountered problem: new, optimised, code, doesn't work in some
> specific case. Here's the old version of the code:
> 
> (3x^2 + 2x + 1  <=>  poly([3, 2, 1]), btw)
> 
>     def __add__(self, other):
>         "Return sum of two polynomials"
>         rcoefs1 = list(reversed(self.coefs))
>         rcoefs2 = list(reversed(other.coefs))
>         coefs = [c1+c2 for c1,c2 in zip(rcoefs1, rcoefs2)]
>         minlen = min(len(rcoefs1), len(rcoefs2))
>         coefs.extend(rcoefs1[minlen:] + rcoefs2[minlen:])
>         return Polynomial(reversed(coefs))
> 
> Here's the new version:
> 
>     def __add__(self, other):
>         rcoefs1 = reversed(self.coefs)
>         rcoefs2 = reversed(other.coefs)
>         coefs = [c1+c2 for c1,c2 in it.izip(rcoefs1, rcoefs2)]
>         coefs.extend(it.chain(rcoefs1, rcoefs2)) #? -- here is magic
>         if coefs[-1] != 0:
>             return Polynomial(reversed(coefs), False, False)
>         else:
>             return Polynomial(reversed(coefs), False)
> 
> Last four lines are ok (tested), "magic" seems to occure in #? line.
> What's the magic? Here it is:
> 
> poly([1,2,1]) + poly([1,-2,1]) is ok,
> poly([1,-2,1]) + poly([5,4,3,2,1]) is ok,
> poly([1]) + poly([2]) is ok,
> poly([1,2,1]) + poly([5,4,3,2,1]) is ok, but
> 
> poly([1,0]) + poly([-1])  gives poly([-1]),
> poly([1,-3]) + poly([-2]) gives poly([-5]) etc.
> 
> "magic" happens when processing something like poly([a,b]) +
> poly([c]) and it gives poly([b+c]) as result. Can anybody help me with
> it?

OK, the trick is to think about how zip/izip _must_ work.
When the first list runs out first it stops.  When the
second list runs out, it has already read ahead one element
of the first list.

      def __add__(self, other):
          shorter = reversed(self.coefs)
          longer = reversed(other.coefs)
          if len(self.coefs) > len(other.coefs):
              shorter, longer = longer, shorter  # insure shorter first
          coefs = [c1+c2 for c1,c2 in it.izip(shorter, longer)]
          if len(self.coefs) == len(other.coefs):
              while coefs and coefs[-1] == 0:
                  coefs.pop()
          else:
              coefs.extend(longer)
          ...

--Scott David Daniels
scott.daniels at acm.org