Noldorin's Blog

For whatever reason, I remember quite clearly the first time I was introduced to the wonder of paradoxes. Curiously, it was during an English class in my first year of secondary school, and the rather eccentric teacher had a particular tendency to ramble on about any interesting topic (usually well outside of the syllabus). A criticism this is not, as it was many years before the seriousness of GCSEs and A-levels. I think that in looking back I took great enjoyment out of those classes, even if I did not so much realise it then. (And it wasn’t just for the fact that we didn’t spend countless hours analysing poetry or Shakespeare.) Moreover, it is plain now that he was, through a variety of ways, trying to open our young and malleable minds so that they might perhaps (idealistically) become sharp and inquisitive, and remain so through the future years of drudgery.

Before I continue too far on such a tangent myself, let me present the focus of this post, that is one of the paradoxes with which I became acquainted during one of those many unusual English classes. I have forgetten the precise details, but the following I think is a half-way accurate rendition of what was then told (though the many embellishments may differ to those of my former teacher). As you may guess from the title, I term this little problem the “Traveller’s Paradox”, though I don’t think it has any conventional name, and has undoubtedly been repeated in many varying forms.

Warning to unsuspecting readers: the following situation is presented in the fairy-tale style. I was told it this way, so that’s how it’s going to get repeated – can’t please everyone!

A wearied prince has travelled many leagues on his quest to reach the all but forgotten castle that is the target of his quest; the location of the the legendary gem that is the final chance to save his kingdom from ruin. The pale sun is gradually vanishing behind the horizon as the young man approaches a great fork in the road ahead, far beyond which he can glimpse the tall spires of the castle that is his destination. Having sought his goal by his wits and instincts alone thus far, he is now unsure of which path to take from this point. Alas, time permits him to delay no longer if he is to succeed in his quest, and he must make the choice of road before darkness falls.

Approaching the split in the wide path, he scarcely notices two giants standing motionlessly at the side of the path. In this moment the prince recalls the words of the sage whom he had oft consulted; these twin giants, identical in appearance, were the only living creatures who know the safe pafe to the fabled castle. Yet he has a dilemma, for one of them always lies while the other always tells the truth, and what is worse, no-one may ask either of them but a single question.

Making the wrong choice of path will lead inevitably to peril and the ultimate failure of his quest. Only one of the roads provides a safe route directly to his goal. Not willing to let the fate of his realms rest in the hands chance, the prince knows he must ask one of the giants the question that will tell him the safe path – but which giant, and what question?

Now, before continuing, do ponder for a while the nature of this paradox, if you are not already. I do promise  that this dilemma does in fact have a sane solution, and unlike other paradoxes, is not a fundamental contradiction of logic and reason. Read on only when you wish to see the answer, and more relevantly, the formal (mathematical) method we can use in treating such a paradox.

Mathematical (or formal) logic is arguably at the heart of mathematics itself, and is to many the foundation of all science, philosophy, and general reason. Logic is unfortunately not such an intuitive thing to we as humans (without exception) – at least, beyond the very superficial level. Certainly, what has developed into the field of formal logic (in particular modern research into higher-order logics) would make little to zero sense to anyone discovering it upon the first time. It does not take much consideration to realise that the human mind, not unalike to those of other creatures, is one tailored by the eons of evolution to the tasks of survival and continuation of the species. Indeed, we were never remotely designed to unravel the mysteries of the universe, and it is only through our higher level capacities developed through other means that we may begin to do so. (That is at least the brutal atheists approach, and I am among those who would argue the point at a higher level.)

Without assuming too much prior knowledge of fundamental mathematics, specifically formal logic, I will now introduce an approach to resolving in a (simple?) mathematical manner what initially appears to be a very counter-intuitive situation. Do not fret though, for I myself have barely touched the surface of these areas. Still, for the sake of conciseness, I am going to assume you either have an elementary knowledge of formal logic, or can look up the ideas involved, where necessary. If you haven’t yet seen it, I mentioned a great tutorial for starting out in a previous post. (The Wikipedia pages may be enough if you just want an overview though.)

Firstly, let us formulate the given problem in the language of propositional logic, which involves nothing more than the manipulation of true and false values, in essence. There is no fool-proof way of doing this translation, of course, but read on and I think you will see it all works out pretty well.

