Week 7

This week we finished proofs and started learning about algorithm analysis and asymptotic notation. In computer science, big O notation is used for classifying algorithms and is one of the most important topics in computer science so I am very excited to learn about this topic. We also looked at a few different sorting algorithms. Another sorting algorithm that I found quite interesting is bogosort. According to Wikipedia, "if bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted." This algorithm has an average time complexity of O((n+1)!).

Penny Piles Puzzle

We were also given another puzzle to solve in class this week.

Given two drawers, with the left containing 64 pennies and the right containing none, can you arrange things so that one of the drawers has 48 pennies using the following operation on the two drawers:

If a drawer has an even number of pennies, you can transfer half of them to the other drawer. If the drawer has an odd number of pennies, you may not perform this operation.

Let's see what the steps you would have to take to get 48 pennies.

(64,0) # Starting off with 64 and 0 pennies

(32,32) # Move half (32) from left to right

(48,16) # Move half (16) from right to left

That was easy enough. Let's try it with an odd number. Say 25. It looks difficult to get from 64 to 25 so lets try working backwards.

(25, 39) # Starting off with 25 and 39

(50, 14) # Try performing the reverse action, double the left drawer

(36, 28) # Since we can't double the left drawer, double the right drawer

(8, 56) # Double the lower number (28) to get 56

(16, 48) # Double the lower number (28) to get 56

(32, 32) # Double the lower number (16) to get 32

(64, 0) # Finally, double the lower number (32) to get 64

So it seems that by working backwards, we can see that the pattern to get to 64 is to double the lower number between the two drawers and take the pennies from the other drawer, and keep performing this until you get back to 64 pennies in a drawer.

The following is my general solution written in Python. It takes two parameters, the first is the starting number of pennies in a drawer, which has to be a power of 2, and the second is the desired number of pennies to end up in a drawer, which has to be between 0 and the first number.

def penny_piles(pennies, number):
    """ (int, int) -> NoneType

    Prints the sequence of moves to get to desired number of pennies.

    Parameters:
    - pennies: the starting number of pennies in one drawer, must be a power of
    2
    - number: the number of pennies to end up with in one drawer
    """
    left = number
    right = pennies - number
    sequence = []

    # Check that the number of pennies is a power of 2
    if not (pennies != 0 and ((pennies & (pennies - 1)) == 0)):
        print("Number of pennies must be a power of 2.")
    elif number > pennies or number < 0:
        print("Number of pennies in one drawer cannot be larger than initial "
              "number of pennies or less than 0.")
    else:
        sequence.append('[' + str(left) + ',' + str(right) + ']')
        while left != pennies and right != pennies:
            if left < right:
                right -= left
                left *= 2
            else:
                left -= right
                right *= 2
            sequence.append('[' + str(left) + ',' + str(right) + ']')

        for step in reversed(sequence):
            print(step)

You can try it out here: http://repl.it/2St/1

This week we received the second assignment and it is all proofs and some of them look difficult so I have some work to do. We also received our Assignment 1 marks back and I got perfect on that so hopefully I can do the same with this assignment. Thanks for reading.