Greetings from a fellow Oxonian 🙂
I’ll preface this with the information that I’ve programmed on & off in a number of languages over the years (including hand assembly and some very resource limited systems) – learning Python as a new language rather than learning programming from scratch. So my perspective is probably different to someone new to programming. That said, I’ve never considered myself as a programmer, just an engineer who does some programming as part of the job, and so I’m learning new stuff apart from “just Python”.
At some point in the video, you mentioned that the number of moved required is n^2-1, but didn’t really give any idea where that comes from. When tossing in facts like this (especially to people who could be new to programming), I think you need to at least say where that comes from – in this case, f(1)=1, f(n)=f(n-1) + 1 + f(n-1) or 2f(n-1)+1 where f(n-1) represents recursing back into the function to move n-1 counters. I’m not suggesting that you go into the mathematics, for the purposes of this it’s enough to say that mathematicians can tell you that it equates to f(n)=n^2-1. It goes hand in hand with the idea that the recursive solution invokes the move function twice for n-1 counters, plus moving one counter, to move n counters.
The other issue I think should be mentioned is that while your solution is good for demonstrating the recursive nature of the problem, it is inefficient in terms of computer resources used. I chose to write a move function which took references to a global dictionary containing the stacks – and thus didn’t copy the stacks each time. I’m not suggesting that you present this variation as it would be a bit too much for the target audience – but I do think it’s important to point out (as you did with the 2 sum problem) where there are significant efficiencies to be gained. You did mention this in (IIRC) the Fibonacci section – demonstrating how a recursive solution could quickly exceed available resources.
Unfortunately I think too many programmers these days work on the basis that “computing is cheap” and have no real understanding of efficiency. It’s important to at instil at least a basic appreciation of efficiency in new programmers – I’m hoping this will play a larger part in the search and sort section that’s coming up. My next work project, and one of the reasons for learning Python, could be working with very large datasets. My next home project will be with Arduino which is very resource constrained – something else I’m learning at the same time. In both cases efficiency is important – but at different ends of the scale.
Hi Simon,
thanks for reaching out! I agree with you, that this isn’t the most efficient solution, certainly. You’re also right that this course assumes that people have no prior or little knowledge in Python programming, that’s why the aim is to present simple solutions (in terms of the code required). Nonetheless, I believe our students would be interested to see your solution, as well, so if you’d like you could post it here in the Q & A section.
I believe you’ve brought up an excellent point regarding efficiency. This could be an interesting topic to address if we decide to include an algorithms and data structures course. So far, however, most of courses are aimed at practical examples and challenges and in some of our other courses we do tackle working in Python and larger datasets(though we don’t handle very large datasets exclusively). Hope you’ll find something interesting there, as well.
Best,
365 Eli
I agree, it’s a tough line to draw. At this level it’s probably not necessary to go into efficiency in great detail – but I do believe it’s important to at least mention it, if only to say that “this is the easy to understand way of coding it, but it’s not the most efficient”.
This is my solution.
I use global variables so I never copy/duplicate the stacks, just pass pointers to which stack I am moving to where. It still recursively calls the move stack function, one less counter each time until it gets to one counter.
N.B. I found it really hard work getting this code into the answer box – needed to manually edit the html.
def move_stack(src_stack,dest_stack,num_counter):
# Move num_counters counters from stack src_stack to stack dest_stack
global stacks,move_count
num_counter=int(num_counter)
if num_counter<1:
print("Counters to move must be >= 1")
if (src_stack=="a" and dest_stack=="b") or (src_stack=="b" and dest_stack=="a"):
inter_stack="c"
elif (src_stack=="a" and dest_stack=="c") or (src_stack=="c" and dest_stack=="a"):
inter_stack="b"
elif (src_stack=="b" and dest_stack=="c") or (src_stack=="c" and dest_stack=="b"):
inter_stack="a"
else:
print("Error, source and destination must be in 'a', 'b', 'c'")
return false
if num_counter==1:
# move 1 counter, then we're done
counter=stacks[src_stack].pop()
stacks[dest_stack].append(counter)
move_count+=1
# print(f"Moved counter {counter} from {src_stack} to {dest_stack}, moves={move_count}, {stacks}")
else:
# Move n-1 counters to intermediate stack, move 1 counter to destination, move n-1 counters from intermediate stack to destination
move_stack(src_stack,inter_stack,num_counter-1)
move_stack(src_stack,dest_stack,1)
move_stack(inter_stack,dest_stack,num_counter-1)
def do_hanoi(num_counters):
# Setup and run the problem, num_counters is number of counters to load on first stack
global stacks
global move_count
move_count=0
stacks={"a":[],'b':[],'c':[]}
# Load the initial stack
for i in range(num_counters,0,-1):
stacks['a'].append(i)
move_stack('a','c',num_counters)
print(f"Towers moved in {move_count} moves")
do_hanoi(3)
Oops, I see I’ve made a right blooper there. It’s not n^2-1 moves, it’s 2^n-1 moves