[1]:
# Remember to execute this cell with Control+Enter
import jupman;

Functions 4 - exercises with lists

Introduction

Exercise - printwords

✪ Write a function printwords that PRINTS all the words in a phrase

>>> printwords("ciao come stai?")
ciao
come
stai?
Show solution
[2]:

# write here


Exercise - printeven

✪ Write a function printeven(numbers) that PRINTS all even numbers in a list of numbers xs

>>> printeven([1,2,3,4,5,6])

2
4
6
Show solution
[3]:


# write here


Exercise - find26

✪ Write a function that RETURN True if the number 26 is contained in a list of numbers

>>> find26( [1,26,143,431,53,6] )
True
Show solution
[4]:

# write here


Exercise - firstsec

✪ Write a function firstsec(s) that PRINTS the first and second word of a phrase.

  • to find a list of words, you can use .split() method

>>> firstsec("ciao come stai?")
ciao come
Show solution
[5]:

# write here


Exercise - threeven

✪ Write a function that PRINTS "yes" if first three elements of a list are even numbers. Otherwise, the function must PRINT "no". In case the list contains less than three elements, PRINT "not good"

>>> threeven([6,4,8,4,5])
yes
>>> threeven([2,5,6,3,4,5])
no
>>> threeven([4])
not good
Show solution
[6]:

# write here


Exercise - separate_ip

✪ An IP address is a string with four sequences of numbers (of max length 3), separated by a dot .. For example, 192.168.19.34 and 255.31.1.0 are IP addresses.

Write a function that given an IP address as input, PRINTS the numbers inside the IP address

  • NOTE: do NOT use .replace method !

>>> separate_ip("192.168.0.1")

192
168
0
1
Show solution
[7]:

# write here


Exercise - average

✪ Given a list of integer numbers, write a function average(xs) that RETURNS the arithmetic average of the numbers it contains. If the given list is empty, RETURN zero.

>>> x = average([3,4,2,3])  # ( 10/4 => 2.5)
>>> x
2.5
>>> y = average([])
>>> y
0
>>> z = average([ 30, 28 , 20, 29 ])
>>> z
26.75
Show solution
[8]:

# write here


Functions with assert

We will discuss differences between modifying a list and returning a new one, and look into basic operations like transform, filter, mapping.

ATTENTION: Following exercises contain require to know tests with asserts, do understand how to carry them out, you can read first Error handling and testing

Mapping

Generally speaking, mapping (or transform) operations take something in input and gives back the same type of thing with elements somehow changed.

In these cases, pay attention if it is required to give back a NEW list or MODIFY the existing list.

Exercise - newdoublef

✪ Takes a list of integers in input and RETURN a NEW one with all the numbers of lst doubled.

  • USE a for loop

Show solution
[9]:
def newdoublef(lst):
    raise Exception('TODO IMPLEMENT ME !')

# TEST START - DO NOT TOUCH!
# if you wrote the whole code correct, and execute the cell, Python shouldn't raise `AssertionError`
assert newdoublef([]) == []
assert newdoublef([3]) == [6]
assert newdoublef([3,7,1]) == [6,14,2]

l = [3,7,1]
assert newdoublefor(l) == [6,14,2]
assert l == [3,7,1]
# TEST END
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
/tmp/ipykernel_3032/3187043984.py in <module>
     14
     15 l = [3,7,1]
---> 16 assert newdoublefor(l) == [6,14,2]
     17 assert l == [3,7,1]
     18 # TEST END

NameError: name 'newdoublefor' is not defined

Exercise - doublemod

✪✪ Takes a list of integers in input and MODIFIES it by doubling all the numbers.

Show solution
[ ]:
def doublemod(lst):

    raise Exception('TODO IMPLEMENT ME !')

# TEST START - DO NOT TOUCH!
# if you wrote the whole code correct, and execute the cell, Python shouldn't raise `AssertionError`
l = []
doublemod(l)
assert l == []

l = [3]
doublemod(l)
assert l == [6]

