## Teaching

### Assignment 7: Backtracking

#### 19 November, 2022 Due 30 November 6 December, 2022

When we add a number to a depot, it results in a sequence of moves that ends with some value being appended as the last element in a row. Hence, we can start with the last element in each row and try to "undo" the move that brought it there.

For instance, consider the depot

```	1 4 5
2 9
3
```
• If we assume the last move resulted in the 3 in the third row, it must have been pushed there because 2 displaced it from the previous row. This 2 must have come from the first row, where it must have been displaced by 1. So the last move consisted of inserting 1 into the depot
```	2 4 5
3 9
```
• If we assume the last move resulted in the 9 at the end of the second row, it must have been pushed there because 5 displaced it from the first row. So the last move consisted of inserting 5 into the depot
```	1 4 9
2
3
```
• If the last move resulted in the 5 at the end of the first row, the last move consisted of inserting 5 into the depot
```	1 4
2 9
3
```

We can then repeat this analysis to extract the number inserted at the second last step etc, so we reconstruct the original input sequences in reverse order.

Notice that any legal depot will have each row in ascending order and no row can be longer than the row above it.

Submit your solution via Moodle, as a Jupyter notebook, with explanatory comments.