NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

## All the Perl that's Practical to Extract and Report

#### Ovid (2709)

Ovid
(email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

### Journal of Ovid (2709)

Wednesday April 18, 2007
03:02 AM

### Embarrassing Solutions

[ #33017 ]

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

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden
• #### Your maths are good(Score:1)

From what I read, your maths are good. Regarding your statistics, I found different distributions around the Internet - I picked one and it worked at least for the example.

(I'd be curious to see your solution, I can send mine if you want so that you can judge if I'm entitled to see yours. flavio [at] polettix.it)

Sent!

• #### Ooh, interesting(Score:1)

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 h

• #### Re:(Score:1)

Oh and could I have a look at your script too please? :)
• #### Re:(Score:1)

And while I'm talking to myself...

Check out the Burrows Wheeler Transform [wikipedia.org]. It's quite magical and working out how it works puts you in quite similar territory to this problem.

• #### Re:(Score:2)

Sent. Hope it looks reasonable.

• #### Strikingly Similar Algorithm(Score:1)

I ran across a similar scenario linked on Chris Neukirchen's [anarchaia.org] tumblelog, a similar problem w/a cute algorithm: