A Hitchhiker's Guide to Hackathons

This summer, I went travelling in Australia and New Zealand, and did some pretty crazy stuff - helicopter rides, bungy jumping, white water rafting, skydiving...it was scary at times, but I survived and loved the adrenaline rush.  I guess our bodies reward us with the adrenaline rush because we're about to do something that looks like it might kill us, and we are happy not just because we stayed alive, but also because we feel like we have achieved something by conquering the fear.

Although not quite as extreme, I had the same feelings of trepidation, excitement, stress and sense of accomplishment when attending a hackathon for the first time.  Last month I went to CodessHack and Hasbro Play/Hack, click on the links to find out more about these events or go to the bottom of this post for a bit more blurb on what they involved and what my team(s) built!

As a hitchhiker's guide to hackathons for the newbs, let's start with the basics...

What is this hackathon business?

It's usually a one or two day event where a large group of people come together, form teams and work on creative projects for a particular theme/brief to try and create something new and exciting in a limited amount of time.  For example, at the Codess hackathon we had to build a web app, mobile app or game to illustrate or visualize the impacts of climate change.  And the Hasbro involved creating a new game or adapting existing ones - it didn't have to be something digital, in fact quite a few people made some pretty cool prototypes out of cardboard!

Do you have to be a programmer to enter?

No - there are some super-serious highly-competitive hackathons out there that are more suited to experienced coders, but the ones I have been to warmly welcomed newbs and it was still possible to make a meaningful contribution to the team.  I helped out with the project management side of things, and you can create a lot of cool looking stuff with minimal programming experience by adapting existing templates to your needs!  With the help excellent documentation for Javascript libraries, HTML5, and other things like Google Charts, Google Maps etc, you can make a nice little web app.  Knowing about the existence of these resources and what is or isn't possible, rather than deep programming knowledge is enough to get you started on your project.

So how do these things work?

The general format is that a theme and a project brief is sent out to participants beforehand - you are encouraged to read a little bit about the background and brainstorm some ideas, but any actual coding doesn't take place until the day of the event.  The hackathon usually kicks off with some mingling, followed by a series of pitches-  this is when people who have a particular idea that they want to work on, are given 1 minute to describe their idea to all the other participants.  After everyone has pitched their ideas, you then go and scope out a team that you might want to join.  Once everyone is in a team, the hacking begins!  Several hours (and coffees) later, the frantic coding ends and each team gives a 3 minute presentation on their idea for the judges to deliberate over.

Hackathon Vital Prep:

Sleep as much as possible the night before - you have a pretty intense day ahead of you

Read the preparatory materials - familiarity with the project brief will save on vital hacking time and give you a better idea of what kind of projects you would like to work on

Tell your loved ones you are going "off the grid" - not only does this sound cool and make out like you are doing some top secret undercover operation, but it also means your boyfriend isn't annoyed when you haven't texted him to say goodnight (even though you aren't actually going to sleep until 4am).

Bring toothpaste and toothbrush (very important due to the vast amounts of sweets and coffee that will be consumed) and spare clothes, sleeping bag, pillow (and if possible, a yoga mat as a mattress) if you are staying overnight.  I felt very apprehensive about staying the night - I decided to do it in the end to try and get the "full hackathon experience" and it was kinda cool!  It was not the most comfortable night's sleep, but I got enough shuteye.  Lots of people did go home for sleep though, and as long as everyone on your team knows that's the plan, then it's totally fine so there's no need to feel pressured into staying overnight!

Come with an open mind, ideas are not necessary.  There will be a LOT of other people pitching their ideas, so if you don't have a fully formed killer app idea in your head, it's fine!  In fact, if you pitch an idea, you should basically try to lead a team and bring it to fruition - this could be a little overwhelming at your first hackathon!

During the Hackathon:

Keep calm! You will be working with people you only just met, people who are passionate about their ideas that might be different to your own, deadlines will creep closer at a seemingly exponential rate, code will fail to compile, your laptop may freeze, you might have to evacuate the building due to someone burning their toast and end up standing outside Tower Bridge in only your pyjamas... Rise above this and remain composed - somehow, things will all work out in the end.

Fantastic Four or Fabulous Five - it seems to me like 4-5 people teams are generally speaking, the optimum sizes.  Two or three-man teams have been really successful at the hackathons I've been to, but you have to have some serious skillz to compensate for reduced manpower.  Teams with more than 5 people can find it hard to agree on things, and it gets increasingly difficult to make sure everyone is on the same page and working towards the same goal as team sizes get larger.

Cool and Simple - a simple idea that serves a specific purpose, pitched in a very cool and jazzy way (e.g. using Moovly instead of Powerpoint!) is better than an idea that aims to meet all aspects of the project brief in one go.

The Demo is your only objective - I think this picture sums it up quite well:

At the end of the day you have 3 minutes to pitch what you have been working on for the past 12 hours.  Therefore the old saying that done is better than perfect really cannot be overemphasised!  It's called a hackathon for a reason. You won't be able to demo a fully functional product and you will not have time to share the trials and tribulations you have gone through.  What you want to show is an exciting-looking prototype that is enough to give people an idea of what the full thing would look like if you had more time to build it.

Chocolate is your friend - Coffee is good, but I find white chocolate mice are best for keeping me going!  How do I avoid crashing after a sugar high? - maintain the consumption of chocolate at an even rate throughout the hackathon and everything will be just fine! (Disclaimer: this does not constitute medical advice).

Best of luck and keep on hacking....  :)

Stuff that I worked on

Check out my github page for the gory details (warning: it might be a bit messy!)

