Lights Out (Game)

I was watching this year's RI Christmas Lectures, and it reminded me of this game I had when I was much younger. It was, I think, a Christmas present from my grandparents, back in '96. It was called Lights Out, and it looked something like this.

Basically, the console had a 5x5 grid of these rubbery, transluscent buttons with little red lights underneath them. When you press a button, that button and the four adjacent buttons switch state - light on to light off, or off to on. So, in the example below (where blue square are lights), if you press the centre square, the centre square turns off and the four adjacent squares turn on.

In the game, you're given a pattern of lights, such as the one above, and the task is to press buttons until all the lights are out.

Interestingly, in the pattern above (on the left), you can clear the board by just pressing the squares that are on at the start (in any order).

Anyway, I was reminded of that. Meanwhile, I'd been learning some Pygame for this other thing (that I'll talk about in a later blog). Now, Pygame is a Python library for making games (amongst other things). So you can probably see where this is going...

Coding a 'Lights Out' clone was straightforward enough - the code is short and not too complicated. The above images are actually screenshots. You can look at my code/download it here. You'll need Python and Pygame to run it.

This is a very threadbare version of the game. You can load a level as a text file of five lines of ones and zeros, like here. Or else you can just play from a blank board - make patterns then try to get rid of them again (not necessarily as easy as it sounds).

If you want something more fancy, or if you don't want to install Python and all that, there are probably loads of playable clones online.

Now, at this point you're probably thinking "Yeah, that's great. But what about the maths of Lights Out?". And you'd be damn right to ask. If you're interested, there's a good summary, as well as links to articles/papers, on the wikipedia page. I don't want to just repeat what's written there. Basically, it all comes down to linear algebra.


Anyway, have fun with that.


Oatzy.


[Call this a late Christmas present.]

Is There a Formula for The 'Perfect' Christmas Tree?

The other week I was waiting for my tram, reading Metro, and I see this article - Treegonometry: Formula for perfect Christmas tree discovered

In other word, a set of equations that will tell you, for example, how much tinsel, or how many baubles are 'required' for the 'perfect' Christmas tree.

Here is the press release, with the actual formulas.

Now, I have a few issues with this. For one thing, it's a bit silly. Surely the perfect tree is a matter of personal preference, and in that sense can't be defined by a set of mathematical rules.

Plus, it seems kind of arrogant to declare that their way is the 'perfect' way, and that (implicitly) any other way is wrong.

Also, the fact that the equations are preposterously simple (perfect thing = constant*tree height) makes me suspicious of them. But, worse than that, it really bothers me that I have no idea how they were derived.

But I'm starting to rant.

The equations in question were actually from a 'study' by the Sheffield University Maths Society (student from my university), and were commissioned by Debenhams (department store). So, I dunno, maybe I'm just bitter that no-one's ever commissioned me to do maths.

Anyway. If they'd said that these were equations for an 'ideal' Christmas tree, then I'd consider that more reasonable. You can say, for example, that the ideal Christmas tree should strike a balance between too many and too few decorations, etc.

So, to that end, I'm going to have a crack at deriving some, more general, 'Equations for an Ideal Christmas Tree' of my own.


Lights

Before we start, there's one simplification we need to make - we will assume that Christmas trees can be approximated to a smooth, regular, right-circular cone - height h, and base radius r.

There's going to be a certain degree of error as a result of this approximation, but I'm not going for perfect.

Okay. So, for lights, there's actually a justifiable basis for an ideal - the ideal tree should have its lights evenly distributed.

Or, to put it another way, you ideally want to wrap your lights such that you have a (roughly) constant light surface density (lights per unit surface area); because you don't want your tree to be covered in clumps and bald spots.

This seems like a vague point; how do you decide on the correct 'density'?

Well, we actually have two constraints to work from: firstly, we have to wrap a single line around our conical shape, and second, the distance (s) between each pair of adjacent lights on a string will be fixed.

From this, we can layout a (hypothetical) grid on the surface of the tree, so that all the lights are equally spaced out.

So, how do we do that?

1) Draw yourself a cone (tree)
2) Draw a grid
3) Draw lights at the points where the grid lines meet
4) Draw in the proper row lines - these represent the actual string of lights

In this cases, I've drawn the grid a little tight, so you'd probably want two strings of lights to get this layout (hence the two colours).

And if you like, you can play with the distances between rows, and the angles, to get some slightly different layouts

The best grid to try for would be a triangular grid, where the distances between each light and the six nearest are the same

So, let's say we've picked a grid. How many light will we need?

There's a nice short-cut to working this out, without having to worry about lengths of spirals on conic surfaces. To do this, we take advantage of the regular grid layout to work out the lights density (lights per unit area).

Each section of grid is roughly a diamond, with all sides about the same length

So with a bit of trigonometry, you can get an approximate equation for the area of this diamond

