THE REINSURANCE ACTUARY
  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer

Gaming my office's Cheltenham Sweepstake

31/3/2019

 

​Every year we have an office sweepstake for the Cheltenham horse racing festival. Like most sweepstakes, this one attempts to remove the skill, allowing everyone to take part without necessarily needing to know much about horse racing.

In case you’re not familiar with a Sweepstake, here’s a simple example of how one based on the World Cup might work:
  • Entry costs £5
  • Each player randomly selects a team
  • The player who picked the team that goes on to win, gets all the money
This allows anyone to enter and have an equal chance of winning (the chance is equal prior to drawing, but not equal once the draw has been made), otherwise everyone would just want Spain or Germany, or whichever team is currently considered the favourite.
 
Note that in order for this to work properly, you need to ensure that the team draw is not carried out until everyone who wants to play has put their money in – otherwise you introduce some optionality and people can then decide whether to enter based on the teams that are still left. i.e. if you know that Germany and Spain have already been picked then there is less value in entering the competition.
 
The rules for our Cheltenham sweepstake were as follows:
 
The Rules
 
The festival comprises 7 races a day for 4 days, for a total of 28 races.
 
The sweepstake costs £20 to enter, and the winnings are calculated as follows:
 
3rd place in competition = 10% of pot
2nd place in competition = 20% of pot
1st place in competition = 70% of pot
 
Each participant picks one horse per race each morning. Points are then calculated using the following scoring system:

  • 1st place – 5 x odds
  • 2nd place – 3 x odds
  • 3rd place – 1 x odds
 
A running total is kept throughout the competition, and the winner is determined after the final race.
 
The odds the scoring are based on are set using the odds printed in the Metro Newspaper on the morning of the races.
 
(as an example, for a horse which has odds of 11/2 in the Metro - if the horse then places 1st, if we selected this horse, we would win (1+11/2)*5 = 32.5 points)
 
Initial thoughts
 
Any set of betting odds can be converted to an implied probability of winning, these would be the odds which over the long run would cause you to breakeven if the race were repeated multiple times with each horse winning a proportion equal to its probability of winning.

Because the scoring in our sweepstake is based on the betting odds, using implied probabilities derived from the odds to help select our horses ends up cancelling itself out (which was the intention when designing the rules). The implied probability can be calculated as one over the odds As an aside, the bookie is indifferent to whether this is the correct probability of winning, they structures the odds purely on the ratio of how their customers are betting. They then structure the odds so that they make money on each race, regardless of which horse wins, for an explanation of this, see my post on creating a Dutchbook:
​
​www.lewiswalsh.net/blog/archives/12-2017
 
Here is an example showing how we would calculate the implied probabilities using some made up odds:
 
Picture
​
We can then use the implied probabilities we just calculated to see what would happen if each horse finished in the first three positions. Once we have done this, we can then calculate the Expected Value of betting on each horse:
Picture
We see that the payout varies for each horse, but the EV is the same. This is by design, the intention is that it should not matter which horse you bet on, the sweepstake rules equalise everyone.

So what can we - an actuary who knows nothing much about horse racing - do? I don’t have any special knowledge that would allow me to select a horse which would beat the odds listed in the Metro, we appear to be at an impasse.

I could attempt to build a model of which horse will win, and then select my horse based on that, but unless it proves to be more accurate than the Metro odds, I might as well just pick at random. Furthermore, if I could build such a model, then I could just start betting actual money. This probably shows you what a difficult problem this is! There's no such thing as free money. It would be a cool project to try, and it’s something I’ve been meaning to attempt for a while, but that’s best saved for another day.

Attempt 1 - Metro vs pre-race odds

My first thought was that we can exploit the difference in odds between those published in the Metro in the morning, and the latest odds published closer to the start of the race. It seems reasonable to assume that the odds just before the race should be more accurate than the metro odds. There will have been time for additional information to be included in the more up to date odds, e.g. the weather is worse than expected therefore horse x is expected to be slower than usual. Since the payout will be based on the Metro, we will then be able to maximise our EV by exploiting this differential. 

Our table will end up looking something like this:
​
Picture
 
We see that we have very small variations in the EVs for some of the horses. It looks like according to this analysis Horse 3 would be the best selection as it has the highest EVs for 1st, 2nd, and 3rd. Based on this strategy, we would then go through each race and select the horse with the highest EV.

Is this what I did? No, for a couple of reasons. The biggest issue was that the Metro did not publish odds in the morning for all races, meaning we couldn’t use the Metro, and therefore the rules of the sweepstake were amended to use the official pre-race odds to calculate the payout instead. This meant there was only one set of odds used, and our edge disappeared!
​
Even if we had used this method, there was a more fundamental issue - the margins we ended up with were tiny anyway. The Metro vs pre-race odds did not swing wildly, meaning that even selecting the horse with the highest EV were only marginally better than picking at random.

So, was there an alternative?

Attempt 2 - 2nd and 3rd place odds
​

My next attempt at an exploitative strategy was based on the insight that the payout multiplier for 2nd and 3rd place was based on the odds of the horse coming 1st, rather than the odds of the horse coming 2nd or 3rd.

The expected value of a horse was not quite as I calculated above, it was actually:
$$EV = P(1)*p_1 + P(2)*p_2 + P(3)*p_3$$
Above, we were using the implied probability of the horse coming first as a proxy for the probability it would come second and third. This is not the same, and some betting websites do allow you to bet on whether a horse will come 2nd or 3rd.

For websites that do not allow you to bet directly on this, then we may still be able to calculate it from the odds for whether a horse finishes in the top 2 or 3 places. We just need to subtract out the implied probability of coming 1st from the probability of coming in the top 2, and then subtracting this out from coming top 3 etc.

​I therefore added some more columns to my table above, corresponding to the probability of the horses coming 2nd and 3rd, and then used this to calculate the EV instead.
Picture

We see that the final column, Total EV, now has quite different values for each horse. In this case Horse 15, Seddon has an EV of 11.72. The favourite horse on the other hand - number 7  - only has an EV of 6.2. The intuitive explanation of this is that the probability of Seddon coming first is very low – this is the reflected in the long odds of 67, this then gives us a large multiplier, but the odds of the horse coming second or third are actually relatively less far out – the fact that it is not the favourite actually increases the odds of it coming in a position which is not 1st. But then if does come in 2nd or 3rd, we would still apply the same large multiplier for the odds of it coming 1st. This then gives us our 2nd edge – we can gain a positive EV by focusing.

As a thought experiment, imagine we have a race with three horses – horse A is a clear favourite, horse B is an average horse, and horse C is clearly the weakest. By betting on horse C – the odds of it winning should be very low, so the multiple should be very high, but then this multiple will be applied even if it comes 2nd or 3rd, which is exactly where it is expected to finish.

This therefore suggests our next potential strategy – select horses which maximise our EV using the implied probabilities of the horses coming 2nd, 3rd etc.

So is this what I did? Well kind of....

The issue with this approach is that typically the horses that provide the best EV also have very long odds. In the race analysed above, our horse has an EV of 11.7, but it only has a 7% chance overall of coming in the top 3. In race two for example, the horse with the best EV actually only had a 2.7% chance of coming in the top 3. Since there are only 28 races in total, if each horse we selected only had a 2.7% chance of coming in, then the probability of us getting 0 points overall in the entire competition would then be:
​
$(1-2.7 \%)^{28} = 48 \%$​

So there is roughly a 50% chance we will get 0 points!

Alternatively, if we selected the favourite every time, we could expect it to come top 3 almost every time, and thereby guarantee ourselves points most races, but it also has the lowest EV.

So we have what appears to be a risk vs reward trade off. Pick outsiders and give ourselves the highest EV overall, or pick the favourites thereby reducing our overall EV but also reducing our volatility.

This leads us  neatly to attempt 3 - trying to think about how to maximise our probability of winning the competition rather than simply maximising EV for each race.
​
Attempt 3 - EP curves
​

From the work above, we now have our model of the position each horse will finish in each race – using the 1st, 2nd, and 3rd implied probabilities - and we have the payout for each horse – using the odds of the horse coming 1st. We can then bring our selection of horse and these probabilities together in a summary tab and simulate our daily score stochastically using a Monte Carlo method. To do this we just need to turn the implied probabilities into a CDF, and lookup the value of each position and repeat 10,000 times. The output for this then ends up looking like the following, where the value is the number of points we will for a given race.

Picture

So we see that across this sample of 20 simulations, most days we to end up with 0 points overall, but a few days have very high scores. So far so good!

The next step is to set up an EP table of the following, which looks like the following:

Picture


The EP table gives us the probability of exceeding various scores in the competition based on our horse selections. In this case, we see that there is a 1 in 20 chance of getting 453 points or greater in the day.

This is useful even on its own – when I was deciding which horses to bet on, I simply played around with the selections until I got an EP table I was comfortable with. My reasoning was quite basic – I decided I wanted to maximise the 1 in 20 value. I wanted to give myself something like a 1/4 chance of winning the whole competition and a 3/4 chance of getting very few points. Since there were four days of races, dividing the 1/4 by another 4 suggests we should be looking at maximising the 1 in 20 level (I admit this reasoning was a bit rough, but it seemed to serve its purpose)

The insight here is that the payout structure of the sweepstake is such that coming in the top 3 is all that matters, and in particular coming 1st is disproportionately rewarded. To see this, we can think of the daily selection of horses as attempting to maximise the EV of the overall prize rather than the EV of our overall score - maximising the EV of each race is only a means to this end. So we are actually interested in maximising the following:

$0.7 * P(1st) + 0.2 + P(2nd) + 0.1 * P(3rd)$

Which will largely be dominated by P(1st), given the $0.7$ factor.
​
This is largely the strategy I went for in the end.

Attempt 4 - Game theory?

