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.

Playing with Pac-Man

What the Puck?

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

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

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

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


Wakking Round in Circles

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

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


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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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


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


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


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

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

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

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

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

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

Or something like that.

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


Oatzy.

Picking and Scoring Words for Hangman

Hangman, for those unfamiliar, is a popular way for primary school teachers to teach spelling in the guise of a fun guessing game, and a way for secondary school teachers to pass the time at the end of term when they can't be bothered with teaching.


It Works Like This..

In a dystopian future where the powers that be like to play deadly games with their political prisoners, Hangman sees one such prisoner, 27 year old Adrian Silk, standing on a platform in front of a cheering crowd; his crime - logical thought.

Adrian is presented with an unknown word - 9 letters, title of a 21st century movie - and his task is to determine that word by guessing letters.

With each correct guess he gets closer to discovering the mystery word and winning a stay of execution. With each incorrect guess, another piece of the gallows is built. If he can't reveal the word before the gallows are fully constructed, he'll be dancing a dead man's jig for the crowd.

He starts by guessing the vowels - A, E, I, O, U - two incorrect guesses, two pieces of the gallows built: I__E__IO_

He guesses some common consonants - N, R, S, T - two more incorrect guesses, but still safe: IN_E_TION

Adrian stops to think - "are there any films called INFECTION? There are two, but they're pretty obscure.. Wait..!". And he hazards a guess - INCEPTION ..?

He's right! Adrian jumps for joy, and breathes a sigh of relief. And as the disappointed crowd jeers, Adrian is shot between the eyes by the Games Master - found guilty of the logical thought with which he'd been charged.

Still, if you think that's bad, you should see how they play KerPlunk!


Lets Play a Guessing Game

Okay, imagine you were guessing letters for an unknown word. But in this variation on the game, the hangman will only tell you when you've won, or else when you've run out of letters. That's all the information you get, nothing else.

The simplest approach to finding a word would be to just work your way through the alphabet - 26 letters, a maximum of 26 guesses to uncover any word.

But there will be a limit on how many incorrect guesses you can make - usually around 10. This means that, unless the word you're guessing contains 17+ unique letters this probably isn't the optimal approach.

So with no feedback and a guess limit, all you can do is guess letters 'at random'. But some letters appear more often in the English language than others. So you can make educated guesses, and go for the more common letters first: E, T, A, I, O, N, S, ...

If we assume that the probability, p(ci), of a person guessing a given letter is roughly equal to that letter's frequency in the English language, then the probability, big P, of that person guessing a correct letter in a word equals the sum of the probabilities of each unique letter in that word.

For example, in MISSISSIPPI, the unique letters would be {I,M,P,S}, so

P(MISSISSIPPI) = p(I)+p(M)+p(P)+p(S) = 4.025% + 2.406% + 1.929% + 6.327% = 14.687%


What this immediately suggests for choosing words is:

1) Words with 'uncommon' letters are better

Uncommon letters have lower probability p(ci), so will make totals lower. E.g. C is less common than H, so (in the game described above) CAT is harder to guess than HAT

2) Words with fewer unique letters are better

If there are fewer (and smaller) targets, it's harder to hit one of them by just firing at random.


Parting Words

So what about in a real game, where you get lots of feedback - which letters are right or wrong, where each letter appears and how many times.. This makes deduction a lot easier.

Have you ever tried to cheat at a crossword? There are loads of 'helpers' online - put in the pattern and see what possible words match it. Well for hangman we take that a step further.
Say our pattern is E_UA_I__; there are 5 words it could be - EQUALITY, EQUALING, EQUALISE, EQUATION, EQUATING

First of all, EQUALISE is not a valid solution because it introduces an extra E. And if we'd guessed all the vowels to get that pattern, we can also rule out EQUATION since we've already determined that O doesn't appear in the solution word.

So to put it more concisely - we want to find words that match a given pattern, eliminating those which contain extra letters already guessed.

In the case above we're left with 3 words - EQUALITY, EQUALING, EQUATING - and which of the three the correct word is can be determined by guessing the letter T:

1) E_UA_IT_ which can only be EQUALITY
2) E_UATI__ which can only be EQUATING
3) T doesn't appear in the word, in which case it can only be EQUALING

The fact that T is the most common consonant probably means each of those 3 words are poor choices for hangman. This is an example of a low entropy pattern.

Imagine, instead, that you're presented with a 3 letter word, and you've gone through the vowel and found you're left with the pattern _A_

What could that be? Maybe you guess T next and get _AT - well that could be BAT, CAT, HAT, RAT, .. Or maybe T is wrong, then the word could be MAN, CAN, BAY, RAY, WAX, TAX, .. how many guesses have you got left?

