4
\$\begingroup\$

So I've been working on a generator for Pascal's triangle in Python. Now, I wouldn't call myself a Python god, so my program is a lot longer than the very confusing ones on the internet. It's more of a logical approach to creating the triangle.

Here's the program:

def double_chunker(lst):
  leng = len(lst)
  for i in range(leng):
    if i == 0:
      yield [lst[0]]
    elif i == 1:
      yield [lst[0], lst[1]]
    elif i == leng:
      yield [lst[-1]]
    else:
      yield [lst[i-1], lst[i]]
  yield [lst[-1]]

def chunk_adder(lst):
  for i in lst:
    if len(i) == 1:
      yield i[0]
    else:
      yield sum(i)

def pascal_next(lst):
  return list(chunk_adder(double_chunker(lst)))

def pascal_triangle(rows):
  end = [[1]]
  for i in range(rows):
    end.append(pascal_next(end[-1]))
  return end

A simple go-through of how it works:

  1. double_chunker() splits up a row of Pascal's triangle into the pairs of numbers you would use when adding up to determine the numbers in the next row. This algorithm is little jerry-rigged - I had to add some special exceptions for some numbers on the end of the row to make it work properly.

  2. chunk_adder() adds together a list of chunks generated by double_chunker to determine the next row in the Pascal sequence.

  3. pascal_next()combines both double_chunker() and chunk_adder() to, when given one row in Pascal's triangle, determine the next row in the triangle.

  4. pascal_triangle() iteratively creates rows of Pascal's triangle using pascal_next().

So, here are some of my questions:

  1. Is there anything in my program that seems redundant, repetitive, or can be shortened?

  2. Is there any better code practices I should be employing and am not?

And obviously, as always, feel free to provide any other feedback you may have. Thanks in advance!

\$\endgroup\$
10
\$\begingroup\$
def chunk_adder(lst):
  for i in lst:
    if len(i) == 1:
      yield i[0]
    else:
      yield sum(i)

sum can happilly consume iterable of size 1, it can even consume iterable of size 0:

>>> sum([1])
1
>>> sum([])
0

So you can simplify it to:

def chunck_adder(iterable):
    for element in iterable:
        yield sum(element)

Which is simply

def chunck_adder(iterable):
    yield from map(sum, iterable)

So you could simplify pascal_next instead:

def pascal_next(lst):
    return list(map(sum, double_chunker(lst)))

def double_chunker(lst):
  leng = len(lst)
  for i in range(leng):
    if i == 0:
      yield [lst[0]]
    elif i == 1:
      yield [lst[0], lst[1]]
    elif i == leng:
      yield [lst[-1]]
    else:
      yield [lst[i-1], lst[i]]
  yield [lst[-1]]

The intent is pretty much the same than the pairwise recipe from itertools. Except you want to yield the first and last element as well.

Here you have two possibilities:

  • either yield them manually:

    import itertools
    
    def double_chunker(lst):
        if not lst:
            return
        a, b = itertools.tee(lst)
        next(b, None)
    
        yield [lst[0]]
        yield from zip(a, b)
        yield [lst[-1]]
    

    But this forces the argument to be a list, or at least to know if its empty and to implement __getitem__.

  • or add boundary values to your input so pairwise can work properly:

    import itertools
    
    
    def pairwise(iterable):
        a, b = itertools.tee(iterable)
        next(b, None)
        return zip(a, b)
    
    
    def double_chuncker(iterable):
        extended = itertools.chain([0], iterable, [0])
        return pairwise(extended)
    

    Which I recommend because it happily consume any iterable.


def pascal_triangle(rows):
  end = [[1]]
  for i in range(rows):
    end.append(pascal_next(end[-1]))
  return end

Instead of relying on the list being constructed, I would explicitly store the current row. I would also turn this into an infinite generator because it really is and maybe provide an helper function for convenience:

def pascal_triangle():
    row = [1]
    while True:
        yield row
        row = pascal_next(row)


def pascal_triangle_up_to(n):
    return list(itertools.islice(pascal_triangle(), n))

Full code:

import itertools


def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)


def double_chuncker(iterable):
    extended = itertools.chain([0], iterable, [0])
    return pairwise(extended)


def pascal_next(iterable):
    return list(map(sum, double_chuncker(iterable)))