CodessHack: Codess International Women’s Hackathon Oct 2014:  Climate Change Data Challenge for the Nature Conservancy.  Created a web app to visualise the forecasted evolution of rainfall and temperature by country and continent in 10 hours using Python and Google Charts.  Click on this link to see an animated graph - the individual circles are countries, colour coded by continent.

Hasbro Play/Hack: Created a prototype of an online game aimed at girls with Science, Technology, Engineering and Maths themes, using Google Maps API and Kinetic JS.  You can find the github repository here.

Collatz Sequence: Euler 14 Problem Walkthrough in Python

Have you heard the statistic that only 1 in 5 developers is female?  Many people in the world of tech have certainly taken notice of this and there is an abundance of meetups, initiatives, networking groups and email lists to encourage more women to get into coding (I mentioned one called Codebar in a previous blog post).

I went to one of these meetups recently called Pyladies (many thanks to them and Mozilla for organising a lovely evening!) and that's where I came across the problem set that I'm going to tackle in this post (as with previous posts, you can find all my code uploaded at https://github.com/ttz21).

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)

n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13->40->20->10->5->16->8->4->2->1

13: 9

40:8

20:7

It can be seen that this sequence (starting at 13 and finishing at 1) contains

10 terms. Although it has not been proved yet (Collatz Problem), it is thought

that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

In case you are not familiar with Project Euler, it's a series of mathsy programming problem sets which you can work through to help develop your coding skills and this problem is number 14 of Project Euler.  

After talking about the recent Python conference and other very interesting-sounding Python-related meetups, as well as munching through some pizza, we got down to business.  It was pretty obvious that we could solve this thing using the brute force method and go through all the numbers between 1 and 1million to find the answer, but this would not be the most efficient solution by any stretch of the imagination!  Still, we were curious to know how long the brute force method would take...

Solution Attempt #1: Brute Force

The first line of attack is to write code that implements the "if the number is even, do this..., but if it's odd, do that..." rule : 

def use_rule(n):

    if n%2 ==0:

        n /= 2

    else:

        n = 3*n+1

    return n

