Recursion challenges

While exporing the inner mysteries of recursion, your quest for knowledge has lead you to unspeakable torments few souls ever dared to challenge.

Start solving them in SimpleFP style, then consider using ModAcc style with possibly Divide and Conquer strategy (where appropriate / feasible).

Challenge - Cthulhu

Given an lst with an even nuber of elements, RETURN a NEW list with the elements from both sides alternated

• DO NOT use slice stepping

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

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

assert cthu([]) == []
assert cthu(['a','b']) == ['a','b']
assert cthu(['x','y','z','w']) == ['x','z','y','w']
assert cthu(['x','y','t','z','w','g']) == ['x','z','y','w','t','g']
assert cthu(['a','b','c','d','e','f','g','h']) == ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']

Challenge - Ghatanothoa

Given a list of characters, RETURN True if all a characters are both preceded and followed by b character(s).

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


result1 = ghat(['a','b','a','b','e','b','a','b'])
print(result1) # True
result2 = ghat(['c','a','b','a','b','a','b'])
print(result2) # False

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

Challenge - Hastur

Given an lst alternating characters and sequences of dashes -, RETURN a NEW list of characters where dashes are replaced by the characters preceding them.

• assume lst never begins with a character which is a dash

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

result = hastur(['a','-','-','-','b','-','-','c','-','-','-','-'])
print(result)  #  ['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'c', 'c']

assert hastur([]) == []
assert hastur(['a']) == ['a']
assert hastur(['a','-']) == ['a','a']
assert hastur(['a','-','b']) == ['a','a','b']
assert hastur(['a','-','-']) == ['a','a','a']
assert hastur(['a','b','-']) == ['a','b','b']
assert hastur(['c','-','-','a']) == ['c','c','c','a']
assert hastur(['c','-','-','-','b','-','a','-']) == ['c','c','c','c','b','b','a','a']
assert hastur(['a','-','-','-','b','-','-','c','-','-','-','-']) == ['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'c', 'c']

Challenge - Tsathoggua

Given a list of characters, RETURN the length of longest sequence of contiguous equal characters

• DO NOT use .count() method

• DO NOT use dictionaries

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

result = tsat(['a','a','a','b','b','c','c','c','c','c','e','e','e','f','f','f','f'])
print(result)  # 5

assert tsat([]) == 0
assert tsat(['a']) == 1
assert tsat(['a','b']) == 1
assert tsat(['a','b','b']) == 2
assert tsat(['a','a','b']) == 2
assert tsat(['a','b','c']) == 1
assert tsat(['c','c','a']) == 2
assert tsat(['c','c','c']) == 3
assert tsat(['c','c','a','a','a','b','b']) == 3
assert tsat(['c','c','a','a','a','a','b','b']) == 4
assert tsat(['d','e','c','c','c','c','c','a','b','b']) == 5
assert tsat(['e','e','e','e','b','b','b','b']) == 4
assert tsat(['g','e','a','b','b','c','c']) == 2

Challenge - Yig

Given lists of numbers la and lb of equal size, RETURN a NEW list with the pairwise greatest numbers

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

result = yig([5,2,7,2,4,8], [9,4,3,5,2,5])
print(result)  # [9,4,7,5,4,8]

assert yig([], []) == []
assert yig([3], [4]) == [4]
assert yig([5], [2]) == [5]
assert yig([0], [0]) == [0]
assert yig([0,4], [7,3]) == [7,4]
assert yig([9,4], [7,8]) == [9,8]
assert yig([5,2,7,2,4,8], [9,4,3,5,2,5]) == [9,4,7,5,4,8]

Challenge - Shub-Niggurath

Given a list la and a list of numbers lb such that the sum(lb) == len(la), RETURN a NEW list of lists in which elements of la are grouped according to the sizes expressed in lb.

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

result = shub([5,9,6,2,3,1,4,7,5,2], [1,4,2,3])
print(result) # [[5],[9,6,2,3],[1,4],[7,5,2]]

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

Challenge - Shoggoth

Given a list of progressively nested lists which ultimately always contain at most two characters, RETURN a NEW list with all the characters

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

result = sho(['s',['h',['o',['g','g'],'o'],'t'],'h'])
print(result)  # ['s','h','o','g','g','o','t','h']

assert sho([]) == []
assert sho(['a','a']) == ['a','a']
assert sho(['a',['b','c'],'d']) == ['a','b','c','d']
assert sho(['a',['b',['z'],'c'],'d']) == ['a','b','z','c','d']
assert sho(['a',['b',['x','y'],'c'],'d']) == ['a','b','x','y','c','d']
assert sho(['a',['b',['x',['y'],'z'],'c'],'d']) == ['a','b','x','y','z','c','d']
assert sho(['s',['h',['o',['g','g'],'o'],'t'],'h']) == ['s','h','o','g','g','o','t','h']

Challenge - Azathoth

Given a list of arbitrarily nested lists which eventually contain strings, RETURN a NEW list of strings

HINT: you need double recursion, both in first element depth and in following elements in the sequence

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

result = aza([[['a']],[['z'],['a'],[['t','h']]],['o','t','h']])
print(result) # ['a','z','a','t','h','o','t','h']

assert aza([]) == []
assert aza(['a']) == ['a']
assert aza([['b']]) == ['b']
assert aza([[['c']]]) == ['c']
assert aza(['x','y']) == ['x','y']
assert aza([['x'],'y']) == ['x','y']
assert aza(['x',['y']]) == ['x','y']
assert aza([['a'],['x']]) == ['a','x']
assert aza([['a'],[['x']]]) == ['a','x']
assert aza(['q','e','d']) == ['q','e','d']
assert aza(['q',['e','d']]) == ['q','e','d']
assert aza([['q','e'],'d']) == ['q','e','d']
assert aza([['q','e','d']]) == ['q','e','d']
assert aza([[['q'],'e',['d']]]) == ['q','e','d']
assert aza([[['a']],[['z'],['a'],[['t','h']]],['o','t','h']]) == ['a','z','a','t','h','o','t','h']

References

• Unaussprechlichen Kulten, by Friedrich von Junzt

• The Pnakotic Manuscripts, unknown authors