Note that I use for the truth value and for the false value here.

To begin let us define the propositional variables and functions we will be using:

By arbitrarily labelling the pair of giants, let represent the truth-telling one and the lie-telling one.

Note that $\equiv$ is not actually a symbol in propositional logic, but just syntax for defining a variable.

Now, using this notation, and carefully analysing the situation (problem) presented in the above text, we can see that the problem is to find a formula for that satisfies a proposition that represents the problem. First, observe that whichever giant you ask, the reply you get will be either or in response.

The proposition that defines the situation is then:

In words, that is: asking the particular question to either giant, you will get the same response (yes/no answer) every time, and this answer will also indicate that you should take path (if true, the “first” path; if false, the “second” path).

Unsurprisingly perhaps, there is no well-defined procedure for finding the correct formula for . (There are in fact a number of perfectly valid/equivalent solutions that are relatively simple.) Now, since is simply a function of the propositional variable , we can quite easily factor out the dependence on and still write without loss of generality as:

If one wanted to be utterly rigorous, one could then take this formula for , substitute it into the problem definition, and use the rules of inference (for whatever formal system) to manipulate it into a form that explicitly gives and . On the other hand, I’d rather not lose any readers I still have at this point, so let’s do things the slightly more intuitive way by using some simple human analysis!

The propositional operator , while defined as the bidirectional application of the logical implication operator (i.e. ), can also be seen as representing equivalence of two formulas. (This can indeed by proven formally, though again it’s not really worth the space here I feel.)

Taking the original proposition, we can see (again, with a bit of higher-level analysis) that it implies both:

and

By straightforward substitution for , and a bit of simplification, we can then deduce that:

With the understanding of as representing identity, as previously stated, we can substitute the values for and back into the previous formula to get the following.

Problem solved… right? Well no, not quite actually. If we had mechanically applied the rules of inference from the axioms and the formulaic representation of the problem, we would undoubtedly be able to stop at this point (requiring a good few more pages of derivation however). Since we have not been completely rigorous, we must now prove that this definition of is indeed a correct solution to the problem. Let us substitute the formula back into the problem definition and see.

Hence, we now know that the above solution is correct. What remains is only to translate this formula into plain English. Not so trivial, I think we would agree. The first thing to note is that the parameter is unknown to the prince who asks the question. Well, enough hints…  let’s see if anyone can figure it out first (no cheating), and I’ll update the post with an answer in a few days.

These  famous words of the French philosopher Voltaire are probably better understood as one of the many examples of his keen wit, rather than a profound statement; yet they do contain a certain poignancy. The self-referential nature of this quotation makes it so wonderfully ironic and perhaps even paradoxical. As with so many quotes that are worth knowing, there are often several levels of meanings: some obvious, others concaled; some sincere, others facetious. I would in fact beg to disagree with the title of this post (though I, as perhaps anyone) cannot say whether Voltaire made this comment literally or not. To me, it is the very nature of most, if not all, witty quotes, to in some way express a deeper truth – in some respect I think it is part of the definition. After all, truth is beauty, they say.

Enough of this meta-discussion, though. The purpose of this post is really just to share the small selection of the more memorable quotes I’ve picked up over the years (or at least the ones I’ve managed to jot down before they slipped away). Indeed, rather than launching into a commentary here of all the quotes, I thought it would be better simply to list them as a (hopefully dynamic) collection, leaving it as an “exercise for the reader” to gather what interpretation they will from the words. It is my opinion that they are both better understood and appreciated in such a way – at best it gives the reader undesirable preconceptions, at worst it demeans the thing.

Well, here they are then: my collection of quotations, aphorisms, adages, or whatever you want to call them. I’ve written them in what I believe to be their most commonly accepted form, and attributed them to their most widely acknowledged sources. Nonetheless, I have little doubt that some of them have been distorted, and may even be apophrycal, yet this never made a difference to me and I don’t see why it ever should from any but a historical perspective. Good sayings are often improved over time, sometimes so much that they cannot be attributed to any more than folk wisdom. Whatever they are, they certainly give pause to ponder.

Note: The juxtaposition between the more profound and the more humurous quotes below may seem slightly awkward, but I feel it would be too artificial to separate them out in a clear-cut fashion, so read them as you will.

