Exercises with lists

Exercises with lists#

Introduction#

Exercise - printwords#

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

Hide code cell content 
def printwords(f):
    words = f.split()
    for w in words:
        print(w)

phrase = "ciao come stai?"
printwords(phrase)

ciao
come
stai?

Exercise - printeven#

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

Hide code cell content 
def printeven(xs):
    for x in xs:
        if x % 2 == 0:
            print(x)

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

2
4
6

Exercise - find26#

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

Hide code cell content 
def find26(xs):
    return (26 in xs)

numbers = [1,26,143,431,53,6]
find26(numbers)

True

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

Hide code cell content 
def firstsec(s):
    my_list = phrase.split()
    print(my_list[0], my_list[1])

phrase = "ciao come stai?"
firstsec(phrase)

ciao come

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"

Hide code cell content 
def threeven(xs):
    if len(xs) >= 3:
        if xs[0] % 2 == 0 and xs[1] % 2 == 0 and xs[2] % 2 == 0:
            print("yes")
        else:
            print("no")
    else:
        print("not good")

threeven([6,4,8,4,5])
threeven([2,5,6,3,4,5])
threeven([4])

yes
no
not good

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 !

Hide code cell content 
def separate_ip(s):
    separated = s.split(".")
    for element in separated:
        print(element)

separate_ip("192.168.0.1")

192
168
0
1

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.

Hide code cell content 
def average(xs):
    if len(xs) == 0:
        return 0

    else:
        total = 0
        for x in xs:
            total = total + x
        return(total / len(xs))

av = average([])
print(av)
average([30,28,20,29])

0

26.75

Exercise - Fake news generator#

Functional illiteracy is reading and writing skills that are inadequate “to manage daily living and employment tasks that require reading skills beyond a basic level”

✪✪ Knowing that functional illiteracy is on the rise, a news agency wants to fire obsolete human journalists and attract customers by feeding them with automatically generated fake news. You are asked to develop the algorithm for producing the texts: while ethically questionable, the company pays well, so you accept.

Typically, a fake news starts with a real subject, a real fact (the antecedent), and follows it with some invented statement (the consequence). You are provided by the company three databases, one with subjects, one with antecedents and one of consequences. To each antecedent and consequence is associated a topic.

Write a function fake_news which takes the databases and RETURN a list holding strings with all possible combinations of subjects, antecedents and consequences where the topic of antecedent matches the one of consequence. See desired output for more info.

NOTE: Example data are given but your code must work with any database

Hide code cell content 
def fake_news(subjects, antecedents, consequences):
    ret = []
    for subject in subjects:
        for ant in antecedents:
            for con in consequences:
                if ant[1] == con[0]:
                    ret.append(subject + " " + ant[0] + ", " + con[1])
    return ret

db_subjects = [
    "Government",
    "Party X",
]
db_antecedents = [
    ("passed fiscal reform", "economy"),
    ("passed jobs act", "economy"),
    ("regulated pollution emissions", "environment"),
    ("restricted building in natural areas", "environment"),
    ("introduced more controls in agrifood production", "environment"),
    ("changed immigration policy", "foreign policy"),
]
db_consequences = [
    ("economy", "now spending is out of control"),
    ("economy", "this increased taxes by 10%"),
    ("economy", "this increased deficit by a staggering 20%"),
    ("economy", "as a consequence our GDP has fallen dramatically"),
    ("environment", "businesses had to fire many employees"),
    ("environment", "businesses are struggling to meet law requirements"),
    ("foreign policy", "immigrants are stealing our jobs"),
]

fake_news(db_subjects, db_antecedents, db_consequences)