l = [3,7,1]
doublemod(l)
assert l == [6,14,2]
# TEST END

Exercise - newdoublec

✪ Takes a list of integers in input and RETURN a NEW one with all the numbers of lst doubled.

  • USE a list comprehension

Show solution
[ ]:
def newdoublec(lst):
    raise Exception('TODO IMPLEMENT ME !')

# TEST START - DO NOT TOUCH!
# if you wrote the whole code correct, and execute the cell, Python shouldn't raise `AssertionError`
assert newdoublec([]) == []
assert newdoublec([3]) == [6]
assert newdoublec([3,7,1]) == [6,14,2]

l = [3,7,1]
assert newdoublec(l) == [6,14,2]
assert l == [3,7,1]
# TEST END

Exercise - up

✪ Takes a list of strings and RETURN a NEW list having all the strings in lst in capital

  • USE a list comprehension

Show solution
[ ]:
def up(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert up([]) == []
assert up(['']) == ['']
assert up(['a']) == ['A']
assert up(['aA']) == ['AA']
assert up(['Ba']) == ['BA']
assert up(['Ba', 'aC']) == ['BA','AC']
assert up(['Ba dA']) == ['BA DA']

l = ['ciAo']
assert up(l) == ['CIAO']
assert l == ['ciAo']

Filtering

Generally speaking, filter operations take something in input and give back the same type of thing with elements somehow filtered out.

In these cases, pay attention if it is required to RETURN a NEW list or MODIFY the existing list.

Exercise - remall

✪✪ RETURN a NEW list which has the elements from list2 except the elements in list1

Show solution
[ ]:
def remall(list1, list2):
    raise Exception('TODO IMPLEMENT ME !')

assert remall([],[]) == []
assert remall(['a'], []) == []
assert remall([], ['a']) == ['a']
assert remall(['a'], ['a']) == []
assert remall(['b'], ['a']) == ['a']
assert remall(['a', 'b'], ['a','c','b']) == ['c']

orig_l1,orig_l2 = ['a','d'], ['a','c','d','b']
assert remall(orig_l1, orig_l2) == ['c', 'b']
assert orig_l1 == ['a','d']         # checks it doesn't modify the original ones
assert orig_l2 == ['a','c','d','b']

Exercise - only_capital_for

✪ Takes a list of strings lst and RETURN a NEW list which only contains the strings of lst which are all in capital letters (so keeps 'AB' but not 'aB')

  • USE a for loop

Show solution
[ ]:
def only_capital_for(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert only_capital_for(["CD"]) == [ "CD"]
assert only_capital_for(["ab"]) == []
assert only_capital_for(["dE"]) == []
assert only_capital_for(["De"]) == []
assert only_capital_for(["ab","DE"]) == ["DE"]
orig = ["ab", "CD", "Hb", "EF"]
assert only_capital_for(orig) == [ "CD", "EF"]
assert orig == ["ab", "CD", "Hb", "EF"]

Exercise - only_capital_comp

✪ Takes a list of strings lst and RETURN a NEW list which only contains the strings of lst which are all in capital letters (so keeps 'AB' but not 'aB')

  • USE a list comprehension

Show solution
[ ]:
def only_capital_comp(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert only_capital_comp(["CD"]) == [ "CD"]
assert only_capital_comp(["ab"]) == []
assert only_capital_comp(["dE"]) == []
assert only_capital_comp(["De"]) == []
assert only_capital_comp(["ab","DE"]) == ["DE"]
orig = ["ab", "CD", "Hb", "EF"]
assert only_capital_comp(orig) == [ "CD", "EF"]
assert orig == ["ab", "CD", "Hb", "EF"]

Reducing

Generally speaking, reduce operations involve operating on sets of elements and giving back an often smaller result.

In these cases, we operate on lists. Pay attention if it is required to RETURN a NEW list or MODIFY the existing list.

Exercise - sum_all

✪ RETURN the sum of all elements in lst

  • Implement it as you like.

Show solution
[ ]:
def sum_all(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert sum_all([]) == 0
assert sum_all([7,5]) == 12
assert sum_all([9,5,8]) == 22

Exercise - sumevenf

✪ RETURN the sum of all even elements in lst

  • USE a for loop

Show solution
[ ]:
def sumevenf(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert sumevenf([]) == 0
assert sumevenf([9]) == 0
assert sumevenf([4]) == 4
assert sumevenf([7,2,5,8]) == 10

Exercise - sumevenc

✪ RETURN the sum of all even elements in lst

  • USE a list comprehension

  • WRITE only one line of code

Show solution
[ ]:
def sumevenc(lst):
    raise Exception('TODO IMPLEMENT ME !')

assert sumevenc([]) == 0
assert sumevenc([9]) == 0
assert sumevenc([4]) == 4
assert sumevenc([7,2,5,8]) == 10

Other exercises

Exercise - contains

✪ RETURN True if elem is present in list, otherwise RETURN False

Show solution
[ ]:
def contains(xs, x):
    raise Exception('TODO IMPLEMENT ME !')


assert contains([],'a') == False
assert contains(['a'],'a') == True
assert contains(['a','b','c'],'b') == True
assert contains(['a','b','c'],'z') == False

Exercise - firstn

✪ RETURN a list with the first numbers from 0 included to n excluded

  • For example, firstn(3) must RETURN [0,1,2]

  • if n is strictly negative, RETURN an empty list

Show solution
[ ]:

def firstn(n):
    raise Exception('TODO IMPLEMENT ME !')


assert firstn(-1) == []
assert firstn(-2) == []
assert firstn(0) == []
assert firstn(1) == [0]
assert firstn(2) == [0,1]
assert firstn(3) == [0,1,2]

Exercise - firstlast

✪ RETURN True if the first element of a list is equal to the last one, otherwise RETURN False

NOTE: you can assume the list always contains at least one element.

Show solution
[ ]:

def firstlast(xs):
    raise Exception('TODO IMPLEMENT ME !')



assert firstlast(['a']) == True
assert firstlast(['a','a']) == True
assert firstlast(['a','b']) == False
assert firstlast(['a','b','a']) == True
assert firstlast(['a','b','c','a']) == True
assert firstlast(['a','b','c','d']) == False

Exercise - dup

✪ RETURN a NEW list, in which each list element in input is duplicated. Example:

>>> dup(['hello','world','python'])
['hello','hello','world','world','python','python']
Show solution
[ ]:
def dup(xs):
    raise Exception('TODO IMPLEMENT ME !')


assert dup([]) ==  []
assert dup(['a']) == ['a','a']
assert dup(['a','b']) == ['a','a','b','b']
assert dup(['a','b','c']) == ['a','a','b','b','c','c']
assert dup(['a','a']) == ['a','a','a','a']
assert dup(['a','a','b','b']) == ['a','a','a','a','b','b','b','b']
orig = ['a','a','b','b']
assert dup(orig) == ['a','a','a','a','b','b','b','b']
assert orig == ['a','a','b','b']  # it shouldn't MODIFY the original

Exercise - hasdup

✪✪ RETURN True if xs contains element x more than once, otherwise RETURN False.

  • DO NOT use .count method, too easy!

Show solution
[ ]:
def hasdup(x, xs):
    raise Exception('TODO IMPLEMENT ME !')

assert hasdup("a", []) == False
assert hasdup("a", ["a"]) == False
assert hasdup("a", ["a", "a"]) == True
assert hasdup("a", ["a", "a", "a"]) == True
assert hasdup("a", ["b", "a", "a"]) == True
assert hasdup("a", ["b", "a", "a", "a"]) == True
assert hasdup("b", ["b", "a", "a", "a"]) == False
assert hasdup("b", ["b", "a", "b", "a"]) == True

Exercise - ord3

✪✪ RETURN True if provided list has first three elements increasingly ordered, False otherwise

  • if xs has less than three elements, RETURN False

Show solution
[ ]:
def ord3(xs):
    raise Exception('TODO IMPLEMENT ME !')

assert ord3([5]) == False
assert ord3([4,7]) == False
assert ord3([4,6,9]) == True
assert ord3([4,9,7]) == False
assert ord3([9,5,7]) == False
assert ord3([4,8,9,1,5]) == True     # first 3 elements increasing
assert ord3([9,4,8,10,13]) == False  # first 3 elements NOT increasing

Exercise - filterab

✪✪ Takes as input a list of characters, and RETURN a NEW list containing only the characters 'a' and 'b' found in the input list.

Example:

>>> filterab(['c','a','c','d','b','a','c','a','b','e'])
['a','b','a','a','b']
Show solution
[ ]:
def filterab(xs):
    raise Exception('TODO IMPLEMENT ME !')


assert filterab([]) == []
assert filterab(['a']) == ['a']
assert filterab(['b']) == ['b']
assert filterab(['a','b']) == ['a','b']
assert filterab(['a','b','c']) == ['a','b']
assert filterab(['a','c','b']) == ['a','b']
assert filterab(['c','a','b']) == ['a','b']
assert filterab(['c','a','c','d','b','a','c','a','b','e']) == ['a','b','a','a','b']

l = ['a','c','b']
assert filterab(l) == ['a','b'] # verify a NEW list is returned
assert l == ['a','c','b']      # verify original list was NOT modified

Exercise - hill

✪✪ RETURN a list having as first elements the numbers from 1 to n increasing, and after n the decrease until 1 included.

  • NOTE: n is contained only once.

Example:

>>> hill(4)
[1,2,3,4,3,2,1]
Show solution
[ ]:
def hill(n):

    raise Exception('TODO IMPLEMENT ME !')

assert hill(0) == []
assert hill(1) == [1]
assert hill(2) == [1,2,1]
assert hill(3) == [1,2,3,2,1]
assert hill(4) == [1,2,3,4,3,2,1]
assert hill(5) == [1,2,3,4,5,4,3,2,1]

Exercise - peak

✪✪ Suppose in a list are saved the heights of a mountain road taking a measure every 3 km (we assume the road constantly goes upward). At a certain point, you will arrive at the mountain peak where you will measure the height with respect to the sea. Of course, there is also a road to go down hill (constantly downward) and here also the height will be measured every 3 km.

A measurement example is [100, 400, 800, 1220, 1600, 1400, 1000, 300, 40]

Write a function that RETURNS the value from the list which corresponds to the measurement taken at the peak

  • if the list contains less than three elements, raise exception ValueError

>>> peak([100,400, 800, 1220, 1600, 1400, 1000, 300, 40])
1600
Show solution
[ ]:

def peak(xs):
    raise Exception('TODO IMPLEMENT ME !')


try:
    peak([])         # with this anomalous list we expect the excpetion ValueError is raised

    raise Exception("Shouldn't arrive here!")
except ValueError:    # if exception is raised, it is behaving as expected and we do nothing
    pass
assert peak([5,40,7]) == 40
assert peak([5,30,4]) == 30
assert peak([5,70,70, 4]) == 70
assert peak([5,10,80,25,2]) == 80
assert peak([100,400, 800, 1220, 1600, 1400, 1000, 300, 40]) == 1600

Exercise - even

✪✪ RETURN a list containing the elements at even position, starting from zero which is considered even

  • assume the input list always contains an even number of elements

  • HINT: remember that range can take three parameters

Show solution
[ ]:
def even(xs):
    raise Exception('TODO IMPLEMENT ME !')


assert even([]) == []
assert even(['a','b']) == ['a']
assert even(['a','b','c','d']) == ['a', 'c']
assert even(['a','b','a','c']) == ['a', 'a']
assert even(['a','b','c','d','e','f']) == ['a', 'c','e']

Exercise - mix

✪✪ RETURN a NEW list in which the elements are taken in alternation from lista and listb

  • assume that lista and listb contain the same number of elements

Example:

>>> mix(['a', 'b','c'], ['x', 'y','z'])
['a', 'x', 'b','y', 'c','z']
Show solution
[ ]:

def mix(lista, listb):
    raise Exception('TODO IMPLEMENT ME !')


assert mix([], []) == []
assert mix(['a'], ['x']) == ['a', 'x']
assert mix(['a'], ['a']) == ['a', 'a']
assert mix(['a', 'b'], ['x', 'y']) == ['a', 'x', 'b','y']
assert mix(['a', 'b','c'], ['x', 'y','z']) == ['a', 'x', 'b','y', 'c','z']

Exercise - fill

✪✪ Takes a list lst1 of n elements and a list lst2 of m elements, and MODIFIES lst2 by copying all lst1 elements in the first n positions of lst2

  • If n > m, raises a ValueError

Show solution
[ ]:

def fill(lst1, lst2):

    raise Exception('TODO IMPLEMENT ME !')



try:
    fill(['a','b'], [None])
    raise Exception("TEST FAILED: Should have failed before with a ValueError!")
except ValueError:
    "Test passed"

try:
    fill(['a','b','c'], [None,None])
    raise Exception("TEST FAILED: Should have failed before with a ValueError!")
except ValueError:
    "Test passed"

L1 = []
R1 = []
fill(L1, R1)
assert L1 == []
assert R1 == []


L = []
R = ['x']
fill(L, R)
assert L == []
assert R == ['x']


L = ['a']
R = ['x']
fill(L, R)
assert L == ['a']
assert R == ['a']


L = ['a']
R = ['x','y']
fill(L, R)
assert L == ['a']
assert R == ['a','y']

L = ['a','b']
R = ['x','y']
fill(L, R)
assert L == ['a','b']
assert R == ['a','b']

L = ['a','b']
R = ['x','y','z',]
fill(L, R)
assert L == ['a','b']
assert R == ['a','b','z']


L = ['a']
R = ['x','y','z',]
fill(L, R)
assert L == ['a']
assert R == ['a','y','z']

Exercise - nostop

✪✪ When you analyze a phrase, it might be useful processing it to remove very common words, for example articles and prepositions: "a book on Python" can be simplified in "book Python"

The ‘not so useful’ words are called stopwords. For example, this process is done by search engines to reduce the complexity of input string provided ny the user.

Implement a function which takes a string and RETURN the input string without stopwords

Implementa una funzione che prende una stringa e RITORNA la stringa di input senza le stopwords

HINT 1: Python strings are immutable ! To remove words you need to create a new string from the original string

HINT 2: create a list of words with:

words = stringa.split(" ")

HINT 3: transform the list as needed, and then build the string to return with " ".join(lista)

Show solution
[ ]:

def nostop(s, stopwords):
    raise Exception('TODO IMPLEMENT ME !')

assert nostop("a", ["a"]) == ""
assert nostop("a", []) == "a"
assert nostop("", []) == ""
assert nostop("", ["a"]) == ""
assert nostop("a book", ["a"]) == "book"
assert nostop("a book on Python", ["a","on"]) == "book Python"
assert nostop("a book on Python for beginners", ["a","the","on","at","in", "of", "for"]) == "book Python beginners"

Exercise - threez

✪✪ MODIFY the given lst by placing the string 'z' at the indeces divisible by 3.

>>> lst = ['f','c','s','g','a','w','a','b']
>>> trez(lst)
>>> lst
>>> ['z','c','s','z','a','w','z','b']
Show solution
[ ]:
def threez(lst):
    raise Exception('TODO IMPLEMENT ME !')

l1 = []
threez(l1)
assert l1 == []
l2 = ['a']
threez(l2)
assert l2 == ['z']
l3 = ['a','b']
assert threez(['a','b']) == None  # returns nothing!
threez(l3)
assert l3 == ['z','b']
l4 = ['a','b','c']
threez(l4)
assert l4 == ['z','b','c']
l5 = ['a','b','c','d']
threez(l5)
assert l5 == ['z','b','c','z']
l6 = ['f','c','s','g','a','w','a','b']
threez(l6)
assert l6 == ['z','c','s','z','a','w','z','b']

Exercises with numbers

Exercise - listoint

✪✪ Given a non-empty list of digits representing a non-negative integer, return a proper python integer

The digits are stored such that the most significant digit is at the head of the list, and each element in the list is a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example:

>>> listoint([3,7,5])
375
>>> listoint([2,0])
20
>>> listoint([0])
0

DO NOT try hacks like converting the whole list to string, dirty tricks always bring undesired consequences!

The proper way is to follow rules of math, keeping in mind that in mind that

\[5746 = 5*1000 + 7*100 + 4 * 10 + 6 * 1\]

For our purposes, it is better to rewrite the formula like this:

\[5746 = 6 * 1 + 4 * 10 + 7*100 + 5*1000\]

Basically, we are performing a sum \(4\) times. Each time and starting from the least significant digit, the digit in consideration is multiplied for a progressivly bigger power of 10, starting from \(10^0 = 1\) up to \(10^4=1000\).

To understand how it could work in Python, we might progressivly add stuff to a cumulator variable c like this:

c = 0

c = c + 6*1
c = c + 4*10
c = c + 7*100
c = c + 5*1000

In a more pythonic and concise way, we would write:

c = 0

c += 6*1
c += 4*10
c += 7*100
c += 5*1000

So first of all to get the 6,4,7,5 it might help to try scanning the list in reverse order using the function reversed (notice the ed at the end!)

[ ]:
for x in reversed([5,7,4,6]):
    print(x)

Once we have such sequence, we need a way to get a sequence of progressively increasing powers of 10. To do so, we might use a variable power:

[ ]:
power = 1

for x in reversed([5,7,4,6]):
    print (power)
    power = power * 10

Now you should have the necessary elements to implement the required function by yourself.

PLEASE REMEMBER: if you can’t find a general solution, keep trying with constants and write down all the passages you do. Then in new cells try substituting the constants with variables and keep experimenting - it’s the best method to spot patterns !

Show solution
[ ]:
def listoint(lst):
    """ RETURN a Python integer which is represented by the provided list of digits, which always
        represent a number >= 0 and has no trailing zeroes except for special case of number 0
    """
    raise Exception('TODO IMPLEMENT ME !')

assert listoint([0]) == 0
assert listoint([1]) == 1
assert listoint([2]) == 2
assert listoint([92]) == 92
assert listoint([90]) == 90
assert listoint([5,7,4]) == 574

Exercise - intolist

✪✪ Let’s now try the inverse operation, that is, going from a proper Python number like 574 to a list [5,7,4]

Example:

>>> intolist(375)
[3,7,5]

>>> intolist(20)
[2,0]

>>> intolist(0)
[0]

To do so, we must exploit integer division // and reminder operator %.

Let’s say we want to get the final digit 4 out of 574. To do so, we can notice that 4 is the reminder of integer division between 547 and 10:

[ ]:
574 % 10

This extracts the four, but if we want to find an algorithm for our problem, we must also find a way to progressively reduce the problem size. To do so, we can exploit the integer division operator //:

[ ]:
574 // 10

Now, given any integer number, you know how to

  1. extract last digit

  2. reduce the problem for the next iteration

This should be sufficient to proceed. Pay attention to special case for input 0.

Show solution
[ ]:
def intolist(num):
    """ Takes an integer number >= 0 and RETURN a list of digits representing the number in base 10.
    """
    raise Exception('TODO IMPLEMENT ME !')

assert intolist(0) == [0]
assert intolist(1) == [1]
assert intolist(2) == [2]
assert intolist(92) == [9,2]
assert intolist(90) == [9,0]
assert intolist(574) == [5,7,4]

Exercise - add one

Given a non-empty list of digits representing a non-negative integer, adds one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the list is a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

For example:

Input: [1,2,3]
Output: [1,2,4]

Input: [3,6,9,9]
Output: [3,7,0,0]

Input: [9,9,9,9]
Output: [1,0,0,0,0]

There are two ways to solve this exercise: you can convert to a proper integer, add one, and then convert back to list which you will do in add_one_conv. The other way is to directly operate on a list, using a carry variable, which you will do in add_one_carry

Exercise - add_one_conv

✪✪✪ You need to do three steps:

  1. Convert to a proper python integer

  2. add one to the python integer

  3. convert back to a list and return it

Show solution
[ ]:
def add_one_conv(lst):
    """
        Takes a list of digits representing an integer >= 0 without trailing zeroes except zero itself
        and RETURN a NEW a list representing the value of lst plus one.

        Implement by calling already used implemented functions.
    """
    raise Exception('TODO IMPLEMENT ME !')

assert add_one_conv([0]) == [1]
assert add_one_conv([1]) == [2]
assert add_one_conv([2]) == [3]
assert add_one_conv([9]) == [1, 0]
assert add_one_conv([5,7]) == [5, 8]
assert add_one_conv([5,9]) == [6, 0]
assert add_one_conv([9,9]) == [1, 0, 0]

Exercise - add_one_carry

✪✪✪ Given a non-empty array of digits representing a non-negative integer, adds one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

For example:

>>> add_one_carry([1,2,3])
[1,2,4]

>>> add_one_carry([3,6,9,9])
[3,7,0,0]

>>> add_one_carry([9,9,9,9])
[1,0,0,0,0]

To implement it, directly operate on the list, using a carry variable.

Just follow addition as done in elementary school. Start from the last digit and sum one:

If you get a number <= 9, that is the result of summing last two digits, and the rest is easy:

596+    carry=0
001
----
  7     6 + 1 + carry = 7
596+    carry=0
001
----
 97     9 + 0 + carry = 9
596+    carry=0
001
----
 07     5 + 0 + carry = 5

If you get a number bigger than 9, then you put zero and set carry to one:

3599+    carry=0
0001
-----
   0     9 + 1 + carry = 10    # >9, will write zero and set carry to 1
3599+    carry=1
0001
----
  00     9 + 0 + carry = 10   # >9, will write zero and set carry to 1
3599+    carry=1
0001
-----
 600     5 + 0 + carry = 6    # <= 9, will write result and set carry to zero
3599+    carry=0
0001
-----
3600     3 + 0 + carry = 3    # <= 9, will write result and set carry to zero
Show solution
[10]:
def add_one_carry(lst):
    """
        Takes a list of digits representing a >= 0 integer without trailing zeroes except zero itself
        and RETURN a NEW a list representing the value of lst plus one.
    """
    raise Exception('TODO IMPLEMENT ME !')

assert add_one_carry([0]) == [1]
assert add_one_carry([1]) == [2]
assert add_one_carry([2]) == [3]
assert add_one_carry([9]) == [1, 0]
assert add_one_carry([5,7]) == [5, 8]
assert add_one_carry([5,9]) == [6, 0]
assert add_one_carry([9,9]) == [1, 0, 0]

Exercise - collatz

✪✪✪✪ The Collatz conjecture says that starting from any n, by performing these calculations recursively you obtain a sequence which finally ends up to 1:

  • if n is even, divide n by 2

  • if n is odd, multiply it by 3 and add 1

  • Repeat until you reach the value of 1

Example: for n = 3 , the sequence is [3 , 10 , 5 , 16 , 8 , 4 , 2 , 1] .

Write a program that creates a list seq , such that for each value n between 1 and 50 , seq [ n ] contains the length of the sequence so generated. In case of n = 3 , the length is 8 . In case of n = 27 , the length is 111.

If you need to check your results, you can also try this nice online tool

[11]:
def collatz():
    raise Exception("TODO IMPLEMENT ME!")

Continue

Go on with exercises about functions and tuples

[ ]: