Coding fun, that is. Why, what were you thinking?
Amy, for reasons best known to herself, posited the following problem on Facebook:
Challenge: See how many words you can make using the letters from "entertainment", but *only* in the order they originally appear, i.e. tram is fine but meat is not.
We'll ignore the pro-public-transport-and-vegetarianism agenda clearly supported by this brain-washing exercise, and focus on solving the problem.
I used the word list available here: http://www.puzzlers.org/pub/wordlists/enable1.txt to solve the problem. A more efficient, but slightly less comprehensive, solution would have used the Official Scrabble Wordlist, which is limited to words of eight or fewer letters, and is available here: http://www.puzzlers.org/pub/wordlists/ospd.txt. Thankfully, "aardwolf", my new favourite word, is included on both.
The Python script I used to solve the problem can be found here: http://pastebin.com/1QvTwvCq. Anyone on a Mac or a UNIX/Linux computer should be able to simply run the script by double-clicking it - anyone on Windows will probably have to download and install the excellent, wonderful, graceful, beautiful, utterly splendid language known as Python (from the download link off of here) to run it. You won't regret it. Coding has been one of the more life-changing skills I've ever learnt (not that I would claim to be very good!), and while every nerd has their favourite language, Python is generally acknowledged as being one of the easiest to learn on (citation: here)
Monday, 12 March 2012
Friday, 9 March 2012
Foundation's Edge
Several years ago, the only presents I asked for for my birthday were the "Foundation" series, by Isaac Asimov. I'd just discovered some of his incredible "Robots" short stories, which are widely regarded as being some of the most concise, imaginative, and visionary science fiction of its time. I think it's fair to say that, without Asimov's pioneering work in exploring the possibilities of robotics, and the mirror that it holds up to humanity, both science fiction and science fact would have been majorly hampered. I'd put good money on a large proportion of engineering or physics students having been inspired, at least partly, by an Asimovian story - and, as John Jenkins said in a review, "It has been pointed out that most science fiction writers since the 1950s have been affected by Asimov, either modeling their style on his or deliberately avoiding anything like his style."
I had great fun poking around in the many dusty old bookstores of Uppingham, happening across all manner of quaint and curious volumes of forgotten lore which, if I had a thousand lifetimes and funds to match, I would happily devour. Eventually I tracked down battered old paperback versions, which were promptly bought on my behalf and ceremonially presented to me.
The Foundation saga is one of Asimov's two best known series, along with the Robots series. The main premise of this futuristic storyline is the concept that, with a great deal of sophistication and study, and the application of statistical modelling, it would be possible to refine large-scale sociology to the state of being a predictive science, capable (in the hands of a skilled analyst) of making accurate forecasts of the behaviour of large bodies of people. Using this newly-founded discipline of "psychohistory", a man named Hari Seldon realises that the current apparently-glorious Galactic Empire is soon headed for a collapse, after which there will be a period of thirty thousand years of "dark ages", where planets will become cut off from one another, and science and civilization will regress. He foresaw a solution to the equations, however, wherein this interregnum was limited to only one thousand years, after which a new uniting Empire would arise, preserving the knowledge and culture of humanity. To this end, he commissions the foundation of a colony of scientists and researchers at the precise point in unsettled space where, according to his calculations, the evolution of their society will be such that they will be perfectly situated to react to any emerging threats, and to spread their influence until they can establish a new Empire.
The first book in the series, Foundation, was originally written and published as a string of short stories, which together told of the Foundation's rise to prominence - and it is simply wonderful. While the writing isn't of Shakespearean, Wildean, or Wodehousean standards, it's still very enjoyable - but the beauty of the series lies not in its language, but in its content. Each episode succinctly encapsulates another stage in the society's development, with most providing some sort of interesting twist or witty observation. The next two books, Foundation and Empire and Second Foundation, told more of a cohesive story - of the burgeoning Foundation's clashes with the expiring Empire, and subsequently with a mutated human named the Mule, who has the ability to affect emotions and inspire fanatical loyalty - something which Seldon's plan, relying as it did abstractions over large groups of people and the assumption that no single person could have a measurable effect on galactic civilization, was not designed to accommodate.
Three fantastic books, with which Asimov was well-pleased, and which wrapped up with a satisfying conclusion. Unfortunately, while the series continued to be popular more than thirty years after their publication, Asimov's publishers exerted increasing pressure on him to return to the series, despite his protests. "Foundation's Edge" is the result - and his lack of inspiration really shows. The writing falls prey to the worst pitfalls of bad science-fiction writing - over-emphasis on technological development itself (rather than its effect on persons and society), and "tell, not show" dialogue - "as I'm sure you're aware, my friend, this ship is equipped with the latest gravitic drive technology...". In fact, there is a character - a previously planet-bound historian who accompanies the main character on his journeys - who, except for one short passage in which he takes a leading role, serves solely as an exposition-post: "oh, I know nothing of the ways of space travel - please, tell me [and the reader] what is going on!". I paraphrase, but the awkwardness of the writing is of almost that level.
What's more, the book isn't redeemed by its predecessors' intriguing insights or unexpected twists either. Every "surprise" is easily foreseeable, every hidden allegiance is plainly obvious - it got to the stage that I was almost expecting a double-bluff, so obvious were the deceptions!
I really wouldn't recommend reading this, unless you are a fanatic Foundation fan and are absolutely desperate for more material (though, even more so than with the latter Matrix movies, it is a "sequel" in almost name-only - the content and style is so far removed to be almost unrecognisable). I'm not even sure that I'll be reading the fifth book, Foundation and Earth. Far better to enjoy the sublime three original books in isolation, and then to move on to another master of science fiction without sullying them. On that note, I discovered that I still have Iain M. Banks' Consider Phlebas sitting on my bookshelf - since the last two of his books that I read were outstanding (and worthy of posts in their own right - certainly The Culture should really have been mentioned in any discussion of transhumanism, so I'll have to remember that for my follow-up post!), and I've been reliably informed that this is even better, I have high hopes!
You may notice that I've been linking out to Amazon more than usual in this post - that's no coincidence. I've just signed up for a service known as "Amazon Associates", whereby, if someone clicks on a link from my site to Amazon and then buys an item, 5% of the price goes to me instead of Amazon (the user pays the same price). I don't foresee being able to retire on the proceeds anytime soon, but I figure every little helps! Clicking a link, browsing around, and then buying another item works in just the same way, so if you do feel the need buy anything from Amazon and decide to navigate to it through one of my links, I would be massively appreciative!
I had great fun poking around in the many dusty old bookstores of Uppingham, happening across all manner of quaint and curious volumes of forgotten lore which, if I had a thousand lifetimes and funds to match, I would happily devour. Eventually I tracked down battered old paperback versions, which were promptly bought on my behalf and ceremonially presented to me.
The Foundation saga is one of Asimov's two best known series, along with the Robots series. The main premise of this futuristic storyline is the concept that, with a great deal of sophistication and study, and the application of statistical modelling, it would be possible to refine large-scale sociology to the state of being a predictive science, capable (in the hands of a skilled analyst) of making accurate forecasts of the behaviour of large bodies of people. Using this newly-founded discipline of "psychohistory", a man named Hari Seldon realises that the current apparently-glorious Galactic Empire is soon headed for a collapse, after which there will be a period of thirty thousand years of "dark ages", where planets will become cut off from one another, and science and civilization will regress. He foresaw a solution to the equations, however, wherein this interregnum was limited to only one thousand years, after which a new uniting Empire would arise, preserving the knowledge and culture of humanity. To this end, he commissions the foundation of a colony of scientists and researchers at the precise point in unsettled space where, according to his calculations, the evolution of their society will be such that they will be perfectly situated to react to any emerging threats, and to spread their influence until they can establish a new Empire.
The first book in the series, Foundation, was originally written and published as a string of short stories, which together told of the Foundation's rise to prominence - and it is simply wonderful. While the writing isn't of Shakespearean, Wildean, or Wodehousean standards, it's still very enjoyable - but the beauty of the series lies not in its language, but in its content. Each episode succinctly encapsulates another stage in the society's development, with most providing some sort of interesting twist or witty observation. The next two books, Foundation and Empire and Second Foundation, told more of a cohesive story - of the burgeoning Foundation's clashes with the expiring Empire, and subsequently with a mutated human named the Mule, who has the ability to affect emotions and inspire fanatical loyalty - something which Seldon's plan, relying as it did abstractions over large groups of people and the assumption that no single person could have a measurable effect on galactic civilization, was not designed to accommodate.
Three fantastic books, with which Asimov was well-pleased, and which wrapped up with a satisfying conclusion. Unfortunately, while the series continued to be popular more than thirty years after their publication, Asimov's publishers exerted increasing pressure on him to return to the series, despite his protests. "Foundation's Edge" is the result - and his lack of inspiration really shows. The writing falls prey to the worst pitfalls of bad science-fiction writing - over-emphasis on technological development itself (rather than its effect on persons and society), and "tell, not show" dialogue - "as I'm sure you're aware, my friend, this ship is equipped with the latest gravitic drive technology...". In fact, there is a character - a previously planet-bound historian who accompanies the main character on his journeys - who, except for one short passage in which he takes a leading role, serves solely as an exposition-post: "oh, I know nothing of the ways of space travel - please, tell me [and the reader] what is going on!". I paraphrase, but the awkwardness of the writing is of almost that level.
What's more, the book isn't redeemed by its predecessors' intriguing insights or unexpected twists either. Every "surprise" is easily foreseeable, every hidden allegiance is plainly obvious - it got to the stage that I was almost expecting a double-bluff, so obvious were the deceptions!
I really wouldn't recommend reading this, unless you are a fanatic Foundation fan and are absolutely desperate for more material (though, even more so than with the latter Matrix movies, it is a "sequel" in almost name-only - the content and style is so far removed to be almost unrecognisable). I'm not even sure that I'll be reading the fifth book, Foundation and Earth. Far better to enjoy the sublime three original books in isolation, and then to move on to another master of science fiction without sullying them. On that note, I discovered that I still have Iain M. Banks' Consider Phlebas sitting on my bookshelf - since the last two of his books that I read were outstanding (and worthy of posts in their own right - certainly The Culture should really have been mentioned in any discussion of transhumanism, so I'll have to remember that for my follow-up post!), and I've been reliably informed that this is even better, I have high hopes!
You may notice that I've been linking out to Amazon more than usual in this post - that's no coincidence. I've just signed up for a service known as "Amazon Associates", whereby, if someone clicks on a link from my site to Amazon and then buys an item, 5% of the price goes to me instead of Amazon (the user pays the same price). I don't foresee being able to retire on the proceeds anytime soon, but I figure every little helps! Clicking a link, browsing around, and then buying another item works in just the same way, so if you do feel the need buy anything from Amazon and decide to navigate to it through one of my links, I would be massively appreciative!
Saturday, 3 March 2012
Pilindrome
[Warning: this blog post contains mathematical notation. Continue at your own risk]
[edit: It's by no means clear that the A(i) are mutually exclusive, which renders this proof dodgy - though you can consider the events B(i), that the sequence up to i is a palindrome but contains no shorter palindromes, which are mutually exclusive, and have (I believe) the same probability, yielding the same result]
I recently rediscovered the truly excellent Abstruse Goose, a webcomic in the same vein as XKCD - reflections on a life more nerdy. Their (currently) latest comic piqued my interest - of course, π isn't a palindrome, since it's endless, but there are related questions that are intriguing.
I was particularly interested in determining whether π could be definitively stated to contain a palindromic elision - that is, some point at which, if you chopped it off there, the first digits of π (without decimal point) would read 314159265...562951413. A quick google turned up the following question, involving a reply from someone who clearly knows more about the relevant areas of maths than I do - I never took measure theory, and number theory and probability weren't my strong points. Still, I thought there would still be something interesting that I could tinker about with.
Since the question of π's normality[1] is apparently both important to the question, and an unsettled matter, I thought I'd transfer the question to a random sequence, since they're a bit more well-behaved. Note that below I'm investigating the question of whether truncating this sequence at some point will generate a palindrome, rather than the somewhat-looser question of whether the sequence will contain a palindrome at some point[2].
However, the "answer" that I got out doesn't seem intuitively right (for one thing, I was expecting a series that converged to 1), so I'm by no means staking my mathematical reputation on this - if anyone with a better grasp on the mathematics spots an error, please, by all means point it out!
Since this blog is meant to be accessible to non-nerds, I've done my best to provide a line-by-line commentary below so those without a mathematical education can follow along.
(Note that I'm not counting single digits as palindromes here, because that's a) silly and b) boring)
1. Let xi be an infinite random sequence, xi ∈ [9] ∀i
2. Let a finite sequence y1, y2, ... yn-1, yn, be called palindromic if yi = yn-i ∀i
3. We seek the probability that ∃n s.t. xi≤n is palindromic
4. Let A(n) be the event that x1, x2, ..., xn-1, xn is palindromic. Then we seek ℙ[j=2U∞ A(j)]
5. ℙ[A(j)] = 10 -floor(j/2)
6. ℙ[j=2U∞ A(j)] = j=2Σ∞10 -floor(j/2) = 2 j=1Σ∞10 -j
∴ Probability sought is 0.2̇
Apologies for the horrible horrible formatting - I haven't yet found a way to write LaTeX or similar on blogger, if anyone knows of one, please let me know!
Right, walkthrough time:
1. The subscript "i" is the index of the sequence. For instance, x1 would be the 1st number in the sequence, x52 the 52nd, and so on. [n] is a shorthand notation for "the set of numbers less than or equal to that number" - so [9] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The symbol ∀ means "for all" - so this statement is saying "whichever number you choose for i, xi will be a whole number between 0 and 9 inclusive"
2. This is defining what we mean by "palindromic" in terms of mathematical notation.
3. That symbol ∃ means "there exists" - i.e., we are looking for the probability that there is a number n such that, if we chop off the sequence at the nth number, it will form a palindrome.
4. The double-struck P (this font is sometimes called "Blackboard Bold") stands for "probability". The "U" symbol stands for "Union" (essentially, "combining" various events), and the sub- and super-script means that we are taking the union from j=2 to infinity. That is, we are looking for the probability that any truncation of the sequence (of length two or more) will be a palindrome.
5. This is stating the probability of the truncation at the nth digit being a palindrome. "floor" is a function that gives the smallest whole number less than or equal to the argument - so floor(2.5) is 2, but floor(3) is 3. The explanation for this probability is as follows; in order for a sequence to be a palindrome, we need the second half of the numbers (rounded down) to match the first half. The probability of any one number matching its partner is 1/10 (as there are 10 digits to choose from), so the probability of all of them matching is (1/10)floor(j/2) - and since (1/10) can be represented as 10-1, this gives the probability given above.
6. Putting a bar over a symbol or expression in maths is a common way of expressing "not/negation". In this case, since A(n) is the probability of the n-truncated sequence being a palindrome, A(n) is the probability of it not being a palindrome. If p is the probability of an event happening, then 1-p is the probability of that event not happening.
7. The spikey-E shape on the right-hand side here is called "Sigma". It represents repeated addition - in this case, "add up all values of 10 -floor(j/2) from j=2 upwards". We can do this because the probabilites of A(n) are mutually exclusive - that is, the probability of either one of them occurring is the addition of both of their probabilities. Since floor(2n/2) = floor(2n+1/2), this is equal to twice the addition with the floor and division-by-two removed.
The dot over the 2 means "repeating" - that is, the probability is 0.22222...
So, in summary, the maths above, in which I can't find a problem, gives us a 0.2222... probability of any given random sequence of numbers having a palindromic. In hindsight, and having benefitted from the added insight afforded by having to explain my working, I'm less uncomfortable with this answer than I was before - an answer of 0 would have been non-sensical, as clearly some random sequences exist with a palindromic truncation, but so would 1 as there "do" exist infinite sequences not containing palindromes. In fact, the construction of palindromes is quite artificial, so you would expect them to be reasonably rare. 0.222... therefore seems a sensible value for this probability.
It's amazing how quickly I've lost my fluency with maths, and especially probability - I could still remember all the pertinent details and get it done, but with none of the fluidity that I used to have! Definitely need to keep my brain in gear somehow...the iTunes U courses that have been recommended might be a good idea!
Anyway, I hope you've enjoyed this jaunt through maths...I'm at home right now, and our dinner guest has just appeared, so I must away!
[1] A "normal" number is one in which every possible digit (from 0 to 9, in the decimal system) occurs with the same density (i.e. has the same "chance" of occurring), every pair of digits has an equal density, every triple has an equal density, every string of four digits has an equal density, and so on. Confusingly, the vast majority of numbers that we encounter outside of a maths degree are not normal, because they are either integers ("whole numbers"), or terminating decimals (e.g. 5.324, as opposed to a non-terminating decimal like 7.3333333...). A little thought will show that neither of these can be normal, since they only have a finite number of digits to play with, and so they could not fulfil all of the conditions - trivially, it cannot be true that an integer with n digits contains all (n-1)-length digit strings with equal density, because there is only room for two such strings.
[2] Indeed, this is certain to happen in an infinite random sequence. Consider the fact that dd is a palindrome for any digit d. Then we seek the probability that the sequence contains any dd. The probability that any digit pair is any dd is 1/10 (the first digit can be chosen freely, and there is a one in ten chance that the next digit matches), so the probability they do not match is thus 9/10. The probability that not a single pair of digits in the sequence match is (9/10)*(9/10)*(9/10)*..., which tends to 0. So the probability that the sequence contains a matching pair (which are a palindrome) is 1.
[edit: It's by no means clear that the A(i) are mutually exclusive, which renders this proof dodgy - though you can consider the events B(i), that the sequence up to i is a palindrome but contains no shorter palindromes, which are mutually exclusive, and have (I believe) the same probability, yielding the same result]
I recently rediscovered the truly excellent Abstruse Goose, a webcomic in the same vein as XKCD - reflections on a life more nerdy. Their (currently) latest comic piqued my interest - of course, π isn't a palindrome, since it's endless, but there are related questions that are intriguing.
I was particularly interested in determining whether π could be definitively stated to contain a palindromic elision - that is, some point at which, if you chopped it off there, the first digits of π (without decimal point) would read 314159265...562951413. A quick google turned up the following question, involving a reply from someone who clearly knows more about the relevant areas of maths than I do - I never took measure theory, and number theory and probability weren't my strong points. Still, I thought there would still be something interesting that I could tinker about with.
Since the question of π's normality[1] is apparently both important to the question, and an unsettled matter, I thought I'd transfer the question to a random sequence, since they're a bit more well-behaved. Note that below I'm investigating the question of whether truncating this sequence at some point will generate a palindrome, rather than the somewhat-looser question of whether the sequence will contain a palindrome at some point[2].
However, the "answer" that I got out doesn't seem intuitively right (for one thing, I was expecting a series that converged to 1), so I'm by no means staking my mathematical reputation on this - if anyone with a better grasp on the mathematics spots an error, please, by all means point it out!
Since this blog is meant to be accessible to non-nerds, I've done my best to provide a line-by-line commentary below so those without a mathematical education can follow along.
(Note that I'm not counting single digits as palindromes here, because that's a) silly and b) boring)
1. Let xi be an infinite random sequence, xi ∈ [9] ∀i
2. Let a finite sequence y1, y2, ... yn-1, yn, be called palindromic if yi = yn-i ∀i
3. We seek the probability that ∃n s.t. xi≤n is palindromic
4. Let A(n) be the event that x1, x2, ..., xn-1, xn is palindromic. Then we seek ℙ[j=2U∞ A(j)]
5. ℙ[A(j)] = 10 -floor(j/2)
6. ℙ[j=2U∞ A(j)] = j=2Σ∞10 -floor(j/2) = 2 j=1Σ∞10 -j
∴ Probability sought is 0.2̇
Apologies for the horrible horrible formatting - I haven't yet found a way to write LaTeX or similar on blogger, if anyone knows of one, please let me know!
Right, walkthrough time:
1. The subscript "i" is the index of the sequence. For instance, x1 would be the 1st number in the sequence, x52 the 52nd, and so on. [n] is a shorthand notation for "the set of numbers less than or equal to that number" - so [9] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The symbol ∀ means "for all" - so this statement is saying "whichever number you choose for i, xi will be a whole number between 0 and 9 inclusive"
2. This is defining what we mean by "palindromic" in terms of mathematical notation.
3. That symbol ∃ means "there exists" - i.e., we are looking for the probability that there is a number n such that, if we chop off the sequence at the nth number, it will form a palindrome.
4. The double-struck P (this font is sometimes called "Blackboard Bold") stands for "probability". The "U" symbol stands for "Union" (essentially, "combining" various events), and the sub- and super-script means that we are taking the union from j=2 to infinity. That is, we are looking for the probability that any truncation of the sequence (of length two or more) will be a palindrome.
5. This is stating the probability of the truncation at the nth digit being a palindrome. "floor" is a function that gives the smallest whole number less than or equal to the argument - so floor(2.5) is 2, but floor(3) is 3. The explanation for this probability is as follows; in order for a sequence to be a palindrome, we need the second half of the numbers (rounded down) to match the first half. The probability of any one number matching its partner is 1/10 (as there are 10 digits to choose from), so the probability of all of them matching is (1/10)floor(j/2) - and since (1/10) can be represented as 10-1, this gives the probability given above.
6. Putting a bar over a symbol or expression in maths is a common way of expressing "not/negation". In this case, since A(n) is the probability of the n-truncated sequence being a palindrome, A(n) is the probability of it not being a palindrome. If p is the probability of an event happening, then 1-p is the probability of that event not happening.
7. The spikey-E shape on the right-hand side here is called "Sigma". It represents repeated addition - in this case, "add up all values of 10 -floor(j/2) from j=2 upwards". We can do this because the probabilites of A(n) are mutually exclusive - that is, the probability of either one of them occurring is the addition of both of their probabilities. Since floor(2n/2) = floor(2n+1/2), this is equal to twice the addition with the floor and division-by-two removed.
The dot over the 2 means "repeating" - that is, the probability is 0.22222...
So, in summary, the maths above, in which I can't find a problem, gives us a 0.2222... probability of any given random sequence of numbers having a palindromic. In hindsight, and having benefitted from the added insight afforded by having to explain my working, I'm less uncomfortable with this answer than I was before - an answer of 0 would have been non-sensical, as clearly some random sequences exist with a palindromic truncation, but so would 1 as there "do" exist infinite sequences not containing palindromes. In fact, the construction of palindromes is quite artificial, so you would expect them to be reasonably rare. 0.222... therefore seems a sensible value for this probability.
It's amazing how quickly I've lost my fluency with maths, and especially probability - I could still remember all the pertinent details and get it done, but with none of the fluidity that I used to have! Definitely need to keep my brain in gear somehow...the iTunes U courses that have been recommended might be a good idea!
Anyway, I hope you've enjoyed this jaunt through maths...I'm at home right now, and our dinner guest has just appeared, so I must away!
[1] A "normal" number is one in which every possible digit (from 0 to 9, in the decimal system) occurs with the same density (i.e. has the same "chance" of occurring), every pair of digits has an equal density, every triple has an equal density, every string of four digits has an equal density, and so on. Confusingly, the vast majority of numbers that we encounter outside of a maths degree are not normal, because they are either integers ("whole numbers"), or terminating decimals (e.g. 5.324, as opposed to a non-terminating decimal like 7.3333333...). A little thought will show that neither of these can be normal, since they only have a finite number of digits to play with, and so they could not fulfil all of the conditions - trivially, it cannot be true that an integer with n digits contains all (n-1)-length digit strings with equal density, because there is only room for two such strings.
[2] Indeed, this is certain to happen in an infinite random sequence. Consider the fact that dd is a palindrome for any digit d. Then we seek the probability that the sequence contains any dd. The probability that any digit pair is any dd is 1/10 (the first digit can be chosen freely, and there is a one in ten chance that the next digit matches), so the probability they do not match is thus 9/10. The probability that not a single pair of digits in the sequence match is (9/10)*(9/10)*(9/10)*..., which tends to 0. So the probability that the sequence contains a matching pair (which are a palindrome) is 1.
Subscribe to:
Posts (Atom)