diff options
| -rw-r--r-- | challenge-287/e-choroba/blog.txt | 1 | ||||
| -rwxr-xr-x | challenge-287/e-choroba/perl/ch-1.pl | 118 |
2 files changed, 88 insertions, 31 deletions
diff --git a/challenge-287/e-choroba/blog.txt b/challenge-287/e-choroba/blog.txt new file mode 100644 index 0000000000..e64aba8f04 --- /dev/null +++ b/challenge-287/e-choroba/blog.txt @@ -0,0 +1 @@ +https://blogs.perl.org/users/e_choroba/2024/09/strong-password.html diff --git a/challenge-287/e-choroba/perl/ch-1.pl b/challenge-287/e-choroba/perl/ch-1.pl index c79a966a13..a67e4979ed 100755 --- a/challenge-287/e-choroba/perl/ch-1.pl +++ b/challenge-287/e-choroba/perl/ch-1.pl @@ -3,23 +3,19 @@ use warnings; use strict; use experimental qw( signatures ); -use List::Util qw{ first }; - # We can ignore deletion. We can always replace a character with a character # of the same class different to the previous and following one instead. -sub strong_password($str) { - my %agenda = ($str => 0); +sub strong_password_simple($str) { + my %agenda = ($str => undef); + my $steps = 0; while (1) { my %next; for my $s (keys %agenda) { if (6 > length $s) { - for my $char (qw( a A 0 )) { - $next{ $s . (($char eq substr $str, -1) - ? chr(1 + ord $char) - : $char) - } = 1 + $agenda{$s}; + for my $char ($s =~ /[aA0]$/ ? qw( b B 1 ) : qw( a A 0 )) { + undef $next{ $s . $char }; } } elsif ($s !~ /[[:lower:]]/ || $s !~ /[[:upper:]]/ @@ -34,35 +30,95 @@ sub strong_password($str) { ? 'a' : substr $s, $l + 1, 1; - # Try replacing every character with a lower-cased char, - # upper-cased char, and a digit different to the char - # itself, the preceding character, and the following - # character. - $next{ substr($s, 0, $l) . $_ . substr($s, $l + 1) } - = 1 + $agenda{$s} - for grep defined, - map { - first { /[^$this$previous$following]/ } - @$_ - } - [qw[ 0 1 2 ]], [qw[ a b c ]], [qw[ A B C ]]; + my $match; + $match .= /[a-z]/ ? 'a-z' + : /[A-Z]/ ? 'A-Z' + : '0-9' for $previous, $this, $following; + + undef $next{ substr($s, 0, $l) . $_ . substr($s, $l + 1) } + for grep /[^$match]/, qw( 0 a A ); + } + } else { + return $steps + } + } + %agenda = %next; + ++$steps; + } +} + + +sub strong_password($str) { + my %agenda = ($str => undef); + + my $steps = 0; + while (1) { + my %next; + for my $s (keys %agenda) { + + if (6 > length $s) { + for my $char ($s =~ /[aA0]$/ ? qw( b B 1 ) : qw( a A 0 )) { + undef $next{ $s . $char }; + } + + } elsif ($s =~ /(.)\1\1/) { + while ($s =~ /(.)(?=\1\1)/g) { + my $l = $-[0] + 1; + my $this = $1; + my $re = $this =~ tr/[a-z]// ? 'a-z' + : $this =~ tr/[A-Z]// ? 'A-Z' + : '0-9'; + + undef $next{ substr($s, 0, $l) . $_ . substr($s, $l + 1) } + for grep /[^$re]/, qw( 0 a A ); } + } else { - return $agenda{$s} + my %count; + $count{'a-z'} = $s =~ tr/a-z//; + $count{'A-Z'} = $s =~ tr/A-Z//; + $count{'0-9'} = $s =~ tr/0-9//; + + return $steps + if ! grep 0 == $_, values %count; + + my ($repeated, $replacement); + for my $class (qw( a-z A-Z 0-9 )) { + $repeated = $class if $count{$class} > 1; + $replacement = substr $class, 0, 1 if 0 == $count{$class}; + } + undef $next{ $s =~ s/[$repeated]/$replacement/r }; } } %agenda = %next; + ++$steps; } } -use Test::More tests => 5 + 3; +use Test::More tests => 2 * (5 + 3); + +for my $strong_password (\&strong_password_simple, \&strong_password) { + is $strong_password->('a'), 5, 'Example 1'; + is $strong_password->('aB2'), 3, 'Example 2'; + is $strong_password->('PaaSW0rd'), 0, 'Example 3'; + is $strong_password->('Paaasw0rd'), 1, 'Example 4'; + is $strong_password->('aaaaa'), 2, 'Example 5'; -is strong_password('a'), 5, 'Example 1'; -is strong_password('aB2'), 3, 'Example 2'; -is strong_password('PaaSW0rd'), 0, 'Example 3'; -is strong_password('Paaasw0rd'), 1, 'Example 4'; -is strong_password('aaaaa'), 2, 'Example 5'; + is $strong_password->('aaaZZZ999'), 3, 'Repeated triplets'; + is $strong_password->('0Zaaab'), 1, 'Creating a triple'; + is $strong_password->('000aaa000'), 3, 'Combined actions'; +} + +my @inputs; +for (1 .. 1000) { + my $s = join "", map +('a' .. 'z', 'A' .. 'Z', 0 .. 9)[rand 62], + 1 .. rand 15; + strong_password($s) == strong_password_simple($s) or warn "Diff $s"; + push @inputs, $s; +} -is strong_password('aaaZZZ999'), 3, 'Repeated triplets'; -is strong_password('0Zaaab'), 1, 'Creating a triple'; -is strong_password('000aaa000'), 3, 'Combined actions'; +use Benchmark qw{ cmpthese }; +cmpthese(-3, { + original => sub { strong_password($_) for @inputs }, + optimised => sub { strong_password_simple($_) for @inputs } +}); |