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.]

So What Was the Best Day To Go Shopping?

Alright, let's be done with this.

Just a quick reminder - what I did was collect Foursquare check-in data for various shopping centres around the UK, in the hope that the data might show something interesting.

Previous blog posts on this data collecting - Best Day to Go Shopping, Panic Saturday, Christmas Eve.

Anyway, I've been collecting data for over 3 months now. And that seems like quite enough.

Here's a graph of (normalised) averaged check-ins on each day of the week for 4 periods:

DecAv (blue) is 21st Nov 2011 to 18th Dec 2011
ChrAv (grey) is 19th Dec 2011 to 1st Jan 2012
JanAv (orange) is 5th Jan 2012 to 2nd Feb 2012
FebAv (green) is 6th Feb 2012 to 4th Mar 2012

Aside from the two weeks either side of Christmas (grey) - when people, apparently, did their shopping more midweek - the pattern is basically the same.

For further clarity, here's the average of those three averages (excluding Christmas)

And here is the order of days, from least to most busy ('relative busyness' in brackets):

1) Wednesday (1.00)
2) Monday (1.01)
3) Tuesday (1.03)
4) Thursday (1.11)
5) Sunday (1.15)
6) Friday (1.24)
7) Saturday (1.78)

Note that the differences between Monday, Tuesday, and Wednesday are not statistically significant - they're essentially the same, and are likely to be as busy as each other/not noticeably different.

So, to answer the title question - Monday, Tuesday, and Wednesday are the best days to go shopping. At least, in as much as they're the days shopping centres are likely to be least busy. And, as you'd expect, Saturday is, by far, the worst/most busy.

And the last thing to point out is that these are the averages over 20 shopping centres for a ~3 month period - numbers for specific locations, and at different times (eg holidays) are likely to deviate from the averages.

And, basically, that's that.

If you're interested, you can see the raw check-in data here.


Oatzy.


[That was definitely worth the effort.]

Where are the Carriages?

<rant>

So it's around 9am, and you're waiting for a train. The trains in your area are a bit scummy, but whatever, you can't drive, and you've got to get to work/uni somehow. It's pretty busy, what with it being 9am, and when the train finally pulls up.. it's a single carriage.

Now a single car has around 50 seats, and this train is packed tight, with people standing in the aisles and the doorways, being forced to get intimate. And with everyone on board the conductor can barely get through the door. There are clearly enough people on this train to fill two cars, with people still having to stand.

So what gives? You're pretty pissed about having to stand for half an hour, and you've been inadvertently touched by strangers in ways you're not comfortable with. So you get your complaining hat on, and you turn to the internet to unleash the fury.

The train company's website directs you to their Twitter feed, where a poor public relations person is taking a barrage of vitriol from other angry commuters, while doing their best to remain polite and professional.

Several other people have already made your complaint, but all they're getting in return is "Apologies we try to avoid this where possible", or that the short trains were "due to operational reasons". And that's not really a satisfying response. You're not even sure it means anything.

</rant>


So Where Are The Carriages?

Disclaimer: I have no idea how the train company actually operates. I just like to write blogs about applied maths.

Here's the setup - you're in charge of logistics for the train company. You have a fixed number of trains/cars, and, for each day, a list of services and expected numbers of passengers.

How do you apportion the carriages between the services?

Obviously, every service needs at least one car, and services with more passengers need more cars.

So if you had, for example, three services with 50, 100, and 150 passengers respectively, and 6 cars, then it's easy to divvy them up - one for the first, two for the second, and three for the third.

But in general, it won't be possible to divide up the cars exactly like that; so what do you do about remainders?

This is actually similar to the problem of apportioning parliamentary seats between states in the US.

Currently there are 435 seats in the House of Representatives, which need to be shared out between the 50 states according to each state's population - the idea being that each seat should represent roughly the same number of voters.

There are various methods for doing this, but I'm only going to go over two of them.


The Hamilton method

Hamilton's Method is the easiest and most intuitive.

Say you've got only two services - service A has 85 passengers, service B has 115 passengers (200 passengers total). And you happen to have 4 carriages - a total 200 seats. So seats for everyone! Except service A needs 1.7 cars, and service B needs 2.3 cars. And you can't divide a car into two chunks.

But for starters, you can give one car to service A (50 seats), and two to service B (100 seats). So what about the fourth? Regardless of which service you give it to, some people are going to end up having to stand. So what you want to do is minimise that number.

For service A, 35 people need a seat. For service B, 15 people need a seat. So it makes sense to give the last car to service A. 15 people still have to stand, but - short of building more cars - there's really nothing you can do about that.

This is also known as the largest remainder method.

What if the passenger numbers were 75 and 125? Well in that case, I guess it would have to be a judgement call.

Anyway, that's the basic idea of the Hamilton method - divide up the cars as far as you can, then give the remaining car(s) to the service(s) which 'need them most'.

