Coding Stories: Combining Coins
As a teacher I think a lot about what is worth teaching. Framing questions, allocating time for discussion, structuring projects, and designing assessments all involve value judgements where I weigh one use of time against another. Time is a limited resource in the classroom and as a teacher I want to make good use of it. How do you decide when a tangential discussion is worth pursuing and when it is time to move on? How do you ensure that the projects you assign are the best path of learning for your students. These days with a global pandemic going on I have been thinking even more about what aspects of my teaching are most valuable. Time on task feels more limited than ever by zoom fatigue, distraction, and challenges with motivation.
One great way to learn how to code is to get hooked on a really good problem. When you get hooked, a few hours may pass and you wonder where the time has gone. Getting excited about good problems, I would argue, is more important for my students than most of the facts I can teach them. Today I am going to tell you the story of one problem that I assigned to my students and how I fell in love with it. Hopefully, I also inspired my students along the way. Perhaps you might get inspired to start your own problem solving journey.
The problem that I assigned is a challenge from the project Euler website a great resource for CS teachers. I chose Project Euler #31. Here is the problem statement.
In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p). It is possible to make £2 in the following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p. How many different ways can £2 be made using any number of coins?
We started off the class working in small groups, trying to sketch a solution strategy for the problem. Then we met back as a whole group to share what we had found. The first thing my students noticed is that the problem has many solutions. Part of what makes it a good puzzle is that there are numerous ways to arrange the coins. We talked about solving the puzzle with physical coins and decided that we would need the following: 200 1p coins, 100 2p coins, 40 5p coins, 20 10p coins, 10 20p coins, 4 50p coins, 2 100p coins, and a single 200p coin.
Notice how we converted the pounds into pence removing one piece of complexity from the problem. We got the quantities by dividing the target value of 200p by the coin values. Since the target value is evenly divisible by each of the coin values, we have already listed eight valid solutions to the problem. All of the remaining solutions can be assembled from this group of coins. In Computer Science one approach to this sort of problem is to use brute force. This means trying every possible combination of coins and then seeing which ones work. This is useful because computers are adept at making a mind boggling number of calculations in a very short time. On the other hand humans struggle with complexity, so I put on my teacher voice and talked to my students about simplifying.
Simplifying a problem is perhaps the most important problem solving strategy you can employ. Our brains are limited in how many things can be thought about at one time. By reducing the complexity or perhaps the number of items in a problem it is easier to mentally manipulate the problem components and play with them in your head. The trick is to find a simpler form that still contains the essential elements of the original problem. The objective is to find a suitable simplification, get some good ideas from the simplified version, and then scale the problem back to its original form.
So I proposed to the class that we solve the case of 5 pence. For this simplification we would only need five 1p coins, two 2p coins and one 5p coin. Eight coins seems much more manageable. Now, how can we get all the possible combinations of coins?
One group of students came up with a solution using 3 nested loops. For 1p we can have 0, 1, 2, 3, 4, or 5 of these. For 2p we can have 0, 1, or 2 of these. For 5p we can have either 0 or 1 of these. This leads to 6x3x2 = 36 possible combinations of coins. Here is the code the students wrote in Python to check all these combinations. They wrote in a conditional statement to count the combinations that added to the goal of 5p. In this case there are four possibilities.
count=0
for i in range(6):
for j in range(3):
for k in range(2):
if i+2*j+5*k == 5: count+=1
print(count)Later I decided to create a p5.js sketch as I find it easier to create visuals in p5.js. Often visuals play an important role in my problem solving process. Notice the empty set symbol representing the absence of coins.
To organize my code for this graphic I decided to define a Coin class in Javascript. The coin class served as a template for each of the coin objects on the screen.
class Coin {
constructor(val, pos){
this.val = val;
this.pos = pos;
}
show() {
fill('#45a632'); // Later I ended up coloring by coin value
ellipse(this.pos.x,this.pos.y,28);
fill(255);
text(this.val,this.pos.x,this.pos.y);
}
}Next I wanted to animate this graphic having the coins fly in one at a time. I can easily adjust the Coin class to make the coins fly in from the left.
// lines added to Coin constructorthis.toPos = pos; // set up fly in
this.pos = createVector(-100,height/2);// new function for Coin classupdate() {
if (this.toPos) {
this.pos.add(this.toPos.copy().sub(this.pos).mult(0.25));
if (this.pos.dist(this.toPos) < 0.5) {
this.pos = this.toPos;
delete this.toPos;
}
}
}
The problem is that I don’t want all the coins to fly in at once but rather one at a time. I spent some time thinking about how to organize my code for this.
Meanwhile as the students were working on solving the problem we decided it would be useful to represent a particular collection of coins in the computer’s memory. One group suggested that we create a list of integers. They explained that if the coin values were given by a list, coins = [1,2,5], then the quantity of each coin could be represented by an integer in the same order. For example, quantities = [1,2,0]. This would have one 1p coin as well as two 2p coins. Here is a visual of the coins.
I realized I could take advantage of this idea in my Javascript code. I decided to implement a Combination class that stored the array of integers and could perform some methods as well.
class Combination {
constructor(target, coinVals) {
this.target = target;
this.coinVals = coinVals
this.amts = new Array(coinVals.length).fill(0);
this.coinIndex = 0; }
nextCombo() { // steps through all possible coin combinations
let position = 0;
while(position<this.coinVals.length) {
this.amts[position]+=1;
if (this.amts[position]*this.coinVals[position]>this.target) {
this.amts[position]=0;
position+=1;
} else return;
}
}
}
The nextCombo() method steps through each combination of coins similar to the way adding one to a decimal number steps through all the combinations of place values. For example if you started at the number 0 and kept adding one you would step through all the possible combinations 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 … 996, 997, 998, 999. Using this simple procedure we have visited all 1000 combinations of a three digit base-10 number. Similarly I can add one pence to my coin combination representation and get all the combinations like this 000, 100, 200, 300, 400, 500, 010, 110 … 321, 421, 521. The maximum value of each of the place values in this representation depends on how many of that coin fit into the target value, in this case 5 pence. I started considering that this works like an odometer and maybe I should create an animation of an odometer for the Combination class. I did not end up finding time to make this animation but I think it would be another fun way to help clarify how my representation works. I am not sure why I put the smallest value coin on the left in opposition to the convention in the decimal system of putting the smallest place value on the right.
Organizing code into classes and developing useful representations helps with problem solving because it is another way of simplifying the problem. By tucking the complexity inside the class definition or the data representation your brain is freed up to tackle other aspects of the problem.
To get the animation to work I also included a nextCoin() method in the Combinations class so that each of the coins for each combination could be returned one at a time and then the nextCombo() method would only be called when all the coins of one combo were returned. To be honest this method is a bit of a mess. If I had time I would clean it up and come up with a more clever way to write it, but for now it at least it works.
nextCoin() {
let i = this.coinIndex
let a = this.amts;
let x = 40 + int(this.combos/12)*300;
let y = 10 + (this.combos%12)*67;
let coin;
if (i < a[0]) {
x+=i*17;
coin = new Coin(1,createVector(x,y),28)
} else if (i - a[0] < a[1]) {
x+=a[0]*17 + (a[0] ? 12 : 0) + (i-a[0])*18
coin = new Coin(2,createVector(x,y),32);
} else if (i - a[0] - a[1] < a[2]) {
x+=a[0]*17+a[1]*18+(a[0] ? 12 : 0) + (a[1] ? 12 : 0)+(i-a[0]-a[1])*22;
coin = new Coin(5,createVector(x,y),36);
} else {
this.nextCombo();
this.coinIndex = 0;
return
}
this.coinIndex++;
return coin;
}Here is the animation
I ended up showing my students the animation and we talked about the problem solving process. Sometimes developing an animation like this leads to important insights. One of the students pointed out that we don’t need to check all 36 combinations. Once a combination exceeds the target value of 5p then we can cleverly skip that combination and possibly a whole series of combinations. For example take the step from 020 to 120 … The next combination should be 220 but that is valued at 6 pence. So I know that it won’t work. By resetting the 1p dial to zero I save myself from checking 320, 420, and 520. So I skip to 030. But that also adds up to 6p so I should reset the 2p dial skipping 130, 230, 330, 430, and 530. That brings us to 001 which is actually the last combination that is valued less than or equal to 5p. In the end this new approach narrows the number of combinations to 12.
Here is the code that I added.
getValue() { // new method in Combination class
let val = 0;
for (let i=0;i<this.coinVals.length;i++) {
val+=this.coinVals[i]*this.amounts[i];
}
return val;
}// replaced the conditional on the nextCombo method.if (this.getValue() > this.target) {
And here is the new animation:
When we started looking more closely at this new animation a student noticed that only one of the solutions actually added to 5p in each of the four regions where the coins were grouped. In fact maybe we don’t need to loop through the 1p coins at all.
“What if we only arranged the 2p and 5p coins and then just added the right number of 1p coins at the end to make it add to 5p.” said one of my students. This was a truly brilliant idea. So here are all the combinations of 2p and 5p coins
0 x 2p + 0 x 5p = 0p … so add 5 1p coins to this one
1 x 2p + 0 x 5p = 2p … so add 3 1p coins to this one
2 x 2p + 0 x 5p = 4p … so add 1 1p coin to this one
0 x 2p + 1 x 5p = 5p … so add 0 1p coins to this one
Based on this insight I rewrote the nextCombo() method to only generate valid solutions. So now for the 5p simplification we will only visit the four valid solutions.
Similarly we can now generate all the solutions for 200p using the same design. When we did we found an answer of 73682.
Then we talked about how we could make the code as efficient as possible to solve the larger problem. One student wrote a set of nested for loops.
count = 0
for a in range(0,201,2): # 2p
for b in range(a,201,5): # 5p
for c in range(b,201,10): # 10p
for d in range(c,201,20): # 20p
for e in range(d,201,50): # 50p
for f in range(e,201,100): # 100p
for g in range(f,201,200): # 200p
count +=1This runs quickly. However, it is not very adaptable. You are stuck with the number of for loops written. That inspired me to come up with a different way to write it.
def solutions(coins,goal,start=0):
if coins==[]: return 1
count=0
for val in range(start,goal+1,coins[0]):
count+=solutions(coins[1:],goal,val)
return countsolutions([1,2,5,10,20,50,100,200],200)
This solution uses recursion whereby a function calls itself and it is easy to adapt to a new set of coins. Another student found an interesting solution online similar to the code below.
coins = [1,2,5,10,20,50,100,200]
def count_solutions(goal):
solutions = [1] + ([0]*goal)
for coin in coins:
for amt in range(coin, goal+1):
solutions[amt] += solutions[amt-coin]
return solutions[goal]This was even more efficient and came up with the same solution. The problem was that we had no idea how it worked. I usually steer my students away from Googling solutions because you learn so much figuring it out yourself. But I was drawn to the elegance of this solution and I wanted to understand it.
We ended up talking through the lines of code as a class. The approach is called dynamic programming. Instead of solving the 200p problem off the bat, we first solve the 0p problem. That is easy as there is only one way to make 0p. Then we solve the 1p problem which also has only one solution. Building up to the 2p solution you can add a 1p coin to the 1p solution or a 2p coin to the 0p solution. This give 2 possible solutions. In this way you can build all the way up to 200p. One important consideration is that 1p followed by 2p is the same solution as 2p followed by 1p. To avoid these duplicates the algorithm only builds solutions in coin value order. At the end the value stored in solutions[200] represents the number of solutions to the problem.
Let’s explore the case of 5p again. First we look at the 1p coin and following the loop the solutions array gets filled with 1’s
solutions = [1,1,1,1,1,1]
There is only one way to make each target value with a 1p coins. Then we can look at the 2p coins solutions. I decided I could visualize this with a p5.js sketch. I represented each coins as a rectangle with rounded corners where the horizontal dimension represents the coin value. We can start by placing a single 2p coin.
solutions = [1,1,2,1,1,1]Now we raise the target to 3 and can add the following solution
solutions = [1,1,2,2,1,1]If you continue the loop you end up with all the following possibilities.
solutions = [1,1,2,2,3,3]Some of the solutions listed don’t add to 5p but they will be used in later goals. Notice how I have added new lines each time there is a unique way to lay out the coins in value order. Finally I used the 5p coin to make 5p.
solutions = [1,1,2,2,3,4]What is special about this approach is that we are not just solving one target value but all the target values and building them up in an elegant way. I turned this process into an animation that I showed the class.
The grey vertical line represents the current target value each row is a distinct sequence of coins in value order. Over time the solutions are built up an the amounts array is shown at the top of the animation. Later in the animation I zoom out to give a greater scope ending on the solution for 19p.
I was quite happy with how this animation turned out. I think it it the most visually pleasing one and it helps me better understand the process of dynamic programming. I am starting to wonder how I can help students think of problems in terms of building up the solutions rather than breaking them down. What I enjoy most about this blog it the interplay of thinking, visualization and working with students. Having the opportunity to do this work on a regular basis makes me a very lucky person. At the start of the post I argued that learning to fall in love with good problems is the most important thing I can teach my students. I would like to amend that. The most important thing I can give them is helping them find their own path to a love of learning. Hopefully sharing my love of Project Euler #31 helped in some small way to make this happen. Below is an expanded visual for 49p
