While I have written some problem solving blogs usually it
was directly related to a specific problem encountered in lecture or in
tutorial. I decided I wanted to try and use this knowledge on other problems. I
was really inspired by Albert Xie’s approach to solving the penny pile problem.
He actually went home and wrote a python function that calculated all possible
penny piles transferring from left to right and right to left.
The link for his entry is here:
http://99bugsbutaglitchaintone.blogspot.ca/2014/10/week-7-penny-piles-recursive-solution.html
Given all the extra work he did, I decided to work with Lebo
Radebe on a common google interview question for fun. We found the problem
online and took some time to try and work out a process to solve it. She also
wrote up her experiences with solving the problem. Her slog can be found at the
following link:
http://slog165lr.blogspot.ca/
THE PROBLEM:
Five pirates of five ages have 100 gold coins to split. The
pirates are both greedy and democratic. The oldest one gets to propose how to
split the gold coins and everyone gets to vote on it. If 50% or more agree with
it, that is how they will divide the coins. If not, the oldest pirate gets
thrown overboard and they repeat the process.
THE PROCESS & SOLUTION:
1) Understanding the problem:
Taken
from Danny, I asked myself what the possible inputs would be and what would the
outputs be?
In this respect, I thought about if I was
building a function in python, I would need to know the number of pirates and
need to know how many gold coins are being divided. The output would be the
number of coins each pirate would receive .
What
would they like me to achieve in this problem?
The goal of this problem is to devise a
division of coins that would be acceptable for enough of the five pirates to
vote for it. Right away I know that I don’t have to appease all the pirates, which
I think will be an important consideration later on.
2) Devise a plan:
Given that I have now thought about my
inputs and outputs, I can also think about the extra information that we are
given. Since I know the pirates are greedy and democratic, I would assume they
would try and maximize their potential earnings while still keeping in mind
that they could be outvoted by others.
I also realize that this can be a complex
problem to start with. I think I will start with a smaller number of pirates,
work out how that can be achieved and then move on to a larger group. I will also
want to look at even or odd numbers
The strategy that works for me:
As mentioned above, I know that I like to
work with smaller numbers, consider many different cases and I would also like
to visualize the problem in some sort of diagram or chart.
3) Carry out the plan
The first thing I did was figure out what
would happen with the smallest group possible. Given if there was only two
pirates, I would know that the leader could take as many gold coins as he
wanted and the first pirate would end up with nothing.
Now I add one more pirate to the scenario.
As we are dealing with an odd number of pirates, there has to be at least one
other pirate (other than the leader) who is appeased by the arrangement in
order for the deal to work. As the 2nd oldest pirate knows that if
he doesn’t vote for the arrangement he would be the leader, only by giving him
all of the coins could the leader get his deal passed. In contrast, by only
giving one gold coin to the youngest pirate, it is guaranteed his deal is going
to go through. The youngest pirate would take one coin over nothing and so he
will vote in favour of the third pirate’s proposal.
When adding four pirates it becomes more
complicated. There are two things that should be taken into consideration. We
are told that if a pirate would receive a similar deal if he gets rid of the
leader, he will vote against the leader. Also, we need to remember the deal
that would have been made given three pirates. Thus for four pirates, he cannot give one
to the youngest to get his 50% of the votes, as we know that the youngest will
vote against him given the deal. Furthermore, the 3rd oldest will
vote against him because he knows that if he gets rid of the older pirate he
will get 99 gold coins. Thus, the best solution is to give one gold coin to the
second youngest and keep 99 for himself.
Finally with the fifth pirate, all previous
cases need to be taken into consideration. She knows that she needs to win over
at least two other votes in order to make her deal pass. The second oldest
pirate will never take the deal as he knows by voting her out he can have 99
coins. Additionally, we know that the 2nd youngest pirate will not
take 1 coin as payment because he would get the same deal if the 2nd
oldest was in charge. Thus you would have to give him at least two but you
would still have to buy off someone else to get 50% of the votes. This means giving
away at least three coins. Alternatively, if the oldest pirate gave one gold
coin to the youngest pirate and one gold coin to the third pirate, she would only
lose two gold coins. The two younger pirates would take the deal as if the 2nd
oldest pirate was in charge they would get nothing.
While I wrote out this problem in words, I
used the same logic but Lebo and I worked it out in a table. Here is an image
of the table that we used to figure out the configuration for each number of
pirates.
I was really happy to have Lebo
here to discuss the problem with me. She questioned why I made the decisions I
did and made me look at the problem in a different light. While having only two
or three pirates was simple, once we got to four, we had to discuss why we
thought certain pirates had to have extra coins. Working through it with Lebo
made it more fun but it also made it more challenging (in a good way!)
Overall it was a fun process. I
figured out by creating tables, using smaller cases and by discussing with
someone your process (or by writing it down), you don’t skip over steps. I
think in the future, I will try and write out my process as it helps me catch
my own inconsistencies.
FINAL THOUGHTS:
I just want to end this slog
saying how much I enjoyed this course. Coming in I was not so sure how well I
would do and I really didn’t think I would enjoy the material. I was really
pleasantly surprised. I also am very fortunate to have great lecturers, Danny
and Larry, who both care a lot about their students. I also had an awesome TA
who took time after class to continuously help me. That is a rare thing.
Finally, my classmates have been really insightful and they are an incredible resource.
Learning how other people think through problems has made me evaluate how I
look at problems. I honestly can say that this class has made me a better
student and a more critical thinker.