I’ve brushed over one difficulty above; in order to maximise our prize EV we need to consider not just which strategy we should take, but how this strategy will fare against the strategies that other people will take. If everyone is maximising their 1 in 20 return period then there’s little point us doing exactly the same. Luckily for me, most people were doing little more than picking horses randomly. We could then formalise this assumption, and come up with a numerical solution to the problem above.

To do this, we would simulate our returns for each day across 10,000 simulations as above, but this time we would compare ourselves against a ‘base strategy’ of random selection of horses and we would simulate this base strategy for the approximately 40 people who entered.

Each simulation would then give us a ranking we would finish in the competition, Here is an example of what that would look like:

Picture

​And we could then convert this into an EP table which would look like the following:

Picture

So we see that if we select these horses, we end up having somewhere between a 1 in 10 and a 1 in 5 chance of winning the competition.

Now that we have all of this set up, we can then optimise our horse selection to target a particular return period.

I didn’t actually end up setting up the above for the sweepstake, but I suspect it would have been an improvement on my approach

Attempt 5 - Multiple day?

There is a further refinement we can make to the above. We have so far only really been focusing on maximising our chance of winning by using a fixed strategy throughout the competition. But there is no reason we have to do this. After the first day, we should really be including the current scores of each competitor as part of our calculation of our ranking. i.e. if person 1 had a great day and now has 200 points but we had a bad day and still have 0 points, by accounting for this, the model should automatically increase our volatility i.e. start picking horses with longer odds so as to increase the chance of us catching up. If on the other hand, we had a really good first day and are now in the lead, the model should then automatically reduce our volatility and start selecting the favourites more often to help safely maintain our lead.
​
How did it work in practice?

I ended up placing 2nd, and taking 20% of the prize pot which was great! I was behind for most of the competition but then pulled back on the last day when a 66/1 came in 1st place, and I picked up 330 points off a single race. This may look miraculous, but is exactly how the model is supposed to work. 

Does that have any applicability to gambling generally? Unfortunately not, basically all of the work above is based on exploiting the specific scoring system of the sweepstake. There's no real way of apply this to gambling generally.


Song Lyrics in China Mieville Novels

8/3/2018

 

I just finished reading China Mieville's novel Kraken. It was really cool, it did take me a while to get into Mieville's voice, but once I got into the swing of it I really enjoyed it. Here is the blurb in case you are interested:

"In the Darwin Centre at London’s Natural History Museum, Billy Harrow, a cephalopod specialist, is conducting a tour whose climax is meant to be the Centre’s prize specimen of a rare Architeuthis dux--better known as the Giant Squid. But Billy’s tour takes an unexpected turn when the squid suddenly and impossibly vanishes into thin air."

One of the lines in the book struck me as surprisingly familiar. Here is the quote from the book:

"She flicked through a pad by her bed, where she made notes of various summonings. A spaceape, all writhing tentacles, to stimulate her audio nerve directly? Too much attitude."

After thinking about this for a moment, it clicked that this is a reference to a Burial song called Spaceape (from his self titled album). The line goes:

"Living spaceapes, creatures, covered, smothered in writhing tentacles
Stimulating the audio nerve directly"


I couldn't find any reference online to the inclusion of Burial lyrics in Mieville's novels. Okay I thought, that's a cool a easter egg, but it got my thinking, are there any other song lyrics buried in Mieville's books? And if so, is there any way we can scan them automatically?

Collecting Lyrics

The first step was to get a database of song lyrics which we can use to scan the novels for, Unfortunately there is no easy place to find a database of song lyrics, so I was forced to scrape them from a lyrics site.

I used the following free chrome extension web scraper which is very easy to use, and in my experience very reliable:
webscraper.io/

After about 10 minutes of setting it up, and about an hour of leaving it to run. I had managed to scrape most of Burial's lyrics in to csv files.

I also scraped lyrics by Kode9 and Spaceape so I could see if they were referenced anywhere. It's hard to know which artist I should look for, but both of these have been mentioned by Mieville in interviews.

The web scraping add-in has an easy to use GUI. Here is a screenshot of what it looks like to set it up:
​
Picture

Ebooks in text format


The next step was then to get his ebooks into a format that I could easily analyse. I assumed that I would need them in a csv format, but I actually got away with using .txt in the end. In order to get them into .txt. I used the built-in bulk converter in the following free ebook management program:
calibre-ebook.com/

Here is a screenshot of Calibre. It is also very easy to use, and freely available online.
Picture

Analysing the text

This is now the hardest part of the problem. We have electronic copies of China Mieville's novels in .txt format, and we have a collection of lyrics in .txt format which we would like to compare them against, how can we programmatically analyse whether Mieville references other Burial lyrics in one of his books?

If we simply attempt to match entire strings, then we have the issue that we might miss out on some references due to small changes in word ordering or punctuation. For example, in the example above using Burial's Spaceape, the wording is slightly different and the tenses of some of the words have been changed, therefore looking for an exact match between lyrics and text will probably not work. If on the other hand we don't match complete strings, but just try to match words, then we will be overwhelmed by small words like 'the' and 'a' which will be used multiple times in both Burial's song lyrics, and in China Mieville's novels.

There are two main approaches I came up with.to solve this problem. My first thought was to match individual words, generating a huge list of matches, and then to count the number of uses of each word in Mieville's novels, and then sorting by the words that match but which are also the most uncommon. For example I would imagine that Spaceape is only ever used once in all of Mieville's novels, giving us information about how unusual this word is. Combined with the fact that this word is also used in a Burial lyric, gives us enough information to assume that there is a high probability of a match, at this point we could investigate manually. 

I ultimately didn't go down this road. Instead, I had the idea to try to adapt plagiarism detection software to this problem. When you think about it, the two problems are actually quite similar. Plagiarism detection is about trying to automatically check two documents for similar phrases, without relying on complete matches.

Open Source Plagiarism Detection

I found the following free-to-use program created by Lou Bloomfield of the University of Virginia which is perfect for what I was trying to do.
plagiarism.bloomfieldmedia.com/wordpress/

It compares two sets of files and then creates a side by side hyperlinked comparison, which can be viewed in chrome, highlighting the parts of the documents where a possible match has been detected. There are various settings you can tweak to specify how close of a match you are interested in. 

I have included a screenshot below of the section where the Spaceape line is detected. There were about 500 matches detected when I ran this, but it only took about a minute to scroll through and check up on the ones that looked significant.

​
Picture

Results

Ultimately, this analysis felt like a bit of a failure. These were the only lyrics I could find in all of his novels and while  there is always the chance that I need to expand the number of artists I'm looking at, or refine my detection methods I imagine this is all there is. I still thought the process was quite cool so I thought I'd write up what I had done anyway.

If you have any thoughts, let me know by leaving a comment.

Drinking Game Analysis

3/3/2018

 
When you are playing a drinking game, do you ever catch yourself calculating the probabilities of various events happening? If you are like most people the answer to that is probably "..... um..... no....... why would I ever do that...."

Okay, maybe that's not the kind of thing you think about when playing a drinking game. But I bet you think it would be interesting to know what the odds are anyway? No? Really? Still not that interested? .... Okay... well I find it interesting, so I'm going to write about it anyway. 

Eyes up/Eyes down

I've only played this game a couple of times but it's pretty fun, it requires no equipment, and has quite a lot of drinking. All players sit in a circle, one player calls out "Eye's down" at which point everyone looks down, the same player then says "Eye's up" at which point everyone looks up at a random person in the circle. If the person you are looking at is also looking at you, then you both drink. Pretty simple.

What is the probability that you will drink? Let's denote the event that you have matched someone with $M$. Then:

$$P(M) = \frac{1}{n-1} $$
Where $n$ is the number of players.

To see that this is true, assume that everyone is picking a random person to look at, then it shouldn't matter who you are looking at, that person will always have $n-1$ people to pick from, and therefore a $ \frac{1}{n-1} $ chance of looking at you.

​Of course people in real life tend not to pick a random person to look at, and even if they attempt to pick a random person, people have been shown to be terrible at picking randomly. But for the purposes of this analysis, unless we make this assumption, the only alternative would be to play the game hundreds of times, record how often matches are made, and then make an empirical claim. As fun as it sounds to play this game hundreds of times in a row, it would be better for your health to just assume a uniform spread of guesses.


The fact that you have a $ \frac{1}{n-1} $ chance of getting a match means that the more people are playing the game, the less likely each person is to drink. Does this apply to the group as a whole though? What is the probability that someone in the group drinks? If we had a hundred people playing, then each individual would hardly ever drink. In fact you would expect them to drink once every $99$ goes. But would you expect it to also be unlikely that anyone at all drinks?  I spent about an hour trying to calculate this and didn't get very far.

Calculating through conditional probabilities doesn't seem to help, and I couldn't come up with a decent approach to count the permutations of all the possible ways of selecting pairings for elements in a set, such that there are no 2-cycles. In the end I gave up and just wrote a program to calculate the answer stochastically. Monte Carlo analysis really is such a versatile tool for problems like these. Anytime you can formulate the problem easily, but struggle to come up with an analytical solution, Monte Carlo analysis will probably work.

Here is the table I generated of the probability of someone in the group drinking for a group of size n:
Picture
There is a definite trend here, if we plot the values on the chart it looks pretty clear that out solution converges to $0.6$. No idea why though! I might come back to this problem another time, but if anyone has any thoughts then please let me know.
​
Picture

Odds

So this is not technically a drinking game, but is played quite often by people who are out drinking. The rules for this game are pretty simple, anytime you would like to dare someone to do something you say "odds of you doing this". The dare might be anything, from 'eating a spoon full of chilli powder, downing your drink, or even getting a tattoo (that last one is a real one I heard about from a friend who playing the game while travelling in Eastern Europe). The person you have challenged then gives you a number. They might say $20$, then each of you count down from $3$ and say an integer from $1$ to $20$ (or whatever number they selected). If you both said the same number, then they have to do the dare. Therefore the higher number you pick, the less likely it is that you will have to do the dare. 