def pascal_triangle():
    row = [1]
    while True:
        yield row
        row = pascal_next(row)


def pascal_triangle_up_to(n):
    return list(itertools.islice(pascal_triangle(), n))


if __name__ == '__main__':
    # Testing
    for row in pascal_triangle():
        print(row, end='')
        if (input()):
            break
\$\endgroup\$
5
\$\begingroup\$

Names

I am not fully convinced by the different function names but I have nothing better to suggest for the time being.

Style

Python has a Style Guide called PEP 8. It is an interesting read. The most significant impact for your code would be to use 4 spaces for each indentation level instead of 2.

Simplify double_chunker

In double_chunker, the following condition is never true:

elif i == leng:
  yield [lst[-1]]

Also, you don't need to handle explicitly the case:

elif i == 1:
  yield [lst[0], lst[1]]

as it is just a particular case for [lst[i-1], lst[i]] with i == 1.

Simplify chunk_adder

In chunk_adder, instead of:

if len(i) == 1:
  yield i[0]
else:
  yield sum(i)

We can write:

yield sum(i)

Then, we could rewrite the function using generator expressions:

def chunk_adder(lst):
  return (sum(i) for i in lst)

Then, it looks like the function is not really needed. We could write:

def pascal_next(lst):
  return [sum(i) for i in double_chunker(lst)]

At this stage, we have:

def double_chunker(lst):
  for i in range(len(lst)):
    if i == 0:
      yield [lst[0]]
    else:
      yield [lst[i-1], lst[i]]
  yield [lst[-1]]


def pascal_next(lst):
  return [sum(i) for i in double_chunker(lst)]

def pascal_triangle(rows):
  end = [[1]]
  for i in range(rows):
    end.append(pascal_next(end[-1]))
  return end


print(pascal_triangle(8))

More simplification in double_chunker

We could handle the case i == 0 before the loop rather than inside the loop. That could lead to a slightly different behavior when the input is an empty list but that case is not handled properly anyway (exception thrown).

def double_chunker(lst):
  yield [lst[0]]
  for i in range(1, len(lst)):
    yield [lst[i-1], lst[i]]
  yield [lst[-1]]

Then, it becomes obvious what we want to do: we want to iterate over all pairs of consecutive items in a list which is a problem common enough to find various solutions to it.

\$\endgroup\$
3
\$\begingroup\$

Is there any better code practices I should be employing and am not?

  • The first thing that caught my attention is the missing tests

You should implement a few test cases to ensure that after changes the program does still work as intended

Both the unittest module or doctest are good Python modules for testing, I have used the unittest as an example

class PascalTriangleTest(unittest.TestCase):
    def test_triangle_0(self):
        self.assertEqual(
            pascal_triangle(0), 
            [[1]]
        )

    def test_triangle_1(self):
        self.assertEqual(
            pascal_triangle(1), 
            [[1], [1, 1]]
        )

    def test_triangle_2(self):
        self.assertEqual(
            pascal_triangle(2), 
            [[1], [1, 1], [1, 2, 1]]
        )

    def test_triangle_3(self):
        self.assertEqual(
            pascal_triangle(3), 
            [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
        )

if __name__ == '__main__':
    unittest.main()
  • The second one would be the missing docstrings

The comments below your code would be a good start to make the docstring for each function.

See PEP257, for docstring conventions

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

Is there anything in my program that seems redundant, repetitive, or can be shortened?

The 22 lines of double_chunker, chunk_adder, and pascal_next can be shortened to

def pascal_next(lst):
  return [left + right for (left, right) in zip(lst + [0], [0] + lst)]
\$\endgroup\$
  • 1
    \$\begingroup\$ Or return [sum(pair) for pair in zip(lst + [0], [0] + lst)] to make use of the built in sum \$\endgroup\$ – Ludisposed Jan 17 at 14:47
  • \$\begingroup\$ @Ludisposed, I deliberately chose not to do that because I regard it as a pessimisation. \$\endgroup\$ – Peter Taylor Jan 17 at 15:28
  • \$\begingroup\$ You could also omit the parenthesis: [left + right for left, right in zip(lst + [0], [0] + lst)]. \$\endgroup\$ – Graipher Jan 17 at 15:30

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.