FIT1045/53 Algorithmic Problem Solving – Workshop 10.
Objectives
The objectives of this workshop are:
• To understand the uses of stacks.
• To practice using backtracking to solve problems.
MARKS: You must follow all restrictions outlined to receive any marks. Assuming restrictions are followed,
marks for this workshop will be determined by the tester.
Preparation
Revise backtracking and stacks, as discussed in the lectures.
Task 0
Download test files and create Python file
Name Python file FIT1045 workshop10.py.
Task 1: Using Stacks

Write a function reduce(stack) that takes as input a stack of integers and returns the length of a reduction
of the stack. To reduce the stack, you may remove pairs of adjacent numbers as they occur (they need not
be adjacent in original list). For example, calling reduce([5,3,4,2,2,4,5]) would return 3 because of the
following operations:
• [5,3,4,2,2,4,5] remove the two 2s
• [5,3,4,4,5] remove the two 4s
• [5,3,5] nothing else can be removed, return the length of the stack
You must only use stack operations in this task (i.e. when manipulating the list, you may use pop() and
append()).
Task 2: Backtracking

In the lectures you were given the following code:
def solutions(completed, options, partial=[]):
#function code from FIT1045 Lecture 17, slide 42
if completed(partial):
return [partial]
else:
res = []
for o in options(partial):
augmented = partial+[o]
res += solutions(completed, options, augmented)
return res
1
def backtracking_task(x):
def options(partial):
...
def completed(partial):
...
return solutions(completed, options, starting_partial)
This code provides a framework for many (although not all) of the backtracking problems you will see in this
unit; however, you may not fully understand everything it does. Ensure you understand what each line of code
is doing before you implement it. Remember, if you use code from the lectures you must cite it. It is sufficient
to include a comment such as #code for < function > adapted from Lecture #, slide #.
Part A - Palindromic Bitlists
Write a function palindrome binary(n) which returns a list of bitlists of length n, where every bitlist is
a palindrome. The returned list of bitlists must be in lexicographical order (think about the order of your
options). You must use backtracking to solve this problem (i.e. do not use brute force).
Part B - All Paths
Write a function all paths(M, u, v) which takes as input an adjacency matrix of a graph, M, and two vertices
u, v and returns a list of all paths from u to v in M. A path is a list of vertices. Note that a path cannot use the
same vertex twice, but two different paths can use some of the same vertices. The returned list of paths must
be in lexicographical order. You must use backtracking to solve this problem (i.e. do not use brute force).
Part C - Stairs
Write a function stairs(staircase) which takes information regarding a staircase, and returns the number of
different ways it is possible to climb the staircase. The function must:
• take a bitlist of length ≥ 2 representing a staircase as input.
• the first and last elements of the staircase are always 1, as they represent the start and finish points.
• elements in staircase that are not the first and last may be 0 or 1, where 0 represents an unsafe stair,
and 1 a safe stair.
• it is possible to climb the staircase by jumping one step, two steps, or three steps; but it is not possible to
jump the same number of steps twice in a row.
Example: calling stairs([1,1,0,1,1]) returns 3 as it is possible to jump start-first-third-final, start-first-
final, or start-third-final. Calling stairs([1,0,1,0,1]) returns 0 as it is not possible to climb the staircase,
given the restrictions.
You must use backtracking to solve this problem (i.e. do not use brute force).
[Extension] Task 3: Converting Numbers
Write a function convert(a, b, c) which takes three positive integers, a, b, and c, and returns the fewest
number of operations needed to convert a to b. There are three permitted operations:
• a -= 1
• a -= 2
• a *= c
Example: calling convert(3,20,2) returns 4 as a can be converted to b using the following (minimum) series
of operations :
• a = a*2
• a = a-1
2
• a = a*2
• a = a*2 thus, a == 20 == b
This problem can be solved using backtracking. However, you will find that if you try to use the backtracking
framework given to you in lectures, you will always get a stack-overflow error (think about why this might be
by drawing out the trace tree). You will need to come up with a different way of utilising the strengths of
backtracking.
3