We had our third week of practice last night. Approximately 10 people were there, so the numbers are staying consistent. I’m hoping that we’ll have about 15 for the competition on the 31st.
Ian Bull showed up at the beginning to talk about the Google Summer of Code project. He participated last year and is possibly mentoring this coming summer. We both thought the club members might be interested in the opportunity.
At the meeting we first went over last weeks problems. I did this rather quickly, so I’m not sure whether everyone followed my discussion. I decided to have a little mini-contest last night. In previous weeks, I’ve been splitting people up into experienced and newbies, where the experienced people work on harder problems, but this week everyone worked on the same set of four problems.
I told everyone that the person that solves the most problems would win a prize. The extravagant prize turned out to be a Snickers bar! I mocked up a scoreboard on the whiteboard to keep track of everything.
Dan Sanders ended up winning with three problems solved. He solved the three in about an hour and fifteen minutes, but was stuck on the last. I eventually told him to move onto solving the problem of the week instead. Unfortunately, most of the other experienced guys either had to come late or leave early, so Dan didn’t have any major challengers. Two others, Tristin and Kevin, solved two problems each, and everyone solved at least one.
The four problems came from a mixture of problems I had used at old contests I ran at UNB.
The first problem was a very simple problem where you need to determine whether a car is speeding or not, based on different speed limit zones and the cars speed through that zone. Everyone solved this one.
The second problem was a card game simulation called “Beat the Devil”. It’s not too devilish (sorry, bad pun), but it requires a bit of input processing and logic. You to read in a deck of cards and simulate the logic of the game.
The third problem was a geometry problem. The break down of the problem is that given a bunch of points, you need to find the largest triangle that can be made from the set of points that does not contain any other point. I give the area formula for a triangle in the problem and a hint about how to easily detect if a point is within a triangle. To do that, you can form three triangles between the given point and the vertices of the triangle. If the sum of the area of those three triangles equals the area of the original triangle then the point is within the triangle. There are other tests, like using dot products to see which side the point is relative to the lines of the triangle or using the general point in polygon test.
The last problem was the hardest one. In the problem you have pennies, nickels, and dimes and you want to buy X candies, each of which costs 8 cents. If you put more than 8 cents in, the machine gives you back change using the least number of coins. In the problem, you must buy the X candies using the least number of coins possible.
Initially, the problem looks easy and it looks like you can solve it by using the largest coins first (greedy algorithm), however, this is not necessarily optimal.
For example, if we consider the case of wanting to buy 6 candies where we have 3 pennies, 10 nickels, and 0 dimes, then the greedy algorithm gives us the following answer:
| Pennies | Nickels | Dimes | Candies | Coins used |
| 3 | 10 | 0 | 0 | 0 |
| 5 | 8 | 0 | 1 | 2 |
| 7 | 6 | 0 | 2 | 4 |
| 9 | 4 | 0 | 3 | 6 |
| 11 | 2 | 0 | 4 | 8 |
| 13 | 0 | 0 | 5 | 10 |
| 5 | 10 | 0 | 6 | 18 |
That’s 18 coins used. The optimal only requires 16 coins. In the optimal, we pay for a candy with 3 pennies and a nickel when we can, that way we save a nickel and don’t end up having to use 8 pennies at the end.
| Pennies | Nickels | Dimes | Candies | Coins used |
| 3 | 10 | 0 | 0 | 0 |
| 0 | 9 | 0 | 1 | 4 |
| 2 | 7 | 0 | 2 | 6 |
| 4 | 5 | 0 | 3 | 8 |
| 1 | 4 | 0 | 4 | 12 |
| 3 | 2 | 0 | 5 | 14 |
| 5 | 0 | 0 | 6 | 16 |
This often happens with greedy algorithms, it turns out they are wrong because the locally optimal decisions made don’t necessarily translate to a global optimal.
You have to use dynamic programming to solve this problem. In my solution, I recurse on every way that you can buy a candy using your current coin configuration and store the minimum number of coins used to reach a solution in a table so that I can prevent recalculating answers I calculated earlier.
This is the essence of dynamic programming or memoization. You can cut off recursion branches where you’ve already calculated the solution to a sub-problem. However, it’s not always obvious what the recursion is.