Then, the density is one over that area (since there's one light per grid diamond).

We then multiply this density by the total conic surface area (excluding the base) to get the total number of lights needed

And, finally, multiplying that by the separation between lights (s), we get the total length needed:

Easy. Though, somewhat more complicated than the L = pi*h equation, derived by SUMS.

So, then, for the triangular grid (theta=60), you get

Cool.

The only problem then is getting the lights to line up on a grid on the actual tree. So... good luck with that.

Realistically, all of this is mostly irrelevant anyway - you can't go out and ask for, say, exactly 5.83m of lights; you buy your lights in pre-cut lengths. Can't get hold of the 'perfect' length of light? Then your tree is imperfect, and you should feel bad.

Anyway. The point is, if you can get your lights more or less even - so that there aren't any clumps or bald spots -, then as far as I'm concerned, you're on to a winner.


Tinsel

What's interesting about their equation for tinsel is this factor of 13/8. Now, again, I don't know how these equations were derived, so I don't know if this was intentional; But, 8 and 13 are consecutive Fibonacci numbers. Why is this important? Well, the Fibonacci sequence is closely related to spirals.

In particular, there's this thing you see in nature; for example, if you look at the spirals on a pineapple, the spirals going in one direction might be 13 and the number in the opposite direction might be 8. Or the numbers might be 21 left and 13 right... The point is, the numbers of spirals on a pineapple are always consecutive Fibonacci numbers (or sometimes Lucas numbers).

And you get the same effect on other things, like the spirals of seeds in the head of a sunflower, or the seeds on a strawberry, or the spirals on a pinecone, or a cauliflower, or all sorts of things. Hell, maybe the branches on a Christmas tree form Fibonacci spirals.

Vi Hart explains it better than me.

So maybe that has something to do with that pre-factor. Or maybe not. It's an interesting tidbit, though.

Anyway.


The thing with tinsel is different people like to do tinsel differently - some like to elegantly drape it across the outer branches, others like to wrap up their tree light they're restraining a hostage. It's a matter of preference. But it's going to affect the amount of tinsel you'll need.

Where tinsel differs from lights is, you're not trying to set up a grid, or get an even surface density. Rather, in this case, you'd probably want to wrap it such that the rows are more horizontal, with a roughly constant vertical separation.

Here's where things get messy; the equation for the length of a spiral on the surface of a cone is given by

I know, right? Maybe you would be better using the SUMS equation for this one.


Extras

The star/angel is going to be some fraction of the height of the tree.

I don't know what the ideal value of the fraction (alpha) would be, but the 10th they came up with seems reasonable.

Baubles, I haven't a clue how they came up with those numbers. The factor of sqrt(17) makes me think some geometry was probably involved, but I dunno.

You would probably want to figure it out as some ideal ornament surface density, Db (like with the lights). In this case, the number of baubles needed would be something like

In fact, if your baubles are all, more or less, the same, you can lay them out on a grid, like the lights. Though, this time, you'd want to have them a little more spaced out, since baubles are much bigger than fairy-lights. But at least this time you don't have the separation constraint.


Thoughts

Here are various things Ben Goldacre, of Bad Science, has said on the subject of commissioned, 'perfect' formulas. Here is an article by mathematician, Simon Singh. Here is an article on BBC News. And here is a collection of such formulas on Apathy Sketchpad.


To be honest, I wouldn't bother with any of this; their equations, or mine. I mean, would you really want a tree that was 'perfectly' decorated? Cold and artificial are the words that come to mind.

And, frankly, I'm not sure my equations would actually work in practice.

I'd say, use your best judgement on how much of everything you'll need, and just do your own thing. Have fun with it!


Our Christmas tree is imperfect. In fact, it's gloriously imperfect. No, seriously, it's a mess.

My ex's family used to construct these massive, elaborate, works-of-art trees; with yearly colour schemes, and matching baubles, and everything. By comparison, she described our tree as kitsch.

But it's adorned with all the baubles, and tinsel, and decorations we accumulated over the last 20-odd years; at least, the ones that haven't been lost or broken. And, in a sentimental sort of way, it is perfect.

Well, okay, not perfect. But, damn it, it's ours.





Oatzy.


[I want you to know, I had no part in decorating that tree.]

[...And, yes, that's a weeping angel on top.]

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

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

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

Weeping Angel Christmas Tree Topper

Template here, in case you fancied making one of your own,

Feel free to modify, redistribute, whatever.

For mine, I reinforced them with card, then in true Blue Peter style used a toilet roll tube and double-sided sticky tape to make the shape of it. In case you couldn't tell, they go back to back, so you just have to turn it to see whichever side.

Or you could do it as a hanging decoration like Andrew did.

For maximum effect, put it on the tree without telling anyone ;)


Oatzy.