['Government passed fiscal reform, now spending is out of control',
 'Government passed fiscal reform, this increased taxes by 10%',
 'Government passed fiscal reform, this increased deficit by a staggering 20%',
 'Government passed fiscal reform, as a consequence our GDP has fallen dramatically',
 'Government passed jobs act, now spending is out of control',
 'Government passed jobs act, this increased taxes by 10%',
 'Government passed jobs act, this increased deficit by a staggering 20%',
 'Government passed jobs act, as a consequence our GDP has fallen dramatically',
 'Government regulated pollution emissions, businesses had to fire many employees',
 'Government regulated pollution emissions, businesses are struggling to meet law requirements',
 'Government restricted building in natural areas, businesses had to fire many employees',
 'Government restricted building in natural areas, businesses are struggling to meet law requirements',
 'Government introduced more controls in agrifood production, businesses had to fire many employees',
 'Government introduced more controls in agrifood production, businesses are struggling to meet law requirements',
 'Government changed immigration policy, immigrants are stealing our jobs',
 'Party X passed fiscal reform, now spending is out of control',
 'Party X passed fiscal reform, this increased taxes by 10%',
 'Party X passed fiscal reform, this increased deficit by a staggering 20%',
 'Party X passed fiscal reform, as a consequence our GDP has fallen dramatically',
 'Party X passed jobs act, now spending is out of control',
 'Party X passed jobs act, this increased taxes by 10%',
 'Party X passed jobs act, this increased deficit by a staggering 20%',
 'Party X passed jobs act, as a consequence our GDP has fallen dramatically',
 'Party X regulated pollution emissions, businesses had to fire many employees',
 'Party X regulated pollution emissions, businesses are struggling to meet law requirements',
 'Party X restricted building in natural areas, businesses had to fire many employees',
 'Party X restricted building in natural areas, businesses are struggling to meet law requirements',
 'Party X introduced more controls in agrifood production, businesses had to fire many employees',
 'Party X introduced more controls in agrifood production, businesses are struggling to meet law requirements',
 'Party X changed immigration policy, immigrants are stealing our jobs']

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.

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

Hide code cell content 
def newdoublef(lst):
    ret = []
    for x in lst:
        ret.append(x*2)
    return ret

assert newdoublef([]) == []
assert newdoublef([3]) == [6]
assert newdoublef([3,7,1]) == [6,14,2]

l = [3,7,1]
assert newdoublef(l) == [6,14,2]
assert l == [3,7,1]

Exercise - doublemod#

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

Hide code cell content 
def doublemod(lst):
    for i in range(len(lst)):
        lst[i] = lst[i] * 2

li = []
doublemod(li)
assert li == []

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

li = [3, 7, 1]
doublemod(li)
assert li == [6, 14, 2]

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

Hide code cell content 
def newdoublec(lst):
    return [x * 2 for x in lst]

assert newdoublec([]) == []
assert newdoublec([3]) == [6]
assert newdoublec([3,7,1]) == [6,14,2]

li = [3,7,1]
assert newdoublec(li) == [6,14,2]
assert li == [3,7,1]

Exercise - up#

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

  • USE a list comprehension

Hide code cell content 
def up(lst):
    return [x.upper() for x in lst]

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']

li = ['ciAo']
assert up(li) == ['CIAO']
assert li == ['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

Hide code cell content 
def remall(list1, list2):
    list3 = list2[:]
    for x in list1:
        if x in list3:
            list3.remove(x)
    
    return list3

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']
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

Hide code cell content 
def only_capital_for(lst):
    ret = []
    for el in lst:
        if el.isupper():
            ret.append(el)
    return ret

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

Hide code cell content 
def only_capital_comp(lst):
    return [el for el in lst if el.isupper()]

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.

Hide code cell content 
def sum_all(lst):
    return sum(lst)

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

Hide code cell content 
def sumevenf(lst):
    ret = 0
    for el in lst:
        if el % 2 == 0:
            ret += el
    return ret

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

Hide code cell content 
def sumevenc(lst):
    return sum([el for el in lst if el % 2 == 0])

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

Hide code cell content 
def contains(xs, x):  
    return x in xs

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

Hide code cell content 
def firstn(n):
    return list(range(n))

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.

Hide code cell content 
def firstlast(xs):
    return xs[0] == xs[-1]
    # note: the comparison xs[0] == xs[-1] is an EXPRESSION which generates a boolean,
    #       in this case True if the first character is equal to the last one and False
    #       otherwise so we can directly return the result of the expression

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:

Hide code cell content 
def dup(xs):
    ret = []
    for x in xs:
        ret.append(x)
        ret.append(x)
    return ret

dup(['hello','world','python'])

['hello', 'hello', 'world', 'world', 'python', 'python']

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!

Hide code cell content 
def hasdup(x, xs):
    counter = 0
    for y in xs:
        if y == x:
            counter += 1
            if counter > 1:
                return True
    return False

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

Hide code cell content 
def ord3(xs):
    if len(xs) >= 3:
        return xs[0] <= xs[1] and xs[1] <= xs[2]
    else:
        return False

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.

Hide code cell content 
def filterab(xs):
    ret = []
    for x in xs: 
        if x == 'a' or x == 'b':
            ret.append(x)
    return ret

filterab(["c", "a", "c", "d", "b", "a", "c", "a", "b", "e"])

['a', 'b', 'a', 'a', 'b']

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",
]