In fact, there are 179 possible words which match this pattern. This would be a high entropy pattern.


So, more tips for picking good words:

1) Pick obscure words

Even if there is only one word a pattern could fit, if the opponent doesn't know that word, then they are forced to keep guessing letter-wise. Which makes things a little more tricky.

2) Pick shorter words

There are more 3 and 4 letter words in the English language than 8 and 9 letter words.

3) Avoid too many repeated letters

For example, MISSISSIPPI only has 4 unique letters, but once you've guessed I and S, you've uncovered 73% of the word, and there's really nothing else _ISSISSI__I could be.

4) Pick words with high entropy patterns


A Question of Uncertainty

In Information Theory, entropy relates to the uncertainty in a piece of information. It's measured in bits, and, for a set of equally likely outcomes, is calculated as the base two logarithm of uncertainty.

So a coin toss has an uncertainty of 2, because there are two possible, equally likely outcome. That gives an entropy of 1 bit. For a given character in a word, if we assume all letters are equally likely, then there is an uncertainty of 26 - so that gives an entropy of log2(26) = 4.7 bits.

But as pointed out above, all letters are not equally likely in the English language. So the entropy is more complicated to work out: H = -SUM[p(ci)*log2(p(ci))]. Anyway, it turns out the entropy of a given unknown letter is 4.18 bits.

In the case of word patterns, we work out entropy as log2 of number of valid words matching the pattern, since all matching words have the same probability of being correct.

For the low entropy example above, there are 3 possible words that match the pattern so that would give an entropy of log2(3) = 1.58 bits. The 3 letter, high entropy example, on the other hand - with it's 179 possible solutions - would have an entropy of 7.48 bits.


So Where Does This Leave Us?

The idea is this - to come up with a scheme for scoring the 'quality' of a word in terms of how hard it is to guess in a game of hangman.

First, we score our word by its letter, as described above, to get the probability of guessing a correct letter. We then take one minus this to find the probability that a letter guess is wrong - the lower the probability of guessing a correct letter, the higher that word's score.

Entropy has a well define method of measurement in Information Theory, as discussed above.

But if we measure the entropy of a word before any letters are guessed, we find that all words of the same length have the same entropy. So instead, it would be more useful to measure a word's entropy after, say, some common letters have been filled in. Since most people start by guessing the vowels, that is what I'm going to go with.

In some cases, there are so many possible pattern matches, that you'd do better to simply make educated guesses at letters until the solution is found. For this, we work out the letter-wise entropy. Again, before any letters are guessed, all words with the same number of unique letters have the same entropy.

So. Each unknown, unique letter in a word can be one of those not already guessed. So we can work out the entropy, H(alpha), of the alphabet, sans the letters already guessed. Then, multiply that by the number of unique letters left to find, n.

So for example, if we guess the vowels and get the pattern _A_, then the entropy is  2*H(consonants) = 5.62 bits


From a Practical Stand Point

To work out the word entropy we can download a dictionary, then write some code which will find and count the words which match our required pattern, excluding those containing already guessed letters.

We then find the 'smallest maximum' entropy - which of the character entropy and the word entropy is smallest. In most cases it'll be the word entropy.

And finally we multiply that by the probability, one minus big P, to assign to each word a score:

(1-P)*min{H(W), H(C)}

Or you can use this code.

In and of themselves, the scores this gives don't have any specific meaning - the exact score for each word will depend on your choice of dictionary and initial guess letters. But so long as you use them consistently, the scores should stand as an indicator of each word's relative 'quality'.

For example, by this system, CAT gets a score of 5.3, and EQUALITY gets a score of 1.4. So CAT is a much better hangman word than EQUALITY.


So What's the Best Word

JAZZ, apparently. In fact, while researching this blog, I came across a few other people's attempts to find the best words for hangman. Pleasingly, they went with different approaches to me.

In fact, JAZZ never occurred to me when I was thinking up random good words. The best I thought of was WAX. Also reassuring is the fact that JAZZ does score highly under my system - 6.07 - and scores only slightly better than WAX, with its score of 5.92

QUIZ is an interesting word. It contains the two least common consonants and the two least common vowels (P=9.89%). But there are only 12 words that match _UI_, so it has low entropy. Its final score is 4.13 - lower than that of CAT, with its more common letter set (P=20.0%).

Similarly GYM; it has P=6.34% and has no vowels, but there are only 29 words it could be, so has a score of 5.48. Or MY, with P=4.38% but only 5 possibilities, score 3.18. So it's a matter of balance between probability and entropy.