Simple enough!  And next, we need a process that will keep using this rule until the number collapses (or should I say.. "collatzes"!...ok that was a terrible joke, but jokes about the Collatz sequence are very limited) to 1.  Then finally, we just ask the computer to do this a million times, and keep a track of which number gives us the longest chain.  The parameter highest is the largest number we want to iterate to, and so the range of numbers we calculate over is from 2 to highest+1 (Python's "for" loops start from the first number in range() and goes up to, but not including the second number).

def brute_max_chain(highest):

    max_count=0

    max_value=1

    for i in range (2, highest+1):

        latest = i

        chain_ length =0

        while(latest != 1):

             latest =use_rule(latest)

             chain_ length +=1

        if(chain_ length >max_count):

            max_count=chain_length

            max_value=i

    return (max_value, max_count)

On my embarrassingly old Windows 7 laptop, this brute force method took almost 90 seconds (using Python's time functions as a stopwatch).  Since the meetup, I have gotten my hands on a shiny new 2.8Ghz 16GB RAM Macbook Pro and with this laptop it takes just under 30 seconds!  Who needs to write efficient code when you can just buy a better machine?!

Whichever machine is used to run the code, the answer for the number with the longest Collatz sequence is the same: 837799 (with a chain length of 524 - the way I have calculated the chain lengths is the number of steps taken to get to 2, so the chain length is 1 less than the way the problem description above counts the chain).

Can we improve on this?

Solution Attempt #2: The dictionary method

When trying to think of a way to improve on the brute force method, one route that came immediately to mind was storing information on the chain length for the other numbers we encounter during the chain calculation.  In the problem description, the example given calculates the chain for the number 13, but while we are doing this series of calculations, we are also discovering what the chain length is for 40, 20, 10 etc etc.  Therefore, there is no longer any need to do the Collatz iteration rule over the other numbers that we experience along the way while we are doing the calculations with the number 13.   Similarly, for any future calculations that we do for higher numbers, if their chains ever reach 13, we now know that they are 8 steps away from collapsing to 1 and there is no need to carry on with the iteration.

Those were the thoughts running through my head while trying to improve on the brute force method.  Bear in mind I had not touched Python for quite a few months, having been concentrating on doing C++ pre-course reading for my Masters, and given I was at a Python meetup,  I was trying hard to come up with a "Pythonic" solution.  I vaguely remembered from my Udacity courses that dictionaries are a data structure unique to Python - they are a set of key:value pairs, where the keys are unique and they do pretty much what it says on the tin.  You can look up a key in the dictionary and it returns the value associated with that key.  They are a very nifty, highly intuitive way of storing and fetching data.  

The method I coded using a dictionary is not as clear as it could be, but I shall try to explain my thinking!  We start off with an empty dictionary called known_chains  - this is where we will store numbers (the dictionary keys) and their corresponding chain lengths (values associated with those keys).  

Similarly with the brute force method, we put in a "for" loop that goes from 2 to highest+1.  Remember that each time we use the Collatz rule on a number, we create a chain of numbers and during the process, we also discover the chain length for those numbers.  I have used another dictionary called  new_knowns to track the chain length for the numbers in the current chain, and we can add the new_knowns dictionary to known_chains once the sequence collapses to 1.

Because we now have a dictionary of known_chains, if the Collatz rule leads us to a number for which we already know the chain length (i.e. if latest in known_chains), we can use that knowledge instead of carrying on iterating with the use_rule() function.  Otherwise, if the latest number is not in the dictionary of known_chains, then we carry on using the use_rule() function (and incrementing the chain length values for the numbers in new_knowns) or until we hit 1 or a number that is in known_chains.

def dict_max_chain(highest):

    known_chains = dict()

    max_count=0

    max_value=1

    for i in range(2,highest+1):

        new_knowns=dict()

        latest = i

        while(latest != 1):

            if latest in known_chains:  

                for entry in new_knowns:

                    new_knowns[entry] += known_chains[latest]

                latest=1

            else:

                new_knowns[latest]=0;

                latest =use_rule(latest)

                for entry in new_knowns:

                    new_knowns[entry] += 1

        for entry in new_knowns:

            known_chains[entry] = new_knowns[entry]

            if new_knowns[entry] > max_count:

                max_count= new_knowns[entry]

                max_value = entry

     

    return (max_value, max_count)

For example, let's say we are calculating the chain length for the number 13 for the first time.  An entry is made into the new_knowns dictionary of 13:0 as we start counting.  If we apply the Collatz rule once, we get the number 40 - let's say we have not yet calculated the chain length for 40 - because we have used the rule once, we increment the dictionary value for 13:1 and we also add 40:0 to the new_knowns dictionary.  Next, we apply the rule once more and hit 20 - again, let's say that this is not already in the dictionary of known_chains, and so we enter 20:0 to the new_knowns dictionary while incrementing the values for the previous numbers in the chain (i.e. we now have 13:2 and 40:1).  

This time when we apply the rule (and increment chain length values...i.e..13:3, 40:2 and 20:1), we end up with 10.  This should definitely already be in the dictionary of known_chains (as 13>10) with a corresponding value of 5.  Therefore we add 5 to all the values in the new_knowns dictionary (i.e. 13:8, 40:7, 20:6) and we can end the while loop, as we no longer need to do any calculations relating to the chain that started with the number 13.  All that's left for us to do now is add these new_knowns to the known_chains dictionary and while doing so, check if any of the chain lengths exceed what we currently have recorded as the maximum chain length count.

Phew! That was a long explanation.  Thankfully it didn't take nearly as long for the computer to do this calculation - my Macbook clocked it at just under 5 seconds.  That's an improvement on the brute force method by a factor of 6!  But surely we can do even better...?

Solution Attempt #3: The list method

So Python dictionaries are super easy to use, but it turns out that they tend to be more useful when the keys are unordered, e.g. if you were adding words in no particular order.  For our purposes, we are filling in chain lengths corresponding to the numbers from 2 to 1,000,000  and although we are not discovering chain lengths in numerical order,  numbers do inherently have an order!!! (Unless you are in a black hole or something crazy like that...then you probably wouldn't care that much about the Collatz sequence). 

When you want to store data in an ordered way, we can use a list in Python (sort of like an array in other programming languages).  Instead of starting out with an empty dictionary, you can start out with a list that has 1million entries of the number zero (I've kept the name known_chains in the code below).  That sounds like a pretty long list, but it still uses less memory than a dictionary with a million entries.  The ith entry in the list can then correspond to the chain length for the number i - if the ith entry is zero, we know that we have not yet calculated the chain length and as we discover chain lengths, we can add them to the list using an expression that follows the format: list[i] = chain_length.  

Another reason why the dictionary method is slower and uses up more memory is that it stores chain lengths for numbers greater than 1,000,000.  We are only interested in finding the chain length for numbers below a million, but while calculating a chain, there is no restriction on the size of numbers in the chain.  If we are using a list with a pre-defined size however, we cannot add entries for an index, i that is greater than this pre-defined size (i.e. 1,000,000).  This is why there are extra if conditions in this code that tests whether a number is higher than a million.

The code otherwise works in a very similar way to the dictionary method.  Instead of having a new_chains dictionary, we store the numbers in the current chain in a list called current_chain_numbers.  As we calculate numbers along the chain, we append them to this list and we keep going until we hit 1 or a number that we already know the chain length for.  When that happens, we go through the numbers we have in current_chain_number and add our new knowledge of chain lengths to known_chains, which also depends on the position of each number in the current_chain_number list.

def list_max_chain(highest):

    known_chains = [0]*(highest+1)

    known_chains[2]=1

    max_count=0

    max_value=1

    for i in range(2,highest+1):

        current_chain_numbers = []

        latest = i

        while(latest != 1):

            if latest > highest or known_chains[latest]==0:  

                current_chain_numbers.append(latest)

                latest=use_rule(latest)

            else: 

                for entry in current_chain_numbers:

                    if entry <= highest:

                        known_chains[entry] += known_chains[latest]+(len(current_chain_numbers) - current_chain_numbers.index(entry))

                        if known_chains[entry]>max_count:

                            max_count=known_chains[entry]

                            max_value=entry

                latest=1

     

    return (max_value, max_count)

Let's use the 13 chain again as an example, i.e. currently in the code below i=13, we have an empty list of current_chain_numbers,  known_chains[13] is still at zero and latest has been set to 13.  Therefore in the while statement, we follow the first if branch and append 13 to the current_chain_numbers list and use the Collatz rule on 13.  This means that latest is now set to 40 and we go round the while loop for a second time and again, follow the if branch (assuming known_chains[40]==0), adding 40 to current_chain_numbers and using the Collatz rule to set latest to 20.  Doing this whole process one more time means that current_chain_numbers will become [13, 40, 20] and latest=10.  However, the next time we go through the while statement, let's say we have an entry for known_chains[10] , so we now follow the else branch.  Because all the numbers we have in current_chain_numbers are below a million, we need to add the chain lengths for all of them to known_chains.  current_chain_numbers is a list with 3 entries - the chain length of the first number in the list is going to be known_chains[10]+3, the length for the second number will be known_chains[10]+2 and the length for the third number will be known_chains[10]+1.  Accounting for the number's position in current_chain_numbers is why we add the term: len(current_chain_numbers) - current_chain_numbers.index(entry).

And of course, as we are filling in these new chain lengths, we want to check whether they are higher than what we currently have recorded as the maximum chain length.

Don't ask me why, but Python can interpret lists and do things with lists much faster than with dictionaries.  This method takes around 1.7 seconds, an improvement on the dictionary method by a factor almost 3x!

But bear with me, because we can still shave off a bit more from the clock!

Solution Attempt #4: The recursive method

After writing the list method, I have to admit, I was feeling pretty smug with my sub-2 seconds solution.  However, as with many things, someone else on the internet is bound to have come up with an even better method and that's when I came across the idea of using a recursive way to calculate chain lengths.  Recursion is when a function references itself (sort of like how a Russian doll contains a version of itself, or kind of like how Ryan Gosling and Macaulay Culkin wear tshirts of each other).

Recursion....sort of.
I don't need an excuse to use pictures of Ryan Gosling in my blog anyway!

With a recursive solution, you have to have a base input so that the solution knows when to stop referencing itself.  That's why this problem is perfect for a recursive solution combined with the list method of storing previously discovered chain lengths.  We take a number, n and we keep adding 1 to the chain length (stored at known_chains[n]) and run the recursive_method() function again (after applying the Collatz rule).  We keep doing this until we hit a number whose chain we have already discovered (i.e. where known_chains[n]>0)- that number is our base input that stops the recursion.  

Similarly with the list method, because we have a list of a pre-defined size, we have to make allowances for numbers along the chain to be higher than a million.

highest = 1000000

known_chains = [0] * (highest+1)

known_chains[2] = 1

def recursive_method(n):

    if n < highest:

        if known_chains[n]: #i.e. known_chains[n]!=0

           return known_chains[n]

        elif n%2: #if the number is odd

            known_chains[n] = 1 + recursive_method(3*n + 1)

        else:

            known_chains[n] = 1 + recursive_method(n/2)

        return known_chains[n]

    elif n%2:

        return 1 + recursive_method(3*n + 1)

    else:

        return 1 + recursive_method(n/2)

max_count = 0

max_value = 1

for i in range(2, highest+1):

    chain_length = recursive_method(i)

    if chain_length > max_count:

        max_count = chain_length

        max_value = i

My Macbook Pro can get this solution in just under 1 second, so we've come a long way since the brute force method! There are things you can do to tweak the running time by writing the code a bit more succinctly and I think there are packages you can install to speed up simple calculations like these, but I'm satisfied with the clock stopping at sub 1-second.  And now for a well earned cup of tea...

The Game of Life Solution Walkthrough

Dear blog, it has been an awfully long time since my last post, I hope you are in a forgiving mood.  During the past two months, I have actually been blogging elsewhere, but you will always be my first and most important blog site.  The reason for the absence is that in mid-July I started my one-year sabbatical from my finance job in order to do my Computer Science Masters (see my Back To School post from March) and I used the summer to go travelling in Singapore, Australia and New Zealand.  I used this blog as a photo diary of my adventures so that my parents could check that I was still alive.

Maybe I should have done a career change to become a beach bum instead....

While on my travels, I really lived life on the edge - I went on helicopters, mountain and glacier hikes, caving, white water rafting, scuba diving, bungy jumping and sky diving, but throughout my trip my laptop and university pre-course reading were never far away.  The textbook I have been working through is called Problem Solving with C++ by Walter Savitch...many people I met on my trip thought it was weird that I had brought work with me, but I had some looooong coach journeys to sit through and so far I have enjoyed working through the "homework" problems at the end of each chapter.

This blog post is a walkthrough of my solution to one of these problem sets, and what better way to resurrect my blog than with an article about the Game of Life.  Before we get into the meat of the solution, I just want to spend a bit of time comparing and contrasting C++ with Python (the programming language I had previously had most experience with).  When people who have some programming knowledge ask me what language my Masters course will use, they generally make the following face, when I tell them it will be taught in C++:

People then go on to say things like "If you can do it in C++, you can do it in any language".  I'm not sure how C++ acquired this formidable reputation, but so far, I have to say that Python was definitely easier to learn and seems to be more flexible.  As you will see with my C++ solution to the Game of Life, at the top of the code, there are some header statements  - when you are a newb you just have to accept this as given and not get too bogged down with the details of why they are there.  Also, with C++, when you use variables in your program, you have to define the variable's type in advance (e.g. whether it will be an integer, or a character etc), whereas Python sort of allows variable types to be defined as and when they are created.  Similarly, when you want to run programs you have written in C++, they must be compiled first (compiling just means the computer checks through the code you have written in your editor and converts into code that your machine can understand), but again, Python cobbles it all together while the program is being run.  The compilation stage is often useful as it brings up any errors before your program is being executed, and you do get a super satisfying feeling whenever your program compiles correctly the first time!

Ok, I've used this meme before - forgive me, I'm a Futurama fanatic

Most of the time, it doesn't compile and for me, more often than not, it's because of these darn semicolons you have to put at the end of every statement in C++!  After being used to coding in Python, it takes a while to get used to them...  My final gripe with C++ is Microsoft Visual Studio Express - ok, so it's not really related to the language itself, but this is possibly one of the least intuitive and most beginner-unfriendly development environments EVER!  Thankfully a new Macbook Pro is on its way to me and I will hopefully never have to deal with Visual Studio again!

Another way to illustrate the differences between Python and C++ is the different philosophies behind the two languages.  The bullet points below are taken from Wikipedia, and I think the way they are written gives you a real feel of the conceptual differences between them as well as an idea of what it is like to code with them.

Python:

• Beautiful is better than ugly
• Explicit is better than implicit
• Simple is better than complex
• Complex is better than complicated
• Readability counts

C++:

• It must be driven by actual problems and its features should be useful immediately in real world programs.
• Every feature should be implementable (with a reasonably obvious way to do so).
• Programmers should be free to pick their own programming style, and that style should be fully supported by C++.
• Allowing a useful feature is more important than preventing every possible misuse of C++.
• It should provide facilities for organising programs into well-defined separate parts, and provide facilities for combining separately developed parts.
• No implicit violations of the type system (but allow explicit violations that have been explicitly asked for by the programmer).
• Make user created types have equal support and performance to built in types.
• Any features that you do not use you do not pay for (e.g. in performance).
• There should be no language beneath C++ (except assembly language).
• C++ should work alongside other pre-existing programming languages, rather than being part of its own separate and incompatible programming environment.
• If what the programmer wants to do is unknown, allow the programmer to specify (provide manual control).

This all sounds like a big rant against C++, but as with all new things, I've learnt to adapt and get used to it, so there really is no bad feeling between me and C++.  Also, I'm sure it has many advantages over other languages that I'm yet to understand, but hope to discover during my Masters course!

Phew! That was a long detour, but now we've gotten that out of the way, let's get onto the meat of the Game of Life solution! The following description is taken from Chapter 7,  Programming Project 13 of the Savitch textbook and you can also read a more detailed and very interesting Wikipedia article (complete with cool gif animations!):

The mathematician John Horton Conway invented the "Game of Life". Though not a "game" in any traditional sense, it provides interesting behaviour that is specified with only a few rules.  This Project asks you to write a program that allows you to specify and initial configuration.  The program follows the rules of LIFE to show the continuing behaviour of the configuration.

LIFE is an organism that lives in a discrete, two-dimensional world...This world is an array with each cell capable of holding one LIFE cell.  Generations mark the passing of time.  Each generation brings births and deaths to the LIFE community:

• We define each cell to have 8 neighbour cells...(directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left).
• If an occupied cell has 0 or 1 neighours, it dies of loneliness (awwww....). If an occupied cell has more than three neighbours, it dies of overcrowding (anyone who has been on the Central Line will sympathise with this).
• If an empty cell has exactly 3 occupied neighbour cells, there is a birth of a new cell to replace the empty cell (hmm, talk about a love triangle..?! this Conway dude can't have been much of a biologist)
• Births and deaths are instantaneous and occur at the changes of generation.  A cell dying for whatever reason may help cause birth, but a newborn cell cannot resurrect a cell that is dying, nor will a cell's death prevent the death of another, say, by reducing the local population.

So given these rules and a starting pattern of live cells on a two dimensional grid, with every generation the pattern of the live cells evolves.

I have put my code on my github page: https://github.com/ttz21/Game-of-Life

Using the framework for problem solving I outlined in my TicTacToe Solution walkthrough, I'm going to start off with the all-important Step 0: Don't Panic.  So after taking deep breath, let's consider the following....

1. What are the inputs?

That's simple - the initial configuration of live cells on a board.  In my solution I have used a 20 x 20 array, because it roughly suits the default size of the screen that pops up when the code is run.  Of course, we could have also written the program to let the user specify the size of the board.  We can declare the size of this board as a constant right at the beginning, so in future we can easily alter it's size without having to go through the entire code:

const int WIDTH = 20, HEIGHT = 20;  (it's customary to give constants names in uppercase, the const means the program can't alter these variables, and the int declares them as integer variables)

I have used an array of integers to track live (1) versus dead (0) cells, though this could also be accomplished using an array of booleans (true/false).  For this solution, the initial configuration has to be input manually (no, I didn't sit and write out all the curly brackets and "0," x400, I wrote a program that did it for me!) - I have put in a little star pulsar pattern that repeats itself every third generation, to give us something pretty to look at when the program is complete!  The code below declares a two-dimensional array of integers named "board", with HEIGHT+2 rows and WIDTH+2 columns (the reason for the +2 will become clear later...)

int board[HEIGHT + 2][WIDTH + 2] = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};

2. What are the outputs?

We want to display the board to the screen in response to a user prompt (e.g. pressing the Enter key to bring up the next generation).  Rather than showing 1s and 0s, it would be more visually appealing to show asterisks for live cells and just a blank for dead ones.  The function display_board below uses board as an input and uses a nested loop (i.e. loop within a loop) to go through all the rows and columns to print "*" to a screen when the ith row and jth column of the board has an entry of 1.

In C++, when functions are defined, you must declare whether the function returns a value or variable.  The display_board does not return anything, as it simply prints stuff to the user's screen so we declare it as a "void" function.  The "for" loops can be interpreted as: starting with an integer, i at 1, increment i by 1 each time (i++) while i is smaller than HEIGHT+1.  "cout <<" means output the statements that follow to the screen and "endl" simply puts the cursor onto a new line.

void display_board(int board[HEIGHT+2][WIDTH+2])
{

for (int i = 1; i < HEIGHT+1; i++)

{
for (int j = 1; j < WIDTH+1; j++)
{
if (board[i][j] == 1)
cout << "*";
else
cout << " ";
}
cout << endl;
}
}

3. Solve the problem!

To work out what the pattern of the new generation of cells looks like, we need to look at the neighbouring cells of every cell in the current generation.  The problem brief specifies that every cell has 8 neighbours - however, this is not strictly true, because the cells at the very edges of our board will have fewer than 8 neighbours.  In order to get around this, we actually use a 22x22 size board to help us calculate each generation's births and deaths (i.e. giving our 20x20 board a border with the width of 1 cell), but when we are choosing what to display to the user, we only iterate over the inner 20x20 board, and reset the "shell" to dead cells every period (because they technically don't exist and are not part of the game).

We need to know what the previous generation's board looks like in order to calculate the new generation, but after this has been done, we can discard the old board. This means we need to have two boards to work with at one time, as well as a function to copy the board that we use for our calculations onto the board used by the display_board function to show the latest generation.

The new_generation function below takes our board as an input and creates a temporary board of the same size.  This temporary board is then filled with 1s and 0s according to the rules of the Game of Life using the configuration of our input board.  When this has been done, our board with the initial configuration is overwritten with the temporary board using the copy_board function.


void new_generation(int board[HEIGHT + 2][WIDTH + 2])
{
int temp_board[HEIGHT+2][WIDTH+2];
int neighbours;

for (int i = 0; i < HEIGHT+2; i++)
{
for (int j = 0; j < WIDTH + 2; j++)
{
if (i == 0 || j == 0 || i == HEIGHT + 2 || j == WIDTH + 2)
temp_board[i][j] = 0;
else
{
//counting alive neighbouring cells
neighbours = board[i - 1][j - 1] + board[i - 1][j] + board[i - 1][j + 1]
                                   + board[i][j - 1] + board[i][j + 1]
                        + board[i + 1][j - 1] + board[i + 1][j] + board[i + 1][j + 1];
 
if (board[i][j] == 1)
{
if (neighbours < 2 || neighbours > 3)
temp_board[i][j] = 0; //cell dies due to loneliness or overcrowding
else
temp_board[i][j] = 1;  //don't strictly need to write this line, but I have added it for extra clarity
}

else
{
if (neighbours == 3)
temp_board[i][j] = 1; //birth of a new cell
else
temp_board[i][j] = 0;
}
}
}
}

copy_board(temp_board, board);


}

void copy_board(int board1[HEIGHT + 2][WIDTH + 2], int board2[HEIGHT + 2][WIDTH + 2])
{
for (int i = 0; i < HEIGHT + 2; i++)
{
for (int j = 0; j < WIDTH + 2; j++)
{
board2[i][j] = board1[i][j];
}
}
}

Once we have the display_board, new_generation and copy_board functions, all we need to do is implement them in the main function of the program!  The code below has a "while" loop that keeps repeats as long as the user hits the Enter key. The program displays the board, then reads the user's input using the command cin.get(repeat) and then calculates the next generation of LIFE.  cin is like the opposite of cout - it reads in a user's input from the keyboard and we are asking it to "get" one character (which I have called repeat).  '\n' is the way we represent the "Enter" character in C++.

int main()
{
char repeat;

do
{
display_board(board);
cin.get(repeat);
new_generation(board);

}while (repeat == '\n');

return 0;
}

For the initial configuration I entered, the displayed output should look a little something like an asterisk version of this:

Ta da!

I don't want the solution to get too complicated in this blog post, but from the subsequent chapters I have read in my textbook, I could have implemented LIFE as a class and represented the board as a dynamic array.  There are also interesting extensions to this problem to find static displays or cool evolving patterns, but I'll leave that to the mathematicians out there...

Udacity Web Development course

Like many other Londoners, on my daily commute I plug in my earphones and listen to a variety of podcasts in an attempt to block out the what-I-like-to-call "post-apocalyptic nightmare" that is travelling on the London Underground during rush hour (when your transport infrastructure is more than 100 years old, it's always rush hour).  One of my favourite podcasts is TEDTalks, which is a series of short videos of "Ideas worth spreading" and I like it because they cover such a vast range of topics, some are serious, some more entertaining, they do vary in quality, but I always learn something new from watching a TED video (the acronym stands for Technology, Entertainment and Design).

One I watched recently was about what makes a new word officially a word, and one of the examples was "adorkable" (A guy that is a nerd, but in a very cute/adorable way), and this word actually made it into the Collins English Dictionary very recently.  For me, the embodiment of adorkable is Steve Huffman, co-founder of reddit, who is the instructor for a great Web Development course I took this year with Udacity.com.

What is printed in the dictionary, under the definition of "adorkable"

This course requires basic knowledge of Python and is a good follow-on to Udacity's Intro to Computer Science 101 course that I did a few months ago.  The course is focused on building a basic blog website as a web application from the ground up, using Google App Engine to develop and host the site.  You start off by learning some basic HTML, but the majority of the course is not focused on the appearance of the website (i.e. "the front-end"), rather you learn the programming associated with creating and storing new blog posts, displaying these posts, as well as creating user accounts and how cookies work (i.e. "back-end" development).  As a side-project that compliments the main blog-building part of the course, you also learn how to build a website that allows users to submit ASCII art.  You can see my code for both the blog assignment and the ascii art website on my GitHub account.

For your enjoyment, here's a pretty awesome retro-cool example of a simple ASCII art piece:
             

             |\_|\
             | a_a\
             | | "]
         ____| '-\___
        /.----.___.-'\
       //        _    \
      //   .-. (~v~) /|
     |'|  /\:  .--  / \
    // |-/  \_/____/\/~|
   |/  \ |  []_|_|_] \ |
   | \  | \ |___   _\ ]_}
   | |  '-' /   '.'  |
   | |     /    /|:  |
   | |     |   / |:  /\
   | |     /  /  |  /  \
   | |    |  /  /  |    \
   \ |    |/\/  |/|/\    \
    \|\ |\|  |  | / /\/\__\
     \ \| | /   | |__
   snd    / |   |____)
          |_/

I found the course very engaging (not just because of Steve Huffman - he actually wasn't the best lecturer!). Although the set-up was obviously a lot simpler than what is used by "real" websites, understanding how to create user accounts with passwords, logging users in and out, storing and retrieving the blog posts using a database, caching pages etc was really interesting and gives you a basic understanding of how web applications work.  It was also encouraging and inspiring to know that when Steve Huffman co-founded reddit, his experience in web development was about the same as the pre-requisite level of knowledge for this course!

Although overall this is a course that I would thoroughly recommend, and given that it's a totally free resource, I feel bad about complaining, but there were some aspects that I found lacking.  First of all, it was a downright pain installing and running Google App Engine on my Windows laptop - if it wasn't for the advice that was posted on the Udacity forums by other users and answers I found via in-depth googling, I would not have been able to get it to work.  Google App Engine is a platform that you use to write the back-end code for your web application and get it functioning on a real life website. However, Google have now come up with something called Cloud Playground, which looks like it would give you all the functionality of App Engine without having to install anything! This brings me onto my main gripe about this course - it was created a few years ago and the world of web development is evolving so fast that some of the course content is already not as relevant as it could be.

You might be wondering by now why I'm not using the content of the course to host this blog.  As I mentioned earlier, the course focuses almost entirely on the back-end, which means the appearance of the blog that you build with the course leaves a lot to be desired.  To help improve the front end, I went along to a few Codebar sessions to get some expert input.  Codebar is a fantastic (and free!) initiative set up to give free one-on-one coding advice and tutorials to people who are under-represented in the tech industry (i.e. women, ethnic minorities and LGBT).  These sessions take place on a weekly basis around the Silicon Roundabout, where students are paired up with coaches, who are all full-time professional web developers, plus there's free pizza!

FREE PIZZA!!!!!!!!!!

On a serious note, the Codebar organisers and coaches are actually *amazing* and I feel so lucky and grateful I live near to such an incredible and generous resource, that I haven't done anything to deserve!!!

When I rocked up with my  blog web application, no one had heard of  Google App Engine or the template language (Jinja) that was used in the course to build the basic framework of the individual blog pages.  It was also very difficult and frustrating to get the back-end stuff that I had written to work with some of the commonly used "industry standard" templates.  After a while, I also began to realise that I was basically re-inventing the wheel and while I was learning a lot along the way, it would be productive to get to grips with a more widely used set up and learn how to customise that rather than committing to a project where I had built the back end....this is still a work in progress, so, watch this space!

Tic Tac Toe Solution Walkthrough

A couple of blog posts ago, I interviewed my friend Stuart about his new job as an app developer. As part of his interview, he was given a week to program a simple 2-player tic-tac-toe game using a programming language of his choice.  This seems to be a common homework problem for computer programming students and I thought it would be good practice to see if I could write my own version in Python. Here is an example of a tic-tac-toe programming assignment I found from a google search:

You are to implement the two player game of Tic Tac Toe. The program should display the board and prompt each user a move. The program should validate each move and handle any incorrect input. The entire user interaction should be command line based. Upon winning or a draw of the game, an appropriate message should be displayed acknowledging such condition.

Not a valid win.

Through the Computer Science 101 course I did with Udacity.com, there was a very good segment on "How to solve problems" that I've found useful as a framework to tackle programming projects.  At the risk of stating the obvious, the heart of the framework is just pure good old-fashioned common sense, but it's often sooooo tempting to just jump straight into the problem.  By breaking down the solution into steps, you can (hopefully) get to a more efficient and elegant solution, which should save time and frustration later on.

So the most important thing is to start off by heeding the zero-th rule! (this is computer programming after all, and everything begins from 0 rather than 1).  The all important zero-th rule is....

0. DON'T PANIC!  Take a deep breath and keep calm... 

It's actually really funny how many times the instructor reminds us to not panic during the Udacity video lesson on Problem Solving.  Computer Science students must be an anxious bunch.

So after our chill pill, the next thing to do is to make sure we understand the problem - what are the possible inputs and what are the desired outputs.  The solution is getting to a procedure that takes those inputs and maps these to the outputs defined by the job spec.

1. What are the inputs? 

• Which player (X or O) is playing

• The position that the player wants to play 

We need to consider how the inputs are represented -I chose to go with inputs passed in as numerical coordinates (e.g. the user enters the number of the row and column they wish to place their move).  Whenever a program uses user input, we also need to program "defensively", i.e. take into account invalid inputs by the user such as inputting letters instead of numbers or coordinates on the board that don't exist or are already occupied.  

2. What are the outputs?  

• Print out the board after each move

• Return when a game is complete; who won or if there was a stalemate.

3. Solve the problem!  

Working out the relationship between the inputs and outputs is clearly the hardest part (at various points, you may need to remind yourself of step 0). Some good advice is to start off by working out some examples and test cases by hand, consider what could a win looks like? What does a stalemate look like?Everyone has played tic tac toe so I won't bother going through the mechanics of the game here. Once you think systematically about how a human would play the game, we can come up with some "pseudocode" for our solution (i.e. an algorithm that describes the processes you want your code to run).  The aim of this is to get down a draft of an idea for the solution and see if it makes sense.

Pseudocode:

• Decide which player is going first

• Ask for that player's first move and check if it's legal (e.g. that it's on a 3x3 board, and in an empty space)

• Has a win or a stalemate occurred?

• If not, it's the next player's go

• Keep going til we get to a win or stalemate

Once you get to a process of a sensible-looking solution that you're happy with, the next part is to decide which part of the code to write first.  In general, the advice is to write the simple cases first and worry about special cases at a later date - don't optimise too early.  Write small bits of code, test them and understand fully what they do before adding to it.  Obviously it depends on the problem in hand, but it's good to make a start and make your code flexible to incorporate potential changes.  I like writing a little welcome message to really get me in the mood!

print "Welcome to Tic Tac Toe, in order to play please enter your row and column numbers between 1 and 3"  

Here is my full code on Github (it is written for a 2player as well as a 1player game where the computer chooses its moves randomly among the available spaces): https://github.com/ttz21/TicTacToe/blob/master/TicTacToe.py

I probably should have commented it a bit better, but below is a little bit more of a step-by-step walkthrough of how I went about solving it (Disclaimer: it's clearly not the only solution and hopefully in future, with a bit more experience I'll have time to revisit this problem and improve it).

So I started out by deciding that I would have the tic tac toe board as an array in the program, and wrote the code that would go through each entry in the array and “print” out the board on the screen:

board = [[" "," "," "],[" "," "," "],[" "," "," "]]

def print_board(board):

    for i in range(0,3):

        print " "+board[i][0]+" : "+board[i][1]+" : "+board[i][2]

        if i<=1:

            print "..........."

Next, I thought about how moves would be recorded to the board array using the raw_input() function, and how to account for invalid inputs from the user (i.e. if something other than a 1,2 or 3 was entered as a co-ordinate value).  The function get_player_input() below asks for either the row or the column coordinate and returns the player’s entry –e.g. get_player_input( “X”, “row”) will ask player X for the row coordinate on their move.  During gameplay, this “helper” function is then used to alternately between player X and O to get their moves and store them in the board array.

def get_player_input(player_name, coordinate):

    correct_input=False

    while(not correct_input):

        value = raw_input("Player "+player_name+", it is your go, enter your desired "+coordinate+": ")

        try:

            value=int(value)

        except ValueError:

            print "That is not a valid input!"

             

        if value>3 or value<1:

            print "Co-ordinate must be a number between 1 and 3"

        else:

            correct_input=True

    return value

Besides inputting invalid numbers as co-ordinates, a player could also enter a co-ordinate that is already filled, so we also need another helper function that checks whether a particular cell is empty and returns either True or False (otherwise known as a boolean).

def valid_cell(board, row_value, col_value):

    if(board[row_value-1][col_value-1]==" "):

        return True

    else:

        return False

This can then be combined with the get_player_input() function in order to write the user’s input to the board and then display the board on the screen:

def check_player_input(player_name):

    valid=False

    while(not valid):

        row_value = get_player_input(player_name,"row")

        col_value = get_player_input(player_name,"col")

        if(valid_cell(board, row_value, col_value)):

            board[row_value-1][col_value-1]=player_name

            print_board(board)

            valid=True

        else:

            print "That cell is already taken!"

                      

After these steps, it was time to write what a win looks like in tic tac toe.  The function below returns a Boolean (True/False) by first checking whether a player has filled the cells diagonally and then loops through the rows and columns to check for horizontal and vertical wins.

def check_for_win(board, player_name):

    if (board[0][0]==board[1][1]==board[2][2]==player_name):

        return True

    if (board[0][2]==board[1][1]==board[2][0]==player_name):

        return True

    for i in range(0,3):

        if(board[i][0]==board[i][1]==board[i][2]==player_name):

            return True

        if(board[0][i]==board[1][i]==board[2][i]==player_name):

            return True

    return False

In addition to a win, the game can also be stopped by a stalemate if the board is full – the function below loops through the entries in the board searching for empty cells.

def board_full(board):

    for i in range(0,3):

        for j in range(0,3):

            if board[i][j]==" ":

                return False

    return True

Finally, we just need to alternate between the players until there is a win or the board is full.  I also added some extra functions to allow players to choose whether X or O would go first, and later on, I put in a computer player that would make moves at random – you can see the code for this on the github link above, but I won’t go into it in detail in this post.

def determine_play_mode():

    mode = raw_input("Would you like a 1 or 2 player game? ")

    return mode

def determine_first_go():

    go= raw_input("Who would like to go first? (X, O, or flip a coin?)")

    if(go.upper()=="X"):

        return["X", "O"]

    elif(go.upper()=="O"):

        return ["O", "X"]

    else:

        if(random.randint(0,1)==0):

            return ["O", "X"]

        else:

            return ["X", "O"]

gameplay = True

num_gos = 0

play_order = determine_first_go()

play_mode = determine_play_mode()

while gameplay:

    if(num_gos%2==0):

        check_player_input(play_order[0])

    else:

        if(play_mode == 2):

            check_player_input(play_order[1])

        else:

            print "Computer thinking..."

            get_AI_input(play_order[1])

    if(check_for_win(board,"X")):

        print "Congratulations Player X, you have won!"

        gameplay=False

    elif(check_for_win(board,"O")):

        print "Congratulations Player O, you have won!"

        gameplay=False

    elif(board_full(board)):

        print "This round was a draw..."

        gameplay=False

    if(not gameplay):

        again = raw_input("Would you like to play again? Enter Y to play again, or any other entry to quit: ")

        if (again.upper()=="Y"):

             gameplay = True

             board = [[" "," "," "],[" "," "," "],[" "," "," "]]

             play_order = determine_first_go()

             play_mode = determine_play_mode()

             num_gos=-1

              

    num_gos=num_gos+1