The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 19,000 times in 2011. If it were a concert at Sydney Opera House, it would take about 7 sold-out performances for that many people to see it.

Yeah, so that still doesn’t impress me too much. I suppose the analogy works if you presume most people turn up for the opera and leave after a mere 30 seconds or 1 minute.

In 2011, there were 6 new posts, growing the total archive of this blog to 62 posts.

Okay, I admit it; this was a really poor year in terms of output. I blame that nasty thing called a degree (followed by the even nastier demands of a job). At least you can rest assured that care and effort goes into every post!

The top referring sites in 2011 were:

• reddit.com
• en.wikipedia.org
• dotnetkicks.com
• noldorin.com
• ru.wikipedia.org

I think this just proves the best way of getting blog visitors is to spam Reddit. Or link to yourself on Wikipedia. Shameless I know, but it requires minimal effort on my half at least, and maximum benefit for everyone.

Most visitors came from The United States. The United Kingdom & Germany were not far behind.

Right; English speaking (either natively or to a high level) and technologically advanced nations. Big surprise there. Other notables seem to include: Russia, Sweden, India, Brazil, Egypt, South Africa, Australia.

Quite amusingly, my most popular post of the whole year was posted was only posted several of days from the end, while I was on holidays. That’s inspiration for you.

So in conclusion, it would seem what these wonderfully informative stats are telling me is a) visitors are almost totally due to viral marketing and much less to content, b) I don’t really care about the popularity contest, c) nothing I really didn’t know already.

Until 2013, folks. (Or perhaps not, if the Mayans turn out to be right.)

The event was a gruelling but undoubtedly challenging and enjoyable 24 hours of programming solutions to a range of small problems given to us by the competition organisers. Alas, we were restricted to C++ for our solutions (the lesser of two evils when compared to Java), but considering than myself and one of the two other team members were far from regular users, I thought we did a fair job of coping. (We were constantly refreshing ourselves on much of the basics!)

The results were published not too long ago, and I must say I was amazed we managed to rank as high as 71 overall (out of some 1,500 teams). In fact, I gather we were somewhere in the 20s at one point, but evidently slipped dramatically when we all lost the desire to keep going about four hours from the end.  What’s even more astounding is that our lone Imperial College team managed to rank first among the teams from the United Kingdom. Admittedly, this says more about the popularity of this relatively new contest in the UK, especially when one notes how many British teams entered. Eastern European countries unsurprisingly put forth a host of participants. Still, I was moderately pleased with our effort. Our phenomenal team spirit more than made up for any shortcomings, of course.

Oh, and as it turns out, a power outage in that area of London induced a delay of some two hours, mainly spent dashing around the campus. The fire alarm and standing around in the freezing area wasn’t much appreciated, though I doubt it affected our success in any real way. Though that isn’t what I’ll be telling the electricity company, of course, when I claim full competition-related damages.

Most annoyingly of all during the marathon competition, there was a singularly irritating problem relating to dynamic programming that none of our team was able to solve throughout the event — despite persistent efforts and the fact that the great majority of other team had no problem! The contest had its faults too; the arbitrary swings in difficulty level of many questions often took us by surprise, as the times taken for us to fully solve the questions ranged from 20 minutes to 5 hours to never. I hear most were rather better specified than their counterparts from last year, however.

In all, my day of IEEEXtreme was a perversely enjoyable exercise in frantic coding and sleep deprivation. Probably not one I’ll repeat in its current form (even if I were still in university), but not one I’d take back either. I daresay I’ll be revisiting the similar but less biologically demanding Google Code Jam contest this year, only to fail utterly in the second one, when facing up against some truly super-human competitors.

Although “The Hardest Logic Puzzle Ever” is scarcely a logically verifiable statement, the puzzle does indeed have a reputation as a rather tricky logic puzzle (at least among those encountered by laymen) and in any case has a non-trivial solution. The problem has some notable names attached to it, having originally been published in The Harvard Review of Philosophy by the logician George Boolos, but originating with the popular mathematician Raymond Smullyan, and altered slightly by the late computer scientist and AI pioneer John McCarthy.

The puzzle is commonly stated as follows.

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