Ideally, I'd have run a whole dictionary through my system to look for a list of best words. But I didn't. You can if you really want. Otherwise, I'd recommend one of the blogs linked above for lists.


In Summary

So there you go. You can score some of your own words if you so wish. But for on the fly word assessment, just remember, pick:

1) Words with 'uncommon' letters
2) Words with fewer unique letters
3) Obscure words
4) Shorter words
5) Words with fewer repeated letters
6) Words with high entropy patterns

And if you're trying to guess a 4 letter word with an A in the second position, odds are someone is trying to outfox you with JAZZ.


Oatzy.


[Full disclosure: If I got the information theory stuff wrong, it's because I only know as much as the one chapter of this book, and odd bits on wikipedia.]

Su Doku Solver

Cold Hard Logic

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

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

The problem are,

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

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

The Rules

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

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


Brute Force

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

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

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

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

[There are probably better brute-force methods.]

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

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

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

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


Rewriting the Rules

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

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

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

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

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

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

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

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


Setting Up The Problem

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

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

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

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

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

Checking columns and boxes works similarly.


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

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

Parsing our puzzle into the Grid works like this then:

for i in range(0, 9):

    for j in range(0, 9):

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

And so on..


Applying the Rules

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

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

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

3) Repeat for all squares in the grid

From there, we can apply Rule Two:

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

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

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

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

Or more technically,

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

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

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


One More 'Rule'

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

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

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

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

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

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

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


A Note on P versus NP

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

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

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

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

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

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

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

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

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

What P versus NP asks, then, is

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

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


Where's The Code?

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

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

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

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

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

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


In Case You Were Interested

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

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


Oatzy.

Quick Look: Don't Blink..

"..Don't even blink. Blink, and you're dead!" threatened the frustrated photographer, following a fifth failed photo..

No, this isn't a Doctor Who thing (sorry). No, this is based on another lost article I read a while back:

How many photos do you have to take in order to get at least one where no one's blinking?


First things first, what's the probability of one person blinking when you take a photo of them?

Well for one thing, that's going to vary depending on environment, lighting, etc. And also on the shutter speed of the camera being used to take the picture.. But for simplicity, I'm ignoring all that.

The average person blinks around 10 times per minute, with an average blink lasting 300-400 milliseconds (call it 350ms). So in any given minute, the average person's eyes will be closed for a total of 3.5 seconds.

We'll say the shutter is open for less than the duration of a blink. So the probability of a persons eyes being closed while the shutter is open -> p = 0.058.

[I'll be honest, I'm not not entirely convinced that's right. But I'll go with it anyway.]

So the probability they don't blink -> (1-p) = 0.942


If you're taking a picture of one person, that's only a 5.8% chance of the subject ruining a photo by blinking. So your odds of a good shot are pretty good.

But if we have a much larger group of people - n = 30 - the probability that none of those people blink while a photo is being taken:

p1 = (1-p)^n = 0.165

That's an 83.5% chance that at least one person will blink. Those odds aren't so good.


So if we take S number of photos, what is the probability that at least one of those is 'perfect'?

This goes back to the methods use in the Law Of Truly Large Numbers post - the probability of at least one perfect photo, big P, is one minus the probability that none of the S photos are perfect:

P = 1 - (1-p1)^S

So if we were to take, say, S = 5 photos -> P = 0.594

Bearing in mind that you have to make these 30 people stand around while you take your however many photos, an almost 60% chance of the perfect shot from 5 tries it pretty reasonable.

But let's say you're the panicky sort, and you want to be 90% certain that you have at least one perfect shot..?

Without going into the nitty-gritty, we can find S for P = 0.9, using some logarithms and algebra thus:

S = ln(1-P)/ln(1-p1) = 12.8 shots

And if you can get a group of 30 people to stand still for 13 photos, knowing that there's still a 10% chance you won't get that perfect shot, then more power to you.


When people know they're having their picture taken, they generally try harder not to blink. Especially if you use a count down. So the probability of blinking, and by extension, the number of photos you'd have to take, drops dramatically. The numbers worked out above are probably more applicable for candid shots.

On the other hand, maybe the flashing going off (if you use one) will cause some people to automatically blink. And, admittedly, I've taken pictures of myself that have still managed to get capture me mid-blink. Though that might be down to a delay between click and shutter.


Of course, in this day and age, of digital cameras with instant preview, you can just keep shooting until you get the photo you want. Not like the dark old days of film cameras and photo roulette...


Oatzy.


[The word 'blink' and its variants appear ~17 times in this post]

[As a random aside, working out the number of pokéball you need to throw to catch a given Pokémon is done in much the same.]