Regexp golf question

[ajs]

I wrote a program that generates passwords (
http://www.ajs.com/~ajs/mkpasswd.html for those who are curious ), and
was discussing it with someone who asked if it could restrict its
results to those that alternate sides of the keyboard. This is a
feature I've been mulling for a while, but I suggested to him that he
could just generate many passwords, and filter them using grep or perl
or whatever. The pattern I suggested was (I'll use Perl here):

m{ ^
(([12345qwertasdfgzxcvb][67890\-yuiophjkl;nm,./])*
|
([67890\-yuiophjkl;nm,./][12345qwertasdfgzxcvb])*)
$ }xi

But that feels wrong to me... it seems as if there should be some
shorter way to express that. Any regexp golfers want to take a swing?
Obviously I could have:

$left = qr{[12345qwertasdfgzxcvb]}i;
$right = qr{[67890\-yuiophjkl;nm,./]}i;
m{^(($left$right)*|($right$left)*)$};

but that's not quite the same as coming up with a shorter pattern.

Note that that's not ALL of the characters. I've left out a bunch of
punctuation for brevity, but you get the idea.

PS: I'm using the new Google Groups to try it out. If it eats my
formatting, above... well, sorry.

 

[Anno Siegel]

I wrote a program that generates passwords (
http://www.ajs.com/~ajs/mkpasswd.html for those who are curious ), and
was discussing it with someone who asked if it could restrict its
results to those that alternate sides of the keyboard. This is a
feature I've been mulling for a while, but I suggested to him that he
could just generate many passwords, and filter them using grep or perl
or whatever. The pattern I suggested was (I'll use Perl here):

That doesn't seem to be an economical method to generate such
passwords. The probability for a string to be alternating is
2**(length( $str) - 1). (Any character can be first, every subsequent
character has a 50% chance of being wrong.) So you'd generate about
128 passwords for an alternating one of length 8. And it gets worse...

m{ ^
(([12345qwertasdfgzxcvb][67890\-yuiophjkl;nm,./])*
|
([67890\-yuiophjkl;nm,./][12345qwertasdfgzxcvb])*)
$ }xi

But that feels wrong to me... it seems as if there should be some
shorter way to express that. Any regexp golfers want to take a swing?
Obviously I could have:

$left = qr{[12345qwertasdfgzxcvb]}i;
$right = qr{[67890\-yuiophjkl;nm,./]}i;
m{^(($left$right)*|($right$left)*)$};
but that's not quite the same as coming up with a shorter pattern.

I'd write that (using capturing parentheses for simplicity)

/^$left?($right$left)*$right?$/i

It's not much shorter, but it doesn't build complete regexes for the
two possible cases, so I claim that logically it's only half as long.

Anno

 

[ajs]

$left = qr{[12345qwertasdfgzxcvb]}i;
$right = qr{[67890\-yuiophjkl;nm,./]}i;
m{^(($left$right)*|($right$left)*)$};

I'd write that (using capturing parentheses for simplicity)

/^$left?($right$left)*$right?$/i

Thanks, that's exactly what I was looking for. For some reason, I just
could not see that.

 

[ajs]

That doesn't seem to be an economical method to generate such
passwords. The probability for a string to be alternating is
2**(length( $str) - 1). (Any character can be first, every subsequent
character has a 50% chance of being wrong.) So you'd generate about
128 passwords for an alternating one of length 8. And it gets

worse...

Yes, I know this, which is why I have not made it a feature in my
program yet. The way the program works, it would be hard to add a
control like this in an efficient way, as it would have to constrain
many decisions in strange ways. For example, you would limit the
dictionary for patterns that involve dictionary words to those words
which alternate, but then it gets dicey when you start replacing parts
of words later on. A simple example is replacing an "i" in "fish" with
"1"... ooops, now its no-longer valid. Even worse, if you replace the
"t" in "stay" with a "7", it now DOES alternate.

This is only a simple, contrived example, but it shows the difficulty.
The same problems come up in pseudo-word generation, inserting variable
lengths of random sequences and a bunch of other places.
I'll do this at some point, but it's probably a "2.0" sort of feature.

 

[Jason Dufair]

I wrote a program that generates passwords (
http://www.ajs.com/~ajs/mkpasswd.html for those who are curious ), and
was discussing it with someone who asked if it could restrict its
results to those that alternate sides of the keyboard. This is a

I would point out that a keyboard is not a keyboard. It would appear
that you mean the US QWERTY keyboard. This alternation would not work
for a Dvorak keyboard user or a non-US keyboard user, etc. I suppose
you could keep a hash of keyboards and left-hand/right-hand keys and let
the user select the keyboard.
--
Jason Dufair - (e-mail address removed)
http://www.dufair.org/
<xterm> The problem with America is stupidity. I'm not saying there
should be a capital punishment for stupidity, but why don't we just
take the safety labels off of everything and let the problem solve
itself?