Things get trickier when you're dealing with larger numbers of passengers and cars, but ultimately it's pretty straight-forward.


The Huntington-Hill Method

Where trains differ from apportioning of parliamentary seats, is that a carriage has a fixed capacity, whereas the number of people a seat can represent is free to change.

And this means that you won't encounter some of the 'quirks' that arise from the Hamilton method - such as the Alabama Paradox (where increasing the total number of seats can mean a state losing seats), or the Population Paradox (where increasing a state's population can result in that state losing seats).

[You won't encounter them, but they're worth mentioning 'cause they're pretty cool.]

Huntington-Hill's Method - the one currently used by the House of Representatives - is, generally, a more powerful method than Hamilton's, and isn't susceptible to the various paradoxes. Another benefit is that it can be set up to guarantee that each state will get at least one seat.

It works by assigning seats, one by one, based on each state's 'priority quotient' - itself based on the state's population, and a 'modified divisor' based on the number of seats already allocated to that state.

But one advantage Hamilton's Method has over HHM, is that it will always give each service its ideal number of cars, either rounded up of down to the nearest whole number. So if a service's ideal number is 3.67, then Hamilton's method will assign either 3 or 4 cars to that service.

HHM, on the other hand, can 'violate quota' - that is, it can result in a given service being assigned more or fewer cars than it's ideal number (e.g. the 3.67 service might end up with only 2 cars). But this problem only occurs when the number of cars is fixed prior to apportioning. And sadly, it usually is.


As an aside, it turns out it's impossible to find a 'perfect' method of apportioning - one with neither paradoxes nor quota violating. Incidentally, the mathematical theory surrounding voting is quite fascinating. You know, if you're into that sort of thing.


Unfortunately..

Either method would work perfectly well. The problem is, while rounding up or down to the nearest car may seem trivial, the 50 seats that that one car represents can be a significant gain/loss for a service.

The lack of precise information can cause problems as well. You can only estimate how many passengers a given service will have in advance, and if you under-estimate, people are gonna be pretty pissed.

And on top of that, the numbers have to be recalculated from time to time as passenger numbers change..

Basically, getting the number of cars right can be tricky.


Of course, this all assumes that Northern Rail (or whatever company) has enough carriages to adequately satisfy its needs in the first place. Some how I doubt that's the case.

So ideally, NR needs to work out how many cars it actually needs, and build them. But I can't see that happening. And even if it did happen, it'd probably mean higher fares. And fares are pretty bad as they are.

Really, though, NR could do with a complete makeover just in general, given how shitty it is. Seriously, you should see the difference between them and the London Midland service. Ridiculous.

Incidentally, I also have strong feelings about the buses; don't even get me started. Trams are alright though - one every 10mins, seldom short of seats, sufficient leg-room.. bliss.


tl;dr - Where are the carriages, then? As it turns out, it's probably just that they don't have enough to go around.

This is what we get for privatising the trains...


Oatzy.


