Sexuality and Population Dynamics

So I was reading this response to a Daily Mail opinion piece about those 'gay cure' bus adverts, and I see this quote (from the Mail article)

“Since only about one percent of us are [gay], homosexuality is obviously a departure from the norm... Reversing that proportion would spell the end of the human race, which is clearly undesirable.”

There are several things wrong with this statement - some of which the response, linked above, points out.

First of all, that 1% values. The actual number is a tricky figure to pin down. The UK Office of National Statistics puts the figure at 1.5% gay or bisexual; the linked response lists 3 studies which put the value around 7% (for the UK), and various other studies suggest number in the modern West is somewhere between 2-13%.

Secondly, just because something is (statistically) "a departure from the norm", doesn't mean it's bad - for example, ~10% of people are left-handed, ~2% of people have red hair, etc. (Historical beliefs notwithstanding.)


But all that's tangential. What I'm interested in is the second part - would a majority gay population spell the end of humanity?

[NB/ for the remainder of the blog, I shall be using 'gay' colloquially, as shorthand for all of LGBTQUA, etc.]


The Simple Model

It's an interesting population dynamics question, and it's easy to model if we make some assumptions and simplifications:

1) We assume that homosexuals don't reproduce at all (either directly or indirectly). This isn't true - but it seems to be a common belief.

2) We assume that the rest of the population reproduces with some fixed rate (b=0.02059), which doesn't change from year to year. Similarly, we assumes a fixed death rate (d=0.00812), which affects all members of the population equally.

3) We assume that sexuality is binary, definite and static, with a fixed incidence of homosexuality, g = 0.07 - that is, of all children born 7% will be gay.


So the model we're using is preposterously simplified - effectively,

new population = old population + births - deaths

And we can easily program this model and run simulations.

Now, there are two ways to interpret the article's statement in the context of our model -


1) "if 99% of the (initial) population were gay" assuming the 7% incidence

The outcome looks like this

In this case, the population drops at first, but then starts to grow again, exponentially - certainly not the end of the human race. Also notable is that the proportion of the population that is gay stabilises at 7% (as expected).

2) "if 99% of people were born gay"

Now, the outcome looks like this

Exponential decay - so, in this case, humanity would die out. But if 99% of the population isn't reproducing, what do you expect?

Here are the phase portraits of the above two cases, for a slightly different view of what's happening (gay population along x, straight population along y)

Again, for g=0.07 the population tends to infinity; for g=0.99 the population tends to zero. Note that this behaviour is (ultimately) the same for all initial population ratios.


What I Learned in MAS271

We don't actually need numerical simulations to study the behaviour of this (or similar) systems - the model can be solved analytically.

First of all, we generalise the system. We start with a pair of coupled, first-order differential equations describing the behaviour of the two populations

Now, these two populations are mutually exclusive subgroups of the total population - that is, total population z = x + y. So with a little mathematical trickery, we can combine these two into a single equation, describing the behaviour of the total population

This is a second-order, linear differential equation, so has the general solution of the form

Where lambda values are given by

And A-coefficients are constants, which are determined by the system's initial conditions. If the initial total population is z0, and the inital size of the x population is x0, then we get

In other words, we now have an (analytical) equation which completely describes how the population will behave for any given set of variable.

Incidentally, the equations for x and y have the same form as z. The only difference is the A-coefficients.


Boom or Bust

What we want to do is be able to determine the long term behaviour of the population based on the given set of variables - that is, will the population grow, or die out?

For the coupled system above, there is only one stationary point, at (x,y) = (0,0) - i.e. when the total population is zero. What this means is, if the population is zero, it will stay zero. If it has any other value, then the population size will change over time.

In terms of the stability of the system, if (0,0) is stable, the population will tend towards zero - i.e. will die out. If (0,0) is unstable, the population will tend to infinity - i.e. grow indefinitely.

As it turns out, the lambda values above are the eigenvalues of the coupled system, meaning their values determine the stability of the system:

i) if both lambdas are negative, the system is stable and the population will die out;

ii) if one or both of the lambdas are positive, the system is unstable and the population will grow to infinity.

Now, if we take the limit of z(t) for t tends to infinity, we can simplify the population equation

What this tells us is, if lambda1 is less than one the population will die out. If lambda1 is greater than one, the population will grow.

And we can use this to determine the conditions for instability - the conditions under which the population will grow. In this case the condition is lambda1 > 0. But this can be simplified down to

There's one last trick we can do - determine what proportion of the total population will be in the sub-population x (e.g. what what fraction of the population will be gay) as t tends to infinity.

For this, we determine the equation for population x (in a similar fashion to z), and take advantage of the limits to get the equation

Note that this equation is time-independant, i.e. the proportion will tend to some constant value.


Back to Basics

Just as a sort of check, we'll go back to the basic model. For this, we have

Which gives lambda and A values

Which gives the population equation

Which behaves like the graphs at the top. And this tends to

And gives