What are the odds of you having to do whatever it is you are betting on, based on you selecting the number $n$? This is quite a straightforward problem, the answer is just $\frac{1} {n} $. I was playing this game last week with someone who thought the answer might be $\frac{1} {n^2} $. This would give a very different likelihood of having to do the dare. For example if you selected $20$, then you would have a $5 \%$ chance of having to do the dare, but according to my friend's calculation he thought you would have $0.25 \%$ chance of doing the dare.

Here is a table showing the correct probabilities for various values of $n$.
Picture

Dirty Pint Flip

I wouldn't recommend playing this game to be honest. I played it in uni once, but it's a bit grim. All the players sit in a circle with a central pint glass in the middle, the players take it in turn to pour any amount of their own drink into the central pint glass as they would like, they then have to flip a coin and guess whether it will be heads or tails. If they get it right, then the game moves on to the person to their left, if they get it wrong, then they have to down the dirty pint. When I played it some people were drinking wine, some people were drinking beer... it was not a good combination.

What is the probability that you will have to drink? This is quite straight forward, it is simply the probability that you will guess the coin flip correctly. Which is just $\frac{1}{2} $.


What about the question of how much you will drink on average? That is, on average if you have to drink, how many people will have poured their drink into the glass before you drink? We can model this as a geometric distribution and calculate the probabilities of each possible number of people. Let's denote the number of people who have poured in before you, given you are about to drink as $N$, then:

$$N \sim Geo(0.5) $$
Giving us the following table:
Picture

The expected value of the number of drinks is then the sumproduct of these two columns . This gives us a value of $2$. Therefore, if you have to drink, the average number of drinks that will have been poured into the pint is $2$.

Two Dice Nominate

This is another game I've only played a couple of times. And I'm not sure if it has a better name than the one I've given it, if you know of one then let me know. In this game, you sit in a circle with a range of drinks on the table, you take it in turns to nominate a person, a drink, and a number between $2$ and $12$. You then roll two dice and add them together. If you have rolled the correct number, the person you nominated drinks the drink you selected, if however you roll a double, then you drink that drink. If it is both a double and you get it correct, then you both have to drink.

The reason that this game does not have much depth to it is that you can always just pick the most likely number to come up when rolling two dice. Here is a table showing the probability of each value coming up:
Picture


Therefore you might as well pick $7$ every single time! Is there anything else we can say about this game? We know that if we roll  a double, then we have to drink the drink. What is the probability of you rolling a double in this game? The probability of this is always just $\frac{1}{6} $. Interesting this is the same probability as rolling the dice such that the sum is $7$. Therefore, if you do pick $7$, there is an equal chance of you and the person you are nominating drinking the drink.
​

Poker - Equity Calculator against a Hand Range

21/2/2018

 

Recently I've been reading The Mathematics of Poker (2009, Bill Chen and Jerrod Ankenman) and I came across an interesting idea that I thought I'd write about. For me, understanding how to analyse this situation really gets to the heart of how I think about poker. I'd love to spend more time playing and studying poker but it's such a time-sink and I don't really have the oodles of free time it would require, but every now and again I'll still open up a poker book and read about something, this is one of those interesting topics I was reading about hopefully you find it as interesting as I do.

Calling a shove pre-flop in heads up

The scenario being analysed in the book is a relatively common situation, particularly in online poker where people are more inclined to shove than in real life games. The question is:

How should we analyse whether to call when we have a moderately strong hand against an opponent who has gone all-in pre flop.

Let's set up an example so that we have something concrete to talk about. Say we have pocket Kings pre flop, and our opponent goes all-in, how should we decide whether to call? Obviously without knowing our opponent's hand there is no 100% correct answer. There is  however one very useful way of analysing the situation.

Equity against a range

We need to ask ourselves - what cards would are opponent go all-in with, and how does my current hand fare against that range? i.e. we need to calculate our equity against our opponent's range. We are adding another layer of stochastic uncertainty on the event, instead of trying to guess what hand our opponent has (which is almost impossible) we are trying to guess what kind of hands he might go all-in with (which is very much possible). We then take this extra level of uncertainty and calculate the correct mathematical way to proceed.

On the one extreme, let's suppose that based on our read of how our opponent is playing, we might think that they would only go all-in with very strong hands, in this case just pocket Aces. We would then be a 4:1 underdog if we call with Ks, and we should definitely fold. (In order to calculate this we could use any standard poker calculator like the following)

www.cardplayer.com/poker-tools/odds-calculator/texas-holdem

One the other hand, suppose we know for a fact that our opponent has not looked at their cards at all but has still decided to go all in. In this case we should definitely call. The only cards we will be behind are pocket Aces, which make up a small fraction of the possible hands that our opponent could shove with, and we will be ahead or equal against all other possible hands. Therefore we would have a positive EV when calling.

What if our read on our opponent's range is somewhere in between though?

What we need to do is calculate our equity against each individual hand in our opponent's range, and then calculate the probability of our opponent having a given hand from that range. That is to say, in order to calculate the conditional expectation, we need to calculate the unconditional expectations against each hand and then multiply by the conditional probability of our opponent having that hand, given our belief about our opponent's range. 

Numerical Example

Let's go back to our numerical example, and suppose that we have pocket Kings, and we put our opponent on either Pocket Aces, Kings, Queens, or Jacks. All of these hands are equally likely, so there is a 25% chance of our opponent having each hand. We can look up our equity against each hand (after you've been playing for a while, you naturally start to memorise hand equities anyway)

Our probability of winning is then:

$$P(A) * P(beating A) + P(K)*P(beating K) + P(Q)*P(beating Q) + P(J) * P(beating J)$$
Putting in our values:

$$ 0.25*0.2 + 0.25*0.5 + 0.25*0.8 + 0.25*0.8 = 0.575.$$

​We therefore see we have a positive expectation against this range, and should call.

No one actually thinks like this in real games?

It is a general misconception that professional poker is a game where players are trying to guess exactly what hand their opponent has, are constantly trying to bluff each other, or trying to pick up on subtle tells or signs that their opponent is or isn't bluffing.

The more mundane truth is that poker is ultimately a game of imperfect information, where the better player is the one who can correctly interpret the betting information their opponent is giving them, and can then quickly and accurately make the kind of judgements described above during a game.

Obviously poker players are not carrying out these calculations in their head to multiple decimal places in real time, what they will do though is review their hands after a game, calculate exactly what they should have done, and try to build up an intuition as to what the correct answer is, so that in the middle of a game they can quickly make decisions.

Software to Analyse this situation

Is there an easy software based method way of calculating our equity against a range? After I did a quick google there are a few programs that offer this type of analysis. For example:

combonator.com/
www.power-equilab.com/

More interestingly though, I also found the following open source software, that can be adapted to carry out this type of analysis:

github.com/zekyll/OMPEval

At some point, I might try to use this code to set up a page on this website to let people analyse this situation.

Myst - Solving the Gear Puzzle

26/1/2018

 


Over the Christmas break, I finally got around to playing some Computer Games, which I unfortunately haven't done in ages. One really fun game (if you're like me and love difficult puzzles) is a game called Myst.
Picture

It was originally released in 1993 as a point and click puzzle adventure game, but it has subsequently been remade, using the Unity engine, as a full 3d interactive game. I really liked the fact that there is no time limit, no danger of dying, just a cool story, interesting puzzles and relaxing music.

One puzzle that I thought was cool involved aligning gear wheels. If you haven't played the game and don't want spoilers, then stop reading now.

The Gear Puzzle

​We are given the contraption in the image below, and are told that we need to end up with the numbers 2,2,1 (reading from top to bottom). We have three levers we can pull, the left lever moves the top two gears left once, the right lever moves the bottom two gears right once. The lever on the back wall resets the machine. The starting values of the gears are 3,3,3. So how many times do we need to pull each lever in order to end up at 2,2,1?
Picture

After playing around with it for a while I began to think that it might not even be possible to get to 2,2,1 using the two levers. Then I thought if that's true, can I prove it as well?

Proof that the puzzle is impossible

Instead of thinking of the value as $3$, let's call it $0$ instead. We can then think of the starting state as a vector:
$$ \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} $$ And we can think of the left lever as adding on the following vector: $$ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} $$ And the right lever as adding the following vector: $$ \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$ We need to work in $mod$ $3$ in order to properly account for the fact that after we go past $3$, we come back to $1$. Then the goal is to produce the state: $$ \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} $$
To see that we are not able to do this with just the basic operations from the starting point we are given, note that the the sum of the first and third elements of our starting vector is equal to the second vector mod $3$, that is, $0 + 0 \equiv 0$ $(mod$ $3)$. For the vector we trying to create, the first and third is not congruent to the second element mod $3$. Instead we have $ 2 + 1 \equiv 0$ $(mod$ $3) $ rather than $2$.

The two operations we are applying to our starting vector preserve this congruence property, as it applies to both the vectors we are adding on as well. Therefore, we can conclude that this property is an invariant of the system, and because our goal does not satisfy this condition, we will never be able to reach:
$$ \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} $$

by just using simple pulls of the lever. We need to realise this in order to force us to look for an alternative way to solve the puzzle. Otherwise we would probably just keep yanking on the levers in the hope that we will eventually get there. Once we realise this and start looking around, we are able to find another way to manipulate the machine, allowing us to make the numbers we need.

Making people smarter by designing a more efficient number system

14/5/2017

 

Designing a new number system

I got interested in alternative number systems when I read Malcolm Gladwell's book Outliers back in uni. You might be surprised that Gladwell would write about this topic, but he actually uses it to attempt to explain why Asian students tend to do so well at maths in the US. I was flicking through an old notebook the other day and I can across my attempt at designing such a system. I thought it might be interesting to write up my system. 

