Cage-fighting for geeks!
At CodeWars teams of programmers complete programming tasks on stage as fast as possible with their laptops connected to projectors. The teams can program in any language, but they can only have one laptop, no network connection and have to deal with commentary and heckling from the audience. Teams code head to head with the winner advancing to the next round. It is all about having fun and programming with alcohol.
Originally based on an idea from the book PeopleWare, CodeWars has been run by RocketBoots in conjunction with the Sydney WebDU conference since 2008. After attending the awesome WebDu CodeWars in May, Dylan Jay and I decided it would be cool to organise a similar event for the python conference in June. A few months later, RocketBoots organised another CodeWars to coincide with Web Directions South and asked us to help out with the questions. Anyone who has attended a Sydney CodeWars knows that the events wouldn’t be the same with out the hilarious and insightful commentary provided by Robin Hilliard from RocketBoots.
There were more than a few requests for the questions and answers for both events to be posted online, so here they are:
PyCon CodeWars 25th June 2010 at Atlassian, pizza by Anchor, beer by Atlassian
1a. Triangles
Print out the names of the following triangles ordered by area. Data is in format x1,y1,x2,y2,x3,y3 and they are all right-angled triangles aligned with the x and y axis’.
Tom 4,5,7,5,4,1 Ben 5,1,2,1,5,4 Jim 1,3,1,1,6,3 Rob 1,0,3,0,3,4
Unfortunately, neither team grasped the significance of being aligned with the x and y axis’. It took over 23 minutes one team eventually solved this, by this time, nearly everyone in the audience had worked out the correct solution on their laptops – we had Anchor T-shirts to give away to the first audience member that completed a question. The easiest way to find the areas of the triangles is to work out the area of their bounding rectangles then divide this by two (because all you have to do is order them by size, you don’t even have to divide by 2). The correct answer is:
Rob, area: 4 Ben, area: 4.5 Jim, area: 5 Tom, area: 6
1b. Julia’s Game
What is the 10,000th prime number?
In honour of Australia’s first female prime minister, who had only been in power for a few days, the teams had to find the 10,000th prime number. If ever you are stuck for a topic of conversation with a programmer, then I can highly recommend using this problem to break the silence. Anyone can come up with a solution, but optimising the solution can get into lots of little intricacies of languages and how to optimise them.
The answer is 104729 but it can take anywhere from a few milliseconds to over 5 minutes to execute.
If you want to know if x is prime, you might have the following pseudo code:
for(y=2; y<x; y++) if(x%y==0) return true return false
If you change the y<x condition to y<√x it can cut the execution time from a few minutes to a few seconds, but √ is normally a very expensive operation so y<(x/y)+1 is much faster. Even calculating √x once is normally more expensive than iterating through the whole for loop with y<(x/y)+1. I have also seen fast solutions that store each prime number in a list and to test if a number is prime, you see if it is divisible by any number in the list. For this solution to be fast you have to know what is the fastest type of list or array to read/write to and also beware that list.length() normally counts each item in the list, which can take some time. The most complex solution I have seen used the fact that every prime number can be expressed as (n*6)±1 where n is an integer. As you can see there is a lot of scope for geeking out on prime numbers.
1c. Numbers
Find the smallest number divisible by 84 and 37 with only one ’2′ and two ’5′s eg. 475524 or 556332
The answer is 59052 and this was solved in three lines of python written in less than 90 seconds by the team that went on to win the competition, the first line of code was pretty awesome:
while (i+=84) :
1d. Points
Which of the following points is furthest from the origin. Data format: x1,y1,x2,y2,x3,y3, …
3,4,-3,-5,3,5,-4,9,9,4,0,7,6,3,-8,6,8,0,5,-4
The correct answer is -8,6
Like most CodeWars questions, importing the data can be the hardest part. For problems like this it can save lots of time if you just copy paste the comma separated string and manually edit it to create something like this:
points = [(3,4),(-3,-5),(3,5),(-4,9),(9,4),(0,7),(6,3),(-8,6),(8,0),(5,-4)]
Both the round 2 questions used the text of Alice in Wonderland supplied on a usb drive. Download this and the other required files here. It is worth noting that every non-python team had been eliminated by this stage.
2a. Down the rabbit hole
Decode the following phrase:
C7731 V5157 V3310 SPACE C5241 V5112 C7494 V5072 SPACE C8390 C5271 V3507 SPACE C3981 V3086 C8863 SPACE C9971 V5292 C659 C5533 SPACE C1898 V1256 V5221 SPACE C10369 C7797 V67 C4157 SPACE V4392 C503 SPACE C1220 V3615 C10924 C852 V3099 C10778 C1164 V3171 C4130 C10534
SPACE = a space
V34 = 34th vowel from Alice in Wonderland
C435 = 435th consonant from Alice in Wonderland
Assume vowels are aeiou and consonants are all other letters, start counting from the first character in the text file.
The answer is “you take the red pill you stay in wonderland”. One team that was using a rather obscure flavour of linux was at a slight disadvantage when they spent the first minute trying to mount the usb drive from the command line.
2b. Aceil
This is a sentence from Alice in Wonderland with the punctuation removed and all of the letters re-ordered alphabetically. Find the original sentence.
Yaaddeeeeeeeghiinnnnnooprrrssstttuuy
Assume a sentence is a series of characters between two ‘!’, ‘?’ or ‘.’
The python-themed answer is “You’re a serpent; and there’s no use denying it.” but we accepted answers without the ‘ and ;
Final Multitap
Decode the following phrase using multitap. Eg 44 33 555 555 666 0 9 666 777 555 is hello world.
444 333 0 999 666 88 0 9 666 777 55 33 3 0 8 44 444 7777 0 666 88 8 0 666 66 0 7 2 7 33 777 0 8 44 33 66 0 999 666 88 0 777 666 222 55
Multitap is the system of entering text on a numeric keypad, so 2 is A and 22 is B – like how we used to text before touch screens came along. Within 30 seconds of this question going up on the screen, an few audience members had worked out the answer just by typing it into their phones, but we decided this was cheating.
The answer is “if you worked this out on paper then you rock” but since mobile phones don’t count as paper, no one rocked.
The team that ended up winning had such a clear division of responsibilities that one team member read out the letters from a phone keypad while another team member typed in the letters and the third checked for typos. In reality, this meant that one of the team members read out the alphabet whilst the other typed it in.
Web Directions South 14 October at Crown Plaza Darling Harbour, bar tab provided by RocketBoots
1a. Stock
Using the ‘daily’ stock prices for Google, find out over how many days did the price increased by 1% or more over the previous day? Assume the difference between rows is 1 day (ignore weekends, holidays).
sample data:
2010-10-11 538.84 2010-10-08 536.35 2010-10-07 530.01 ....
The answer is 457, the only hard part here is realising that the data is in reverse chronological order, if you iterate the wrong way round you get an answer of 381.
1b. To Diff
We’ve been developing a developer’s edition of the Macquarie dictionary, but we’ve lost track of our changes to the list of verbs.The before/after lists are on this USB key. Can you list in alphabetical order:
(1) The list of deleted verbs
(2) The list of additional verbs
Answer:
Deleted – abbreviate, estimate, listerize, ogle, windsurf
Added – scrumulate, enguessulatise, jirate
This problem was made slightly harder by a mistake on the part of the question setting team that was only discovered after 1 of the teams and 3 audience members all got the a different answer than the one we were expecting.
1c. City Zones
Approximating a timezone to be 15 deg wide and with GMT +0 = ±7.5 deg – which timezone has the most capital cities in. No city is on a boundary, GMT +12 and GMT -12 are each 7.5 deg wide. Answer in the form “GMT -9″
sample data:
Afghanistan Kabul 34.31N 069.12E Albania Tirana 41.20N 019.49E Algeria Algiers 36.50N 003.00E ...
Unless you do geocoding on a regular basis, this question is full of areas to trip up. For example, remembering to make all latitude values ending in W are negative. The answer is GMT +1.
1d. Are you smarter than…?
Order the following people by order of smartness.
Data format:
<smart> <less-smart>
(taken from http://www.cs.oswego.edu/~mohammad/contest/f05/Problems.htm)
Einstein Feynmann Feynmann Gell-Mann Gell-Mann Thorne Einstein Lorentz Lorentz Planck Hilbert Noether Poincare Noether
We only had 7 teams signed up so the 7th team was about to advance through this round unchallenged. Luckily the free bar had been going for some time and one audience member was drunk enough to attempt this heat using excel.
So for the first time ever we had bash shell scripts against excel trying to complete a problem that is almost impossible in either language.
The problem is made harder because there is more than one correct answer, we planned to use crowd-sourced validation – if an answer appeared on screen, then the audience had to check that it met all the rules. After 10 minutes one team used a graphing language to generate a graph illustrating “every possible answer” to which the audience responded “feature creep!”, but since the other team still had an almost blank excel spreadsheet it was decided to allow this answer.
For the second round we decided to have a creative round. The teams had to set up their laptops, the problem was displayed up on the centre screen and everyone was given a 5 minute beer break to gather their thoughts before the coding started. After 20 minutes, the teams had to pitch their ideas to the audience and who ever got the loudest applause went through to the final.
2a. In-pipe entertainment
Design an entertainment system for use in a Chilean rescue pod.
At the time of the competition, the Chilean miners were just being rescued in frightening rescue pods. We decided to get the teams to create something to entertain the miners as they made their way to safety.
One team used a linux text to speech library to recite questions and took input in the form of numbers. We were told that this could be easily ported to a simple battery-powered device with a number keypad and a speaker. It only asked one question relating to the infidelity of the miners’ wives. The other team created a web page with a picture of a bonsai tree moving around the page using jquery (because you never know which browser will be available down a mine). We were told that this team planned to implement a feature where a message would pop up telling the miner to calm down when they clicked on the tree. The team did not implement this feature, not because they ran out of time, but because they thought no interaction was a better metaphor for the futility of life. The bonsai tree won.
2b. Newsom lorem
Create a random text generator more awesrom thansum lorem ipsum.
You are only allowed to use files already on your laptops.
One team used a random number generator to select letters from an array, then add some spaces and punctuation. The other team parsed a text file looking for which word followed which and stored this in a list as a set of bigrams. They chose a start word, then looked up the words that followed this in the list of bigrams, chose one of options and then looked which word could follow this word and so on. The heat was one by the bigram team after their amazing pitch where we were told that the multiple spaces that dotted their text, were not errors, but dramatic pauses.
Final ASCII Prisoner
XXXXXXXXXX XXXXXXXXXX XXXX.XXXXX XXXX0XXXXX X XX X . X XX1X56789 X XX XXX X XX234XXX X XXXXXXXX X XXXXXXXX
It takes 9 steps to escape the maze above, how many steps does it take to escape the maze below? There are no ‘decisions’ to make – there is only one way to escape. Replacing white space with X’s and counting white space is NOT allowed.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXX.XXXX XXX XXX XX XXX XXXXXXXXXXXXXXXXXXXX XXX XXXXXXXXXX XXX XX XXX XX XX XXX XX XX XXX XX XXX XX XXXXXXXXXXXXXX XX XXX XX XX XXX XX XXX XX XXXXXXXXXX XX XX XXX XX XX XXX XX XXX XX XXX XX XX XX XXX XX XX XXX XX XXX XX XXX XXX XX XX XX XXX XX XX XXX XX XXX XX XXX XXX XX XX XX XXX XXXXXXXXXX XXX XX XXX XX XXX XX XX XX XXX XXXXX XXX XX XXX XXXXXXXXXX XX XX XX XXXXXXXX XXXXX XXX XX XXX XXX XX XX XXXXXXX XX XXXXX XXX XX XXX XXX XXXXXXXXX XX XX XX XXXXX XXX XX XXX XXX XX XXXXXXX XX XX XXXXX XXXXXXXXXXX XXX XX XX XXXXXXXX XXXXX . XXXXXXXXXX XX XXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
The answer is 145 steps. The easiest solution finds the starting point, replaces that with an X and then finds the only adjacent whitespace, replaces that with an X and so on. Replacing the current location with an X gets rid of the possibility of going back where you came from.
The Sydney CodeWars team is currently planning the 2011 calendar so you better get in training.