That is, the proportion of the population that will be gay stabilises at the pre-defined 'birth' ratio - which is what we saw from the numerical model. Note also that this value is independent of initial conditions and doesn't vary over time.


Simple Instability

Finally, for the simple model, the condition for instability (growth) is given by

For the numerical values chosen above, this gives the condition g < 0.606 - that is, if less than 61% of the population is 'born' gay, then the population won't die out. And 61% is a pretty high upper limit - a majority, in fact.

Similarly, we can use this inequality to find under what conditions g=0.99 is viable. In this case, it requires a birth rate 100 times the death rate.

So, if the death rate is 0.008 (i.e. 8 death for every 1,000 people), then it requires a birth rate of 0.8 (800 birth per 1,000 people). Now, for each 1,000 people, 99% is gay, meaning 10 straight people per 1,000. Of those, about half is female (5). In other words, each woman would have to give birth to 160 babies per year!

Clearly this isn't feasible. But for comparisons sake, consider bees or ants - these species are eusocial, meaning populations made of one fertile queen, and hundreds of (mostly) sterile drones. In this case, the high birth-to-death ratio is more reasonable, and the predominantly non-reproducing population is still viable.


A More Complex Model

In the simple model we assumed that only the straight population reproduces, and that both populations die at the same rate. So we make the following modifications:

1) First of all, lets tweak the model so that the gay population has children as well, with some separate birth rate, b1.

2) Of those born to gay couples, some proportion g1 will be gay (NB/ studies show that the majority of children raised by same-sex parents grow up to be heterosexual).

3) And for completeness, lets say that the gay population has a different death rate as well, d1.

Here's what the model looks like

And here are the coupled equations

Now, all the previously derived general equations and such from earlier still apply. But in this case, the variables can't really be simplified, and writing them out in full would just be a mess.

So if we take, for example, b and d as before, and b1 = 0.00103, d1 = 0.01218, and g1 = 0.03, here are the new phase diagrams for g = 0.07 and 0.99

For this model, the phase portraits are basically the same as for the simple model - i.e. the effect of using the modified model over the simple model is negligible.


Complex Conditions

So, for this model, the condition for growth looks like this

The important thing to note here is, if the condition for the simple model (g<1-d/b) is satified, then the condition for the complex model is necessarilty satisfied.

In fact, if we set g to its maximum possible value 1 (i.e. all babies born to straight couple are gay), then the human race will still persist so long as g1 > d1/b1.

And what this means is, so long as the birth rate (b1) is greater than the death rate (d1), then every baby born could be gay, the human race still wouldn't die out.

However, given the low birth rate for gay couples (compared to death rate), this might not actually be satisfied IRL. In which case, an entirely gay population is still not sustainable.

For the b and d values already chosen, we can use the condition to plot how the upper limit of g varies with g1

So for these values, the upper limit of g can increase by no more than 3.4%. So, again, the extra complexity doesn't give a significantly different result compared to the simple model.

In fact, the additional variables only become significant when (b1/d1)g1 > 0.15 (for the values above); or in general, when

So, if we keep b and d as before, g=0.07, and re-set b1=b, d1=d, and g1=0.06, then (b1/d1)g1=0.152, and the phase portrait looks like this

Here, the upper limit on g has risen to 0.67. (cf: 0.61 for the simple model). And, if we set the initial condition x0=0.07*z0, then the limit of x/z = 0.0697; just less than g.



tl;dr - So, would homosexuality ever mean the end of the human race? - Under some circumstances, yes. But in most (real world) cases, no. And even if a majority of the population were LGBT, the human race still wouldn't necessarily die out.

BUT, as a final note - remember that these are very simplified models of population dynamics. So take the results with a grain of salt. The science of sexuality is much more complex and much less abstract than this.


Oatzy.


[Putting my degree to good use.]

Some Twitter Infographics

I did some stuff like this before. And I figured, while I was updating my network graphs, why not update some of the other graphics?

And it helps that I worked out how to easily extract data from Twitter (see previous blog). The code is here. Again, rate limits apply.


Who Do I Follow?

This is one of the ones I did before - collect together the bios of the people I follow, then make a word cloud (using Wordle)

Basically, I follow a bunch of geeks and writers. Who like 'things'. So really, same as a year and a half ago.

I would point out though that 6 of the people I follow don't have bios, and about 7 just have lyrics.

Data here.


Who Tweets the Most?

These rates are worked out as (total tweets posted)/(total days online). Obviously, the actually post rate will vary over different time scales..

Bubble chart (made with ManyEyes) - bubbles sized by tweet rate (the numbers on some of the bubbles).

The graph below gives a better idea of relative rates, and 'rankings' (click to embiggen)

The blue line is actual values.

The orange is a logarithmic trend-line. It's a pretty good fit (R2=0.95); and, loosely speaking, it means ~70% of the tweets in my timeline come from ~30% of the people I follow. [cf: Pareto Principle]

You get similar log-shaped graphs when you split up the genders.

Full data here.


Chattiest Gender?

You can read all the explanation, caveats, etc. in the previous posts (here and here). I'm just going to go straight into the data.