Socrates (469 – 399 BC) – Ancient Greek philospher

I cannot teach anybody anything, I can only make them think.

Education is the kindling of a flame, not the filling of a vessel.

I know that I am intelligent, because I know that I know nothing.

The unexamined life is not worth living.

Plato (428 – 348 BC) -  Ancient Greek philospher

Be kind, for everyone you meet is fighting a hard battle.

For a man to conquer himself is the first and noblest of all victories.

Courage is knowing what not to fear.

Excess of liberty, whether it lies in state or individuals, seems only to pass into excess of slavery.

Wise men talk because they have something to say; fools, because they have to say something.

Voltaire (1694 – 1778 AD) – French Enlightenment philosopher

Judge a person by their questions, rather than their answers.

He who thinks himself wise, O heavens! is a great fool.

Prejudice is opinion without judgement.

The multitude of books is making us ignorant.

I disapprove of what you say, but I will defend to the death your right to say it.

Common sense is not so common.

This agglomeration which was called and which still calls itself the Holy Roman Empire was neither holy, nor Roman, nor an empire.

Oscar Wilde (1854 – 1900 AD) – Irish poet and playright

Man can believe the impossible, but can never believe the improbable.

What is a cynic? A man who knows the price of everything and the value of nothing.

A man who does not think for himself does not think at all.

Nothing that is worth knowing can be taught.

Albert Einstein (1879 – 1955 AD) – German theoretical physicist

There are two ways to live: you can live as if nothing is a miracle; you can live as if everything is a miracle.

Science without religion is lame, religion without science is blind.

Logic will get you from A to B. Imagination will take you everywhere.

The important thing is not to stop questioning. Curiosity has its own reason for existing.

Everything should be as simple as it is, but not simpler.

Once we accept our limits, we go beyond them.

Small is the number of people who see with their eyes and think with their minds.

Try not to become a man of success but rather to become a man of value.

Imagination is more important than knowledge. For knowledge is limited to all we now know and understand, while imagination embraces the entire world, and all there ever will be to know and understand.

Common sense is the collection of prejudices acquired by age eighteen.

Mark Twain (1835 – 1910 AD) – American author

All generalizations are false, including this one.

Do not put off till tomorrow what can be put off till day-after-tomorrow just as well.

Good friends, good books and a sleepy conscience: this is the ideal life.

The man who does not read good books has no advantage over the man who cannot read them.

Never let formal education get in the way of your learning.

It is better to keep your mouth shut and appear stupid than to open it and remove all doubt.

Karl Weierstrass (1815 – 1897) – German mathematician

When I wrote this, only God and I understood what I was doing. Now, God only knows.

Oliver Heaviside (1850 – 1925) – English mathematician and physicist

Why should I refuse a good dinner simply because I do not understand the digestive processes involved?

As I said, I hope to update this list over time as I pick up more – do however please feel free to suggest any particularly worthwhile along the same themes expressed here.

The Qualification round for Google Code Jam 2009 is entering its closing hours, and having submitted my solutions for the three problems, I thought I would share just the framework I set up for solving the problems. This is something I originally began  writing for last year’s Code Jam, but I have updated it for the altered format this year, as well as expanded the functionality.

The framework consitsts of a class that has a number of simple methods for accessing the input data as well as writing the output cases. The main convience is its abstraction of the text file I/O  into simple methods that deal with arrays (and arrays of arrays) of primitive types. As a bonus, all the relevant output information, as well as the execution time, is printed to the standard out stream (console window).

using System;
using System.IO;
using System.Text;

public class CodeJamProblem : IDisposable
{
    protected int caseNumber;

    protected StreamReader textReader;
    protected StreamWriter textWriter;

    private bool disposed = false;

