Understanding the Problem:
*Note: The original problem given on the worksheet in class
has been generalized here for some initial condition (n, m), where n represents
the number of pennies in the left drawer and m represents the number of pennies
in the right drawer.
Here is some notation that will be used in our solution
below:
(x, y) = a configuration with x number of pennies in the
left drawer and y number of pennies in the right drawer
(n, m) = the initial condition
“0” = operation L
“1” = operation R
“0101…” = some sequence of operations L and R
Given some initial condition (n, m), for the number of
pennies in the left and right drawers respectively, the problem is to determine
whether a certain new configuration (x, y) is achievable given only two possible
operations:
·
L: transfer half of the pennies in the left
drawer to the right drawer only if the left has an even number of pennies
·
R: transfer half of the pennies in the right
drawer to the left drawer only if the right has an even number of pennies.
Moreover, we would also like to determine all possible configurations for the
number of pennies in each drawer given some initial condition (n, m) as well as the sequence of steps required to achieve each new configuration.
Of course, the set of new configurations depends on the
initial condition. For example, if n and
m were two odd numbers then there would be no other possible configurations.
To break this down, our input would be some ordered pair (n,
m) and our output would be all possible new ordered pairs (x, y) that can be
achieved by operations L and R above.
The sequence of operations needed to achieve each new configuration should
also be included in our output.
Devising a Plan:
This problem falls under the category of a binary tree
problem similar to what is currently being taught in another programming course. Since there are only two possible operations,
then each node (representing a specific configuration) of the tree has at most
two subtrees. The leaves of the tree
represent the configurations where no further operations can be
performed. To simplify the solution
further, we can say that the leaves also encompass the configurations that have
been previously identified from exploring some other part of the tree. These two
types of configurations provide our stopping conditions or “base cases” for a
possible recursive solution.
Here is a small diagram showing that the tree will look
like.
Our plan here is to develop a recursive python function that
computes and prints all possible configurations given some initial condition
input.
Each configuration and its sequence of operations will be
stored in a python dictionary, which is passed into a recursive function along
with the current configuration and current sequence of steps used to arrive at
the current state. During each
iteration, the program checks if any further operation can be performed or
whether the current configuration has been encountered before. If so, then it stops exploring this branch
and passes the information back up the line.
If a new operation can be performed, then the new configuration and new
sequence is stored in the dictionary and we move down the branch.
Eventually, all possible branches (sequence of operations)
will be explored thus giving us all possible configurations for the number of
pennies in each pile.
Carrying Out the Plan:
To carry out this plan I have implemented the python
function penny_piles( ) shown below. The
output of the function can be verified by performing the sequence of operations
on the initial condition. This check can
also be implemented in a separate python function to verify that each output is
correct.
def penny_piles(start, steps = "", poss_piles = None):
""" (tuple of (int, int), str, dict(tuple of (int, int), str) -> None
Prints all possible configurations for two piles of pennies given in
start followed by a binary string showing the sequence of operations
performed on the start condition to obtain the new configuration.
A "0" represents a left operation and a "1" represents a right operation.
left operation = shift half of the pennies in the left to the right if
the left side is even
right operation = shift half of the pennies on the right to the left if
right side is even
>>> penny_piles((0,4))
(0, 4) -
(1, 3) 10
(2, 2) 1
(3, 1) 11
"""
if poss_piles == None:
poss_piles = {}
left = start[0]
right = start[1]
if steps == "" and left % 2 != 0 and right % 2 != 0:
print(start)
return None
if left % 2 != 0 and right % 2 != 0:
return {}
else:
if left % 2 == 0 and left != 0:
new_start = (int(left / 2), int(right + left / 2))
if new_start not in poss_piles:
new_steps = steps + "0"
poss_piles[new_start] = new_steps
poss_piles.update(penny_piles(new_start, new_steps, poss_piles))
if right % 2 == 0 and right != 0:
new_start = (int(left + right / 2), int(right / 2))
if new_start not in poss_piles:
new_steps = steps + "1"
poss_piles[new_start] = new_steps
poss_piles.update(penny_piles(new_start, new_steps, poss_piles))
if steps == "":
poss_piles[start] = "-"
lst_of_keys = list(poss_piles)
lst_of_keys.sort()
for key in lst_of_keys:
print(key, poss_piles[key])
return None
return poss_piles
if __name__ == "__main__":
pass
Looking Back:
This function has been tested and verified for various inputs
including corner cases such as (0, 0) and odd number only values. The results are easily checked by hand or
using another Python function.
This solution can be re-implemented in many other ways
including ones that do not use recursion explicitly, although it does help to
think recursively for this problem. I can say, however, that this function is
efficient in that it does not explore duplicate branches.
Recursion can be used a wide variety of problems where the
problem can be broken down into smaller problems of the same type (e.g. a
linked-list or a family tree). In this
case we had an initial condition and all the sub-configurations of this initial
condition are made up of all the other sub-configurations of each
new-configuration.