At first glance, the problem may appear insurmountable due to the behaviour of god C, yet when we notice that his behaviour is not truly random, but rather only his veracity is — he otherwise follows all rules of logic. Boolos clarified: “Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.”.

Encountering this puzzle for the first time just in the past week, I made an effort to solve it on my own using a formal approach, as much as possible. As it turns out, I had some success, and hence thought I might share my reasoning here in the form of an article.

Let us begin by setting up the puzzle in the standard language of propositional logic (that is, Boolean algebra). We first define our useful propositional variables and predicates, which are

• , whether the da response corresponds to yes (absolute truth). $R$ is thus true if da means yes and ja means no, and false if da means no and ja means yes;
• , whether a given god (we consider them independently) is telling the truth. Note, this has a well-defined value even for Random (god C), since the context is a specific question and corresponding response.
• , the question (propositional predicate) that is asked to a given god.

Note that the latter two variables are semantically valid within only within individual questions. However, because we shall only utilise them within the context of question-response pairs, we need not concern ourselves with this.

There is a number of ways to convert the verbal problem statement into a set of formal logical expressions, but I shall adopt a fairly direct and unambiguous one here. We start by noting two simple facts regarding the truthfulness of a particular yes-no response .

Note that the biconditional () can be interpreted as material (syntactic) equality. This is precisely equivalent to the non-fundamental XNOR () operator in propositional logic. With a bit of manipulation it can be shown that

In other words, the yes-no of any response shall be the absolute (true) answer to the question XNOR whether one is asking a truth-teller.

We must then note the complication to the puzzle introduced by the fact we do not understand the language of the gods. ‘da’ could mean either yes or no and ‘ja’ conversely. To account for this, we can write two more statements specifically about the da-ja response (denoted ), which take virtually identical forms to before;

Unsurprisingly, this can be rewritten in the same way to use the XNOR operator;

Note that the value of represents the actual response; that is, it is the single observable of the logical system we have constructured to represent the puzzle.

While we could restrict ourselves to the use of the primitive Boolean operators (AND, OR, and NOT), the use of the XOR operator here facilitates things considerably, due to its special properties (notably commutativity and associativity) and the simplicity it gives our theorems.

Now, combining the two expressions (theorems) for and (this can be seen easily by considering the biconditional as equality), we can factor out the negations and use associativity of the XOR operator to write

We now have an easily manageable form for the da-ja response of a given god. The question now becomes, how do we extract the absolute truth value of the response from this observable variable? Clearly, one has no control over the and variables, which are predetermined by god being asked the question (and possibly by the flip of a coin) as well as the language of the gods. However, we do have direct and full control over the question to ask, the predicate .

In order to extra meaningful (absolute) truth value we first note that any propositional variable XNOR itself is false, thus disappearing from its containing expression. Given that we wish to eliminate the variables and from the final expression, we can decompose the predicate ; that is, give it an explicit form.

Let . Hence, we can say

At this point we almost have a solution to the puzzle. We have shown that one can obtain an accurate true-false response to any question we wish to ask any god. As long as we ask a question of the form , then a response (effectively to question ) of ‘da’ always corresponds to truth and ‘ja’ always to falsehood.

There are a number of ways to use this to reveal the identities of the three gods. The simplest and most direct, I feel, is to ask gods A and B whether they are Random. This definitively indicates the Random god (since if both answer in the negative, then it must be god C by elimination). One can then simply ask either of the remaining gods (not Random) whether he is True, deducing the identities of the True and False gods in a single question. Hence, we have totally and provably solved the puzzle within the desired three questions.

The only task that now remains is to translate the formal solution, which we have stated as a set of predicates of form (in zeroth-order logic), into natural language. Since the first question to ask is invariably the most intricate, and the second or third must be conditional on previous answer(s) in some way, it makes sense only to consider the verbal representation of the first as an exercise.

George Boolos (the populariser of the puzzle) proposed asking the following initial question.

Does da mean yes iff you are True iff B is Random?

When we recall that iff (if and only if), i.e. the biconditional connective, is logically equivalent to the XNOR operator, it is quite straightforward to see that this is of the above proposed form for . (Note that a triple of formulas connected either by a pair of XOR or pair of XNOR operators form the equivalent expression.)

The Wikipedia entry for the logic puzzle gives only a slight variation on the above that is fully equivalent;