To set the scene, here is the relevant extract from the book:

"Take a look at the following list of numbers: 4,8,5,3,9,7,6. Read them out loud to yourself. Now look away, and spend twenty seconds memorizing that sequence before saying them out loud again.If you speak English, you have about a 50 percent chance of remembering that sequence perfectly If you’re Chinese, though, you’re almost certain to get it right every time. Why is that? Because as human beings we store digits in a memory loop that runs for about two seconds. We most easily memorize whatever we can say or read within that two second span. And Chinese speakers get that list of numbers—4,8,5,3,9,7,6—right every time because—unlike English speakers—their language allows them to fit all those seven numbers into two seconds.

That example comes from Stanislas Dehaene’s book “The Number Sense,” and as Dehaene explains:
Chinese number words are remarkably brief. Most of them can be uttered in less than one-quarter of a second (for instance, 4 is ‘si’ and 7 ‘qi’) Their English equivalents—”four,” “seven”—are longer: pronouncing them takes about one-third of a second. The memory gap between English and Chinese apparently is entirely due to this difference in length. In languages as diverse as Welsh, Arabic, Chinese, English and Hebrew, there is a reproducible correlation between the time required to pronounce numbers in a given language and the memory span of its speakers. In this domain, the prize for efficacy goes to the Cantonese dialect of Chinese, whose brevity grants residents of Hong Kong a rocketing memory span of about 10 digits.

It turns out that there is also a big difference in how number-naming systems in Western and Asian languages are constructed. In English, we say fourteen, sixteen, seventeen, eighteen and nineteen, so one would think that we would also say one-teen, two-teen, and three-teen. But we don’t. We make up a different form: eleven, twelve, thirteen, and fifteen. Similarly, we have forty, and sixty, which sound like what they are. But we also say fifty and thirty and twenty, which sort of sound what they are but not really. And, for that matter, for numbers above twenty, we put the “decade” first and the unit number second: twenty-one, twenty-two. For the teens, though, we do it the other way around. We put the decade second and the unit number first: fourteen, seventeen, eighteen. The number system in English is highly irregular. Not so in China, Japan and Korea. They have a logical counting system. Eleven is ten one. Twelve is ten two. Twenty-four is two ten four, and so on.
That difference means that Asian children learn to count much faster. Four year old Chinese children can count, on average, up to forty. American children, at that age, can only count to fifteen, and don’t reach forty until they’re five: by the age of five, in other words, American children are already a year behind their Asian counterparts in the most fundamental of math skills.

The regularity of their number systems also means that Asian children can perform basic functions—like addition—far more easily. Ask an English seven-year-old to add thirty-seven plus twenty two, in her head, and she has to convert the words to numbers (37 + 22). Only then can she do the math: 2 plus 7 is nine and 30 and 20 is 50, which makes 59. Ask an Asian child to add three-tens-seven and two tens-two, and then the necessary equation is right there, embedded in the sentence. No number translation is necessary: It’s five-tens nine.

“The Asian system is transparent,” says Karen Fuson, a Northwestern University psychologist, who has done much of the research on Asian-Western differences. “I think that it makes the whole attitude toward math different. Instead of being a rote learning thing, there’s a pattern I can figure out. There is an expectation that I can do this. There is an expectation that it’s sensible. For fractions, we say three fifths. The Chinese is literally, ‘out of five parts, take three.’ That’s telling you conceptually what a fraction is. It’s differentiating the denominator and the numerator.”

The much-storied disenchantment with mathematics among western children starts in the third and fourth grade, and Fuson argues that perhaps a part of that disenchantment is due to the fact that math doesn’t seem to make sense; its linguistic structure is clumsy; its basic rules seem arbitrary and complicated.

Asian children, by contrast, don’t face nearly that same sense of bafflement. They can hold more numbers in their head, and do calculations faster, and the way fractions are expressed in their language corresponds exactly to the way a fraction actually is—and maybe that makes them a little more likely to enjoy math, and maybe because they enjoy math a little more they try a little harder and take more math classes and are more willing to do their homework, and on and on, in a kind of virtuous circle.

When it comes to math, in other words, Asians have built-in advantage. . ."

Here's a link to Gladwell's website which contains the extract.
gladwell.com/outliers/rice-paddies-and-math-tests/


Base-10 System

Gladwell mainly talks about the words that the Chinese use for numbers and the structure inherent in them, but there is actually another more interesting way we can embed structure in our number system.

Our current number system is base-10, which means that we have different symbols for all the numbers up to 10 (0,1,2,3,4,...,9), and then when we get to the number 10, we use the first number again but we move it over one place, and then put a zero in it's place. When we are teaching a child how to write numbers, this is exactly how we explain it to them. For example to write two hundred and seven, we would tell them that they need to put a 2 in the hundreds columns a 0 in the tens column and a 7 in the units column - 207.

The fact that we use a base-10 number system is actually just a historical quirk. The only reason humans started to use it is just that we have 10 fingers, there's no particular mathematical benefit to a base-10 system. We could actually base our number system on any integer. The most commonly used alternative is the binary number system used extensively in computing. The binary number system is a base-2 number system where we only have 2 symbols - 0 and 1. The trick is that instead of reusing the first symbol when we get to ten, we do it when we get to two. So the sequence of numbers up to 10 in binary is:

Picture

In fact we don't even need to restrict ourselves to integers as the base of our number system. For example, we could even use base $ \pi $! Under this system if we want to write $ \pi $, then we would just write 1, to write $ \pi^2 $ it would just be 10. Writing one in base $ \pi $ would be quite difficult though, and we would need to either write $ 1 / {\pi} $ or invent a new character.



Base 12 number system

So what would be the ideal number on which to base our number system?

I'm going to make the argument that a base 12 number system would be the best option. 12 has a large number of small factors and this makes it ideal as a base.
  • 12 has almost twice as many prime factors as 10. When working in base 10, it is relatively easy to multiply a number by either 2, 5, or 10, this is because these are all factors of 10. When we are working in base 12, it will be easy to multiply by 2, 3, 4, 6, and 12. Division by these numbers is also much easier. 
  • It is the smallest number divisible by 1,2,3, and 4.
  • We seem to intuitively favour the number 12 in many common circumstances. It has it's own name - a dozen, we also used it to split inches into feet. It's actually the largest integer that has still has it's own name. Once we get to 13, it's just a combination of three and teen, and so on for larger numbers, but eleven and twelve have their own names.
  • We have 12 knuckles on the four fingers of each hand (ignoring thumbs) making counting on our hands easy still.

Returning back to Gladwell's idea, another change we could make to the number system to help make it more structured is to change the actual symbols we use for the integers. Here was my attempt from 2011 for alternative symbols we could use.
Picture

My approach was to embed as much structure into the numbers as possible, so the symbol for three is actually just a combination of the symbols for one and two. This applies for all the numbers other than one, two, four, and eight.

I wonder if it would be possible to come up with some sort of rule about how the symbols rotate to further reduce the total number of symbols and also to add some additional structure to the symbols.

Let me know if you can think of any additional improvements that could be made to our number system.
​

SpaceX - A few random interesting facts about SpaceX

19/4/2017

 

Fact 1 - If Airline Companies were ran like Rocket Companies, a trip from London to New York would cost about $300,000.

Prior to SpaceX, launching a a Satellite into orbit was expensive. Really, really expensive. The most commonly used launch vehicle was the Ariane 5, manufactured by the French Company Arianespace, and costing somewhere in the region of USD75 million per launch. 

SpaceX have stated that their eventual hope is target a cost of USD6 million per launch. How do they hope to achieve a more than 10 times cost reduction?

Better Economies of Scale?
Improved Manufacturing Processes?
Cheap Labour?
3d Printing?

Actually none of the above. The answer is actually kind of obvious once you hear it though. They want to make rockets that can be used more than once!

As a though experiment, let's apply the concept of reusability to a familiar mode of transport. If we take the most common airliner in the world - the Boeing 737 - then we can compare the cost of a flight with full reusability against the cost of the flight without reusability.

A new Boeing 737 costs in the region of USD75 million (depending on the exact model) whereas a return ticket to New York on a Boeing 737 only costs about USD600 per seat.  Multiplying the number of seats (~250) by the cost of a one way ticket (~USD300) we see that the total cost of the flight is somewhere around the USD75,000. So each flight costs about 0.1% of the total cost of the airliner.

Suppose though, that like a rocket, a 737 could only be flown once. Then all of a sudden, instead of costing less than USD75,000 per flight, the flight would include the full cost of the 737, meaning each ticket would cost around USD300,000!

By creating rockets that are reusable, SpaceX hopes to get similar cost savings in the arena of launch vehicles.

SpaceX is actually quite close to achieving full reusability, here is a cool video of a Falcon 9 rocket making a vertical landing on a drone ship in April 2016.


Fact 2 - It is easier to land the rocket on a Drone Ships than the original launch site

In the video above, the Falcon 9 lands on a floating platform in the ocean. Given landing on a ship in the ocean seems to add another layer of complexity to an already difficult task why did SpaceX decide to do this? A few ideas spring to mind, you might think that this is because the rocket is not sufficiently accurate and the drone ship has to be able to move around to get into the right place, or possibly that the ocean is a safer environment to land on given the lack of nearby people or property to damage. Or perhaps SpaceX are doing this as a form of marketing given the fact that it looks pretty cool.

However, the actual reason is surprisingly prosaic, and also, once you think about it, kind of obvious again. It'all has to do with how you get a satellite into orbit in the first place.

​
When a rocket attempts to get a satellite into orbit it does not just go vertically up in the air, in order for a satellite to be in a stable orbit, it actually needs to be moving perpendicular to the earth's surface at a very high speed (which can be calculated based on the height of the orbit) in order to not fall back to earth.


