Recursion 2 - Accumulators and indexes

So far in the SimpleFP model we have been creating a lot of new lists by concatenating with + operator and taking slices: this wasted a lot of memory and computation time.

Let’s try to improve performance by creating a new model we named ModAcc with these requirements:

ALLOWED:

• add helper functions to easily pass extra variables

• add special accumulator parameters to the helper function: feel free to MODIFY them (and only them!) by using .append, .extend, etc

• add indexes parameters to the helper function to keep track where to look in the original list

• getting length with len(lst)

• in operator on dictionaries or sets

DO NOT use slices

DO NOT MODIFY input parameters!

DO NOT use in operator on sequences like strings, lists, tuples

DO NOT use * replication operator on lists

DO NOT use predefined functions (sum, max, min, range, ….)

DO NOT use methods!

DO NOT INITIALIZE AN ACCUMULATOR IN THE PARAMETER DECLARATION

• NEVER write stuff like:

def my_helper(lst, acc=[]):

def my_helper(lst, acc={}):

If you initialize to a mutable data structure such as lists or dictionaries, Python will create exactly one memory region for all function invocations, which is quite counterintuitive and bug prone!

Example - adouble

Let’s see an example by improving our double function to take a lst of numbers and RETURN a NEW list with the numbers doubled:

def adouble_helper(lst, i, acc):   # we create a helper function
                                   # with index where to start looking
                                   # and accumulator variable
                                   # note acc is *not* initialized in the parameters
    if i == len(lst):   # base case compares index against end of list
        return acc      #    notice it returns the accumulator
    else:
        acc.append(lst[i]*2)    #  we first MODIFY the accumulator
        return adouble_helper(lst, i+1, acc)  # then do recursion by passing the modified accumulator
                                                # notice passed list is always the same,
                                                # what changes is the starting index

def adouble(lst):
    return adouble_helper(lst, 0, [])

result = adouble([7,9,5])
result
jupman.pytut()

Exercise - debug adouble

Add a level parameter and some debugging indented print to the function

Show solution

def adouble_helper(lst, i, acc, level=0):
    print(' '*level, 'i=',i,' acc=', acc)
    if i == len(lst):
        return acc
    else:
        acc.append(lst[i]*2)
        res = adouble_helper(lst, i+1, acc, level=level+1)
        print(' '*level, 'res=', res)
        return res

def adouble(lst):
    return adouble_helper(lst, 0, [])


result = adouble([4,9,1,5,7,3])
result

 i= 0  acc= []
  i= 1  acc= [8]
   i= 2  acc= [8, 18]
    i= 3  acc= [8, 18, 2]
     i= 4  acc= [8, 18, 2, 10]
      i= 5  acc= [8, 18, 2, 10, 14]
       i= 6  acc= [8, 18, 2, 10, 14, 6]
      res= [8, 18, 2, 10, 14, 6]
     res= [8, 18, 2, 10, 14, 6]
    res= [8, 18, 2, 10, 14, 6]
   res= [8, 18, 2, 10, 14, 6]
  res= [8, 18, 2, 10, 14, 6]
 res= [8, 18, 2, 10, 14, 6]

[8, 18, 2, 10, 14, 6]

result = adouble([4,9,1,5,7,3])
result

 i= 0  acc= []
  i= 1  acc= [8]
   i= 2  acc= [8, 18]
    i= 3  acc= [8, 18, 2]
     i= 4  acc= [8, 18, 2, 10]
      i= 5  acc= [8, 18, 2, 10, 14]
       i= 6  acc= [8, 18, 2, 10, 14, 6]
      res= [8, 18, 2, 10, 14, 6]
     res= [8, 18, 2, 10, 14, 6]
    res= [8, 18, 2, 10, 14, 6]
   res= [8, 18, 2, 10, 14, 6]
  res= [8, 18, 2, 10, 14, 6]
 res= [8, 18, 2, 10, 14, 6]

[8, 18, 2, 10, 14, 6]

Exercise - afilter_even

Takes a lst of numbers, and RETURN a NEW list with only the even numbers

