Peter
Peter Campbell Smith

Strong and valid

Weekly challenge 287 — 16 September 2024

Week 287: 16 Sep 2024

Task 1

Task — Strong password

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:

  • It must have at least 6 characters.
  • It must contains at least one lower-case letter, at least one upper-case letter and at least one digit.
  • It shouldn't contain 3 repeating characters in a row.

The following can be considered as one step:

  • Insert one character
  • Delete one character
  • Replace one character with another

Examples


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

Analysis

A few comments to start:

  • I have assumed 'strong' and 'very strong' mean the same
  • I have assumed non-alphanumeric characters are excluded
  • The output passwords don't meet today's standards of good passwords, so don't use them!

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.

Try it 

Try running the script with any input:



example: Aaardvarkkk99

Script


#!/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;
}
    

Output


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