I wrote a model in Python of a two stage rocket launching a satellite into orbit around earth. I then ran the model multiple times keeping the overall thrust of the rocket exactly the same every time, but varying the initial direction of acceleration. Using this model we can see the large effect that varying the path the rocket takes has on the ease in which a satellite can be put into orbit.

In the first video, the launch rocket is sent almost vertically up in the air, and the satellite (the blue part) makes very little progress before it crashes back down to earth.


In the second attempt, we angle the rocket towards the horizon more, in this case, by 55 degrees. And we can see that whilst the satellite does not make it into orbit, it does come closer than the first attempt.


In the final attempt, we angle the rocket at a 45 degree angle to the horizon. Now we see that the satellite does in fact make it into orbit. Note that the only thing we have changed in all these attempts is the angle of launch, the acceleration of the rocket has not been changed at all.


The point to note from all this is that in order to get a satellite into orbit, the rocket that was used to put it into orbit also needs to have a lot of horizontal velocity.

There are quite a few simplifications in our model. For example, we have not included air resistance which will have an impact as in practice there will be a benefit in gaining as much vertical height as possible initially so as to reduce air resistance. The model also does not take account of the fact that the mass of the rocket will reduce as it gets higher due to the fuel expended. However neither of these simplifications effects the the general principle of needing horizontal acceleration.

To tie it back to our original point, from watching the videos you might be able to tell the problem that SpaceX found themselves dealing with when using this approach. The first stage of the rocket ends up miles away from the launch site!

It turns out that for SpaceX, given the location of their launch site, the landing site for these rockets tends to be in the ocean, and this is why that they land the rockets on barges in the ocean.

Fact 3 - ​The floating ships are named after ships in Iain M. Banks novels

SpaceX have two landing barges (also known as Autonomous Spaceport Drone Ships) that they use to land the rockets on. The barges are called 'Just Read The Instructions' and 'Of Course I Still Love You'.

These may seem like very unusual names for SpaceX to pick, unless you spot that they are in fact names of spaceships in Iain M. Banks' Culture series, a series of sci-fi books set in a Utopian future with an interstellar human race.

Python Code

In case anyone is interested, I have pasted the Python code for the two stage rocket model below. My code was partially based on the following model, which simulates the n-body problem in Python. 
fiftyexamples.readthedocs.io/en/latest/gravity.html
import turtle
import math

turtle.color("White")
turtle.sety(100)
turtle.color("Black")
turtle.circle(-100)
turtle.seth(90)
turtle.color("Red")

Vx = 0.3
Vy = 0.3

SecondStage = False

for sec in range(3500):
    CurrentX = turtle.xcor()
    CurrentY = turtle.ycor()
    d = math.sqrt(CurrentX ** 2 + CurrentY ** 2)
    f = 17 / (d ** 2)
    theta = math.atan2(CurrentY, CurrentX)
    fx = math.cos(theta) * f
    fy = math.sin(theta) * f

    Vx += -fx
    Vy += -fy
   
    if turtle.pencolor() == "Red":
        turtle.goto(turtle.xcor() + Vx, turtle.ycor() + Vy)

    if d < 100:
        turtle.color("white")

    if sec == 250:
        SecondStage = True
        New = turtle.Turtle()
        New.color("white")
        NewCurrentX = CurrentX
        NewCurrentY = CurrentY
        New.goto(NewCurrentX,NewCurrentY)
        New.color("blue")
        VNx = Vx + 0.05
        VNy = Vy - 0.2

    if SecondStage == True:
        NewCurrentX = New.xcor()
        NewCurrentY = New.ycor()
        d = math.sqrt(NewCurrentX ** 2 + NewCurrentY ** 2)
        f = 17 / (d ** 2)
        theta = math.atan2(NewCurrentY, NewCurrentX)
        fx = math.cos(theta) * f
        fy = math.sin(theta) * f
        VNx += -fx
        VNy += -fy
        
        New.goto(New.xcor() + VNx, New.ycor() + VNy)

        if d < 100:
            New.color("white")

turtle.exitonclick()

Poker Strategy - Playing with cards up

21/2/2017

 
I've been playing quite a lot of Poker recently, and the more Poker I've played, the more I've come to realise that it's actually a very deep game. One of the interesting features of Poker that makes it so complex is the inability to see each other's cards (this may sound like I'm stating the obvious but bear with me). Let's consider a thought experiment, what if we played Poker against each other without hiding our cards? I show below why it would still be a fairly difficult game to play well. The fact that we also can't see each other's cards  just adds another level of uncertainty to the underlying complexity. 

Incomplete Information
​
In technical terms Poker is a game of incomplete information. An example of a deep game which has complete information is Chess. In Chess we can see all our opponents pieces, and they can see all our pieces. The fact that we have perfect information when playing Chess in no way makes the game trivial.

Heads Up No Limit Texas Holdem

Let's suppose we are playing heads up No limit Holdem (No-limit Texas Holdem is the proper name for the game most people think of when they think of Poker, heads up just means that there are only two of playing). Let's first consider the case where we can't see each other's cards.

Suppose we have J♣6♣, and the flop is 10♣ 9♣ 8♠ there is $£100$ in the pot, we have a stack of $£200$, and our opponent also has a stack of $£200$. Our opponent goes all-in, what should we do?

Obviously there is no 100% correct answer to this question, and if we were playing in real life, we'd have to consider a large number of other variables. How likely do we think our opponent is to bluff? What was the betting pre flop? Do we think we are a better player than our opponent overall, and therefore want to reduce the variance of the game? Are we the two short stacked players in a tournament?

All of the above considerations are what make poker such an interesting game.

Playing with Complete Information

Now let's suppose that we can see our opponent's cards. For example, imagine we are in the same situation as above, but now our opponent shows us his cards, they have 5♥ 5♣. What should we do now?

It turns out in this case, there is actually a mathematically correct way of playing, but it is by no means obvious what that is.

At the moment our opponent has a better hand - they have a pair of 5s, and we do not have anything. What we do have though is the possibility of making a better hand.

We can reason as follows. We will win if one of the following happens:
  • A Queen or 7 of any suit come on the turn or the river.
  • A Club of any value comes on the turn or the river. 
  • Two consecutive Jacks of any suit come on the turn and then the river.
  • Two consecutive 6s of any suit come on the turn and then the river.

We can calculate the probability of one of these happening, and we also know how much we will win if one of them occurs, we can therefore calculate the expected value of calling our opponents all-in.

It turns out that, the probability of us winning this hand if we call is $68.38$%, the probability of there being a split pot if we call is $1.82$%, and the probability of us losing the pot if we call is $29.08$%. In order to see how to calculate this, we note that there are $46$ cards remaining in the deck, and that we can calculate the probability of getting the cards we need for the $4$ way of winning.

Now that we have the probability of winning, we can compare this to the pay off should we win.


Expected Value of calling

The Expected Value is the average amount we would expect to win over a large sample of hands if we make a given decision.

In this case we calculate the expected value as:

$EV = 0.6838 * 300 - 0.2908 *200 = 146.98$

Therefore, over a large enough number of hands, if we are presented with this exact situation repeatedly and we take the average of how much we win or lose, we would expect the amount we win to converge to $£146.98$

The thing about this I find interesting is that when you are playing in real life, even when you can see your opponent's cards, unless you have access to an EV calculator it is still very difficult to determine the correct way to play, and this difficulty is only compounded by the fact that we also can't see our opponent's card.

In order to play Poker well when playing with Incomplete Information, we have to attempt to reason about who has the better cards, whilst bearing in mind this underlying uncertainty which is present even when playing with Complete Information.

Solving a Snake Cube Puzzle

19/12/2016

 
My colleague at work gave me a snake cube puzzle to try to solve, and if you haven't tried, they are a lot harder to solve than they look.

After trying and failing for about 10 minutes to solve the puzzle, I had a great idea, why not waste a couple of hours writing a program to solve it for me? And then a couple of hours turned into a couple more hours, but I got there in the end!

The aim is to wrap the snake into a 3x3x3 cube. Here is what the snake puzzle looks like when it is unwrapped.
Picture

How does the Program work?

There are two main approaches to solving the puzzle programmatically, you could either systematically enumerate all permutations of the snake, or randomly try different permutations until you find one that works.

I went with the second option. which seemed like it would probably be computationally slower, but easier to program.

I decided to write the code in Python, it works by randomly twisting the snake one joint at a time, and restarting everytime the snake either crosses itself or goes outside a 3x3x3 grid.

The code runs 100,000 simulations in approximately 20 seconds on my laptop, which turns out to be just about fast enough to get an answer when you leave the program to run for a couple of hours.

The code:
from random import randint
import time

def f(x):
    return {
        1: 1,
        2: 2,
        11: 0,
        12: 2,
        21: 0,
        22: 1,
    }[x]

def drandomu():
    drandomint = randint(1, 2)
    if drandomint == 1:
        drandomint = -1
    else:
        drandomint = 1
    return drandomint

def drandom(iDirection):
    drandomint1 = f(iDirection * 10 + randint(1, 2))
    return drandomint1

CurrentTime = time.clock()
vArray = [[[0 for x1 in range(3)] for y1 in range(3)] for z1 in range(3)]
vMaxArray = [[[0 for x2 in range(3)] for y2 in range(3)] for z2 in range(3)]


