### Programming and Data Structures with Python

Aug–Nov 2022

### Assignment 7: Backtracking

#### 19 November, 2022

Due ~~30 November~~ 6 December, 2022

#### The Task

Your task is to solve the problem *Depot* from the
International Olympiad in Informatics, 2001.

#### Solving the Task

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.