    public CodeJamProblem(string inputFileName)
    {
        this.InputFileName = inputFileName;
        this.OutputFileName = Path.ChangeExtension(this.InputFileName, ".out");

        this.textReader = new StreamReader(this.InputFileName);
        this.textWriter = new StreamWriter(this.OutputFileName);

        this.caseNumber = 1;
        this.StartTime = Environment.TickCount;
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected void Dispose(bool disposing)
    {
        if (!disposed)
        {
            if (disposing)
            {
                this.ElapsedTime = Environment.TickCount - this.StartTime;

                textReader.Dispose();
                textWriter.Dispose();

                Console.WriteLine("Elapsed time: {0:#,#0}ms", this.ElapsedTime);
                Console.Beep();
                Console.ReadKey(true);
            }
        }

        disposed = true;
    }

    public int StartTime
    {
        get;
        private set;
    }

    public int ElapsedTime
    {
        get;
        private set;
    }

    public int CurrentCaseNumber
    {
        get { return this.caseNumber; }
    }

    public bool InputAvailable
    {
        get { return this.textReader.Peek() != -1; }
    }

    public string InputFileName
    {
        get;
        private set;
    }

    public string OutputFileName
    {
        get;
        private set;
    }

    public void OutputCase(params object[] values)
    {
        var parts = new string[values.Length];
        for (int i = 0; i < parts.Length; i++)
            parts[i] = values[i].ToString();
        OutputCase(string.Join(" ", parts));
    }

    public void OutputCase()
    {
        OutputCase((string)null);
    }

    public void OutputCase(string value)
    {
        WriteLine("Case #{0:#0}: {1}", this.caseNumber, value);
        this.caseNumber++;
    }

    public void WriteArrays<T>(T[][] entries)
    {
        for (int i = 0; i < entries.Length; i++)
            WriteArray(entries[i]);
    }

    public void WriteArray<T>(T[] values)
    {
        var parts = new string[values.Length];
        for (int i = 0; i < parts.Length; i++)
            parts[i] = values[i].ToString();
        WriteLine(string.Join(" ", parts));
    }

    public void WriteLines(string[] lines)
    {
        for (int i = 0; i < lines.Length; i++)
            WriteLine(lines[i]);
    }

    public void WriteLine(string format, params object[] arg)
    {
        Console.WriteLine(format, arg);
        this.textWriter.WriteLine(format, arg);
    }

    public void WriteLine(string line)
    {
        Console.WriteLine(line);
        this.textWriter.WriteLine(line);
    }

    public int[][] ReadIntArrays(int count)
    {
        var entries = new int[count][];
        for (int i = 0; i < entries.Length; i++)
            entries[i] = ReadIntArray();
        return entries;
    }

    public int[] ReadIntArray()
    {
        var parts = ReadParts();
        var values = new int[parts.Length];
        for (int i = 0; i < values.Length; i++)
            values[i] = int.Parse(parts[i]);
        return values;
    }

    public double[][] ReadDoubleArrays(int count)
    {
        var entries = new double[count][];
        for (int i = 0; i < entries.Length; i++)
            entries[i] = ReadDoubleArray();
        return entries;
    }

    public double[] ReadDoubleArray()
    {
        var parts = ReadParts();
        var values = new double[parts.Length];
        for (int i = 0; i < values.Length; i++)
            values[i] = double.Parse(parts[i]);
        return values;
    }

    public string[] ReadParts()
    {
        return ReadLine().Split(' ');
    }

    public string[] ReadLines(int count)
    {
        var lines = new string[count];
        for (int i = 0; i < lines.Length; i++)
            lines[i] = ReadLine();
        return lines;
    }

    public string ReadLine()
    {
        return this.textReader.ReadLine();
    }
}

Hopefully this will assist someone other tham myself, though I suspect most contestants have set up something of the same sort. I will continue to make minor modifications over the duration of the contest, and will update this post to reflect them.

Regarding the Qualification round itself, the problems have proven to be fairly interesting. (Well, the first was rather trivial if one is honest.) Now, only to wait for the upcoming Round 1, and hope the problems don’t become too much more challenging!

Yesterday I happened to stumble across a code golf question and for no particular reason (except for perhaps boredom) decided to create my own problem and to post it on StackOverflow for the community to reply with their solutions. It actually turned out to be much more popular than I might have anticipated.

A quick definition of code golf for those who are unaware of this enormous (though really quite enjoyable) time sink:

The objective of code golf is simply to write a program/function that solves a given problem using the fewest possible number of characters. This usually involves clever tricks related to the problem and whatever language you use, followed by heavy obfuscation.

Here is the problem specification, copied from my StackOverflow post:

Write a function that takes a single argument that is a string representation of a simple mathematical expression and evaluates it as a floating point value. A “simple expression” may include any of the following: positive or negative decimal numbers, +, -, *, /, (, ). Expressions use (normal) infix notation. Operators should be evaluated in the order they appear, i.e. not as in BODMAS, though brackets should be correctly observed, of course. The function should return the correct result for any possible expression of this form. However, the function does not have to handle malformed expressions (i.e. ones with bad syntax).

Examples of expressions:

1 + 3 / -8                            = -0.5       (No BODMAS)
2*3*4*5+99                            = 219
4 * (9 - 4) / (2 * 6 - 2) + 8         = 10
1 + ((123 * 3 - 69) / 100)            = 4
2.45/8.5*9.27+(5*0.0023)              = 2.68...

Now, my own solution isn’t particularly astounding, but I did get it down to 403 characters, and have since cut off a few more (though haven’t bothered to re-obfuscate it). It is in fact my first proper attempt at code golf, so I don’t consider it too bad.

Here it is, in all its obfuscated glory:

float e(string x){float v=0;if(float.TryParse(x,out v))return v;x+=';';int t=0;char o,s='?',p='+';float n=0;int l=0;for(int i=0;i<x.Length;i++){o=s;if(x[i]!=' '){s=x[i];if(char.IsDigit(x[i])|s=='.'|(s=='-'&o!='1'))s='1';if(s==')')l--;if(s!=o&l==0){if(o=='1'|o==')'){n=e(x.Substring(t,i-t));if(p=='+')v+=n;if(p=='-')v-=n;if(p=='*')v*=n;if(p=='/')v/=n;p=x[i];}t=i;if(s=='(')t++;}if(s=='(')l++;}}return v;}

And in a rather more readable form (identical in functionality):

float Eval(string expr)
{
    float val = 0;
    if (float.TryParse(expr, out val))
        return val;
    expr += ';';
    int tokenStart = 0;
    char oldState, state = '?', op = '+';
    float num = 0;
    int level = 0;
    for (int i = 0; i < expr.Length; i++)
    {
        oldState = state;
        if (expr[i] != ' ')
        {
            state = expr[i];
            if (char.IsDigit(expr[i]) || state == '.' ||
                (state == '-' && oldState != '1'))
                state = '1';
            if (state == ')')
                level--;
            if (state != oldState && level == 0)
            {
                if (oldState == '1' || oldState == ')')
                {
                    num = Eval(expr.Substring(tokenStart, i - tokenStart));
                    if (op == '+') val += num;
                    if (op == '-') val -= num;
                    if (op == '*') val *= num;
                    if (op == '/') val /= num;
                    op = expr[i];
                }
                tokenStart = i;
                if (state == '(')
                    tokenStart++;
            }
            if (state == '(')
                level++;
        }
    }
    return val;
}

The current leading solution in one written in Haskell (a mere 226 chars), with another in Python (237 chars) taking second place. This hardly surprises me – the functional and dynamic languages almost inevitably have more succinct syntax, besides generally being known to be more suitable for creating parsers. (If I hadn’t specified the absence of the BODMAS rules, I would have surely seen a solution containing little more than an “eval” statement!) Interestingly, the top two have both managed to avoid using regex altogether (though other solutions have with some success). In my opinion, it’s worth reading through the question to see how the various languages compare at performing the same task.

Please feel free to reply to the StackOverflow question or this post if you have a unique solution (in any language) that you’d like to share.

Update

I ended up spending just a bit longer on this task, since having seen some of the other solutions, it became pretty clear that I could get the char count down a good deal more. With the help of regex, my new solution stands at 294 characters. That in fact seems to be the winner amongst the set of solutions in C-style languages, so I’m quite pleased. (I have now promised myself not to entertain myself any long with this game, however.)

Here it is in a (relatively) clear form, in case anyone is interested. (It assumes the System.Text.RegularExpressions namespace has been imported.)

float e(string x)
{
    while (x.Contains("("))
        x = Regex.Replace(x, @"\(([^\(]*?)\)", m => e(m.Groups[1].Value).ToString());

    float r = 0;
    foreach (Match m in Regex.Matches("+" + x, @"\D ?-?[\d.]+"))
    {
        var o = m.Value[0];
        var v = float.Parse(m.Value.Substring(1));
        r = o == '+' ? r + v : o == '-' ? r - v : o == '*' ? r * v : r / v;
    }
    return r;
}