I follow 27 men and 21 women (excluding celebrities, etc.). The stats are as follow:

Men:
Average = 6.21 tweets/day
Standard Deviation = 6.47

Women:
Average = 13.79 tweets/day
Standard Deviation = 14.27

For clarity, here's a  boxplot (made in R)

Basically, the women tweet more on average, and their rates are more spread out than for the men. In fact, roughly three quarters of the men tweet less than half of the women. Also, there's one outlier in the female group.

This is similar to what we found last time; although the women's average and spread aren't quite as high (average: 13.79 vs 19.21), and the men's average has increased slightly (6.21 vs 5.29).

If you take the ratio of the averages, the women tweet 2.15 times as much as the men. But maybe I just follow particularly chatty women..

Here's treemap (ManyEyes), which should give you a better idea of the gender balance (boxes sized by tweet rate)

Specifically, the graphic above is 62.5% purple (female).

Data here.


Where in the World Are My Followers?

The site I used last time doesn't seem to exist anymore. So I'm using MapMyFollowers instead. As the name suggests, these are my followers, rather than just the people I follow. Nonetheless..

Mostly in the UK and the US. As you'd probably expect.

I will point out though, some of the locations are a little suspect. Some people haven't made their location available so aren't included, and others seem to be in countries they couldn't possibly be in. But it's the best we can do.

Here's a zoom in on the UK

What Do I Tweet?

Made with Wordle, with data from TweetStats.

Words are sized by how often I tweet them; and by extension, @usernames are sized by how often I tweet those people.

In fact, here are the people I 'mention' the most (TweetStats)

Couldn't get a good source on who @replies me. That was one of the things Twoolr used to do..


When Do I Tweet?

Twoolr used to be awesome for Twitter statistics. But sadly, when they left beta, they started charging. And their free service went to shit. Luckily, I found TweetStats. Weirdly, it doesn't need you to log-in or anything, but somehow it can pull data on (nearly) all your tweets - beyond the 3,200 limit. Strange.

Here's some more graphs

Basically, I tweet most on a Friday and Saturday, and at around 1-2pm.

And I've never tweeted at 5am. But that's probably because I'm always asleep at 5am

Except that one time I got really drunk. (SleepBot)


How Much Do I Tweet?

This is another one I used to go to Twoolr for. And, to be fair, I still could. But that only goes as far back as April '10, and its graphics aren't as clear. Here's TweetStats again

Like I said before, I didn't tweet much in my first year. In fact, I only posted 36 tweets in all of 2009.

Now, the one problem with TweetStats is that 5 month gap in 2010. Why is this significant? Well, I was definitely tweeting during that time. In fact, by my estimates, over those 5 months I posted 5,724 tweets (~37tweets/day). So those 5 months account for 43% of all my tweets.

See, the thing is, in 2010, I was out of university, single, and unemployed. I posted a total 8,823 tweets - 24tweets/day. Since I've been back at university, that number's dropped to 11tweets/day.

That lull in Summer 2011 was when I was spending all my time on Tumblr and watching classic Doctor Who. Incidentally, I haven't posted on Tumblr since the start of September '11. It's terribly addictive, you see. I wouldn't recommend it; unless you're addicted to Doctor Who and Sherlock, and have lots of time on your hands..


So yeah.


Oatzy.


[Self-indulgent statistics, and pretty illustrations.]

Friend Network Evolution

Back in February 2009, I created my Twitter account, upon the insistence of my then-girlfriend. I didn't get it. Back then, Facebook was where it was at, I didn't really get Twitter's appeal. I was pretty much just following the handful of people I knew in real life, and Stephen Fry.

So I didn't use it much. I'd pop up every now and then, post a couple tweets and give up on it again. At one point, I even developed an irrational dislike of it - whenever I saw a site had a "follow us on Twitter" button, it irked me for some reason.

But at some point, towards the end of 2009/early 2010, I gave it yet another try. I don't know why. And even when I started using it, I was resistant; still half-heartedly hating it. But what was different this time, is I started chatting with people, and I was introduced to new people.

People who don't get Twitter think it's just that thing where you can tell people when you're eating a sandwich. It's not. It's the people that make Twitter. (Tweens and arseholes notwithstanding.)

But I'm going off on a tangent.


By August 2010, I was well into Twitter - I was posting around 30 tweets per day, and I had around 30 friends*. And back then, I decided I wanted to see what my friends network looked like. So I broke out Python and the Twitter API, I pulled data, and I made the graph. Here's an updated version of it.

[click to embiggen]

Fairly small, and tidy, and relatively uncomplicated. The bulk on the right is the people I knew in real life (from school, etc.) with a few strands of new acquaintances. Note how tightly packed and interconnected they are. To the left is mostly people I met through Twitter - and in particular, through PkmnTrainerJ.

