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

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.

## 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 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' ... 'Z' -> 'A' each letter has to make 26 steps to get back where it started. In general for any letter there's a sequence of <= 26 moves that gets it back to its starting point. The length of the sequence for a given word is the least common multiple of the lengths of the sequences for each of the letters in the word.

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.

Reply to This## Re: (Score:1)

## 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.