2014-12-05 § 5 Comments
The UK Government Statistical Service recently released its good practice guidance for releasing statistics in spreadsheets. While this advice is clearly well-intentioned*, and parts of it are good, the overall effect is to encourage the release of data in formats that are difficult to process by computer. This is a disappointing retrograde step.
2014-08-22 § 5 Comments
What’s the shortest string that contains every possible permutation of ABCD somewhere inside it? As it happens, it’s 33 letters long: ABCDABCADBCABDCABACDBACBDACBADCBA. A string like this is called a minimal superpermutation.
So what’s the shortest string that contains every possible permutation of ABCDE? It was recently shown that 153 letters is the shortest possible, and that there are eight different superpermutations of this length.
Okay, what about ABCDEF? The answer is that nobody knows. Until this week the shortest known superpermutation of ABCDEF was 873 letters long:
ABCDEFABCDEAFBCDEABFCDEABCFDEABCDFEABCDAEFBCDAEBFCDAEBCFDAEBCDFAEB CDAFEBCDABEFCDABECFDABECDFABECDAFBECDABFECDABCEFDABCEDFABCEDAFBCED ABFCEDABCFEDABCADEFBCADEBFCADEBCFADEBCAFDEBCADFEBCADBEFCADBECFADBE CAFDBECADFBECADBFECADBCEFADBCEAFDBCEADFBCEADBFCEADBCFEADBCAEFDBCAE DFBCAEDBFCAEDBCFAEDBCAFEDBCABDEFCABDECFABDECAFBDECABFDECABDFECABDC EFABDCEAFBDCEABFDCEABDFCEABDCFEABDCAEFBDCAEBFDCAEBDFCAEBDCFAEBDCAF EBDCABEFDCABEDFCABEDCFABEDCAFBEDCABFEDCABACDEFBACDEBFACDEBAFCDEBAC FDEBACDFEBACDBEFACDBEAFCDBEACFDBEACDFBEACDBFEACDBAEFCDBAECFDBAECDF BAECDBFAECDBAFECDBACEFDBACEDFBACEDBFACEDBAFCEDBACFEDBACBDEFACBDEAF CBDEACFBDEACBFDEACBDFEACBDAEFCBDAECFBDAECBFDAECBDFAECBDAFECBDACEFB DACEBFDACEBDFACEBDAFCEBDACFEBDACBEFDACBEDFACBEDAFCBEDACFBEDACBFEDA CBADEFCBADECFBADECBFADECBAFDECBADFECBADCEFBADCEBFADCEBAFDCEBADFCEB ADCFEBADCBEFADCBEAFDCBEADFCBEADCFBEADCBFEADCBAEFDCBAEDFCBAEDCFBAED CBFAEDCBAFEDCBA
and it was thought that might be the shortest possible.
But we now know it isn’t, because I found a shorter one:
ABCDEFABCDEAFBCDEABFCDEABCFDEACBFDEACFBDEACFDBEACFDEBACFDEABCDFEAB CDAEFBCDAEBFCDAEBCFDAEBCDFAEBCDAFEBCDABEFCDABECFDABECDFABECDAFBECD ABFECDABCEFDABCEDFABCEDAFBCEDABFCEDABCFEDACBFEDCABFDECAFBDCEAFBDCA EFBDCAFEBDCAFBEDCAFBDECAFDBECADFBECADBFECADBEFCADBECFADBECAFDEBCAD FEBCADEFBCADEBFCADEBCFADEBCAFDECBAFDECABFDCEABFDCAEBFDCABEFDCBAEFD BCAEDFBCAEDBFCAEDBCFAEDBCAFEDBCAEFDBACEFDBAECFBDAECFBADECFBAEDCFBA ECDFBACEDFBACDEFBACDFEBACDFBEACDFBAECFDBAEFCDBAFECDBAFCEDBAFCDEBAF CDBEAFCDBAEFDCBEAFDCBEFADCBEFDACBEFDCABFEDCBAFEDCBFAECDBFACEDBFACD EBFACDBEFACDBFEACDBFAECBDFEACBDFECABDFCEABDFCAEBDFCABEDFCBAEDFCBEA DFCBEDAFCBEDFACBEDFCABDEFCBADEFCBDAEFCBDEAFCBDEFACBDEFCABDFECBADFE CBDAFECBDFAECBFDAECBFADECBFAEDCBFEADCFBEADCFEBADCEFBADCEBFADCEBAFD CEBADFCEBADCFEABDCFAEBDCFABEDCFABDECFABDCEFABDCFEADBCEFADBCEAFDBCE ADFBCEADBFCEADBCFEADCBFEDACFBEDACFEBDACEFBDACEBFDACEBDFACEBDAFCEBD ACFEDBACFEDABC
I’ve uploaded a short note about it to the arxiv.
2013-08-18 § 37 Comments
I hate the Pumping Lemma for regular languages. It’s a complicated way to express an idea that is fundamentally very simple, and it isn’t even a very good way to prove that a language is not regular.
Here it is, in all its awful majesty: for every regular language L, there exists a positive whole number p such that every string w∈L that has p characters or more can be broken down into three substrings xyz, where y is not the empty string and the total length of xy is at most p, and for every natural number i the string xyiz is also in L.
« Read the rest of this entry »
2013-07-10 § Leave a comment
2013-05-10 § Leave a comment
2013-04-19 § 3 Comments
Quite a few people were surprised by my description of Adrift as a “new game” – even though it was very new at the time – because they had seen similar games or puzzles before.
Adrift puzzles are a little bit different, though: they’re on an unusual grid – the surface of half a cube, i.e. three square grids connected at the edges – and also there are rocks, squares you’re not allowed to use.
2012-10-27 § Leave a comment
Conway is incredibly untidy. The tables in his room at the Department of Pure Mathematics and Mathematical Statistics in Cambridge are heaped high with papers, books, unanswered letters, notes, models, charts, tables, diagrams, dead cups of coffee, and the most amazing assortment of bric-a-brac, which has overflowed most of the floor and all of the chairs, so that it is hard to take more than a pace or two into the room and impossible to sit down. If you can reach the blackboard there is a wide range of coloured chalk, but no space to write. His room in college is in a similar state. In spite of his excellent memory he often fails to find the piece of paper with the important result that he discovered some days before, and which is recorded nowhere else. Even Conway came to see that this was not a desirable state of affairs, and he set to work designing and drawing plans for a device which might induce some order amongst the chaos. He was about to take his idea to someone to get it implemented, when he realised that just what he wanted was standing, empty, in the corner of his room. Conway had invented the filing cabinet!
Richard K Guy on John H Conway, in Mathematical People
I originally posted this to Posterous on 27 October, 2012. Posterous is closing down, so I have migrated it here on 13 March, 2013.