Last night, a friend sent me this link. We discussed it for a bit, I sat down with a notebook and played with some numbers. Then I wrote the program to solve it (which I'm not posting because I don't think that would be fair). I think my solution was elegant, neat, and embarrassing. Because I think it's correct. My math is creaky enough that I can no longer remember how to prove my answer correct. I remembered how to generate prime factors and find the least common multiple (necessary for my solution), so my math isn't entirely shot, but it was a humbling experience. Worse, I might even be wrong.
The problem asks you to generate a number: the maximum number of times tries it's possible to get from the first typing of your name to actually seeing your name. The actual number of attempts is often lower and I think I know why, but I don't remember my statistics well enough to prove that, either. Hunches suck. I think I need to hit the math books again.
To test some ideas, I wrote another program which would actually generate the "typing" outlined in the problem. This helped me to quickly put to rest one suggestion someone else made. This isn't the problem they want you to write, so I think it's OK to post (and I think it shows off why I like Perl so much).
#!/usr/bin/perl -l
use strict;
use warnings;
sub shuffle {
my $i = @_;
while ($i) {
my $j = rand $i--;
@_[ $i, $j ] = @_[ $j, $i ];
}
}
shuffle( my @keys = 'a' .. 'z' );
my %key_for;
@key_for{ 'a' .. 'z', ' ' } = ( @keys, ' ' );
my $name = lc join ' ' => @ARGV;
my @name = map { split '' => $_ } $name;
$" = '';
my @curr_name = @name;
my $attempts = 1;
do {
$_ = $key_for{$_} foreach @curr_name;
print "$attempts: @curr_name";
$attempts++;
} while "@curr_name" ne "@name";
And here's a completely counter-intuitive demonstration of it:
:!perl swap.pl this is a test of the emergency broadcast system 1: mlfb fb j mpbm nh mlp ptpzgpyvw sznjqvjbm bwbmpt 2: tchs hs k trst yl tcr rmrigrwex biykoekst sxstrm 3: mvlb lb d mzbm wc mvz ztzfgzxpa sfwdnpdbm babmzt 4: tecs cs q tist xv tei imihgiarj bhxqyrqst sjstim 5: mpvb vb o mfbm ae mpf ftflgfjzk slaowzobm bkbmft 6: tres es n thst jp trh hmhcghkid bcjnxinst sdsthm 7: mzpb pb y mlbm kr mzl ltlvgldfq svkyafybm bqbmlt 8: tirs rs w tcst dz tic cmcegcqho bedwjhwst sostcm 9: mfzb zb x mvbm qi mfv vtvpgvoln spqxklxbm bnbmvt 10: this is a test of the emergency broadcast system
And here's another:
$ perl swap.pl ovid 1: gexo 2: qwkg 3: cfzq 4: tuic 5: pmxt 6: dskp 7: oazd 8: grio 9: qvxg 10: cekq 11: twzc 12: pfit 13: duxp 14: omkd 15: gszo 16: qaig 17: crxq 18: tvkc 19: pezt 20: dwip 21: ofxd 22: guko 23: qmzg 24: csiq 25: taxc 26: prkt 27: dvzp 28: oeid 29: gwxo 30: qfkg 31: cuzq 32: tmic 33: psxt 34: dakp 35: orzd 36: gvio 37: qexg 38: cwkq 39: tfzc 40: puit 41: dmxp 42: oskd 43: gazo 44: qrig 45: cvxq 46: tekc 47: pwzt 48: dfip 49: ouxd 50: gmko 51: qszg 52: caiq 53: trxc 54: pvkt 55: dezp 56: owid 57: gfxo 58: qukg 59: cmzq 60: tsic 61: paxt 62: drkp 63: ovzd 64: geio 65: qwxg 66: cfkq 67: tuzc 68: pmit 69: dsxp 70: oakd 71: grzo 72: qvig 73: cexq 74: twkc 75: pfzt 76: duip 77: omxd 78: gsko 79: qazg 80: criq 81: tvxc 82: pekt 83: dwzp 84: ofid 85: guxo 86: qmkg 87: cszq 88: taic 89: prxt 90: dvkp 91: oezd 92: gwio 93: qfxg 94: cukq 95: tmzc 96: psit 97: daxp 98: orkd 99: gvzo 100: qeig 101: cwxq 102: tfkc 103: puzt 104: dmip 105: osxd 106: gako 107: qrzg 108: cviq 109: texc 110: pwkt 111: dfzp 112: ouid 113: gmxo 114: qskg 115: cazq 116: tric 117: pvxt 118: dekp 119: owzd 120: gfio 121: quxg 122: cmkq 123: tszc 124: pait 125: drxp 126: ovkd 127: gezo 128: qwig 129: cfxq 130: tukc 131: pmzt 132: dsip 133: oaxd 134: grko 135: qvzg 136: ceiq 137: twxc 138: pfkt 139: duzp 140: omid 141: gsxo 142: qakg 143: crzq 144: tvic 145: pext 146: dwkp 147: ofzd 148: guio 149: qmxg 150: cskq 151: tazc 152: prit 153: dvxp 154: oekd 155: gwzo 156: qfig 157: cuxq 158: tmkc 159: pszt 160: daip 161: orxd 162: gvko 163: qezg 164: cwiq 165: tfxc 166: pukt 167: dmzp 168: osid 169: gaxo 170: qrkg 171: cvzq 172: teic 173: pwxt 174: dfkp 175: ouzd 176: gmio 177: qsxg 178: cakq 179: trzc 180: pvit 181: dexp 182: owkd 183: gfzo 184: quig 185: cmxq 186: tskc 187: pazt 188: drip 189: ovxd 190: geko 191: qwzg 192: cfiq 193: tuxc 194: pmkt 195: dszp 196: oaid 197: grxo 198: qvkg 199: cezq 200: twic 201: pfxt 202: dukp 203: omzd 204: gsio 205: qaxg 206: crkq 207: tvzc 208: peit 209: dwxp 210: ofkd 211: guzo 212: qmig 213: csxq 214: takc 215: przt 216: dvip 217: oexd 218: gwko 219: qfzg 220: cuiq 221: tmxc 222: pskt 223: dazp 224: orid 225: gvxo 226: qekg 227: cwzq 228: tfic 229: puxt 230: dmkp 231: oszd 232: gaio 233: qrxg 234: cvkq 235: tezc 236: pwit 237: dfxp 238: oukd 239: gmzo 240: qsig 241: caxq 242: trkc 243: pvzt 244: deip 245: owxd 246: gfko 247: quzg 248: cmiq 249: tsxc 250: pakt 251: drzp 252: ovid
Re:Your maths are good
Ovid on 2007-04-18T13:19:45
Sent!
This is interesting. A few months ago I posted a puzzle to london.pm that went something like this:
You have a rectangle raster of pixels - say 800 x 600 - stored in a linear array in normal raster fashion (so the first 800 elements of the array are the pixels from the top row, the next 800 from the next row and so on).
Now, you want to rotate that raster through 90 degrees and, crucially, you don't want to use much temporary storage. You certainly can't afford to keep a second copy of the raster so you have to do the rotation in-place.
Let's suppose you're rotating the raster 90 degrees clockwise. The top left pixel in the 800x600 original will become the top right pixel in the 600x800 rotated version. So start by moving the pixel from offset 0 to offset 599 - that's where it has to end up. Now you have the pixel from offset 599 to find a home for. That has to move to offset 600*599+599. And then you have to find out where to put the pixel from offset 600*599+599 and so on.
The algorithm will end up dancing around the image moving pixels from one offset to another until eventually it moves the pixel that will end up at offset 0 - and we're back where we started. Depending on the geometry of the image that may happen after as few as four hops (a square). For other images you only get back to the starting pixel after visiting many others.
It seems to me that this problem is in a similar domain. The keyboard remapping defines the journey each letter must take to get back to where it started. For example if the keyboard is mapped to translate 'A' -> 'B', 'B' -> 'C'
For example if 'A' takes six steps to get back to 'A' and 'B' takes four steps to get back to 'B' then 'AB' will take twelve steps.
And after all that I still can't quite work out how to calculate what the worst case would be. Someone call for MJD.
Re:Ooh, interesting
AndyArmstrong on 2007-04-18T14:36:44
Oh and could I have a look at your script too please?:) Re:Ooh, interesting
AndyArmstrong on 2007-04-18T14:39:03
And while I'm talking to myself...
Check out the Burrows Wheeler Transform. It's quite magical and working out how it works puts you in quite similar territory to this problem.
Re:Ooh, interesting
Ovid on 2007-04-18T14:59:55
Sent. Hope it looks reasonable.