Show solution

def afilter_even_helper(lst, i, acc):

    if i == len(lst):
        return acc
    else:
        if lst[i] % 2 == 0:
            acc.append(lst[i])
            return afilter_even_helper(lst, i=i+1, acc=acc)
        else:
            return afilter_even_helper(lst, i=i+1, acc=acc)


def afilter_even(lst):

    return afilter_even_helper(lst, 0, [])


result = afilter_even([3,7,10,5,4,8,6,11])
print(result)  # [10,4,8,6]

assert afilter_even([3]) == []
assert afilter_even([4]) == [4]
assert afilter_even([3,6]) == [6]
assert afilter_even([8,3]) == [8]
assert afilter_even([8,3,2]) == [8,2]
assert afilter_even([7,7,8,3,2]) == [8,2]
assert afilter_even([3,7,10,5,4,8,6,11]) == [10,4,8,6]

[10, 4, 8, 6]

def afilter_even(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = afilter_even([3,7,10,5,4,8,6,11])
print(result)  # [10,4,8,6]

assert afilter_even([3]) == []
assert afilter_even([4]) == [4]
assert afilter_even([3,6]) == [6]
assert afilter_even([8,3]) == [8]
assert afilter_even([8,3,2]) == [8,2]
assert afilter_even([7,7,8,3,2]) == [8,2]
assert afilter_even([3,7,10,5,4,8,6,11]) == [10,4,8,6]

Exercise - amerry

Given a lst with an even number of elements, RETURN a NEW list holding two element lists with consecutive content taken from the original list.

Show solution

def amerry_helper(lst, i, acc):
    if i == len(lst):
        return acc
    else:
        acc.append([lst[i], lst[i+1]])
        return  amerry_helper(lst, i+2, acc)


def amerry(lst):

    return amerry_helper(lst, 0, [])


result = amerry(['a','b','c','c','a','d','b','a'])
print(result)  # [['a','b'],['c','c'],['a','d'],['b','a']]

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

[['a', 'b'], ['c', 'c'], ['a', 'd'], ['b', 'a']]

def amerry(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = amerry(['a','b','c','c','a','d','b','a'])
print(result)  # [['a','b'],['c','c'],['a','d'],['b','a']]

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

Exercise - afib

Given a number n, RETURN a NEW list with all the numbers of Fibonacci sequence:

\(n\)	0	1	2	3	4	5	6	7	8	9	10
\(x_n\)	0	1	1	2	3	5	8	13	21	34	…

Base cases:

• \(x_0\) = 0

• \(x_1\) = 1

The next number is found by adding up the two numbers before it:

• \(x_2\) is 0+1

• \(x_3\) is 1+1

• \(x_4\) is 2+1

• \(x_5\) is 3+2

• and so on…

Show solution

def afib_helper(n, acc):
    if n == 0:
        acc.append(0)
        return acc
    elif n == 1:
        acc.append(0)
        acc.append(1)
        return acc
    else:
        acc = afib_helper(n-1, acc)
        acc.append(acc[n-1] + acc[n-2])
        return acc


def afib(n):

    return afib_helper(n, [])


result = afib(7)
print(result) # [0,1,1,2,3,5,8,13]

assert afib(0) == [0]
assert afib(1) == [0,1]
assert afib(2) == [0,1,1]
assert afib(3) == [0,1,1,2]
assert afib(4) == [0,1,1,2,3]
assert afib(5) == [0,1,1,2,3,5]
assert afib(6) == [0,1,1,2,3,5,8]
assert afib(7) == [0,1,1,2,3,5,8,13]

[0, 1, 1, 2, 3, 5, 8, 13]

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

result = afib(7)
print(result) # [0,1,1,2,3,5,8,13]

assert afib(0) == [0]
assert afib(1) == [0,1]
assert afib(2) == [0,1,1]
assert afib(3) == [0,1,1,2]
assert afib(4) == [0,1,1,2,3]
assert afib(5) == [0,1,1,2,3,5]
assert afib(6) == [0,1,1,2,3,5,8]
assert afib(7) == [0,1,1,2,3,5,8,13]

[0, 1, 1, 2, 3, 5, 8, 13]

Exercise - asearch

Given an el to search and a lst, RETURN True if such element is present or False otherwise

• DO NOT use in operator nor search methods like .find, .index, ….

• you might consider shortening your code by using Boolean evaluation order

Show solution

def asearch_helper(el, lst, i):

    if i == len(lst):
        return False
    else:
        return lst[i] == el or asearch_helper(el,lst, i+1)  # early termination using  boolean evaluation order!


def asearch(el, lst):

    return asearch_helper(el,lst, 0)


print(asearch(7, [6,4,7,8]))   # True
print(asearch(5, [6,4,7,8]))   # False

assert asearch(7, [6,4,7,8]) == True
assert asearch(7, [8]) == False
assert asearch(8, [8]) == True
assert asearch(5, [8,5]) == True
assert asearch(2, [8,5]) == False
assert asearch(7, [7,8,5]) == True
assert asearch(2, [8,2,5]) == True
assert asearch(9, [7,8,9]) == True
assert asearch(2, [8,9,5]) == False

True
False

def asearch(el, lst):
    raise Exception('TODO IMPLEMENT ME !')

print(asearch(7, [6,4,7,8]))   # True
print(asearch(5, [6,4,7,8]))   # False

assert asearch(7, [6,4,7,8]) == True
assert asearch(7, [8]) == False
assert asearch(8, [8]) == True
assert asearch(5, [8,5]) == True
assert asearch(2, [8,5]) == False
assert asearch(7, [7,8,5]) == True
assert asearch(2, [8,2,5]) == True
assert asearch(9, [7,8,9]) == True
assert asearch(2, [8,9,5]) == False

Exercise - abin_search

If the list is already sorted we can write a faster search. Start looking in the middle of the list: if that cell is the searched element, you’re done. Otherwise, if searched element is lesser do recursion on left sublist, otherwise on right sublist.

• lst is a list of \(n\) already sorted elements

• HINT 1: add indeces parameters i and j are indeces between 0 included and \(n\) included

• HINT 2: keep splitting the search interval in halves until you have a 1 element interval (or empty interval)

DO NOT use in operator, .find nor .index methods

Show solution

def abin_search_helper(el, lst, i, j):
    #print('i =', i, ' j =', j)
    interval = j - i
    #print('interval =', interval)
    k = (i + j) // 2
    #print('k =', k)

    if interval <= 0:
        return False
    elif el == lst[k]:
        return True
    #elif interval == 1:
    #    return False
    elif el < lst[k]:
        return abin_search_helper(el, lst, 0, k)
    else: # >
        return abin_search_helper(el, lst, k+1, j)


def abin_search(el, lst):

    return abin_search_helper(el, lst, 0, len(lst))



print(abin_search(33, [8,9,15,17,20,24,28,29,33,36,39])) # True
print(abin_search(10, [8,9,15,17,20,24,28,29,33,36,39])) # False

assert abin_search(5, [5]) == True
assert abin_search(4, []) == False
assert abin_search(3, [7]) == False
assert abin_search(3, [3,7]) == True
assert abin_search(3, [3,6]) == True
assert abin_search(4, [2,9]) == False
assert abin_search(5, [2,9]) == False
assert abin_search(5, [5,7,9]) == True
assert abin_search(7, [5,7,9]) == True
assert abin_search(9, [5,7,9]) == True
assert abin_search(4, [5,7,9]) == False
assert abin_search(6, [5,7,9]) == False
assert abin_search(8, [5,7,9]) == False
assert abin_search(10, [5,7,9]) == False
assert abin_search(33, [8,9,15,17,20,24,28,29,33,36,39]) == True
assert abin_search(10, [8,9,15,17,20,24,28,29,33,36,39]) == False

True
False

def abin_search(el, lst):
    raise Exception('TODO IMPLEMENT ME !')


print(abin_search(33, [8,9,15,17,20,24,28,29,33,36,39])) # True
print(abin_search(10, [8,9,15,17,20,24,28,29,33,36,39])) # False

assert abin_search(5, [5]) == True
assert abin_search(4, []) == False
assert abin_search(3, [7]) == False
assert abin_search(3, [3,7]) == True
assert abin_search(3, [3,6]) == True
assert abin_search(4, [2,9]) == False
assert abin_search(5, [2,9]) == False
assert abin_search(5, [5,7,9]) == True
assert abin_search(7, [5,7,9]) == True
assert abin_search(9, [5,7,9]) == True
assert abin_search(4, [5,7,9]) == False
assert abin_search(6, [5,7,9]) == False
assert abin_search(8, [5,7,9]) == False
assert abin_search(10, [5,7,9]) == False
assert abin_search(33, [8,9,15,17,20,24,28,29,33,36,39]) == True
assert abin_search(10, [8,9,15,17,20,24,28,29,33,36,39]) == False

Exercise - azip

Given two lists, RETURN a NEW list having couples as tuples with elements taken pairwise from lst1 and lst2

• DO NOT use zip function

Show solution

def azip_helper(lst1, lst2, i, acc):

    if i == len(lst1):
        return acc
    else:
        acc.append((lst1[i], lst2[i]))
        return azip_helper(lst1, lst2, i+1, acc)


def azip(lst1, lst2):

    return azip_helper(lst1, lst2, 0, [])


result = azip([3,5,1,6], ['a','d','e','w'])
print(result)  # [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

assert azip([], []) == []
assert azip(['a'], [0]) == [('a',0)]
assert azip(['z','a'], [2,4]) == [('z',2), ('a',4)]
assert azip([3,5,1,6], ['a','d','e','w']) == [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

[(3, 'a'), (5, 'd'), (1, 'e'), (6, 'w')]

def azip(lst1, lst2):
    raise Exception('TODO IMPLEMENT ME !')

result = azip([3,5,1,6], ['a','d','e','w'])
print(result)  # [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

assert azip([], []) == []
assert azip(['a'], [0]) == [('a',0)]
assert azip(['z','a'], [2,4]) == [('z',2), ('a',4)]
assert azip([3,5,1,6], ['a','d','e','w']) == [(3,'a'), (5,'d'), (1,'e'), (6,'w')]

Exercise - aunnest

Given a lst of lists, RETURN a NEW list without sublists (also called shallow unnest)

• assume sublists cannot have further sublists inside

Show solution

def aunnest_helper(lst, i, acc):

    if i == len(lst):
        return acc
    else:
        acc.extend(lst[i])
        return aunnest_helper(lst, i+1, acc)


def aunnest(lst):

    return aunnest_helper(lst, 0, [])


result = aunnest([[3,2,5], [2,4], [0,9,5,1]])
print(result)  # [3,2,5,2,4,0,9,5,1]

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

[3, 2, 5, 2, 4, 0, 9, 5, 1]

def aunnest(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = aunnest([[3,2,5], [2,4], [0,9,5,1]])
print(result)  # [3,2,5,2,4,0,9,5,1]

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

Exercise - arev

Given a list, RETURN a NEW list reversed.

• DO NOT use reversed function

• DO NOT use slice stepping

Show solution

def arev_helper(lst, i, acc):
    if i == -1:
        return acc
    else:
        acc.append(lst[i])
        return arev_helper(lst, i-1,acc)


def arev(lst):

    return arev_helper(lst, len(lst)-1, [])


result = arev([4,9,7,5,6])
print(result)

assert arev([]) == []
assert arev([3]) == [3]
assert arev([5,3]) == [3,5]
assert arev([6,6,2]) == [2,6,6]
assert arev([4,9,7,5,6]) == [6,5,7,9,4]

[6, 5, 7, 9, 4]

def arev(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = arev([4,9,7,5,6])
print(result)

assert arev([]) == []
assert arev([3]) == [3]
assert arev([5,3]) == [3,5]
assert arev([6,6,2]) == [2,6,6]
assert arev([4,9,7,5,6]) == [6,5,7,9,4]

Exercise - apalindrome

A string is palindrome if it reads the same backward as forward.

Given a string s, return True if the string is palindrome, otherwise return False.

• we assume the empty string is palindrome

• here we use strings but same rules for lists apply

• DO NOT use string methods (so no .index(), .find(), …)

Show solution

def apalindrome_helper(s, i):
    if i == len(s)//2:
        return True
    elif i == len(s)//2 + 1:
        return True
    else:
        if s[i] == s[-i-1]:
            return apalindrome_helper(s, i+1)
        else:
            return False


def apalindrome(s):

    return apalindrome_helper(s,0)


assert apalindrome('') == True
assert apalindrome('a') == True
assert apalindrome('ab') == False
assert apalindrome('cc') == True
assert apalindrome('ddv') == False
assert apalindrome('vddv') == True
assert apalindrome('axyb') == False
assert apalindrome('kayak') == True
assert apalindrome('kayag') == False
assert apalindrome('rotator') == True
assert apalindrome('rotating') == False
assert apalindrome('noon') == True
assert apalindrome('soon') == False
assert apalindrome('abcdba') == False

def apalindrome(s):
    raise Exception('TODO IMPLEMENT ME !')

assert apalindrome('') == True
assert apalindrome('a') == True
assert apalindrome('ab') == False
assert apalindrome('cc') == True
assert apalindrome('ddv') == False
assert apalindrome('vddv') == True
assert apalindrome('axyb') == False
assert apalindrome('kayak') == True
assert apalindrome('kayag') == False
assert apalindrome('rotator') == True
assert apalindrome('rotating') == False
assert apalindrome('noon') == True
assert apalindrome('soon') == False
assert apalindrome('abcdba') == False

Exercise - anest

Given a lst, RETURN a NEW list of deeply right nested lists as in the example

• HINT: you need to create a new list anyway at each helper call

Show solution

def anest_helper(lst, i, acc):
    if i == len(lst):
        return acc
    elif i == len(lst) - 1:
        acc.append(lst[i])
        return acc
    else:
        acc.append(lst[i])
        res = anest_helper(lst, i+1, []) # we need to create a NEW list anyway
        acc.append(res)
        return acc


def anest(lst):

    return anest_helper(lst, 0, [])


result = anest(['a','b','c','d','e','g','h'])
print(result)  # ['a',['b',['c',['d',['e',['g',['h']]]]]]]

assert anest([]) == []
assert anest(['a']) == ['a']
assert anest(['a','b']) == ['a',['b']]
assert anest(['a','b','c']) == ['a',['b',['c']]]
assert anest(['x','x','y']) == ['x',['x',['y']]]
assert anest(['a','b','c','d','e','g','h']) == ['a',['b',['c',['d',['e',['g',['h']]]]]]]

['a', ['b', ['c', ['d', ['e', ['g', ['h']]]]]]]

def anest(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = anest(['a','b','c','d','e','g','h'])
print(result)  # ['a',['b',['c',['d',['e',['g',['h']]]]]]]

assert anest([]) == []
assert anest(['a']) == ['a']
assert anest(['a','b']) == ['a',['b']]
assert anest(['a','b','c']) == ['a',['b',['c']]]
assert anest(['x','x','y']) == ['x',['x',['y']]]
assert anest(['a','b','c','d','e','g','h']) == ['a',['b',['c',['d',['e',['g',['h']]]]]]]

Exercise - apalace

Given a lst of characters, RETURN a NEW list of deeply nested lists as in the example.

• Pay attention to base cases, there are several

• HINT: you need to create a new list anyway at each helper call

Show solution

def apalace_helper(lst, i, acc):
    if len(lst) == 0:
        return acc
    elif i == len(lst)//2 + 1:
        return acc
    elif i == len(lst)//2:
        acc.append(lst[i])
        return acc
    elif i == len(lst) - 2:
        acc.append(lst[i])
        acc.append(lst[i+1])
        return acc
    else:
        acc.append(lst[i])
        res = apalace_helper(lst, i+1, [])  # we need to create a NEW list anyway
        acc.append(res)
        acc.append(lst[-i-1])
        return acc


def apalace(lst):

    return apalace_helper(lst,0,[])


result = apalace(['a','b','c','d','e','f','g','h','i'])
print(result)   # ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

assert apalace([])  == []
assert apalace(['a'])  == ['a']
assert apalace(['a','b'])  == ['a','b']
assert apalace(['b','a'])  == ['b','a']
assert apalace(['c','b','a'])  == ['c',['b'],'a']
assert apalace(['z','w','z'])  == ['z',['w'],'z']
assert apalace(['p','x','y','z','q'])  == ['p',['x',['y'],'z'],'q']
assert apalace(['a','b','c','d','e','f','g','h','i'])  == ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

def apalace(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = apalace(['a','b','c','d','e','f','g','h','i'])
print(result)   # ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

assert apalace([])  == []
assert apalace(['a'])  == ['a']
assert apalace(['a','b'])  == ['a','b']
assert apalace(['b','a'])  == ['b','a']
assert apalace(['c','b','a'])  == ['c',['b'],'a']
assert apalace(['z','w','z'])  == ['z',['w'],'z']
assert apalace(['p','x','y','z','q'])  == ['p',['x',['y'],'z'],'q']
assert apalace(['a','b','c','d','e','f','g','h','i'])  == ['a', ['b', ['c', ['d', ['e'], 'f'], 'g'], 'h'], 'i']

Exercise - arep

Given a list la, and a list lb of integer numbers \(\geq 0\), RETURN a NEW list where all elements of la are repeated the amount of times indicated in the corresponding cell of lb

• assume la and lb have the same size

• DO NOT use * replication operator

• HINT: you will need an additional parameter k in the helper to keep track of the amount of repetitions left

Show solution

def arep_helper(la, lb, i, k, acc):
    if i == len(la):
        return acc
    elif k > 0:
        acc.append(la[i])
        return arep_helper(la, lb, i, k-1, acc)
    else:  # k == 0
        if i + 1 < len(la):
            return arep_helper(la, lb, i+1, lb[i+1], acc)
        else:
            return acc


def arep(la, lb):

    if len(la) == 0:
        return []
    else:
        return arep_helper(la,lb,0,lb[0],[])


result = arep(['a','b','c','d'], [2,5,0,3])
print(result) # ['a','a','b','b','b','b','b','d','d','d']

assert arep([], []) == []
assert arep(['a'], [1]) == ['a']
assert arep(['a'], [0]) == []
assert arep(['b'], [2]) == ['b','b']
assert arep(['a','b'], [1,1]) == ['a','b']
assert arep(['a','b'], [1,2]) == ['a','b','b']
assert arep(['a','b'], [2,1]) == ['a','a','b']
assert arep(['a','b'], [2,0]) == ['a','a']
assert arep(['a','b'], [0,2]) == ['b','b']
assert arep(['a','b','c'], [1,1,1]) == ['a','b','c']
assert arep(['a','b','c'], [0,1,1]) == ['b','c']
assert arep(['a','b','c'], [0,1,0]) == ['b']
assert arep(['a','b','c'], [3,1,2]) == ['a','a','a','b','c','c']
assert arep(['a','b','c','d'], [2,5,0,3]) == ['a','a','b','b','b','b','b','d','d','d']

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

def arep(la, lb):
    raise Exception('TODO IMPLEMENT ME !')

result = arep(['a','b','c','d'], [2,5,0,3])
print(result) # ['a','a','b','b','b','b','b','d','d','d']

assert arep([], []) == []
assert arep(['a'], [1]) == ['a']
assert arep(['a'], [0]) == []
assert arep(['b'], [2]) == ['b','b']
assert arep(['a','b'], [1,1]) == ['a','b']
assert arep(['a','b'], [1,2]) == ['a','b','b']
assert arep(['a','b'], [2,1]) == ['a','a','b']
assert arep(['a','b'], [2,0]) == ['a','a']
assert arep(['a','b'], [0,2]) == ['b','b']
assert arep(['a','b','c'], [1,1,1]) == ['a','b','c']
assert arep(['a','b','c'], [0,1,1]) == ['b','c']
assert arep(['a','b','c'], [0,1,0]) == ['b']
assert arep(['a','b','c'], [3,1,2]) == ['a','a','a','b','c','c']
assert arep(['a','b','c','d'], [2,5,0,3]) == ['a','a','b','b','b','b','b','d','d','d']

Exercise - asortin

Given two already sorted lists la and lb of arbitrary sizes, return True if all numbers of la are present in lb

• assume empty list is always contained in any list

• DO NOT use search methods (find(), index(), …)

• HINT 1: compare list heads one at a time, try thinking when you can return early

• HINT 2: you will need a couple of indexes in the helper (you don’t need an accumulator)

Show solution

def asortin_helper(la, lb, i, j):
    if i == len(la):
        return True
    elif j == len(lb):
        return False
    elif la[i] < lb[j]:
        return False
    elif la[i] > lb[j]:
        return asortin_helper(la, lb, i, j+1)
    else:   # l[i] == lb[j]
        return asortin_helper(la, lb, i+1, j)


def asortin(la, lb):


    return asortin_helper(la,lb,0,0)


assert asortin([], []) == True
assert asortin([], [4,5,8,1]) == True
assert asortin([5], [5]) == True
assert asortin([5], [6]) == False
assert asortin([3], [3,8]) == True
assert asortin([8], [3,8]) == True
assert asortin([2], [3,8]) == False
assert asortin([7,9], [7,9]) == True
assert asortin([7,9], [3,7,9]) == True
assert asortin([7,9], [7,8,9]) == True
assert asortin([7,9], [7,9,10]) == True
assert asortin([5,8], [2,8]) == False
assert asortin([5,8], [5,6]) == False
assert asortin([5,8], [2,4,8]) == False
assert asortin([5,8], [4,5,7]) == False
assert asortin([3,5,6], [3,5,6]) == True
assert asortin([3,5,6], [3,4,5,6]) == True
assert asortin([3,5,6], [3,5,6,7]) == True
assert asortin([4,6,11], [1,3,4,5,6,7,8,10,11,12]) == True

def asortin(la, lb):
    raise Exception('TODO IMPLEMENT ME !')

assert asortin([], []) == True
assert asortin([], [4,5,8,1]) == True
assert asortin([5], [5]) == True
assert asortin([5], [6]) == False
assert asortin([3], [3,8]) == True
assert asortin([8], [3,8]) == True
assert asortin([2], [3,8]) == False
assert asortin([7,9], [7,9]) == True
assert asortin([7,9], [3,7,9]) == True
assert asortin([7,9], [7,8,9]) == True
assert asortin([7,9], [7,9,10]) == True
assert asortin([5,8], [2,8]) == False
assert asortin([5,8], [5,6]) == False
assert asortin([5,8], [2,4,8]) == False
assert asortin([5,8], [4,5,7]) == False
assert asortin([3,5,6], [3,5,6]) == True
assert asortin([3,5,6], [3,4,5,6]) == True
assert asortin([3,5,6], [3,5,6,7]) == True
assert asortin([4,6,11], [1,3,4,5,6,7,8,10,11,12]) == True

Exercise - ahist

Given a lst, RETURN a NEW dictionary with the counts of elements of lst

• DO NOT use search methods (.index, .count, .remove…)

Show solution

def ahist_helper(lst, i, acc):
    if i == len(lst):
        return acc
    else:
        if lst[i] in acc:
            acc[lst[i]] += 1
        else:
            acc[lst[i]] = 1
        return ahist_helper(lst, i+1, acc)


def ahist(lst):

    return ahist_helper(lst, 0, {})


result = ahist(['a','b','a','c','b','b','c','a','b','c','d'])
print(result)  # {'a':3,
               #  'b':4,
               #  'c':3,
               #  'd':1}

assert ahist([]) == {}
assert ahist(['a']) == {'a':1}
assert ahist(['a','a']) == {'a':2}
assert ahist(['a','b']) == {'a':1,
                            'b':1}
assert ahist(['b','c']) == {'c':1,
                            'b':1}
assert ahist(['a','c','a']) == {'a':2,
                                'c':1}
assert ahist(['c','c','a']) == {'a':1,
                                'c':2}
assert ahist(['a','b','a','c','b','b','c','a','b','c','d']) == {'a':3,
                                                                'b':4,
                                                                'c':3,
                                                                'd':1}

{'a': 3, 'b': 4, 'c': 3, 'd': 1}

def ahist(lst):
    raise Exception('TODO IMPLEMENT ME !')

result = ahist(['a','b','a','c','b','b','c','a','b','c','d'])
print(result)  # {'a':3,
               #  'b':4,
               #  'c':3,
               #  'd':1}

assert ahist([]) == {}
assert ahist(['a']) == {'a':1}
assert ahist(['a','a']) == {'a':2}
assert ahist(['a','b']) == {'a':1,
                            'b':1}
assert ahist(['b','c']) == {'c':1,
                            'b':1}
assert ahist(['a','c','a']) == {'a':2,
                                'c':1}
assert ahist(['c','c','a']) == {'a':1,
                                'c':2}
assert ahist(['a','b','a','c','b','b','c','a','b','c','d']) == {'a':3,
                                                                'b':4,
                                                                'c':3,
                                                                'd':1}

Exercise - agap

In a list \(L\) containing \(n≥2\) integers, a gap is an index \(i\), \(0< i < n\), such that \(L[i−1]< L[i]\)

If \(n≥2\) and \(L[0]< L[n−1]\), \(L\) contains at least one gap.

Design an algorithm that, given a list \(L\) containing \(n≥2\) integers such that \(L[0]< L[n−1]\), finds a gap in the list.

We wrote here the gap function as pseudocode, try coding it in Python:

Use the following skeleton and add some test. To understand what’s going on, try copy-pasting in Python tutor

CAREFUL ABOUT agap ASSUMPTIONS!

The specification of agap assumes the input is always a list of at least two elements, and that the first element is less or equal than the last one. If these conditions are not met, function behaviour could be completely erroneus!

When preconditions are not met, execution could stop because of an error like index out of bounds, or, even worse, we might get back some wrong index as a gap! To prevent misuse of the function, a good idea can be putting a check at the beginning of the agap function. Such check should immediately stop the execution and raise an error if the parameters don’t satisfy the preconditions. One way to do this could be adding some assertion that will make python interrupt execution and throw an error as soon it detects list L is too small or with wrong values * This kind of behaviour is also called fail fast, which is better than returning wrong values! * You can put any condition you want after assert, but ideally they should be fast to execute. * asserts might be better here than raise Exception constructs because asserts can be disabled with a flag passed to the interpreter. So, when you debug you can take advantage of them, and when the code is production quality and supposed to be bug free you can disable all assertions at once to gain in execution speed.

GOOD PRACTICE: Notice we wrote what the helper function is expected to receive as a comment. Writing down specs often helps understanding what the function is supposed to do, and helps users of your code as well!

VII COMMANDMENT: You shall also write on paper!

To get an idea of how agap is working, draw histograms on paper like the following, with different heights at index m:

Notice how at each recursive call, we end up with a histogram that is similar to the inital one, that is, it respects the same preconditions (a list of size \(\geq 2\) where first element is smaller or equal than the last one)

Show solution

def agap_helper(L, i, j):

    if j == i+1:
        return j
    else:
        m = (i+j) // 2
        if L[m] < L[j]:
            return agap_helper(L,m,j)
        else:
            return agap_helper(L,i,m)


def agap(L):

    assert len(L) >= 2
    assert L[0] <= L[len(L)-1]
    return agap_helper(L, 0, len(L) - 1)





# try also to write asserts

def agap_helper(L, i, j):
    raise Exception('TODO IMPLEMENT ME !')

def agap(L):
    raise Exception('TODO IMPLEMENT ME !')




# try also to write asserts

Continue

Go on with divide and conquer strategy