# Diagnostic 3: Week 3 review

## Lists, Sequences, and Dictionaries

### Question 1

Define `if_this_not_that`

, which takes a list of integers `i_list`

, and an
integer `this`

, and for each element in `i_list`

if the element is larger than
`this`

then print the element, otherwise print `that`

.

```
def if_this_not_that(i_list, this):
"""
>>> original_list = [1, 2, 3, 4, 5]
>>> if_this_not_that(original_list, 3)
that
that
that
4
5
"""
"*** YOUR CODE HERE ***"
for elem in i_list:
if elem <= this:
print("that")
else:
print(elem)
```

### Question 2: Group

Write a recursive function that divides an input sequence into a list of smaller sequences that each contain 4 or 5 elements from the original sequence. For example, an input sequence of 14 elements should be divided into sequences of 4, 5, and 5 elements. Use as few 5-element sequences as necessary in the result, and all 5-element sequences should be at the end. Finally, preserve the relative ordering of elements from the original sequence.

*Hint*: You may assume that the input sequence has length at least 12.
Think carefully about how many base cases you need, and what they
should be.

```
def group(seq):
"""Divide a sequence of at least 12 elements into groups of 4 or
5. Groups of 5 will be at the end. Returns a list of sequences, each
corresponding to a group.
>>> group(range(14))
[range(0, 4), range(4, 9), range(9, 14)]
>>> group(list(range(17)))
[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15, 16]]
"""
num = len(seq)
assert num >= 12
"*** YOUR CODE HERE ***"
if num == 12 or num == 13:
return [seq[:4], seq[4:8], seq[8:]]
elif num == 14:
return [seq[:4], seq[4:9], seq[9:]]
elif num == 15:
return [seq[:5], seq[5:10], seq[10:]]
return [seq[:4]] + group(seq[4:])
```

### Question 3: Fill in the blanks

Fill in the blanks for the following lines so that each expression
evaluates to the expected output:

```
>>> apply_to_all(_______, [1, 3, -1, -4, 2])
[1, 1, -1, -1, 1]
>>> keep_if(______, [1, 7, 14, 21, 28, 35, 42])
[1, 14, 28, 42]
>>> reduce(_______, _______, '')
'olleh'
>>> reduce(______, apply_to_all(______, 'nnnnn'), __) + ' batman!'
'nanananana batman!'
```

`apply_to_all(lambda x: x // abs(x), [1, 3, -1, -4, 2])`

`keep_if(lambda x: x // 7 % 2 == 0, [1, 7, 14, 21, 28, 35, 42])`

`reduce(lambda x, y: y + x, 'hello', '')`

`reduce(lambda x, y: x + y, apply_to_all(lambda s: s + 'a', 'nnnnn'), '') + ' batman!'`

### Question 4: Replace All

Given a dictionary `d`

, replace all occurences of `x`

as a value (not a key) with `y`

.

```
def replace_all(d, x, y):
"""
>>> d = {'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
>>> replace_all(d, 3, 'poof')
>>> d == {'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
True
"""
"*** YOUR CODE HERE ***"
for key in d:
if d[key] == x:
d[key] = y
```

## Linked Lists

### Question 5: Filter

Implement a `filter`

function for linked lists. Remember, recursion is your
friend!

```
def filter_link(predicate, r):
""" Returns a link only containing elements in r that satisfy
predicate.
>>> r = link(25, link(5, link(50, link(49, empty)))))
>>> new = filter_link(lambda x : x % 2 == 0, r))
>>> first(new)
50
>>> rest(new) == empty_link
True
"""
"*** YOUR CODE HERE ***"
if r == empty:
return r
elif predicate(first(r)):
return link(first(r), filter_link(predicate, rest(r)))
else:
return filter_link(predicate, rest(r))
```

### Question 6

Write iterative and recursive functions that reverse a given linked list,
producing a new linked list with the elements in reverse order. Use only the
`link`

constructor and `first`

and `rest`

selectors to manipulate linked lists.
(You may write and use helper functions.)

```
def reverse_iterative(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reverse_iterative(primes)
(7, (5, (3, (2, None))))
"""
"*** YOUR CODE HERE ***"
rev_list = empty
while s != empty:
rev_list = link(first(s), rev_list)
s = rest(s)
return rev_list
def reverse_recursive(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reverse_recursive(primes)
(7, (5, (3, (2, None))))
"""
"*** YOUR CODE HERE ***"
return reverse_helper(s, empty)
def reverse_helper(s, tail):
if s == empty:
return tail
return reverse_helper(rest(s), link(first(s), tail))
```