Assignment 1: Problem Solving Example

Unit 1 > Assignment 1 > problem solving

Let's start with some visualization:

Consider these two lists:

A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]

Now consider the first "triple" in A, the triple 1,3,5

A = [1, 3, 5, 7, 9, 11, 13]

How do we systematically try all such triples in A?

The next triple starts at position 1:
```
A = [1, 3, 5, 7, 9, 11, 13]
    
```
The one after that at position 2:
```
A = [1, 3, 5, 7, 9, 11, 13]
    
```
And the last one? At position 4:
```
A = [1, 3, 5, 7, 9, 11, 13]
    
```

So, we could have a for-loop that ranges over all the potential start positions, along the lines of:

    for i in range(0, ?)

What is the last position? We want to do this in terms of the length of the list, since any list is given to the function

Is this correct?

    last_pos = len(A) - 3
    for i in range(0, last_pos):

A1.1 Exercise: Write up the above in my_demo_problem1.py. Test it with different lengths to make sure you print all applicable start positions. Justify your code in your assignment1.pdf.

Assuming you've sorted out the last position, remember that the default start position is 0:
```
    for i in range(last_pos):
    
```
Now let's visualize what happens in the second list with the very first triple of the first list:
```
A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]
    
```
- We'll try this at the first position in the second list:
```
A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]
     1, 3, 5
    
```
- Then at the second position in the second list:
```
A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]
        1, 3, 5
    
```
- Then at the third position, and so on.

Since we're doing this for every triple in the first, we will have an inner loop for the second loop:

    last_pos = ...
    for i in range(last_pos):
        last_pos_second = ...
        for j in range(last_pos_second):
            # compare the triple at i with the triple in j

How do we compare the triple beginning at i in the first list against the triple beginning at j in the second list?

For example, consider i=2, j=1

A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]

We know that 5 occurs at i, 7 occurs at i+1, 9 occurs at i+2.
What about 5, 7, 9, in the second list?
5 occurs at j, 7 occurs at j+1, 9 occurs at j+2.

Hence we want to compare

    last_pos = ...
    for i in range(last_pos):
        last_pos_second = ...
        for j in range(last_pos_second):
            # compare the triple at i with the triple in j
            # compare A[i] with B[j], A[i+1] and B[j+1], A[i+2] with B[j+2]

All three need to be equal for us to declare that we've found a triple:

    last_pos = ...
    for i in range(last_pos):
        last_pos_second = ...
        for j in range(last_pos_second):
            # compare the triple at i with the triple in j
            if (A[i] == B[j]) and ...
                print('Found ...')

A1.2 Exercise: Complete the other conditions in the if-statement in my_demo_problem2.py. And also complete the print statement.

Finally, we need to account for the case when no such triple is found.

A1.3 Exercise: When do we know for sure that no such triple exists? Explain how you solved the latter issue (no such triple found) in assignment1.pdf. Complete the whole program in my_demo_problem3.py by including the above ideas in the code needed for the function search_sublist():

def search_sublist(X, Y):
    # Determine whether and where a 3-element sub-list of X exists in Y.

A = [1, 3, 5, 7, 9, 11, 13]
B = [2, 5, 7, 9, 10, 11]
C = [10, 2, 5, 7, 15, 13]
D = [9, 11, 13, 14, 15]

# This should print: Found: at i=2 in X and j=1 in Y
search_sublist(A, B)

# This should print: No 3-element sublist found
search_sublist(A, C)

# This should print: Found: at i=4 in X and j=0 in Y
search_sublist(A, D)