[My complaining hat is a trilby. I like to look bad-ass while I'm complaining.]

A Problem With Puzzles

Here's a puzzle, tweeted by Aetherling

Have a go at it yourself. Solution below.

You see these sorts of puzzle every now and again. And there are usually common 'tricks' to them.

My first instinct was to add the digits. Nothing. Modulus? Nope. Sum and modulus, multiply digits, square, divide? Nope.

So, what?

For some reason, I decided I was going to try some algebra - ignore the fact that the left-hand sides of the equations are numbers, and treat them as variables with some unknown values. And then, add up whatever those values are to get the numbers on the right of the equations.

i.e. 9313 -> '9' + 2x'3' + '1' = 1; 1111 -> 4x'1' = 0; etc.

So from 1111=2222=3333=5555=7777=0 we get that 1,2,3,5,7 = 0

From 0000=6666=9999=4 we get that 0,6,9 = 1

And from 6855=3, 1+'8'=3 => 8=2

4 is undefined. And that makes the answer to the puzzle 2581=2.

It took me about half an hour to come up with that answer..


"If all you have is a hammer, everything looks like a nail"

That is the right answer. But the puzzle suggests that a preschooler would get the correct answer with ease. And I doubt a preschooler would do so with algebra.

So, what would a preschooler do? And why does it take 'higher educated' people so much longer?

What's the 'correct' answer? Take a look at the below

Basically, it's the number of loops in the digits on the left-hand side. This had to be pointed out to me by Aerliss.

But here's the interesting thing - take a look at the values I assigned to the number.

I got to the same answer, and effectively 'derived' the number of loops in the digits, without realising that that's what I was doing.


Source on the subheading quote - Maslow's Hammer.

It's not a perfect analogy, but the idea is this - the more mathematical training you have, the more techniques you'll be trying to use to solve the problem; possibly causing you to miss the 'obvious' answer. As, indeed, I did.

In this analogy, maths is the hammer.

And, strictly speaking, this puzzle isn't a maths problem - even though it's presented as if it were. And even though it can be solved using maths.


Another Problem

Here's another puzzle, recently posted on Reddit

The problem here is that the correct answer isn't known.

The 'obvious' answer (in as much as the one that most commenters came up with) was to add the four cross numbers, divide by 10, and round to the nearest whole number. In that case, the missing number is (23+20+12+3)/10 = 5.8 ~ 6 (B).

But that doesn't explain the set up - why the crosses? Are the positions of the numbers in the cross significant? And rounding is a little messy.

The most compelling proposed solution, once again, doesn't actually involve any maths:

"As far as I can tell, the answer is C: 7 [...] The formula for the number in the center is the number of unique letters shared by the top and bottom numbers as written in English plus the number of unique letters shared by the right and left numbers.."

Finite Rule Paradox

At any rate, what the comment thread shows is, in the absence of a 'true' answer, any answer is potentially correct with some valid justification. Case in point, I've just presented two different possible answers with two valid justifications.

This is an example of Wittgenstein's Finite Rule Paradox.

Stated explicitly - "This was our paradox: no course of action could be determined by a rule, because any course of action can be made out to accord with the rule"

Basically, what I described above..

There's a clearer explanation here. The topic is also a plot point in the novel (and subsequent film adaptation) The Oxford Murders; recommended if you're into maths-fueled murder mysteries.

The paradox is more apparent in 'find the next term in the sequence' puzzles.

For example, if you're given 2, 4, 8, 16 and asked what the next number is, then the obvious answer is 32 - twice the previous number/powers of two.

However, 31 is an equally valid continuation, as Marcus du Sautoy explains:

"[L]et me explain why 31 can be a perfectly legitimate way to continue the sequence 2, 4, 8, 16 ... Draw three dots on a circle and join the dots with lines. The circle gets divided into four pieces. If you now take four dots on the circle and draw all the lines between the dots then you cut the circle into eight pieces. Five dots leads to 16 pieces. But if you draw all the lines between six dots you will only get 31 pieces rather than the 32 you'd expect."

In fact, you can define a function, f(n), which satisfies the first 4 terms of the above sequence, and will give any number you like for the fifth.


The Easy Path

How is that possible? Lagrange Interpolation.

[Discussed in Professor Stewart's Hoard of Mathematical Treasures]

Lagrange interpolation applies to any (numerical) sequence of any (finite) length; so, there are infinitely many ways to continue any given sequence - and, necessarily, one cannot say with absolute certainty that a given sequence will continue in one particular way, only.

Unless the person who set the puzzle says otherwise. Because if it's their puzzle, they know what answer they're looking for. And if you try to score easy marks on an exam by citing Wittgenstein, you're probably going to fail.

Of course, Lagrange polynomials - although interesting that they exist - are likely to be the least interesting way to continue a sequence. Certainly, the equivalent Lagrange polynomial isn't as meaningful or interesting as the circle division sequence; even though they both give the same first 5 terms.

And a Lagrange polynomial will probably never be the most obvious/aesthetically pleasing solution.

"[H]e conjectured that, though in principle all answers were equally probable, there might be something engraved on the human psyche [...] which guided most people to the same place, to the answer that seemed the simplest, clearest or most satisfying. He was definitely thinking that some kind of aesthetic principle was operating a priori which only let through a few possible answers for the final choice." - The Oxford Murders, Chptr 9

Though, as seen in the Reddit puzzle, the simplest answer isn't necessarily the most correct one.


There Must Be Another Way

The important thing is, the existence of Lagrange polynomials 'proves' the Finite Rule Paradox for numerical sequences.

By the same logic, there must exist some functions, f(a,b,c,d), which satisfy the first 20 equations in the first puzzle, but give some values other than 2 for the last. Or, multiple functions which do give 2, but by different methods to the correct one.

Of course, such functions aren't likely to be easy to find. Especially when there are 20 'initial rules' to satisfy. But the fact that there are finitely many rules means it's possible.

Not that counting loops, or manipulating letters count as mathematical functions. But the point still stands.


At any rate, the important thing to remember is not to get too obsessed with the consequences of the Finite Rule Paradox. Or you may end up trying to lobotomise yourself to prove a theory.


Oatzy.


[What comes next - 3, 3, 5, 4, 4, 3, 5, 5, 4, ?]

Funny Story

So there's four of us at the pub, and we're playing the one word game. And we decide that, since this is the future, we should play a marathon game, via Twitter (complete with hashtag, #OneWordGame).

The One Word Game is where a group of people attempt to collectively tell a story, one word at a time. (Also known as Word at a Time Story).

At this point, we've been playing for about two weeks.


So what's our story? Before that, lets play a game.

Below are two 'stories' - one of them is our word-at-a-time story, the other has been randomly generated (using Markov text generation).

Which is which?

When the wizard was masturbating upon a picture of your face which is ugly he said that a giant octopus with swashbuckling offspring however walrus munched on his wardrobe handles while reciting to Steve the only one who played the harmonica case under his umpalumpa cheese tasted spectacular when dipped in French wine and peanut butter making apples with a slightly tangy bumhole that had smelly teeth and pickled onions with slices of cherry on toast. Suddenly a massive caterpillar spawned from a seed which smells of turnip. When select acorns they exploded penises all turned into a

There was no further sound other than the soft tinkle of water. But in the middle of the surface area were encrusted with hard-caked earth but the girl who was confined them to perpetual darkness. This time there would be a very narrow neck extending about an inch above the rest. Could be worth a try I think he changes his name from time to time. Since it was meant to support an entire career However I

The correct answer is, ours is the first one - probably evident from the vulgar language.

As for the second one; I've discussed Markov generators before. In the simplest case, they work by randomly picking words based on how likely they are to follow the preceding word. This particular example was generated from the first four chapters of Dirk Gently's Holistic Detective Agency (Douglas Adams) using this site.

How does this relate to our game?

Well, the game was spread out over such a period of time that, usually, I'd forgotten the story much beyond the previous few words. So, I was picking my words based on what seemed like a coherent continuation to those few. Not unlike a Markov generator.

And, you have to admit, the two make about as much sense as each other.


At any rate, the game is still on-going..


Oatzy.


[What? I never claim our story was funny..]

Simple Harmonic Sleep

So I started using SleepBot Tracker to track my sleep. This is what it's looking like so far

Basically, I'm averaging about 8 hours, except on those two days near the start where I had to get up early for exams.

Now, being a physics student, the graph reminded me of that for damped simple harmonic motion (starting from 20/01, ignoring the first 3 points). And being a crazy person, I decided to try and model my sleep as such.

So what's simple harmonic motion?

Simple harmonic motion is a type of periodic motion with a restoring force directly proportional to the the system's displacement from equilibrium.

For example, a pendulum is a simple harmonic oscillator - it has periodic motion, its equilibrium is the lowest point of the swing, and the restoring force is gravity.

Now, one could argue that sleep is SHM-like - we have some typical sleep length (equilibrium), and if we get too little sleep, then we'll tend to sleep more in response, and vice versa (restoring force). But it's a dubious analogy at best.

A damped harmonic oscillator is one with damping, which tends to reduce the amplitude of oscillations. So, like air resistance in the case of the pendulum, which eventually causes it to stop swinging.

I'm not sure what the sleep-based analogy for damping would be.


There's a standard equation for defining a (weakly) damped harmonic oscillator. It looks like this:

Where:- A0 is the initial displacement, the e bit is the decaying term, gamma is the damping coefficient (which determines how quickly the oscillations decay), cos() is the oscillating term, omega is the (damped) frequency of oscillation, t is time (in days), phi is the phase shift, and C is the equilibrium amplitude.

So working out the variables from the data, the model equation for my sleep looks something like this

And the graph looks like this

And to prove I'm not entirely crazy, here are the real values and the model values plotted together

Not a bad fit, right? [error 0.19]

In fact, you might notice the real data is still oscillating a little. But the equation outlined above tends to a constant amplitude of 8.3 (no more oscillations).

To account for this, we could add a baseline oscillation term

And fitting the data again, here's what the graph looks like

Arguably, a slightly better fit. [error 0.16]

So yeah. Basically, I'm procrastinating..


Oatzy.


[Just gotta be careful not to hit resonant sleepquency]

Gift Wrapping

In these times of austerity, one has to be economical with one's wrapping paper.

Yeah, I know, this would have been much more useful about a week ago. But I just never got around to it. And I use the word 'useful' loosely; any saving one might get from these 'techniques' will most likely be insignificant.

Nonetheless...


Rectangles

All gifts - no matter shape or size - can be wrapped with a rectangular piece of paper.

This is easily proved. However doing so may not be the neatest or most efficient approach. For example, it's easy to efficiently wrap a cuboid (book, DVD, box) with a rectangular piece of paper, it's less easy to wrap a bike (efficiently) with a single, and in this case, very large piece. However, in the case of a bike, one could use several, smaller pieces of paper for more efficient wrapping.

For a ball, one might be tempted to say that a more unusual shape - maybe a truncated icosahedral shell - would be more efficient. However, cutting out such a shape would result in lots of little slivers of waste, and would take a lot of time and effort. Instead, it's usually easier, and not greatly inefficient to just use a rectangular piece, and some creative folding and scrunching.

So here's the point - for a given gift, we can define a rectangle (or set of rectangles) which most efficiently wraps that gift.

For a cuboid of sides L(ength), W(idth), H(eight), the minimum paper would be: (H+L) by 2(H+W), with a bit extra for overlap.

For a cylinder of dimensions H(eight) and R(adius), the paper would need to be: 2PI*R by (H+2R), and a bit.

[Proof that these cuts are optimal is left as an exercise for the reader.]

For other shapes, this may be more tricky to determine, but for the sake of arguing, we will assume we know all the required rectangle's dimensions.


Bin Packing

So for a given collection of gifts to be wrapped, we have defined a set of rectangles. We now have to determine the most efficient way to cut these out from rolls of wrapping paper - i.e. a large rectangle, ~ 1m x 4m.

This is similar to solving a two-dimensional version of the Bin Packing problem.

In the Bin Packing problem, we have several bins (cuboids) of fixed dimensions, and a collection of smaller cuboidal objects. The problem is to pack the objects into as few bins a possible - i.e. find an efficient way of fitting cuboids into boxes.

The problem is NP-Hard, meaning that finding the optimal solution can take a very long time. However, there are algorithms which are fast and give adequately optimal solutions.

One, in particular, is called the First Fit algorithm, and it works something like this:

1) Sort the rectangles into size order
2) Cut out the largest pieces still in the set
2 i) If there is not enough paper left on the current roll, move on to the next/start a new roll
3) Repeat (in descending size order) until there are no more pieces left to cut.