iMax = 0
iTotalBlock = 1
vChain = [3, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2]
m = 1000000
limit = int(m * 1)
for lSim in range(limit):
    try:
        GiveUp = "False"
        iDirection = 0
        iTotalBlock = 1
        vCurrent = [0, 0, 0]
        for x in range(3):
            for y in range(3):
                for z in range(3):
                    vArray[x][y][z] = 0
        for iLink in range(17):
            if GiveUp == "False":
                if iLink == 0:
                    for iBlock in range(vChain[iLink]):
                        if iBlock > 0:
                            vCurrent[0] += 1
                        vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] = iTotalBlock
                        iTotalBlock += 1
                else:
                    iDirection = drandom(iDirection)
                    iUpOrDown = drandomu()
                    for iBlock in range(vChain[iLink]):
                        if vCurrent[iDirection] == 0:
                            iUpOrDown = 1
                        vCurrent[iDirection] += iUpOrDown
                        if vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] != 0:
                            if iMax < iTotalBlock:
                                iMax = iTotalBlock
                                for x in range(3):
                                    for y in range(3):
                                        for z in range(3):
                                            vMaxArray[x][y][z] = vArray[x][y][z]
                            GiveUp = "True1"
                            break
                        else:
                            vArray[vCurrent[0]][vCurrent[1]][vCurrent[2]] = iTotalBlock
                            iTotalBlock += 1

        iTotalBlock = 0
        for x in range(3):
            for y in range(3):
                for z in range(3):
                    iTotalBlock += vArray[x][y][z]

        if iTotalBlock == 378:
            print(vArray)
    except:
        pass

print(int(time.clock() - CurrentTime), "Seconds")
print(int((time.clock() - CurrentTime)/60), "Minutes")

for x in range(3):
    print(vMaxArray[x])

print(iMax)
 

The Solution

The program eventually gave me the following layout as a solution:

[[1, 16, 23],    [18, 17, 22],    [19, 20, 21]]
[[2, 15, 24],    [5,  6,    7],     [10, 9,   8]]
[[3, 14, 25],    [4, 13,  26],    [11, 12,  27]]

The easiest way to think about the solution the program gives is to think of the three blocks of three digits on the left as the bottom layer, the second block of three digits as the second layer, and then the third block of three as the third layer. So the 4th block is directly abov the third block.

Here is the completed puzzle:
Picture

Monte Carlo Tic Tac Toe Engine

24/7/2016

 
Since setting up the approximation of $\pi$ using the Monte Carlo technique of sampling inside a circle, I've been playing around with applying Monte Carlo methods to other problems.

One problem I thought it would be fun to play around with was creating an AI engine that uses Monte Carlo rather than deterministic methods to run. My first thought was to look at a chess engine, I've always wanted to set one up, but after playing around with it for a while I realised setting up the actual game engine was going to be a substantial amount of work before even thinking about the AI. Therefore I shelved that for the time being.

The next game I decided to look at Tic-Tac-Toe or Noughts and Crosses which is on the opposite end of the spectrum in terms of complexity of rules.

Optimal Strategies

As every school age kid quickly learns, there is an optimal strategy for playing Tic-Tac-Toe. In case anyone has forgotten it can easily found online, however programming in the strategy would have been quite tedious, and not as fun as messing around with a stochastic solution.

I thought it was interesting that a Monte Carlo engine, if it can be programmed to play the game well without even being told what the optimal strategy is, should replicate this strategy simply by selecting what it believes is the optimal move based on its own analysis. It can do all of this without ever truly knowing what the strategy is.

I decided to write the engine in VBA, which is not a great development language generally. But meant that I could stick the game into a Spreadsheet which seemed like a fun thing to do. Here's a screenshot of the game:

Picture

How it works

The way the engine works is each time the computer is about to move, it uses the current state of the grid, and plays out a large number of random games (for each move it makes a random selection for itself and then a random selection for the player until one side wins or it is a draw).

The computer tracks who wins each game and more importantly, for each of the possible next moves for the computer, whether it eventually ends in a win, draw or loss. The computer repeats this process a large number of times (the default being 10,000), each time assigning a value to the starting move of +1 if the computer eventually wins the game, +0.5 if the game ends in a draw, and 0 if the computer losses the game. The computer keeps a running total of the value assigned to each starting move. Once the simulation of random games is completed, the computer selects the move with the highest value, this should correspond to the starting move that is the most likely to led to a victory or a draw,

I've linked below to the Excel file with the game inside:

tic_tac_toe.xlsm
File Size: 26 kb
File Type: xlsm
Download File

​And here is the source code in VBA:​
Hide Code

Option Base 1
Option Explicit

Sub MakeMove()

Dim vGrid As Variant
Dim vGridPerm As Variant

Dim iNewCell As Integer
Dim iFirstMove As Integer
Dim irow As Integer

Dim lSimNum As Long
Dim lNumSim As Long

Dim vNextmove(9) As Long

lNumSim = Range("NumSim")
vGrid = Range("Grid")
vGridPerm = Range("Grid")

If CheckWin(vGrid) <> -1 Then
    Exit Sub
End If

For lSimNum = 1 To lNumSim
    
    vGrid = vGridPerm
    
    iFirstMove = GetRandom(vGrid)
    vGrid(iCellToiRow(iFirstMove), iCellToiCol(iFirstMove)) = "X"
    
    While CheckWin(vGrid) = -1
        iNewCell = GetRandom(vGrid)
        vGrid(iCellToiRow(iNewCell), iCellToiCol(iNewCell)) = "O"
        iNewCell = GetRandom(vGrid)
        vGrid(iCellToiRow(iNewCell), iCellToiCol(iNewCell)) = "X"
    Wend

    vNextmove(iFirstMove) = vNextmove(iFirstMove) + CheckWin(vGrid)
    
Next

Range("k6") = findmax(vNextmove)
For irow = 1 To 9
    Range("k7").Offset(irow, 0) = (vNextmove(irow) / lNumSim)
Next

vGridPerm(iCellToiRow(findmax(vNextmove)), iCellToiCol(findmax(vNextmove))) = "X"

Range("grid") = vGridPerm

End Sub

Function findmax(vNextmove)

Dim iCell As Integer
Dim iMax(2) As Integer

iMax(1) = 1

For iCell = 1 To 9
    If vNextmove(iCell) > iMax(1) Then
        iMax(1) = vNextmove(iCell)
        iMax(2) = iCell
    End If
Next

findmax = iMax(2)

End Function

Function GetRandom(vGrid As Variant)

Dim iCell As Integer
Dim iCountBlank As Integer
Dim vEmpty(9) As Variant

iCountBlank = 0

For iCell = 1 To 9
    If vGrid(iCellToiRow(iCell), iCellToiCol(iCell)) = "" Then
        vEmpty(iCountBlank + 1) = iCell
        iCountBlank = iCountBlank + 1
    End If
Next

Randomize
GetRandom = vEmpty(Int(Rnd * (iCountBlank) + 1))

End Function

Function iCellToiRow(iCell As Integer)

iCellToiRow = 1 + Int((iCell - 1) / 3)

End Function

Function iCellToiCol(iCell As Integer)

iCellToiCol = 1 + ((iCell - 1) Mod 3)

End Function

Function CheckWin(vGrid As Variant)

Dim irow As Integer
Dim iCol As Integer
Dim iDiag As Integer

Dim iCountX As Integer
Dim iCountO As Integer
Dim iCountBoth As Integer

'1 = win, 1/2 = draw, 0=Lose, -1 = continuing

' Check X then O
' Check Rows, Check Columns, check down diag, check up diag

CheckWin = -1

For irow = 1 To 3
    iCountX = 0
    iCountO = 0
    For iCol = 1 To 3
        If vGrid(irow, iCol) = "X" Then
            iCountX = iCountX + 1
        End If
        If vGrid(irow, iCol) = "O" Then
            iCountO = iCountO + 1
        End If
    Next
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next


For iCol = 1 To 3
    iCountX = 0
    iCountO = 0
    For irow = 1 To 3
        If vGrid(irow, iCol) = "X" Then
            iCountX = iCountX + 1
        End If
        If vGrid(irow, iCol) = "O" Then
            iCountO = iCountO + 1
        End If
    Next
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountX = 0
iCountO = 0
For iDiag = 1 To 3
    If vGrid(iDiag, iDiag) = "X" Then
        iCountX = iCountX + 1
    End If
    If vGrid(iDiag, iDiag) = "O" Then
        iCountO = iCountO + 1
    End If
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountX = 0
iCountO = 0
For iDiag = 1 To 3
    If vGrid(iDiag, 4 - iDiag) = "X" Then
        iCountX = iCountX + 1
    End If
    If vGrid(iDiag, 4 - iDiag) = "O" Then
        iCountO = iCountO + 1
    End If
    If iCountX = 3 Then
        CheckWin = 1
        Exit Function
    ElseIf iCountO = 3 Then
        CheckWin = 0
        Exit Function
    End If
Next

iCountBoth = 0
For irow = 1 To 3
    For iCol = 1 To 3
        If vGrid(irow, iCol) = "X" Or vGrid(irow, iCol) = "O" Then
            iCountBoth = iCountBoth + 1
        End If
    Next
Next

If iCountBoth = 9 Then
    CheckWin = 0.5
    Exit Function
End If

End Function
 
Show Code

Future Development

Something that I would like to explore in the future is the use of more efficient algorithms for analysing the best move. For example, apparently alpha-beta pruning can be used to focus on the moves that look the most promising rather than spending an equal amount of time looking at all moves.

​I would also like to make a web based version of the game at some point.,

Lyric Analysis - Why Justin Bieber is better than Metallica, but the Beatles are the greatest.

29/6/2016

 
"I’m not a businessman
I’m a business, man!
Let me handle my business, damn"

Kanye West ft Jay.z - Diamonds from Sierra Leone


“It's easier to run
Replacing this pain with something numb
It's so much easier to go
Than face all this pain here all alone.”


Linkin Park - Easier to Run

Recently I've really been getting into hip hop, one thing that really struck me about hip hop, is that contary to popular perception. hip hop is on the whole surprisingly upbeat, especially when contrasted with rock and metal which I listened to a lot of growing up.

In the spirit of being scientific I thought I would try to quantify this difference. My plan was:

