2048 merge function

Question

From: Principles of Computing Part 1 Course on Coursera

I got -2 pts on my OWLTEST which uses Pylint for style guide. The error states:

Too many branches (17/12) function "merge", line 7

What does that mean?

I worked really hard on making this program work and wrote it from scratch. I would also like to know if there are some techniques to make this cleaner and/or utilize best practices. I know there are probably ways to write this in a better way because right now my code looks really messy.

I wish to improve on code style, performance, and readability.

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 3 17:55:56 2015
2048_merge_attempt1.py
@author: Rafeh
"""
def merge(nums):
 '''
 Takes a list as input 
 returns merged pairs with
 non zero values shifted to the left.
 [2, 0, 2, 4] should return [4, 4, 0, 0]
 [0, 0, 2, 2] should return [4, 0, 0, 0]
 [2, 2, 0, 0] should return [4, 0, 0, 0]
 [2, 2, 2, 2, 2] should return [4, 4, 2, 0, 0]
 [8, 16, 16, 8] should return [8, 32, 8, 0]
 '''
 slide = [] # Append non-zeroes first
 for num in nums:
 if num != 0:
 slide.append(num)
 for num in nums:
 if num == 0:
 slide.append(num)
 pairs = []
 for idx, num in enumerate(slide):
 if idx == len(slide)-1:
 pairs.append(num)
 if len(pairs) != len(nums):
 pairs.append(0)
 break
 if num == slide[idx+1]:
 if num != 0:
 pairs.append(num*2)
 slide[idx+1] -= slide[idx+1]
 # slide[idx+1], slide[idx+2] = slide[idx+2], slide[idx+1]
 else:
 pairs.append(num)
 else:
 pairs.append(num) # Even if they don't match you must append
 slide = [] # Append non-zeroes first
 for num in pairs:
 if num != 0:
 slide.append(num)
 for num in nums:
 if num == 0:
 slide.append(num)
 for _ in range(len(nums) - len(slide)):
 if len(nums) != len(slide):
 slide.append(0)
 return slide

• mkrieger1: The indentation is slightly odd, but I'm not sure whether it's only from copy/pasting or it's part of what you want reviewed, and therefore I don't want to edit it. In particular: the coding line is indented by two spaces and the rest of the code by additional two spaces, both are superfluous. Also in line 40, pairs.append(num) is indented one level (four spaces) too deep, which can be misleading, especially in Python.
• Clever Programmer: @mkrieger1 yeah line 40 indentation was incorrect. Thanks for catching that I fixed it in my code now. Weird no style guide analysis caught it. I ran it through like 5 different ones. Is there something that formats or restructures your code automatically once you are done with it so it meets the best possible style guide standards? As far as the indentation, it's not like that in my actual code. Don't know why it's SO indented here.
• mkrieger1: When editing a post, everything indented by four spaces is considered a code block. So you indented the first line by six spaces and the remaining lines by eight spaces when writing the question. A safe way to insert a code block is by pasting it without any extra indentation, then highlighting it and pressing either Ctrl-K or pressing the {} button, which indents everything uniformly by four spaces.
• Clever Programmer: That's what I tried... It did not work? I took the whole code and pasted with 0 indentations and pressed Ctrl-K and it did not work. So I eventually gave up. :(
• rookie: Take a look at some of this code.

Answer 1

A couple of typical patterns to iterate over pairs of items in Python are:

for prev, next in zip(nums[:-1], nums[1:]):
 ...

and

prev = None
for next in nums:
 if prev is None:
 prev = next
 continue
 ...

In your case, I think the second fits the bill better:

def merge(nums):
 prev = None
 store = []
 for next_ in nums:
 if not next_:
 continue
 if prev is None:
 prev = next_
 elif prev == next_:
 store.append(prev + next_)
 prev = None
 else:
 store.append(prev)
 prev = next_
 if prev is not None:
 store.append(prev)
 store.extend([0] * (len(nums) - len(store)))
 return store

• rubik: Neat solution, I love it.
• Clever Programmer: what does the continue statement do? If next_ = 5 for example, the code will jump to next if statement. If next_ = 0 the code will continue and then simply jump to the next if statement? UPDATE: Oh! Continue runs through the next iteration of the loop! Wow learned something new. Leaving this comment here hoping it helps someone else.
• Clever Programmer: I have read this and I understand difference between is vs == is that the former is an object identity checker where == checks whether they are equivalent. However, I do not completely understand this. In my terminal None is not None returns the same as None != None. Please explain. Note I understand that when a=[1,2] & b=[1,2], the statement a is b will return False whereas the == check will return True. However, in this case (None is not None), I do not see the difference
• Clever Programmer: There are lots of good answers. It was hard to decide between @SuperBiasedMan answer and this one. I decided to go with this answer as it is very clean and pythonic. I learned about iterating pairs of values which is a particularly useful technique that I will be able to re-implement in the future. I also learned about the extend method on a list and the continue function. This helps me clean my code significantly and make it super easy to read. The other answer is very useful in terms of list comprehensions. However, I had to pick one, and this one simply carried more useful concepts.
• David Z: In practice I would actually suggest pairwise() from the itertools documentation for iterating over pairs. An implementation can be imported from the more-itertools package.

Answer 2

Use automatic tests

In your doc-string you state:

 [2, 0, 2, 4] should return [4, 4, 0, 0]
 [0, 0, 2, 2] should return [4, 0, 0, 0]
 [2, 2, 0, 0] should return [4, 0, 0, 0]
 [2, 2, 2, 2, 2] should return [4, 4, 2, 0, 0]
 [8, 16, 16, 8] should return [8, 32, 8, 0]

But I either

• Test all this inputs manually (very boring)
• Trust you (nothing personal but code accuracy should not be based on personal subjective trust)

Instead you could have written:

>>> merge([2, 0, 2, 4])
[4, 4, 0, 0]
>>> merge([0, 0, 2, 2])
[4, 0, 0, 0]
>>> merge([2, 2, 0, 0])
[4, 0, 0, 0]
>>> merge([2, 2, 2, 2, 2])
[4, 4, 2, 0, 0]
>>> merge([8, 16, 16, 8])
[8, 32, 8, 0]

This way doctest will run all the test automatically each time the module is executed. This technique will save you much tedious manual testing in the future.

• Clever Programmer: I am a newbie can you please explain more in depth how to use the doctest? I read this: docs.python.org/2/library/doctest.html and I still I created an if name main function at the bottom of my program. I imported doctest, included what you mentioned in my docstring, and executed the code. However, even after all that, it did not work.
• Caridorc: import doctest at the start. doctest.testmod() after your function. No Output means everything correct.
• mkrieger1: Better run python -m doctest <name of your module.py> from the command line, this way your module isn't coupled tightly with doctest and can be used also without it.
• mkrieger1: Yes, but then you can't use the module without running the doctests except by editing it out again.
• Caridorc: @mkrieger1 why would running the doctest bother you?

Answer 3

List comprehensions are your friend. They essentially collapse for loops into one line and directly assign them to a list, saving you pointless time. The syntax is like a for loop in reverse contained in list brackets, [statement for var in iterable]. You could first make slide like this:

 slide = [num for num in nums if num != 0]
 slide += [num for num in nums if num == 0]

But you could also use Python's truthiness to just say if not num which returns True if num is 0 and then if num for the opposite. When building slide again later you can mimic these exact two lines of course.

It's idiomatic to use i instead of idx for a for loop index, and it's shorter too.

Why use this line:

slide[idx+1] -= slide[idx+1]

When all that will ever be is basically:

slide[idx+1] = 0

Lastly, you can use list multiplication to avoid your final for loop:

slide += [0] * (len(nums) - len(slide))

(if the len is the same then their difference will be 0 anyway, so you don't need to check for a length discrepancy)

• user14393: Even better: slide.extend(num for num in nums if num == 0)
• Clever Programmer: Thank you for your answer. I learned a tremendous amount from this! I stated my reason in the best answer's comment section for going with @Jaime 's answer. It was a tough decision! I will ultimately be using your suggestions for the submission of my code on Coursera as your suggestions perfectly coincide with my current code and thought process. Also, Hurkyl great suggestion!
• Clever Programmer: Note: Pylint yells at me for using i instead of idx. @SuperBiasedMan
• SuperBiasedMan: @Rafeh Glad I helped! And the use of i may be contested by some. I do see it a lot, so it's up to you whether you want to listen to Pylint or not. I guess I should note that there's nothing wrong with idx as it is clear, I just like typing less and have never had trouble using i for simple loops like this.
• Clever Programmer: I completely agree! It's just that I lose pts on my course for this, that's all. Otherwise I have never had a problem using "i"s myself during a for loop!

Answer 4

what does that mean?

A branch is when something else than the next line of code is executed. According to OWLTEST, you have 17 branches where it deems 12 the maximum acceptable.

Long story short, it doesn't like your style. There are many loops and many ifs in the same function. Splitting up your function will increase the readability significantly.

Another point it could complain about is the repetition.

 for num in nums:
 if num != 0:
 slide.append(num)
 for num in nums:
 if num == 0:
 slide.append(num)

You're iterating two times over nums right after each other. Have you thought about doing this in one iteration, appending all num != 0 to a first slide, appending all num == 0 to a second slide and paste those slides after each other later?

It would save you at least an iteration. Iterations are expensive.

Answer 5

I have to admit that I am quite confused by your code. It takes a lot of variables, cycles and if statements. Just looking at it I find very hard to understand what it does.

To practice a little bit with Python, I tried to do the same exercise and I came up with this (incorporating the answer of Caridorc):

def merge(nums):
 '''
 Takes a list as input 
 returns merged pairs with
 non zero values shifted to the left.
 test with: 
 python -m doctest 2048.py
 No output == OK!
 >>> merge([2, 0, 2, 4])
 [4, 4, 0, 0]
 >>> merge([0, 0, 2, 2])
 [4, 0, 0, 0]
 >>> merge([2, 2, 0, 0])
 [4, 0, 0, 0]
 >>> merge([2, 2, 2, 2, 2])
 [4, 4, 2, 0, 0]
 >>> merge([8, 16, 16, 8])
 [8, 32, 8, 0]
 '''
 # save the initial length of the list
 size = len(nums)
 # remove all the zeroes - looked up on stackoverflow
 nums[:] = (value for value in nums if value != 0)
 # now do the merging, use an index to run through the list
 i = 0
 while (i < len(nums)-1 ):
 if (nums[i]==nums[i+1]): # if a number is the same as the following
 nums[i] *= 2 # double it 
 del nums[i+1] # remove the following
 i += 1
 # restore the initial list length appending zeroes
 while (len(nums) < size):
 nums.append(0)
 # done
 return nums

Here are the main differences compared to the original code:

1. No line looks similar to any other else. Lots of similar lines are normally an indication that there is a better way to get lighter and easier to read code.
2. Minimal usage of extra variables. Every time you declare new variables one has to understand what are you planning to use them for! The use of lots of supporting variables, especially if they are complex, normally has also an impact on performances.
3. Use while cycles instead of for cycles. The while is the perfect loop when you don't know your range a-priori. Its syntax is simpler than a for cycle and if you keep it simple is also very easy to read.
4. Avoid too many indentation levels. The deeper you go, the harder your code becomes to understand.

I hope this helps to keep up exercising writing better and better code!

---

Integrating the improvements as suggested in the comments:

def merge(nums):
 res = (value for value in nums if value != 0)
 i = 0
 while (i < len(res)-1 ):
 if (res[i]==res[i+1]): # if a number is the same as the following
 res[i] *= 2 # double it 
 del res[i+1] # remove the following
 i += 1
 res.extend([0] * (len(nums)-len(res)))
 return res

The c-looking cycle could be made more pythonic copying in an extra list, but I like it more like that.

• WorldSEnder: The last while(len(nums) < ... can be written better as nums.extend([0] * (size - len(nums))). Also the while (i < ... should be written as for i in range(len(nums)). Leave the unnessecary brackets away. And at last, you should make a new list instead of assinging nums[:]
• DarioP: @WorldSEnder for your first point yes. For the second no: with your proposal as numbers are deleted from the list the index goes out of bound.
• Sjoerd Job Postmus: Here, you are modifying the argument nums in-place, while also returning it. In general, and especially in this case, I would recommend against it.
• Clever Programmer: Thank you for your very useful pointers, @Dario. I do not understand the reason for assigning to nums[:] vs just nums. If you could please elaborate that, that would be great. I agree with WorldSEnder on the use of .extend method. That is very neat.

Answer 6

Out of the initial two loops, we only need the first one. We really only want the non-zero values; we don't need to deal with the zeros until the end.

def merge(nums):
 slide = [] 
 for num in nums:
 if num != 0:
 slide.append(num)

Next, we'll get rid of the main for loop. It's going to become a while loop; we'll handle incrementing ourselves.

 pairs = []
 idx = 0
 while idx < len(slide):
 num = slide[idx]
 if idx == len(slide)-1:
 pairs.append(num)
 break

We also don't need to check the lengths here, we'll deal with the end padding later. We also keep the break, this is how we get out of the loop.

Now the main check. We don't bother checking for zero equality any more, we already know there are no zeros in slide.

 if num == slide[idx+1]:
 pairs.append(num*2)
 idx += 1 

Notice the extra increment, that's so we skip the next number. We have the standard else clause, same as you had. And finally, we increment the counter ourselves.

 else:
 pairs.append(num) 
 idx += 1

Now, at this point, we have the right values we need, we just have to pad it with zeros on the right. Fortunately, you've got a way to do that already.

 for _ in range(len(nums) - len(pairs)):
 pairs.append(0) 
 return pairs

I just changed the variable name from slide back to pairs. Reusing a variable name in the way you originally did it at this point is bad practice, you should avoid it.

Also, we don't need the length check in the loop.

So, all together, the code looks like

def merge(nums):
 slide = [] 
 for num in nums:
 if num != 0:
 slide.append(num)
 pairs = []
 idx = 0
 while idx < len(slide):
 num = slide[idx]
 if idx == len(slide)-1:
 pairs.append(num)
 break
 if num == slide[idx+1]:
 pairs.append(num*2)
 idx += 1 
 else:
 pairs.append(num) 
 idx += 1
 for _ in range(len(nums) - len(pairs)):
 pairs.append(0) 
 return pairs

You'll notice that as the body of the function becomes smaller, it becomes easier to read. Also, reusing two names across three variables make the code difficult to follow. In addition, a bit of whitespace, to separate the "paragraphs" of the function, makes it easier to read.

Your style is not bad. Indentation is consistent, you stick to accepted python abbreviations (like idx, although simply using i is also acceptable), and you use decent variable names (besides the issue I've already mentioned).

• Clever Programmer: Thank you for your insightful answer. This while loop will definitely help me keep my code cleaner! Yeah, I also realized while trying to go through the code again that I do not need to have a 0 appender as I can simply reverse engineer and append all the needed 0's at the end. Your answer is very thorough and great for a beginner/intermediate programmer like myself!