There are also instructions for how to place the rectangles, for example first fit from bottom and right, to left and top.

This article gives a more precise description of a similar algorithm, though that one is defined for a 'roll' of non-restricted dimensions.


Realistically

That's all well and good mathematically. But in the real world, it's likely more trouble to solve the problem than the saving in paper is worth.

However, the general principle of the algorithm can be loosely applied (if indeed it isn't the approach you already use) to improve on efficiency.

In general, you can easily sight-guess which gift in going to require the largest amount of paper. And from that you can apply the First Fit algorithm.

One change I make is, cut out and wrap the largest one left, first. Then wrap the gift(s) which best fits the off-cut.

This is particularly good for rolls, where you want to unroll and use it a 'slice' at a time (rather than unrolling the whole thing).


Anyway, something to think about next time you happen to be wrapping a large number of gifts.

Even better if you can get some of that Tesco wrapping paper with the grid on the back.


Oatzy.


[No wasted paper from my wrapping this year. Just saying.]

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!]

Deal or No Deal

One of the common criticisms of Deal or No Deal (DoND) is that it's basically all just luck, and requires no skill.

Okay, so unlike most TV game-shows you don't have to know anything to play. In fact, based on knowledge/skill required to win and on average pay-out, DoND is probably the best TV show to play on - as said, you don't have to know anything to play, and once you're on the show you're guaranteed to walk away with something.