1) Get hold of a sample of lyrics from different artists of sufficient size.
2) Come up with a method for analysing how positive or negative the lyrics are.
3) Run the analysis on the lyrics and collate the results,

Step 1 - Collect data

So the first step was to obtain a sample of lyrics. This was actually harder than I thought it would be. There are plenty of websites which contain song lyrics, however I was looking for a large collection of songs and artists, and I didn't want to have to trawl through hundreds of webpages by hand.

The process of automating the collection of data from websites is called web scraping. I have played around with webs scraping before using Python, but I found it to be very fiddly to set up and not very reliable. This was a couple of years ago though, and it turns out that since then there have been a number of new tools which make the whole process easier.

I ended up using a tool called 'Web Scraper', website below:
​
http://webscraper.io/

Web Scraper is an add-in to Chrome with an easy to use graphical interface, that can export extracts directly to .csv files.

In total I managed to collect lyrics from about 4,000 songs across 12 artists. Whilst I did manage to automate the process, it was still quite slow going as many websites have anti-scraping technology that blocks you out if you take too much data too quickly. I might try to expand this sample at a later date, but we can already see some clear trends emerging just from these artists.

Step 2 - Develop a method for analysing the lyrics.

Trying to program a computer to understand the semantic meaning of human generated text is a big area of research in the field of Computer Science. It is called 'Natural Language Processing', or NLP for short, there are many advanced methods within NLP being developed at the moment, some of the approaches involve Machine Learning, statistical analysis or other complex methods. For a good introduction the Wikipedia page gives a helpful overview.

However, I was just looking for a very basic method that would allow for a broad brush analysis. I therefore decided to just use the relative frequency of words with positive or negative connotations within the lyrics as a proxy for how positive or negative the lyrics were as a whole.

The obvious weakness of this approach is that just because there are positive words within a sentence, does not necessarily imply the meaning of the sentence is positive as a whole. For example, take the sentence 'This is not fun', an analysis of this sentence just on the basis of the words contained in it would suggest that it is a positive sentence, given we have the word 'fun' in the sentence. The obvious way to counter this would be to start looking at phrases instead. So 'not fun' would be given a negative connotation. Trying to look at phrases rather than words, adds a large degree of additional complexity to the analysis though, and given that all the artist should be exposed to roughly the same degree of false positives and false negatives, and given that we still get interesting results just using this very basic heuristic I decided to stick with it in this case. I might come back to this at a later date though.

So given we are just interested in looking at words rather than phrases, I was looking for a dictionary of words with an indicator of whether the word is positive or negative. It turns out that people have already worked on this problem, and free dictionaries are available online. I found the website of Prof. Bill Mcdonald of the University of Notre Dame in Indiana, USA. He has developed word lists for use in automating the analysis of financial statements, all the lists can be found in the following link:
http://www3.nd.edu/~mcdonald/

​I took Prof. McDonald's list, added in a number of additional words that appear frequently in song lyrics but were not including in the word list. (For example ballin' came up a lot in Hip Hop, but unfortunately is under used in financial statements).

Step 3 - Run the analysis on the data and collate the results

Here are the results of my analysis:

Picture

As we can see, Jay Z and 50 Cent, our representative Hip Hop artists are clearly above the Metal artists in terms of the relative frequency of positive over negative words in their music. We can see that the Metal artists are clustered at the bottom of the table.

One interesting feature of the results, which perhaps should not have been a surprise, was that pop music, i.e. Justin Bieber and the Beatles, were actually the clear winners on these terms. 

Grouping the artists together into genres further emphasises the clear positioning of the genres.
Picture

So there we have it, Hip Hop is more positive than Rock or Metal. And Justin Bieber is better than Metallica, but the Beatles are the most positive band of all!

Solving the GCHQ Christmas Puzzle part 3

19/1/2016

 
Part 3 consists of four questions. The answer to each puzzle is a single word, which can be used to create a URL."
​
  1. Complete the sequence:
    Buck, Cod, Dahlia, Rook, Cuckoo, Rail, Haddock, ?
My first thought when reading this was to look at the semantic meaning. I think this is probably because of the fact that we have both cod and haddock in the list, and quite a few of the others are animals. After playing around with this for a while I was getting nowhere. Then I noticed that the entire sequence of letters is nearly a palindrome. Therefore, the answer is cub, as this turns the sequence into a palindrome.


     2. Sum:
         pest + √(unfixed - riots) = ? 


Hmm, how can we do maths with words? I played around with trying to assign meaning to the sentence, kinda like the old joke that you can show that $women = evil$.

Women take up time and money, therefore:

$Women = Time * Money$

Time is equal to money:

$Time = Money$

Therefore:

$Women = Money^2$

But we also know that money is the root of all evil:

$Money = \sqrt{Evil}$

Therefore:

$Women = \sqrt{{Evil}^2}$

Simplifying:

$Women = Evil$
​
I wasn't able to come up with anything along this vein, therefore we need to try a new approach.

If we are committing to the idea that the words represent numbers somehow then we need to try to assign numbers to these words. I played around with a few ideas before trying anagrams.

I noticed that pest is an anagram of sept. (Which I initially thought related to September and hence 9, but is also French for 7). Running with this idea, we also note that unfixed is an anagram for dix-neuf, and riots is an anagram for trois. So our equation becomes:

$ 7 + \sqrt{19 - 3} = 7 + \sqrt{16} = 7 + 4 = 11$

Therefore our answer is onze. Since the other words were anagrams this is probably an anagram as well. Therefore I think the solution is zone. On to the next question.

     3. Samuel says: if agony is the opposite of denial, and witty is the opposite of tepid, then      what is the opposite of smart?

Samuel says is a strange way to start this question. normally you'd say 'simon says', is this a hint? Who is Samuel? The first thing that comes to my mind is Samuel Pepys, the famous diarist. I wonder if he has any famous quotes that shed light on the question. A quick google doesn't reveal anything. Perhaps this is a different Samuel? Looking up other famous Samuels leads us to another clue - Samuel Morse. Once we know that we are talking about morse code, the obvious next step is to convert the words we've been given into morse code. We find that:
Agony = ... -- .- .-. -
Denial = -.. . -. .. .- .-..
Witty = .-- .. - - -.--
Tepid = - . .--. .. -..
Smart = ... -- .- .-. -

Now we can hopefully see how this works - we replace the dots for dashes.

Therefore our new word is:
​---..-.-.-.-

This word doesn't have the spaces in it. After some experimentation we conclude that the word that is the opposite of smart is often.

     4. The answers to the following cryptic crossword clues are all words of the same      length. We have provided the first four clues only. What is the seventh and last answer? 
 
  1. Withdraw as sailors hold festive sing-song
  2. It receives a worker and returns a queen
  3. Try and sing medley of violin parts
  4. Fit for capture


  5. ?

The next question is a series of cryptic crosswords - which is a bit of an issue since I've never done a cryptic crossword before. We've therefore got two options - learn how to solve cryptic crosswords, or find another way to progress. I attempted to learn how to do cryptic crosswords but I really struggled to solve the crosswords here, though I do now know how to solve cryptic crosswords and can solve a few questions in a newspaper. Therefore we need to find another way to solve this puzzle.

The website provides us with a way to check that our answers are correct. We can input our answers into the boxes provided and click the 'check answer' button and the website will tell us if we have the correct solutions. Hmm.. wonder how this words.

When we view page source and look at the code we see that there is actually a check function. For a given string of letters this function returns two unique numbers. The website takes our answers, calculates the unique numbers associated with it, and checks if the numbers generated are equal to 608334672 and 46009587. So it's simple right? We just work out the string generates these two numbers and this will give us the answer. The problem with this is that the function that generates these numbers is something called a cryptographic hash function. Which is a function which for any input will return a result of a fixed length which is practically impossible to invert.

We have some extra information that help us though - we know the format of the answer, and we know the answers to three out of the four questions. So we know the input to the hash function is of the form:
"cubzoneoften" + new word

I therefore set up a dictionary attack in the following file:
test.html
File Size: 3 kb
File Type: html
Download File

This file works by letting you open a .txt file containing a list of words. The code will then loop through the words in the text file, calculating the results of the hash function. After running this file we find out that the word we are looking for is layered. And the url of the next stage of the challange is:
​
www.cub-zone-often.org.uk/layered

Solving the 2015 GCHQ Christmas Puzzle part 2

10/1/2016

 
As we saw in my post on part 1 of the GCHQ Christmas puzzle, the solution to the grid puzzle gives us a QR code which takes us to the following website:
http://www.gchq.gov.uk/puzz/Pages/index.aspx
Part 2 of the puzzle states:

"Part 2 consists of six multiple choice questions. You must answer them all correctly before you can move on to Part 3."

We are then given our first question:


Q1. Which of these is not the odd one out?
  1. STARLET
  2. SONNET
  3. SAFFRON
  4. SHALLOT
  5. TORRENT
  6. SUGGEST

This is a strangely worded question... which of these is not the odd one out. We are more used to being asked which of these is the odd one out. What would it mean for something not to be the odd one out? My initial reading of the question, which turned out to be the correct one, is that each word except for one will turn out to be the odd one out for a different reason. For example, TORRENT is the only not starting with an S, therefore, it is the odd one out, and not the answer to the puzzle. SAFFRON is the only on ending in an N and is also there not the answer to the puzzle.

As an aside, this question reminds me of the interesting number paradox. If we attempt to divide all numbers up into numbers that are interesting (such as 2 which is the only even prime) and numbers which are not interesting. Then the numbers that are not interesting must have a smallest member. However, since this is an interesting property (the property of being the smallest uninteresting number), this number cannot in fact be an uninteresting number. And we must conclude that there are no uninteresting number. Similarly, if we work out that one of the answers above is not the odd one out, then we have found a way in which the number is the odd one out. Due to the fact that it is the only one which is not the odd one out! 