(In case you hadn't figured it out, the node and label sizes are proportional to number of connections.)

By December 2010, I decided to have a look again.

Again, this is an update of the version I originally posted; and in this case, I've tried to arrange it so that key people stay in approximately the same place.

So you still vaguely have that left-right divide, but now there's much more mixing in the middle. I'd made some new friends, but more interesting is the people who were already in the graph who formed new connections with others in my graph.

I'd also like to draw your attention to shinelikestars_ (formerly shinelikestars6) - take a look at the previous graph, can you spot him? From 2 shared connections to 8 in the space of two months. I don't think there's any sort of point I'm trying to make here. I'm just pointing it out 'cause it's interesting.


And for the next year and a half I didn't do any data collecting. It became too labourious - Twitter changed its API, so that my old code didn't work, and I had to do everything by hand.

So, the latest graph was March 2011 (technical details below). As you can imagine, a lot can happen in a year and a half.

First of all, the new people add, and the old people removed. But more importantly, look how much tighter, and how much more 'segmented' the graph is.

There are now three major groups, loosely centred on the three most connected of my friends.

On the far right are, again, the people I knew in real life. In particular, note how little that group has changed since the first graph.

In the middle, we have 'Shiney's People' - people I was introduced to by shinelikestars_. And on the left are the people I was introduced to by PkmnTrainerJ.

The smaller groups circled in red are cliques - smaller subgroups that, at least from my point of view, form their own little groupings, where (almost) everyone is interconnected. The bottom left 'clique', for example, is my parents and big sister.

And I suspect, if you were to extend the graph beyond my network, you would find that those cliques are just parts of larger interconnected groups.

In case you were wondering, PkmnTrainerJ and SallyBembridge are most connected, both with degree 14. shinelikestars_ is next most, with degree 10.

Notable disappearing nodes - Benjidoom, who deleted his account, then created a new, private one (benjirino); and AimlessAmy, who is a long story.

I should also point out that the people I follow who aren't friends with anyone else in my network do not appear in the pictured graphs. Not that they aren't as cool, they just don't join onto the graph.

* I use friend here to mean people who I follow and who follow me back. Though I would probably consider all the people in my current network (including those not pictured) friends to some degree.


Technical stuff

You can read details on how I collected the data before, in the previous blogs. But, as I say, those methods don't work anymore.

For this run, I read up on the API, and found some bits that don't need authentication to grab and manipulate.

First, you can grab a list of a user's friends with this URL

https://api.twitter.com/1/friends/ids.xml?screen_name=<username>

This will give you a list of the friends ID numbers, so you also need to use this to grab usernames

https://api.twitter.com/1/users/lookup.xml?user_id=<idnumber>

There is also a URL to check if a user follows another user

https://api.twitter.com/1/friendships/exists.xml?user_id_a=<idnumber1>&user_id_b=<idnumber2>

Which works through the browser, but I couldn't get to work in my code. So in place, I used the site DoesFollow.com; partly because it uses the URL scheme  

DoesFollow.com/user1/user2.

Which is very convenient. Though I do worry all the requests might be putting strain on that site's server.

So, putting all that together with a bit of Python, you get something like this.


A few important points:

1) It will take a while to run. I have ~50 friends, and it took well over an hour to pull all the data. In terms of computational complexity, it's O(n^2), but each of those operations takes a significant amount of time.

2) Twitter has an API limit of 150 requests per hour. The number of API requests the code will make is ~ the number of friends being looked up. I think. Which means, if you have more than 100 or so friends, this code probably won't work. Sorry. There might be a way around it, but I don't know how.

3) Obviously, this doesn't work on protected accounts. So for those people you will have to grab data by hand. Though it's not too bad for a small enough number of people.

If you do want to use the code, I've made it so you just have to change the username at the top, and run it. You will need to install Python though.

For creating the graphs, I previously use ManyEyes. But I moved to using Gephi, because it allows for more customising. The output from the code is a text file with a list of name pairs, which you can import directly into Gephi. It will build the graph for you, and then you're free to play as you like.


Aaand... Yeah, I think that's about it.


Oatzy.