Okay, so how much you walk away with does indeed depend a lot on luck. But I would argue that it depends on luck in the same way that, for example, Blackjack (21) depends on luck. One might argue that there's no skill in Blackjack, and yet there's no denying that some people fair better at it than others. And one might say this disparity is the result of skill or strategy.

Certainly card counting (when you can get away with it) is a skill, and one which can increase your winnings.


It's How you Play the Game

Behind all the 'quirky' contestants, the blatant superstition and Noel Edmond's interesting shirts, lies a surprisingly complex game. Albeit a 'complex' game which can be played competently with little to no skill.

In fact skill only comes into it when you start trying to tip the probability scales in your favour, without relying on trinkets and 'special numbers'.

But before we start, I should probably outline the game for the sake of anyone unfamiliar:

There are 22 boxes, of which one is yours. Each box contains some unknown amount of money, ranging from 1p to £250,000.

The idea is to try and determine the value of your box by eliminating other boxes from the game. Also trying to determine the value of your box is 'The Banker', who will attempt to make offers to buy your box, and in doing so, try to make a profit for himself.

Your aim is to come out of the game with as much money as possible - ideally, either by selling your box for more than it's worth, or by keeping a box which is more valuable than any of The Banker's offers.

Still with me?


So there's actually a big game theory element in this, when it comes to dealing with The Banker. There's also a risk assessment element, wherein, based on which values have been eliminated or are still in play, you have to decide whether you should play on.

In this blog, I'm going to be focusing on the offers part of the game, and deciding when to deal. I may come back to the other elements in later blog posts.


Let's Play a Card Game

Take a standard deck of 52 cards, shuffle them, and deal 10 cards face down.

The aim of the game is to get the best card possible.

You turn the cards over one at a time. If you want to keep the card you turn over, then that's your card forever. You can't swap it for another card later. If you turn over a card you don't want to keep then it's gone forever, and you can't go back to it later.


So, for example, say you turn over the first 4 cards, and you get - 2, 9, 8, 5 - Now you could have stuck on 9, since it's a pretty good card. But there are still 6 cards felt to turn over, so you decide play on.

You turn over 2 more cards - A, Q - Since Aces are low, it seems wise to stick on the Queen, since there's only the King that's better, and only 4 cards left to turn over.

So you turn the last 4 cards over  to see how well you fared, and you get - 7, 5, K, 10.

Okay, so there was a better card than the one you ended up with, but you still came out pretty well.

Anyway, hopefully you get an idea of how the game works.


So this is ultimately a game of chance and of how much risk you're willing to take to get a potentially better card. The question is, is there a strategy for maximising your chances of getting the best possible card?

Obviously, since the King is the absolute best possible card, you might be tempted to play until you find one. But since there's no guarantee that there will be a King on the table, you risk playing to the end, only to end up stuck with the last card, which could be really crappy.


The Dating Game

In the book "How Long is a Piece of String", the author offers a variation on this game as a very simplified analogy for dating - the idea being to settle down with the best possible partner, bearing in mind that you usually won't be able to go back to dating anyone you passed on if you aren't able to find anyone better later, and that once you settle down into a relationship you stop dating, and potentially miss out on meeting someone better.

As far as the strategy goes, the author suggests turning over the first three cards as a sort of sample pool, then settling on the first card whose value exceed those of all three sample cards.

According to his probability measurements, this results in you getting the best card one time out of three. Which, apparently, is as good as you can hope to do.

So in the above example, your sample cards are 2, 9, 8. The first card after that which is greater than all those is, in fact, the Queen.

Like I said, it's not perfect. And a 1 in 3 success rate may not sound very good. But lets be clear - this is (theoretically) your absolute best strategy.


Let's Make a Deal

So ignoring the whole boxes stuff completely (I know, but stay with me here) we can reduce DoND to being a game where a contestant is presented with 7 (random) offers and is trying to decide which one (if any) to take.

And this is where the card game comes in - it's basically the same game, just with fewer offers/cards.

In fact, there are 7 offers, but if you decide to reject all those, you're stuck with the value in your box. So that's equivalent to the card game described above played with 8 cards.

So first of all, I should point out that the three card strategy from the book applies to a slightly different variation on the game I outlined. So we also have to tweak our strategy to match our tweaked game.

First of all, the book itself offers this detail - for a game with N card (choices), the sample size should be N/e, where e=2.71.. So for a game of 8 choices our sample should be 2.9 (~3).

But again, this is for a slightly different game than ours. So we'll want to check that this strategy really does apply to our game.

Thing is, there's a whole bunch of probability calculations involved in working that out. And probability calculations are a pain in the arse. So in lieu of all that, I did a Monte Carlo simulation instead.

Here's the code.

And what the code suggests, is that the best strategy is actually to pass on the first two offers - giving a success rate of about ~49%

For comparison, here's the success rates for different numbers of passes (rejected offers):

And nearly 50:50 isn't bad odds. But we do have to keep in mind that this result is for a simulation of a card game which is a simplified analogy for one element of a game show.

Your results may vary.

But the implication is this - in a simplified game of DoND, the optimal strategy is to reject the first two offers, and take the first one after that which exceed them.


Spank the Banker

