Strong and valid
Weekly challenge 287 — 16 September 2024
Week 287: 16 Sep 2024
You are given a string, $str
.
Write a program to return the minimum number of steps required to make the given string a very strong password. If it is already strong then return 0.
Criteria:
The following can be considered as one step:
Example 1 Input: $str = "a" Output: 5 Example 2 Input: $str = "aB2" Output: 3 Example 3 Input: $str = "PaaSW0rd" Output: 0 Example 4 Input: $str = "Paaasw0rd" Output: 1 Example 5 Input: $str = "aaaaa" Output: 2
A few comments to start:
In the following, a
represents any lower case letter, Z
any upper-case letter and 9
any digit.
Stage 1 I believe that the best strategy is to handle first any sequences of 3 (or more) repeated characters, and to do this by inserting a different character (repeatedly if necessary) after the second character:
aaa → aaZa aaaaaa → aaZaaaa → aaZaaZaa aaaZZZ → aa9aZZ9Z
While doing the above, if the password lacks any of the three classes of character (ie a
, Z
or 9
),
the inserted character(s) can be chosen to remedy or partly remedy that lack.
Stage 2 Next, if the password still lacks any of an a
, Z
or 9
, add the missing one(s) to the end:
aZaZaZaZaZ → aZaZaZaZaZ9 abcdef → abcdefG7
Stage 3 Lastly, if the password contains fewer than 6 characters, add characters to the end to bring the total to 6, taking care not to create a new triplet.
aZa → aZa9 → aZa9Z → aZa9Z9
Stage 1 will, at most, take int(length($password) / 3))
steps. Stage 2 will add, at most, 2 steps.
Stage 3 will add at most 6 steps (6 only if the password is initially an empty string).
I believe that there is no solution that will require fewer steps, but am ready to be challenged. I have not used the permitted 'delete a character' or 'replace a character' steps as I don't think they lead to a fewer-steps solution, but again I am prepared to be proved wrong.
If you are checking passwords for strength in a production environment I recommend that you look at Have I been pwned, and I also recommend zxcvbn from Dropbox - amongst many others.
#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-09-16 use utf8; # Week 287 - task 1 - Strong password use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; strong_password('aaabbbcccccc', '4 triplets, no upper or digit'); strong_password('123abcdef', 'no upper case'); strong_password('abcdefghijkl', 'no upper or digit'); strong_password('ABCD5aa6FGHI', 'no change needed'); strong_password('Mi5', 'too short'); strong_password('', 'null'); sub strong_password { my ($password, $comment, $steps, @upper, @lower, @digit, $props, $r, $insert, $length); ($password, $comment) = @_; $steps = 0; @upper = ('A' .. 'Z'); @lower = ('a' .. 'z'); @digit = ('0' .. '9'); # stage 1 - deal with triplets while (1) { $props = assess($password); $r = $props->{triplet}; last unless $r; $insert = ''; do { $insert = $digit[rand(10)] unless $props->{digit}; $insert = $lower[rand(26)] unless $props->{lower}; $insert = $upper[rand(26)] unless $insert; } until $insert ne $r; $password =~ s|$r$r$r|$r$r$insert$r|; $steps ++; } # stage 2 - append any missing class of character $length = length($password); $password .= $lower[rand(26)] unless $props->{lower}; $password .= $upper[rand(26)] unless $props->{upper}; $password .= $digit[rand(10)] unless $props->{digit}; # stage 3 - pad if necessary to 6 chars $password .= $lower[rand(26)] while length($password) < 6; $steps += length($password) - $length; say qq[\nInput: \$password = '$_[0]' ($comment)]; say qq[Output: '$password'] . qq[ after $steps step] . ($steps == 1 ? '' : 's'); } sub assess { my ($password, %props); # get properties of password $password = $_[0]; $props{lower} = $password =~ m|[a-z]|; $props{upper} = $password =~ m|[A-Z]|; $props{digit} = $password =~ m|[0-9]|; $props{triplet} = $password =~ m|(.)\1\1| ? $1 : ''; return \%props; }
Input: $password = 'aaabbbcccccc' (4 triplets, no upper or digit) Output: 'aa7abbPbccBccHcc' after 4 steps Input: $password = '123abcdef' (no upper case) Output: '123abcdefA' after 1 step Input: $password = 'abcdefghijkl' (no upper or digit) Output: 'abcdefghijklZ8' after 2 steps Input: $password = 'ABCD5aa6FGHI' (no change needed) Output: 'ABCD5aa6FGHI' after 0 steps Input: $password = 'Mi5' (too short) Output: 'Mi5pot' after 3 steps Input: $password = '' (null) Output: 'sL8pmb' after 6 steps
Any content of this website which has been created by Peter Campbell Smith is in the public domain