[shinelikestars6 lost his red circle, on account of he isn't my nemesis anymore.]

Christmas Eve

The run up to Christmas is over, and hopefully everyone has their Christmas shopping done. So now seems like as good a time as any to look at what the crowds are doing:

Now that is interesting. I think it is, anyway.

So first of all, the weekday spikes. It seems like a significant number of people left their Christmas shopping to the last week. Now fair enough if they've only just finished work/university/whatever.

Notice also the general week-on-week trend for the weekdays.

But more importantly than all that, look at today - Christmas Eve.


Anti-Crowds

Everyone 'knows' that going shopping on Christmas Eve is suicidal. It's a well known cliché. But that's the thing - everyone thinks it's going to be insanely busy, so a lot of people avoid shopping centres.

But then, this means the shopping centres end up practically deserted (by Christmas standards). And it's not necessarily the result of what I mentioned last time - I was out there, and I saw the lack of crowds.

It's an interesting, and previously studied phenomenon.

I won't go into too much detail, cause it's past midnight on Christmas Eve. But if you're interested in this effect, and in this sort of thing in general, I would suggest reading up on Complexity Theory. In particular, I'd recommend this book, which covers this exact subject in one of the early chapters.


Of course, if we were looking at supermarkets, that would be a different story..


Oatzy.


[Merry Christmas!]

Sorting DVDs

So there are plenty of ways to arrange your DVDs, if indeed you chose to arrange them at all. The most popular one would probably be alphabetically. Alternatives may include arranging by release date, by director, actor, genre..

At one point there was some logic to the arrangement of my own DVD. But as I got more DVDs and less space, it mostly devolved into piles, arranged roughly based on the order they were bought in, and which were watched most recently.

If I ever get time, I will re-sort them.


I accept that alphabetical may be considered 'best'. In particular, if you have a significantly large collection, it can be the most efficient approach, and makes locating any given film much easier.

Now, ordering things alphabetically is usually considered quintessentially 'OCD'/fastidious behaviour. Though there is dispute over whether liking your DVDs (and things in general) to be in order really is, or should be, considered 'abnormal'.

My point is, I could do much worse.


First of all, I think, in general, films by the same director should be kept together; particularly when it's a notable director, say, Tarantino, Kubrick, Burton.. So you could group and sort groups alphabetically by director.

I would say that films of similar genre/theme/styles should be kept close as well - noting that films by a given director will generally stay close together when this criterion is applied.

And while you're at it, why not take into consideration: actors, writers, based on works by, producers, scored by.. Basically, there are a lot of potential connections which may be considered.


So I'd like to put forward two approaches:-



1) Salesman Sort

For this approach we take into consideration 'most meaningful connections' between films, and based on that, attempt to determine which films most belong together.

So, for a given set of films, we build a network graph where pairs of films are connected if they share a common director, actors, theme, etc.

Doing this for Tim Burton films, based on actors only, will give something like this

[NB/ There may be connections missing.]

Or like this without the actor nodes

The connections between films are then weighted based on how 'meaningful' they are.

For example, Moon and American Beauty both star Kevin Spacey. Fight Club and Choke, on the other hand, have no actors in common, but were both based on books by Chuck Palahniuk. I would argue that the connection in the latter case is more meaningful - and so should get a higher weighting - than that of the former.


Now, the trick is to find a way of translating this graph into an arrangement of films. It turns out, this is as 'simple' as running a Traveling Salesman algorithm on the graph.

The traveling salesman works like this - find a path around a graph which visits every node exactly once, while minimising the distance traveled.

In our case, we actually want to find a path which (effectively) maximises 'distance', since that will lead to the more significant connections being chosen by preference.

In the above graph, the connections haven't been weighted, so we can pick any path - for example

But ideally, the connections would be weighted first so that the path (and by extension, arrangement) chosen is more meaningful.

Once a path is found, this is turned into an arrangement by simply looking at the order in which the nodes (films) are visited.


The biggest problem with this approach is forming the graph in the first place. One possible solution is to write a program which can pull details from, say, imdb to build connection. Then you'd also need to come up with some system for weighting - which may vary from person to person, depending on their particular preferences.. So it's tricky.

By comparison, the Traveling Salesman part is relatively straight forward, given that it already has well establish (if potentially slow) algorithms for solution.

This approach can also throw up some eccentricities. For example, films by a common director may be split up by a film which has few other connection elsewhere in the graph. This is why I would advise 'fine tuning' by hand.

Similarly, it's possible that the addition of new DVDs to the collection may lead to a major re-shuffle being required. Obviously, how major or minor the re-arrangement depends on how well the film fits in with your pre-existing collection.



2) Hierarchical Grouping and Associative Sorting

This is actually the approach I started out with, before it went to shit.

You might start by grouping by director. Then you might group directors by genre/theme/style. And within the bigger director groups, you might sub-group by actor. And so on..

In particular, the 'hierarchy' is constructed so that some groupings get priority over others. For example, films with the same actor might be split up when those by the same director need to be kept together. (This will depend on how you chose to structure your hierarchy).

Then, within and amongst, DVDs and groups can be arranged according to alphabet, release date, genre, .., even by colour of cover. This is where the 'associative' part comes in. Ultimately, it can come down to how your own demented logic associates and puts things together.

When I was sorting mine, I did end up with some fairly esoteric, and sometimes laboured groupings and connections in places. But you can see some overall logic in it - e.g.

Nightmare Before Christmas / ... / Sweeney Todd / From Hell / ... / V for Vendetta / ... / X-Men..

In this case - Tim Burton, Johnny Depp, Alan Moore, Graphic Novels, and so on. Note that there is overlapping between adjacent groups. They were then sub-sorted so as to be grouped by theme, and so that they formed a natural thematic progression from one group to the next (as much as possible).



Or if you prefer, you could just arrange them alphabetically. Your call..



Oatzy.