Are an odd number of the following statements true: you are False, da means yes, B is Random.

Start by considering how the operations and change the truth value of . The former clearly inverts the value, while the latter leaves it unchanged. In order words, each XOR with a formula that is true inverts the overall truth value. Hence, considering an arbitrary number of formulae XORed together, we must deduce that if an odd number of statements are true, then the entire expression must in fact be true (and conversely if an even number of statements are true then the entire expression is false).

We now come to a somewhat different form of verbal solution, first proposed by T. S. Roberts (Journal of Philosophical Logic, 2001);

If I asked you Q’, would you say ja?

(We do not assume for now that is the same variable as used in the formal solution given above.)

A counterfactual may be thought of as a nested question; that is, an ‘if-then’ style of statement/predicate. Let us first consider the slightly simpler question: “If I asked you Q’, what would you answer?”. It should not be hard to see that this essential form of the counterfactual is equivalent to . The additional “would you say ja?” (as opposed to simply “what would you say?”) may be evaluated as a post-condition, equating to . Formally, we may infer

Since represents “ja” under our labelling, this formula is clearly equivalent to the expression for reached at the end of the previous section. Hence by equating the separate expressions, the two originally assumed to be independent are in fact rendered identical.

This concludes my article on The Hardest Logic Puzzle ever. I hope that I’ve given readers some appreciation for a formal (mathematical) solution to this intriguing puzzle, and indeed an insight into the equivalence of the various forms of solutions that one might posit from thinking about the problem holistically. No doubt, an exhaustive truth table would have proven the isomorphisms just as well, except that I felt they added little to overall understanding. If anyone has an additional alternative solution or general comments on the preceding, by all means please share via the comments section.

Warning: Rant ahead. Apple fan-boys, avert your gazes.

Four weeks later, and I’m still sitting here with my two-and-a-bit year old iPhone 3GS. I was due for an upgrade on my O2 contract just a week after the initial release, and contacted both O2 directly and my local Carphone Warehouse retailer to find out what the status of this upgrade was. Apparently, not only was the retailer entirely out of stock of the new iPhone 4S (in its warehouses or otherwise), but they had no word on when any further shipments would be arriving soon. In the ensuing three weeks, I’ve made the personal effort of checking for new stock updates every few days, only to be told that a new delivery should be coming soon. Besides a brief restocking a week ago (that didn’t include any of the 64 GB versions), I have repeatedly and consistently been told to come back and enquire again in a few days regarding stock. Now, it’s hard to blame this on Carphone Warehouse, since every employee I spoke to seemed about as perplexed as me.

To me, the simple fact that Apple has failed to sufficiently stock one of their primary UK retailers with the new iPhone model for almost 4 weeks now is absolutely shambolic. I mean, how can one of the largest companies in the world, which prides themselves on customer satisfaction, make such an atrocious mess of logistics? It’s not like Apple has just entered a technology sector with a minor new product no-one has heard about or might consider buying. While undoubtedly initial sales figures for the new iPhone have been quite impressive, I can’t help but think Apple has severely damaged customer relations in the UK, if not suffered a notable loss in sales. At this point in time, I’m really struggling to find that irrational love for a company that so many Apple fan-boys have latched onto over recent years. Sure, my current phone is an older iPhone model and my laptop a MacBook Pro, but I bought these products mainly because they far ahead of the field at the time of release and merited their price tags. With outstanding-looking Android phones currently on the market, and some impressive Windows Phone 7.5 models just released, I’m quickly rethinking whether to let myself be led around by Apple any more.

In short: get your act together, Apple, and don’t expect to remain the dominant player in consumer technology whilst sitting there and twiddling your thumbs. You’ve done of good work to earn the respect of millions of users throughout the world (not least through clever marketing), but realise that you’ve no god-given entitlement to keep it in the future.

The first thing that needs to be mentioned is my total relief at no long being a student of physics. Well alright, it wasn’t all that bad. To be fair, there were many parts of my degree I enjoyed, yet unfortunately my current feelings seem to be dominated by a few painful lecture courses and exams! In any case, I am now happy to announce that I’ve graduated with 2:1 honours in theoretical physics at a world-class university.

Before I commit myself to the unavoidable drudgery of a full-time career, or more likely (given my talent for procrastination) a PhD course, the plan is to take a very non-committal year out — post-university gap year if you like. More on future plans to come in another post, but for now I wanted to mention that I’m going to be doing some part-time month over the coming year. Specifically, I will be working as a private tutor in the areas of mathematics, physics, electronics, computing, and English language/literature. My plan is to do this on an ad-hoc basis alongside other potential freelancing work. Learning and particular pedagogy is something I’m very passionate about. For anyone that may just happen to stumble across this post, I am offering to tutor secondary school students as well as adult learners in the N/NE London and SW Essex regions in these subjects, focusing on GCSE and A-level courses, but willing to accommodate to other courses.

If you’re at all interested, you can check out my profile on First Tutors. Feel free to contact me either via the contact form on this website, or via the First Tutors website.

My problems, however, began when I started to read the Boot Camp installation guide. To my horror, in a clear notice in the guide, I was told that only a full installation disk for Windows can be used to install a Boot Camp (Windows) partition on the machine. Now, having long used Windows Vista on a previous laptop (which I was in the process of retiring), and given my purchase of a Windows 7 Ultimate upgrade disk less than a year earlier, I was most reluctant to shell out another larger sum of cash just to get Windows 7 running on my MacBook Pro. As it happens, my stubbornness insisted that I proceed with the Boot Camp installation anyway. (A few quickly researched articles online seemed to suggest I might have luck doing this.) In fact, I managed to use the upgrade disk to get as far as the verification code screen in the setup, before I decided things weren’t going to happen. Long story short: I played around with things for a while, eventually found a Microsoft support number to call, and had a very helpful and knowledgeable support technician guide me through the end of the installation and activation process.

As there appears to be minimal information regarding this process online, I thought I would post a short set of instructions here for all who are interested. Myself, I was much reassured to know that it is possible to make a clean installation of Windows (7) from an upgrade disk and activate the copy. While I have not tried the process on a machine other than my MacBook / outside of Boot Camp, I was reliabily informed that the process is no different. These are the steps to follow:

1. Insert the Windows Upgrade disk.
2. Follow the setup wizard and select the “clean install” option.
3. Windows should proceed to install successfully, and after a few reboots, you will reach the license key screen.
4. Leave the box for the license key blank and continue.
5. The installation should complete and you should be able to temporarily use Windows in “trial” mode (unactivated license).
6. Reboot the machine with the upgrade disk still in the drive.
7. When the setup screen loads, now select the “upgrade” option.
8. The setup should proceed to perform an “upgrade”. In fact, you are just “upgrading” Windows 7 to Windows 7 (in my case) – this is required for the sake of license activation.
9. When the upgrade process completes, log on to your administrator account.
10. Open the Computer Properties window (Control Panel\System and Security\System).
11. At the bottom of the page is the Windows activation section. Select the “Change product key” option.
12. Enter the product key for your Windows Upgrade disk, and voila, you should have a full licensed copy of Windows in your machine.
13. (If the previous activation step did not work, try the phone activation upon failure, which is virtually guaranteed to succeed.)

While this process is somewhat non-intuitive and poorly documented, it is nonetheless quite possible. (I suspect there may be a loophole that allows customers of only upgrade disks to install full licensed versions of Windows, which explains the lack of information on the matter.) Either way, I hope this short guide helps save others the moderate amount of pain and trouble I had trying to work around this issue myself! I would be pleased to hear of any other success stories.

Portrait of Tomaso Albinoni, to whom the piece is commonly misattributed.

Moving forward in time to the 1950s, we return with this piece to the style of Vivaldi and Bach. Albinoni’s Adagio in G minor was for some time thought to be be a work of the well-known 18th century Italian composer Tomaso Albinoni, yet is now accepted as a Neo-Baroque work of the modern biographer of Albinoni Remo Giazotto (with just perhaps some inspiration from an original Albinoni manuscript). The name and common attribution have nonetheless stuck, even to this day.

Though often described as a musical hoax, passing off a work as one by a famous master was a relatively common practice by lesser-known composers from the 19th century onwards, done in order to gain widespread recognition. In this sense, Giazotto has certainly succeeded, but moreover, he has created a masterpiece of modern classical music and an unforgettable melody of sombre.

Listen or Download Here

(Performed by the Leningrad Chamber Orchestra.)

AE Aurigae and the Flaming Star Nebula. Image Credit & Copyright: Rolf Geissinger.

NASA have for years now run the wonderful Astronomy Picture of the Day website, featuring a new (and almost invariably stunning) image of outer space or some astronomical phenomenon – from our own moon, to neighbouring planets, stars, and galaxies. Even better these days, the pictures are inevitably high-resolution, making them ideal for desktop wallpapers.

As it happens, some clever guy came up with the idea of creating a program to run in the background and automatically update your desktop each day with the latest astronomical picture, published by NASA on their website. The application, called APOD Wallpaper, is available to download and install on your Windows machine, and having used it for roughly a week now, I can already highly recommend this handy little app. As a student of physics (and someone with a particular interest in astrophysics and cosmology), this has quickly become a must-have for my laptop; yet who could not appreciate the beauty of these pictures?

May you never tire of your desktop again!

Update

Having just gotten hold of my lovely new MacBook Pro, I’ve had a chance to play around with getting an automatic APOD wallpaper on OS X too. As it turns out a certain scripting guru (Harold Bakker) has written a script to automatically update the OS X desktop wallpaper with the latest APOD and has kindly put it on his website. It’s slightly less trivial to setup than the Windows app, though he provides clear instructions on how to create a cron job for automatic updates… it’s been working perfectly for me so far!

Joaquin Rodrígo is arguably the greatest composer in the history of Spanish guitar music, though it was far from all he composed. His life, spanning almost the entirety of the 20th century, produced two great and enduring works. The more popular is the Concertio de Aranjuez, but it is his Fantasia para un gentilhombre, which I prefer and which I wish to introduce here. The name literally means “fantasy for a gentleman”; the gentleman in question here being the virtuoso guitarist Andrés Segovia. The piece itself draws inspiration from Spanish folk music, retaining both its lively and lyrical characteristics while making superb use of the classical orchestra. All in all, a true delight.

Watch and Listen:

1st Movement, Villano y Ricercare

2nd Movement, Españoleta y Fanfare

3rd Movement, Danza de las Hachas

4th Movement, Canario

(Performed by Narciso Yepes.)

(Unfortunately I couldn’t find any freely available download, so YouTube will make do! If you’re looking for a good performance to buy though, I can definitely recommend one by Pepe Romero and the Academy of St. Martin in the Fields.)

While such trees perhaps have their best known application in computer graphics, I discovered them here in relation to a computational physics project on which I am currently working. For those who are curious about the context, I have recently been doing some statistical analysis on the distribution stars using the Hipparcos catalogue. Unfortunately due to sheer number of stars (100,000+), performing a nearest neighbour search or range search on each star in 3D (Euclidean) space is simply infeasible without the use of a clever algorithm. This is how I discovered the wonder of kd-trees, reducing a task that would otherwise take days to several minutes.

The software I am writing for this project happens to be in C# 4.0, and upon a bit of investigation, I discovered that there exists no (decent) implementation of the kd-tree structure and its algorithms for .NET.  Thus, with a bit of help from the Wikipedia article and a paper I dug up, I decided to have a go at a generic implementation. Now that it is complete and tested, I can gladly declare that the job was not half as easy as I expected (but somehow quite rewarding)!

The following features have been implemented (and fully documented with XML comments).

• Tree construction
• Dynamic node addition
• Dynamic node removal
• Nearest neighbour search
• Range search

I’ve now uploaded the complete code for the implementation, which is available below as several C# code files. Note that you will also need the (wonderful) Math.NET Numerics library to compile things – it provides the generic vector type and a few other handy things. (You can probably adapt the code easily enough if you don’t fancy having  this dependency.)

Downloads

(All code is licensed under the MIT license. Copyright 2011 Alex Regueiro.)

KdTree.cs

KdTreeNode.cs

Arithmetic.cs

Tests (MSTest framework)

KdTreeTests.cs

The idea is that the KdTree class is available to use as a black box, so let me know if anything is unclear. (If you’re wondering though, the arithmetic stuff is there to provide generic arithmetic support complementing the generic vector support. You’ll probably just want to use double most of the time.) Finally, if you’re interested in the unit tests, you can grab them over at the project repository. Enjoy.