Q2. What comes after GREEN, RED, BROWN, RED, BLUE, -, YELLOW, PINK?
  1. RED
  2. YELLOW
  3. GREEN
  4. BROWN
  5. BLUE
  6. PINK

This turns out to be a cool question. We have a sequence of colours and we need to work out the next value. My first thought when I read this was that it perhaps relates to monopoly (possibly because I had played it just before trying to answer). I played around with this idea for a while but didn't get anywhere. I wasn't a million miles away as in the end my girlfriend gave me a hint that it related to snooker. Once you plug in the values of the snooker balls into this sequence you get the following sequence of numbers:

3   1   4   1   5   -   2   6

Which you will hopefully recognise as the decimal expansion of $\pi$. The next digit is 5 and therefore the answer is Blue.

Q3. Which is the odd one out?
  1. MATURE
  2. LOVE
  3. WILDE
  4. BUCKET
  5. BECKHAM
  6. SHAKA
I had no idea how to solve this question. I tried googling all the names but couldn't really see any common links. Below I show how to progress even though you haven't answered all the questions.

Q4. I was looking at a man on top of a hill using flag semaphore to send a message, but to me it looked like a very odd message. It began "ZGJJQ EZRXM" before seemingly ending with a hashtag. Which hashtag?
  1. #SGM
  2. #SEM
  3. #SEN
  4. #SGN
  5. #TEN
  6. #TGN
​
This should be quite a straightforward question to answer - my guess which turned out to be correct is that there is a fairly straight forward transformation that can be applied to how the man is using flag semaphore so that it makes sense. The first transformation I tried was to rotate the message by various degrees. I got bored of answering this question after a while so I decided to skip it. .

Q5. What comes after 74, 105, 110, 103, 108, 101, 98, 101, 108, 108?
  1. 108
  2. 101
  3. 115
  4. 123
  5. 111
  6. 103

Here we have a sequence of numbers and we need to find the next number. Since the number all cluster around the 70-110 area, my intuition was that they are some sort of encoding. The first thing I checked was the ascii values of these numbers. They come out as J i n g l e b e l l. This should be the answer then! The next value is s, and the next number is therefore 115.

Ascii is a way for computers to represent letters and other characters using numbers. The numbers 0 to 255 (giving a total of 256 characters which is a power of 2) are each assigned a character here is a link to an ascii table:
http://www.asciitable.com/

Q6. What comes next: D, D, P, V, C, C, D, ?
  1. F
  2. E
  3. D
  4. C
  5. B
  6. A

This was quite a fun question. I've got no idea how to help people solve it as I just stared at it for a few minutes then spotted the answer. These are the names of Santa's reindeers! I guess one possible hint was the use of jinglebells in the question above, and the fact that this is a Christmas puzzle.

So we have the answer to 3 of the questions and we have narrowed down some of the options on the other questions.

I noticed that the way the website stores your responses is to take the 6 answers and convert it to a web address. So by answering 1 on each question we will be taken to the following url. (Note the 6 As at the end which correspond to answering 1 in each question)
http://s3-eu-west-1.amazonaws.com/puzzleinabucket/AAAAAA.html
What I did next was set up a Spreadsheet with links to this url corresponding to the possible combinations of answers which I have not eliminated yet. For example, we know that the second digit is E and the second to last digit is C. The url of the next stage is the following:
http://s3-eu-west-1.amazonaws.com/puzzleinabucket/bb1f263f70e45b3d.html

Collecting all 100 tickets at 5 Guys Burgers

3/1/2016

 
When you order at 5 guys burgers (which you should if you haven't because they are amazing) you are given a ticket between 1 and 100 which is then use to collect your order. Last time I was there my friend suggested trying to collect all 100 tickets. The question is:

Assuming you receive a random ticket number between 1 and 100 inclusive on every visit. On average, how many visits would it take to collect all 100 tickets?

Solution:
Define $S$ to be a random variable which counts the number of purchases required to get all 100 tickets. Then we are interested in $\mathbb{E} [S]$

To help us analyse $S$ we need to define another collection of random variables.

Let $X_i$ denote the number of purchases required to get the $ith + 1$ ticket given we have already collected $i$ tickets. So if we have collected 2 tickets (say ticket number 33 and ticket number 51) and the next two tickets we get are 33 and 81, then $X_2 = 2$ because it took us 2 attempts to get a new unique ticket.

We can actually view $S$ as the sum of these $X_i$, i.e. $S = \sum\limits_{i=1}^{100}X_i$ (to see that this is the case the number of visit it takes to collect all 100 tickets will be the number of visits to collect the first ticket plus the number of visits to collect the 2nd unique ticket, and so on)

There are two further observations that we need to make before deriving the solution. Firstly, each $X_i$ is independent of $\sum\limits_{k=1}^{{i-1}}X_i$. Secondly, each $X_i$ is actually distributed as a Geometric Distribution where:
$P( X_i = k ) = \frac{i-1}{100}^{k-1} \frac{101-i}{100}$


Since $X_i$ is a geometric random variable, we know that $\mathbb{E} [ X_i ] = \frac{100}{101-i}$

Giving us:

$\mathbb{E} [ S ] = \mathbb{E} [ \sum\limits_{k=1}^{100} X_i ] = \sum\limits_{k=1}^{100} \mathbb{E} [X_i ] = \sum\limits_{k=1}^{100} \frac{100}{101-i} = 100 \sum\limits_{k=1}^{100} \frac{1}{101-i} = 100 \sum\limits_{k=1}^{100} \frac{1}{i}$
How to compute $100 \sum\limits_{k=1}^{100} \frac{1}{i}$ ?
This is a famous sum in mathematics. The value of this sum for a given upper limit is known as a harmonic number. The nth Harmonic number $H_n$ is defined to be $\sum\limits_{k=1}^{n} \frac{1}{i}$.
In this case, using wolfram alpha to look up the value of $H_100$ tells us that $H_{100} = 5.18737751$
Therefore on average it will take us $100 H_{100}$ visits to 5 guys to collect all 100 tickets. This is approximately equal to $519$ visits, which is a lot of burgers!

Solving the 2015 GCHQ Christmas Puzzle part 1

3/1/2016

 
This year GCHQ released a Christmas Puzzle, in this post I'll show you how to solve the series of puzzles, and also, the thought process that I used to get to the solutions.

If you would like to attempt to solve the puzzle yourself then here is the link to the first part of the puzzle. The solution to the first part will then lead to the second part of the puzzle. In total there are five parts.
http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

From the GCHQ website:

"In this type of grid-shading puzzle, each square is either black or white. Some of the black squares have already been filled in for you.

Each row or column is labelled with a string of numbers. The numbers indicate the length of all consecutive runs of black squares, and are displayed in the order that the runs appear in that line. For example, a label "2 1 6" indicates sets of two, one and six black squares, each of which will have at least one white square separating them."
Picture
I decided to solve this puzzle in excel. The main reason for this was that I wanted to be able to fill in squares automatically rather than shading them by hand. I've posted a link to an excel file below which matches the start of the puzzle. In my version if you press Ctrl+a then the selected cell will turn black, and if you press ctrl+d then the selected cell will turn blue. I'll explain the use of blue cells later.
gchq_qr.xlsm
File Size: 19 kb
File Type: xlsm
Download File

 The first step to solving this puzzle is to count the number of rows and columns in the grid. In this case we have a 25 by 25 grid. In excel I then calculated the minimum number of cells required for each row and column. For example, the third column is listed as 1,3,1,3,1,3,1,3,1. Since there must be a blank space in between each block of black cells, this combination must take up a minimum of 25 cells but since there are only 25 cells in the column we now know which cells in this column need to be coloured black. We can now go ahead and fill in this column. We also know that the spaces in between the blocks of black cells need to be blank, to signify this we can colour these cells blue. Repeating this process allows us to complete 3 columns and 2 rows.

The next step is to look at rows and columns which have high minimum values but which are less than 25 but still high. For example, looking at the first row, it is listed as 7,3,1,1,7 with a minimum of 23. Since the first two blocks on either side are 7 long, cells 17:23 must be coloured in as a minimum, but as a maximum cells 19:25 must be filled in. Since there is an overlap between these two we can colour in the cells in the overlap. Here is an image demonstrating this. There are three copies of the first row, the first row contains the minimum cells and the second row contains the maximum cells. I have then coloured the overlap on the blocks of seven in black.
Picture
Filling in the first cell in a row is also useful as it lets us immediately use the information about that column. For example we know that the third cell in the first row is black, looking at the listing for this column we see that the first block of blacks is a 1, therefore the cell below it in the second column must be blank and can be filled in blue. Using this these techniques we eventually complete the grid. Giving the following image.
Picture
You may recognise this kind of pattern as a QR code. A QR Code is a 2 dimensional bar code. I downloaded a QR reader to my phone and scanned the image which takes you to the following url:
http://www.gchq.gov.uk/puzz/Pages/index.aspx

    Author

    ​​I work as a pricing actuary at a reinsurer in London.

    I mainly write about Maths, Finance, and Technology.
    ​
    If you would like to get in touch, then feel free to send me an email at:
    ​LewisWalshActuary@gmail.com

    Categories

    All
    Actuarial Career
    Actuarial Exams
    Actuarial Modelling
    Bitcoin/Blockchain
    Book Reviews
    Economics
    Finance
    Fun
    Insurance
    Law
    Machine Learning
    Maths
    Modelling
    Physics/Chemistry
    Poker
    Puzzles/Problems
    R
    Statistics
    Technology
    VBA
    Web Scraping

    Archives

    February 2021
    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    May 2020
    March 2020
    February 2020
    January 2020
    December 2019
    November 2019
    October 2019
    September 2019
    April 2019
    March 2019
    August 2018
    July 2018
    June 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    April 2016
    January 2016

    RSS Feed

  • Blog
  • Project Euler
  • Category Theory
  • Disclaimer