li = ["a", "c", "b"]
assert filterab(li) == ["a", "b"]  # verify a NEW list is returned
assert li == ["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.

Hide code cell content 
def hill(n):
    ret = []
    for i in range(1, n):
        ret.append(i)
    for i in range(n, 0, -1):
        ret.append(i)
    return ret

hill(4)

[1, 2, 3, 4, 3, 2, 1]

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

  • USE a while cycle and terminate the function as soon as you reach the peak

  • DO NOT use max function (too easy!)

Hide code cell content 
def peak(xs):
    if len(xs) < 3:
        raise ValueError("Empty list !")
        
    i = 0
    while i < len(xs) - 1:
        if xs[i] > xs[i+1]:
            return xs[i]
        i += 1
                
    return xs[-1]

peak([100, 400, 800, 1220, 1600, 1400, 1000, 300, 40])

1600

try:
    peak([])         # with this anomalous list we expect the exception 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

Hide code cell content 
def even(xs):
    ret = []
    for i in range(0,len(xs),2):
        ret.append(xs[i])
    return ret

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

Hide code cell content 
def mix(lista, listb):
    ret = []
    for i in range(len(lista)):
        ret.append(lista[i])
        ret.append(listb[i])
    return ret

mix(["a", "b", "c"], ["x", "y", "z"])

['a', 'x', 'b', 'y', 'c', 'z']

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

Hide code cell content 
def fill(lst1, lst2):
    if len(lst1) > len(lst2):
        raise ValueError(
            "List 1 is bigger than list 2 ! lst_a = %s, lst_b = %s"
            % (len(lst1), len(lst2))
        )
    j = 0
    for x in lst1:
        lst2[j] = x
        j += 1

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)

Hide code cell content 
def nostop(s, stopwords):
    words = s.split(" ")
    for s in stopwords:
        if s in words:
            words.remove(s)
    return " ".join(words)

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 indices divisible by 3.

Hide code cell content 
def threez(lst):
    for i in range(len(lst)):
        if i % 3 == 0:
            lst[i] = "z"

lst = ["f", "c", "s", "g", "a", "w", "a", "b"]
threez(lst)
lst

['z', 'c', 's', 'z', 'a', 'w', 'z', 'b']

l1 = []
threez(l1)
assert l1 == []
l2 = ["a"]
threez(l2)
assert l2 == ["z"]
l3 = ["a", "b"]
assert threez(["a", "b"]) is 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.

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 = 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 += 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)

6
4
7
5

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

1
10
100
1000

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

Note

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 !

Hide code cell content 
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
    """
    power = 1
    num = 0
    for digit in reversed(lst):
        num += power * digit
        power = power * 10
    return num

listoint([3, 7, 5]), listoint([2, 0]), listoint([0])

(375, 20, 0)

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]

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

4

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

57

Now, given any integer number, you know how to

a. extract last digit b. reduce the problem for the next iteration

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

Hide code cell content 
def intolist(num):
    """ Takes an integer number >= 0 and RETURN a list of digits representing the number in base 10.    
    """
    if num == 0:
        return [0]
    else:
        ret = []
        d = num
        while d > 0:
            digit = d % 10   # remainder of d divided by 10
            ret.append(digit)
            d = d // 10

        return list(reversed(ret))

intolist(375), intolist(20), intolist(0)

([3, 7, 5], [2, 0], [0])

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

Hide code cell content 
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.
    """
    num = listoint(lst)
    return intolist(num + 1)        

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:

>>> [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
Hide code cell content 
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.
    """
    ret = []
    carry = 1
    for digit in reversed(lst):
        new_digit = digit + carry
        if new_digit == 10:
            ret.append(0)
            carry = 1
        else:
            ret.append(new_digit)
            carry = 0
    if carry == 1:
        ret.append(carry)
    ret.reverse()
    return ret

add_one_carry([1, 2, 3]), add_one_carry([3, 6, 9, 9]), add_one_carry([9, 9, 9, 9])

([1, 2, 4], [3, 7, 0, 0], [1, 0, 0, 0, 0])

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