[To be honest, I wouldn't recommend either.]

Playing with Pac-Man

What the Puck?

For those unfamiliar, Pac-Man is an old arcade game, where you play as a cheese pizza trying to collect pellets while being chased round a maze by four whimsically named ghosts. Although really, if you are unfamiliar with Pac-Man, there's something wrong with you. Anyway, you can have a play online here.

The four ghost are Blinky, Pinky, Inky, and Clyde. For a good explanation of the ghosts' behaviours, here's a post from the tragically short-lived 'Game Internals' blog.

tl;dr Blinky chases, Pinky ambushes, Inky teams up with Blinky, and Clyde does pretty much whatever the fuck he wants. But really, you should read the article.

And as for the origin of the name, I'll let Scott Pilgrim explain. Or if you prefer to read, wikipedia.


Wakking Round in Circles

Graph Theory is a fantastic area of maths. Graph Theory can find you the shortest route, help you get out of a maze, tells you how to colour a map so no adjoining regions are of the same colour, to reconstruct DNA fragments, and help you find the best route for sight-seeing. Among many other things.

But sadly graph theory tends to be covered more in Computer Science courses than Maths courses. So for myself, i have to be content with books and the internet. Not that I let such thing hold me back.


So the question is this - Find the optimal route around the Pac-Man maze

What we want to do is find a route around the maze while collects every pellet. Or in graph theory terms, a route which travels along every edge at least once.

First of all, we need to turn the maze into a network graph. For this, we place a node at each junction, and join pairs of nodes according to whether or not there is a direct route between the pair.

So here's what the maze looks like, beside what the graph of that maze looks like.

The blue edges are the ones with pellets. The red edges are the ones without pellets, which you don't necessarily have to visit.

And we can assign to each edge a 'weight' - i.e. the distance (in grid squares) between the pairs of nodes

Now, first of all, we note that there are a lot of node where an odd number of edges meet (with odd degree). What this means is that the graph is not Eulerian - what that means is, there doesn't exist a route around the graph which visits each edge exactly once.

Which means that we will definitely have to travel along some paths more than once.


So the optimal path is going to be the one which minimises the total distance traveled. This is an example of the Chinese Postman Problem, and fortunately, there is an algorithm for finding the shortest route.

Without going into too much detail, what you do is pair up odd nodes, and find the shortest paths between them (using Dijkstra's Algorithm). This makes the graph Eulerian, i.e. so that a route that visits each edge at least once exists.

So if we take the bottom corner as an example, there are four node of odd degree (green).

By finding the shortest paths between pairs of odd nodes (red), we can make this mini-graph Eulerian - i.e. so all nodes have even degree. This means we can find the optimal tour around the graph (right). In this case we have to travel an additional 12 units.

Of course, it gets more complicated when you're working with the full Pac-Man graph.

When there are more than two nodes of odd degree, you also have to find the combination of pairings which minimises the total tour size. For an idea of scale, there are 20 odd nodes in the Pac-Man graph. That means there are 654,729,075 pair combinations to check and compare. And you have to run Dijkstra's algorithm 10 times for each of those permutations. It adds up.


So instead, I took the essence of the algorithm and constructed a route by hand. This is not necessarily the optimal route. For this route, you have to travel an extra 60 units - including 9 units along a path segment that doesn't contain any pellets.

There are other paths around the maze which cover (and recover) the same same ground as the above solution, and others that double back over different ground, but that add up to the same distance.

One constraint, in the case of Pac-Man, is that the path has to start at the point near the bottom of the maze, where Pac-Man starts in the game.

But also, it doesn't matter where the tour finishes (where as, the Chinese Postman starts and finishes at the same point). This means modifications to the 'optimal' solution may be possible/required.

In the bottom-corner example, we can eliminate some of the extra paths (up to 9 units worth) if we don't care where we end up.


If I ever get around to programming and running the proper algorithm, I'll let you know what the 'proper' solution is. And if you can find a better solution, let me know.


Of course what I haven't taken into account is the fact that, as you're making your way around the maze, you're also trying to avoid ghosts. I'll be honest, this path finding was more of an intellectual exercise than anything practical. You can find some strategic tips here.


This Maze Ain't Big Enough For the Both of Us.

If you follow me on Twitter, you may have already read about this - in a dream I formulated a multiplayer version of Pac-Man. But weird, subconscious machinations aside..

I looked it up on wikipedia, and there was already a multiplayer Pac-Man - Pac-Man Vs. But in that game you have one player playing as Pac-Man, and any additional players as ghosts. The aim is for the Pac-Man player to collect pellets and for ghost players to stop them. My idea is better.

First of all, you'd probably need to make the maze bigger. Each player plays as a Pac-Man, and like the normal game, their aim is to collect the most points, while trying to avoid ghosts. The game introduces a new special pellet which lets you cannibalise an opponent Pac-Man (much like the pellet that lets you eat ghosts).

Each player starts with two lives. If they lose both their lives they become a ghost. As a ghost, other ghosts can't hurt you, but you can't collect any pellets. If you catch an opponent Pac-Man, you steal one of their lives (becoming a 'living' Pac-Man again, with one life). If an opponent Pac-Man gets one of the special ghost pellets, they can eat a ghost opponent, killing them for good.

The game ends when all the pellets are collected or when all players are ghosts/dead. The winner is the player with the most points.

Or something like that.

If only I have the know how to make a real, playable version. But, hey, if there happens to be anyone out there reading this who could make it, please do..


Oatzy.

Su Doku Solver

Cold Hard Logic

Let's be frank, Su Doku solvers are dime a dozen. My favourite is the one in Google Goggles - you point your camera at a puzzle and it uses OCR to interpret it, then solves it for you. None of that faffing with inputting the puzzle by hand. Anyway.

At the most basic level, computers run on maths and logic. So logic puzzles should be easy for computers to solve - it's just following a collection of logical rules. No creative thinking required.

The problem are,

1) Inputting a problem in a form that the computer can parse (understand)
2) Translating the logical rules into a form the computer can apply
3) Applying said rules to a given input problem to find its solution.

Here's the main puzzle I'll be using as the example for this post [source]. Feel free to try and solve it yourself before continuing (it should be easy).

The Rules

So what are the rules? In the traditional version you're presented with a 9x9 grid, with some numbers already filled in. The idea is to enter into the grid the numbers 1-9, so that each number appears only once in each row, column, or box (3x3 square).

So that's fairly straight forward. But in that particular form, the rules are really only good for checking if your solution is right.


Brute Force

This can be use in a brute-force approach to solving, e.g.

1) Stick numbers in empty squares at random
2) If any of the numbers break the rules, try again
3) Repeat until the right solution is found.

But that's incredibly inefficient and inelegant, and certainly not the way it's solved by people in the real world.

As an example, say our placement technique is this - take the numbers missing from each row, and just shuffle them around within their given row.

[There are probably better brute-force methods.]

If we use this approach on the puzzle above, there are ~4.95E26 possible number placements (permutations), of which only one is correct. Say our computer can check 1 billion solutions per second, it would take 16 billion years to solve. Which is about 2 billion years longer than the current age of the universe.

As a ball park estimate, the general formula for the number of permutations for a grid of side n is given by -> ((n-a)!)^n  - Where a is the average number of numbers already placed in each row.

If, for example, we try to solve a 16-grid with a=8 (half the numbers already placed), then the number of possible permutations is a mind-meltingly inconceivable 4.88x10^73. At 1 billion checks per second, that would take 1.5x10^57 years to solve - 1 billionth the lifespan of a black hole with the mass of the sun (according to wikipedia).

This is an example of a non-polynomial time (NP) algorithm. More on that later.


Rewriting the Rules

The rules can be re-interpreted and applied in two fundamental ways

1) Which is the only square this number can appear in?

That is, a particular number has to go in one particular square, because if you try to put it in any other square in that row (or column, or box) it will break the rules.

This is the most common approach in real world solving - that is, "three can't go in that row, or those columns because they already have threes in them, so it must go there" sort of thing.

2) What is the only number that can go in this square?

That is, if every other number already appears in the same row, column, or box as a given square, then that square can only be one particular number.

This is most obvious in the case where every other number in a given row is already filled in, but can also be used by considering all the rows, columns and boxes a square belongs to.

This tends to be required more in the harder puzzles; you could probably solve the above puzzle by Rule One alone.


Setting Up The Problem

First of all, we create our grid. We can refer to each square in the grid by a sort of coordinate - (i,j) - with the square in the top left corner being (0,0) and the square in the bottom right being (8,8)

We reference Row i as the set {(i,j) : j in [0,8]} and Column j as {(j,i) : j in [0,8]}

For boxes, we note that the index for the top-left square of each box are multiples of 3 - (0,0) (0,3) (0,6) (3,0) etc. So, Box (m,n) is given as {(3m+i,3n+j) : i,j in [0,2]} for m,n in [0,2]

So from this we can, for example, check the correctness of a puzzle (by rows) like this:

for i in range(0,9):
    for j in range(0,8):
        for k in range(j+1,9):
            if Grid[i][j] == Grid[i][k]:
                return "incorrect puzzle"

Checking columns and boxes works similarly.


If we have a fancy GUI, then inputting and parsing the grid is pretty straight forward. But we don't. So instead, we input the puzzle as one long string -> puzzle = "???36?9???2?.."

The first row is given by the characters (numbers) numbered [0,..,8], the second row is [9,..,17], and so on. In general, row i is the set of characters with index [9i,..,9i+j,...,9i+8]. 

Parsing our puzzle into the Grid works like this then:

for i in range(0, 9):

    for j in range(0, 9):

        Grid[i][j] = puzzle[9i+j]

And so on..


Applying the Rules

Now, if you've done Su Dokus, you might be familiar with the technique of filling each square with the numbers one to nine and eliminating numbers as appropriate. That's basically the bulk of how this solver works:

1) Assign to each empty square ("?") the set [1,...,9]

2) For each number in a given square's set:
    a) Check to see if that number is already fixed in another square in the same row, column, or box as the square in question. If so, eliminate the number from that square's set.