Obviously, DoND, when considered as a whole, is not as simple as accepting or rejecting a series of offers. For one thing, in the real game you have more information (i.e. what values are or aren't still in play) to help inform your decisions.

But this strategy could be considered at least some improvement on the 'by the gut' approach.


So yeah. Until possibly next time..


Oatzy.


[Get it? 'Cause 'deal' can also mean 'to distribute cards'.]

Panic Saturday

Leaving it til the last Minute

So yesterday was what the tabloids called Panic Saturday - the last Saturday before Christmas (excluding Christmas eve), and the day on which everyone goes batshit crazy 'cause they've just realised, it's a week to Christmas and they haven't finished their Christmas shopping yet!

CHRISTMAS!!

So we go to our check-in data, and we can clearly see tha-

Oh.

It's actually the least busy Saturday of the last four weeks..


Or Is It?

Okay, so professional analysts probably have better metrics for measuring crowd sizes than my armchair data collecting.

So what's going on?


One theory would be that Foursquare users, generally, got their Christmas shopping done relatively early. And it's a nice thought, to think that people who obsessively log where they've been are 'more organised' when it comes to shopping.

But the more likely explanation is this - if places were that busy, and if people were that panicked, maybe they were just to busy to bother stop and check-in to Foursquare.

That's what my money is on, anyway.


And as a final point of interest, here is the updated graph for Westfield London

Notice the massive spikes on weekdays, week 4, compared to previous weeks.

Did a load of people finish work/school at the end of week 3, and only just get started on their shopping? Is it just last minute panic? In light of the point of this post, can we even trust these numbers?!

Also notice that the numbers for this particular shopping centre are quite different from the averages.


So all this kinda puts a damper on the reliability and usefulness (if indeed there ever was any) of my data and results.

Oh well.


Oatzy.


[Or the shops weren't nearly as busy as the papers claim.]

Best Day to Go Shopping

The Question

As the title suggests - which is the best (least busy) day to go shopping on?

Or more generally, how do crowds at shopping centres vary over time? Which days are busiest, or least busy? Are the shops getting busier as we get closer to Christmas? Less busy?!

It an interesting question, and one that's probably been looked into before. But still, I had an idea and I'm running with it.

[Feel free to skip straight to the results if you're not interested in statistics and the likes..]


Data Collecting

Data collection on this is tricky. Especially if you don't have legions of people to go out and actually count people. What I want to do is extract numbers with the minimum of effort.

So here's the game - Foursquare.

If you're unfamiliar, Foursquare is a 'social game', for which you 'check-in' to locations and earn points and badges accordingly. It's also good if you're an obsessive types who likes to keep track of where they've been.

So the idea is this - some subset of shoppers will be Foursquare users, who will check-in when they visit any given shopping centre. If we can extract check-in counts over a given time period, hopefully that can be used as an indicator of a place's 'busyness'. Obviously, this is flawed - but more on that below.

Right. So on the Foursquare page for a given venue, there isn't a total historical record of check-ins over time. Instead, what we have is the total number of check-ins at that location up to the time when you loaded the webpage.

What we do, then, is record that number at some fixed time every day (say, midnight). Then the number of check-ins on a given day is the difference between the total at the end of the day and the total for the end of the previous day. Easy.

In fact, to make life a little easier, I wrote this bit of code [python]. All I have to do is remember to run that every evening, and we have our data.


Sampling

There are two possible sources of sampling errors:

1) Location

If we only track one location, we have a very small sample size. That means we're subject to perturbations - for example, a major event like the Christmas lights being switched on - or just general statistical noise. Also, shopping patterns may vary across the country, or depending on how close to a city centre the centre is located, and so on.

It's actually fairly easy to overcome this. First of all, we have this list of the largest shopping centres in the UK. From that list I picked 20 locations to sample. This data can then be normalised and averaged to look for any general patterns that are (relatively) store independent.

Oh, and I should probably mention, since this data is being collected from places in the UK only, patterns may vary for different countries.


2) Users

Using Foursquare data, we're working on the assumption that as the number of shoppers increases (or decreases), the number of Foursquare check-ins will increase in proportion.

This is not necessarily the case.

First of all, we look up the Foursquare user demographics. There is no one source of definitive data on this (that I could find). But to get a general idea, there is this, based on a survey of BART travelers.

Obviously, this demographic source is for users of an American transport service, but I'm assuming it's representative of Foursquare users in general.

From this we see that the typical user is most likely male, age 25-34. Or to put it another way, women, young people, and old people are under-represented. And from my experience, it seems like women and old people are the most common shoppers on weekdays.

So this may introduce a disparity between the data and reality. But it's not one we can really do anything about (without seeking an alternative source of data). So, as long as there is a general size proportionality between shoppers and check-ins, we'll consider the data acceptable.


Results

By far, Saturday is the worst day to go shopping (in terms of crowds). But you already knew that.

So I have my data for the last 3 weeks, for 20 shopping centres across Britain. Here's the raw data, for if you're into that sort of thing.

I worked out the check-ins for each place on each day, then normalised by shopping centre - so that the total number of check-ins for each shopping centre over the three week period now adds up to 100. I then averaged these 'norms' across all shopping centres.

Here's what those results look like.

In fact, I went back and 'tidied up' the data, removing venues with less than 100 check-ins total during the recording period - since their sample sizes were maybe too small for any patterns to be statistically significant - and removed a couple of anomalies (one place ended up with negative check-ins).

This is what the tidy plot looks like

[Updated since original post]

Pretty similar, but some of the bars are now closer together (removes the anomalies from Sunday and Wednesday).

So from the results above, the order of days, from least to most busy, seems to be:

1) Monday
2) Thursday
3) Tuesday
4) Wednesday
5) Sunday
6) Friday
7) Saturday

But note, it's pretty close amongst the top 3 least busy days.

It shouldn't be too surprising that weekdays are less busy than weekends - what with people working.

As for Sunday being so low compared to Friday and Saturday - well, that might be the result of Sunday opening hours.

For example, Meadowhall has typical opening hours of 9am-8pm, but on Sundays it's 11am-5pm -> 11hrs vs 6hrs. So maybe it would make sense to re-adjust accordingly. But deciding how, exactly, to re-adjust is tricky. So we'll just leave it be.

NB/ Wednesday, week 2 maybe distorted due to public sector strikes - there certainly appeared to be more people on the train. But but a lot of that increase was from children (see sample bias above).


Of course, each shopping centre is unique, and there will be variation as to which days are best and worse for each. As an example, here's what the (non-normilised) plot looks like for Westfield London (the most checked-in to shopping centre by far)

Again, pretty similar to the average. But in this case, Wednesday is less busy than the average, and Thursday more. And Friday has that weird dip in week 2, bringing its average down.


One last thing I'd like to point out - notice there is no particular week-on-week trend. That is, the number of check-ins isn't (on average) increasing as we get closer to Christmas. Or decreasing for that matter. Which is, perhaps, not what you'd expect.

