Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Keys beside keys on keyboards

by TedPride (Priest)
on Nov 06, 2006 at 06:41 UTC ( #582387=note: print w/ replies, xml ) Need Help??


in reply to Keys beside keys on keyboards

An interesting problem, even just for English keyboards. The good news is that there's somewhat less than 35,000 possible 3-letter sequences, so the easiest method might just be to generate a hash of those sequences and test every 3-letter sequence in the input string, preferably with a routine that stays up permanently so you don't have to regenerate the hash every time someone enters a new password.

Of course, the interesting part is writing a routine to generate the sequences for you. The following perhaps isn't the cleanest piece of code in the world, but it works as proof of concept:

use strict; use warnings; print find('mskrtgdiwpa'), "\n"; print find('mwslkdftghm'), "\n"; sub find { my $s = $_[0]; my $key = init(); for (0..(length($s)-2)) { return substr($s, $_, 3) if exists $key->{substr($s, $_, 3)}; } } BEGIN { my (@keys, $rows, $cols, %seq, $run); @keys = ('1 2 3 4 5 6 7 8 9 0', 'q w e r t y u i o p', 'a s d f g h j k l ;', 'z x c v b n m , . /'); $_ = [split / /, $_] for @keys; $rows = $#keys; $cols = $#{$keys[0]}; sub init { if (!$run) { my ($x, $y); for $y (0..$rows) { for $x (0..$cols) { spider($x, $y, 3, ''); } } $run = 1; } return \%seq; } sub spider { my ($x, $y, $depth, $s) = @_; $s .= $keys[$y][$x]; if (!--$depth) { $seq{$s} = (); return; } spider($x, $y-1, $depth, $s) if $y > 0; spider($x+1, $y-1, $depth, $s) if $y > 0 && $x < $cols; spider($x-1, $y, $depth, $s) if $x > 0; spider($x, $y, $depth, $s); spider($x+1, $y, $depth, $s) if $x < $cols; spider($x-1, $y+1, $depth, $s) if $y < $rows && $x > 0; spider($x, $y+1, $depth, $s) if $y < $rows; } }
As it turns out, I miscalculated. There are probably less than 1500 sequences.


Comment on Re: Keys beside keys on keyboards
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://582387]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2015-07-02 04:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (27 votes), past polls