Saturday, November 10, 2018

[ekavsxsb] Words into letter buckets

The Master Lock Speed Dial provides 8 stickers, each with 3 or 4 letters: abc def ghi jkl mno pqrs tuv wxyz.  (Incidentally it is the same grouping of letters as phone keypads.)

One can stick each sticker to one of 4 directions on the lock.  How should the stickers be assigned to directions to maximize the diversity of directional combinations, over all possible words in a given dictionary?  Or, given word frequency information, spread out the resulting direction combinations as widely as possible.  In other words, have as few collisions as possible.

More generally, a different number of buckets (directions) than 4: 2 to 7.

More generally, cut up the stickers and allow letters to be assigned to buckets individually.

Add the constraint that the letters have to stay in order in order to find them easily.  For example, consider assigning 26 letters to 10 buckets.  Write the letters in order A through Z. Draw 9 cuts, partitioning the ordered list into 10 pieces.  Or circular partition.

Practical problems with Speed Dial: Is there enough room on the face of the lock for all 8 stickers?  Stickers can fall off, making a combination recorded as a password unusable.  They could be deliberately removed, even reordered, by an adversary (denial of service attack).

No comments :