But maybe that will change within the next couple of weeks. And certainly after Christmas, when the January sales kick off. Maybe.


This is an on-going project - bear in mind, this is only 3 weeks worth of data, so it may be too soon to draw any solid conclusions - but I will keep you posted. Maybe I'll do another post just after Christmas, or after New Year's. At any rate, I'll tweet it when I do.


Oatzy.


[There's always online shopping..]

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.]

The Cost of Loyalty

So if you have a loyalty card for, say, Costa you will get 5 points for every pound you spend. One point is worth 1 pence, so you're effectively saving 5p from each £1 you spend - a saving of 5%, right?

Yeah, it's not that simple.

For one thing, if you think of it as paying full price then getting 5p back per £1, then there's the restriction that these 5 pences you're 'saving' can only be spent in Costa. Also, you only get points for the whole pounds you spend (not the pence).

So what are you saving?

Think of it this way - let's say every time you go to Costa you buy the same thing, spending the same amount of money each time.

The question then is, how many visits does it take to earn enough points to get your usual order for free?


Okay, so we have our usual order, with price P. The amount of money you 'save' (in the form of points) per visits is 0.05*floor(P). The floor function - f() from now on - rounds the price down to the nearest pound, since you don't get points for pennies.

So we want to find the number, N, of purchases we need for the total points value to be greater than or equal to our order price P. In other words:

0.05*f(P)*N = P

or  N = P/(0.05*f(P))

Now, lets start by looking at the simplest case, where P is an exact number of pounds - i.e. P = f(P)

In this case, P and f(P) cancel each other out, so N = 20. Notice, regardless of whether your order is £1 or £20, it will always take 20 visits to get one 'free'.

More generally, the equation becomes N = ceil(20*P/f(P))

Where ceil is a function which rounds the value up to the nearest whole number. Because there's no such thing as a fractional visit, unless you count a visit in which you spend less than usual. Anyway.

Okay, so lets look at an example - a pot of tea costs about £1.60. So we work out N = ceil(20*1.6/f(1.6)) = ceil(32/1) = 32 visits. And just to check, for a pot of tea you get 5 points per visit (5p), and 32*0.05 = 1.60 = the price of a pot of tea. Perfect.


Now. What about savings?

In the tea example, you're buying 32 pots of tea and getting one for free. Which isn't a great saving, but it is a saving nonetheless.

So, the total amount you spend is P*N, and you're getting N+1 pots. That means the effective price per cup works out at P*N/(N+1).

For tea, that means you're effectively paying ~£1.55 per pot - a saving (S) of 5p per pot. What's that saving as a percent? Without going into too much detail, it turns out it's %S = 1/(N+1).

Which works out at 3% for tea. Which is less than the 5% saving you might have expected.


Incidentally..

The example for when the price is an exact number of pounds turns out to offer an effective saving of ~4.76%. Which, again, is less than 5%, but a little better. This, by the way, is also the maximum % saving you can achieve with a Costa card.

In general, the % saving is much worse when the pence amount of P is high and the pound amount is low - the worst case being when the price is £1.99. This would require 40 visits to 'get one free' and offers a saving of only 2.4%.

So based on best and worst case scenarios, we can say that your % saving will always be between 2.4% and 4.8%. Similarly, visits required to get one free, N, will always be between 20 and 40.

[In fact, the absolute worst case is when P is less than 1, in which case you never get any points.]


But to clarify..

This 'saving' is the saving over what you would have paid if you bought N+1 pots of tea and didn't have a loyalty card - i.e. not getting the N+1th one for free.

But what if you could spend the money you saved on something else?

Think of it this way - you've bought N pots of tea, and thanks to the loyalty card, you've saved the equivalent of the cost of one more pot of tea (£1.60). In this case, the saving per pot bought would be P/N. For the pot of tea, that's 1.60/32 = 5p.

To get the percent saving (per order), we divide this number by total price, P. For tea that works out at 3.1%. In fact, this is equivalent to the point-value saved per purchase, divided by the full order price - i.e. 0.05*f(P)/P == 1/N

So for the whole-pound values, this does, in fact, work out at a 5% saving. And the worst saving is still for £1.99 purchases, now working out at a 2.5% saving.


One more thing

All of this also goes for Tesco, and Waterstones, and wherever else does money-for-points loyalty cards too. You just replace 0.05 with however many points you get per pound, divided by 100 (e.g. Tesco = 0.01).

If we call this value rho (which looks a bit like a lower-case p), then the general formulas are:

But again, we're assuming you spend approximately the same amount (P) every time you visit a given place. If not, things get tricky. For a rough estimate, one thing we can try is using an average per visit spend (Pbar).

One other thing we can do is replace the P on the top of the fraction with a target points/saving; replacing f(P) with f(Pbar) if necessary.

So, for example, if the average order (Pbar) is £3.55 and you want enough points to get a free slice lemon cake (£2.50), then it will take N = 17 visits.


Oatzy.