3) Repeat for all squares in the grid

From there, we can apply Rule Two:

4) For each square:
    a) if that square's set contains only one number, fix that square's value accordingly.

5) Go back to (2). Repeat until no more squares can be fixed.

You can actually created a shortcut for this - create a collection of sets for each row (etc.), which contain the values already fixed in that row. That way, instead of checking every square along each row for fixed values, you just check in that row's set. (Trust me, it's easier.)

Applying Rule One is easy as looking along each row (or column, or box) to see if a given number appears in only one of the squares.

Or more technically,

1) For a given row (etc), for each number 1-9:
    a) count how many times that number appears in square sets in that row
    b) if a number's count equals 1, fix the value of the square it appears in accordingly.

2) If you fix any new squares this way, go back to (2) to see if that will allow you to set any more squares.

You then just loop through rules One and Two until the puzzle is (hopefully) solved.


One More 'Rule'

In fact, this is just Rule Two, but with an added 'quirk'.

Here's what happens if you apply the method, so far, to a more difficult puzzle

This is where the program gets stuck. What do you do from here? If we focus on the bottom-right corner box

Notice there are no squares that can take only one value, and no values that only appear in one of the squares.

But look on that bottom row - the circled boxes can only take the values 3 or 5. What this means is that 3 and 5 can't go in any other of the squares in that box. So we eliminate 3s and 5s from the other squares in that box. Similarly for the 1/6 squares in the middle.

We now have the square in the top-right of the box that can only be 8, and the middle-right that can only be 9. So we fix those values. And from there, it's pretty straight forward to solve the rest - going back to looping through Rules Two and One.

Not only is it tricky to spot in real world solving, it's also tricky to translate it into computer logic. It mostly involves looking for pairs of squares in a box (etc.) which have matching sets of size two (or triplets, size 3, or etc.). Fortunately, this sort of thing doesn't come up often.


A Note on P versus NP

So as mentioned above, it's easy enough to apply the standard rules (as states) to check if a solution is correct - you just check to make sure no number appears more than once in any given row, column, or box.

It turns out, checking the correctness of a puzzle can be done in polynomial time (fast). For a grid of side n, the time required to check a solution* is given by -> 3(n^3 - n)/2

..Multiplied by the amount of time it takes a computer to work out if 2 numbers are equal or not (call this time t). So for a 9-grid, that time is 972t.

For a grid of side n=100, the time is ~1.5million t. Which on a modern computer is peanuts. For example, if our hypothetical computer can check 1 billion 9-grids in one second, then it can check 650,000 100-grids in a second.

By comparison, actually solving the puzzle - by the method outlined about, and by all other known methods - is done in non-polynomial time.

What this means, is that if you apply this algorithm to a larger grid - say, a 25x25, or a 36x36 grid - then the amount of time it will take to solve the puzzle increases rapidly (exponentially), to the point where a puzzle couldn't be solve in the lifetime of the universe.

But, since checking the puzzle for correctness is polynomial, even if the puzzle took longer than the life of the universe to solve, you could still check to see if the solution is correct (that no number appears more than once in each row, etc) in a reasonable amount of time.

As mentioned above, the brute-force method outlined is non-polynomial (NP). Notice that it takes catastrophically longer - 70 orders of magnitude - to solve a 16-grid by brute-force, than it takes to check the solution to a, much larger, 100-grid.

Admittedly, I don't know what the time function is for the method outlined above. But suffice it to say, it's more efficient than the brute-force, but still non-polynomial.

What P versus NP asks, then, is

if the solution to a problem can be checked in polynomial time (quickly), then does there exist an algorithm that can solve the problem in polynomial time?

At present, this is one of the great unsolved questions of mathematics and computer science, and a proof of whether or not P=NP will earn its discoverer $1million...


Where's The Code?

You'll probably have noticed, I've given a general, hand-wavy outline of how a program would work, and only given odd snippets of code.

I did write a solver in Python a few years back. I'd taken a Java programming course in my first year at university, and when the lecturer discussed a tic-tac-toe (naughts and crosses) playing program, it gave me the idea of how to represent a grid in a way a computer can parse. It also made me realise that there is actually a point to object-oriented programming.

Anyway, long story short, I wrote the solver 3 years ago. It's kind of sloppy and inelegant. And it can't handle the 'tricky' puzzles - although, oddly enough, according to my notebook, I had worked out a way of implementing it, but apparently never did.

Or to put it another way, it works, but compared to the myriad others out there, it's nothing special.

If you're interested, as I mentioned at the beginning there are plenty of other solvers out there. They might not work according to the methods discussed in this post. But you should at least have an idea of how one might work, now.

And as a final note, these methods can also be used for hand-solving. It's generally not necessary to be so rigidly systematic, though. It's easier for humans to pick out number placements at a glace, without having to go through the whole set-and-elimination approach.


In Case You Were Interested

Here's the solution to the Su Doku at the top of the page

You're on your own with finishing the other ('difficult') one..


Oatzy.