The Weekly Challenge 287

Strong Password & Valid Number: String Validation and Parsing in Perl & Python

Lubos Kolouch September 16, 2024 Challenge Details GitHub Solutions

Task 1: Strong Password

You are given a string, $str.

Write a script to find the minimum number of steps required to make $str a strong password. A password is strong if:

  • It has at least 6 characters.
  • It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
  • It does not contain three repeating characters in a row (e.g., "aaa" is invalid, but "aab" or "aba" is fine).

Method Explanation

The problem requires calculating the minimal number of insertions, deletions, or substitutions to fulfill all password criteria.

We analyze three conditions:

  1. Missing character categories: We check whether at least one lowercase letter, uppercase letter, and digit are present. If any are missing, we count each missing type.
  2. Consecutive repeats of length $\ge 3$: Whenever a sequence of $k$ identical consecutive characters appears, each sequence requires $\lfloor k / 3 \rfloor$ replacements to break the repeats (e.g., "aaaaa" length 5 requires $5 // 3 = 1$ change).
  3. Length constraints:
    • If the string length $n \ge 6$, we can satisfy missing types and broken repeats simultaneously by choosing the replacing characters wisely. Thus, the answer is $\max(\text{missing\_types}, \text{repeats\_to\_fix})$.
    • If $n < 6$, we need at least $6 - n$ insertions. An inserted character can break a repeating triplet or introduce a missing character class. The total steps required is $\max(\text{missing\_types} + \text{repeats\_to\_fix}, 6 - n)$.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);

signature_for strong_password_steps => (
    method     => 0,
    positional => [ Str ],
);

sub strong_password_steps ($s) {
    my $missing_types = 3;
    $missing_types-- if $s =~ /[a-z]/;
    $missing_types-- if $s =~ /[A-Z]/;
    $missing_types-- if $s =~ /\d/;

    my $repeats_to_fix = 0;
    my $i              = 2;
    my $n              = length($s);
    while ( $i < $n ) {
        if ( substr( $s, $i, 1 ) eq substr( $s, $i - 1, 1 ) && substr( $s, $i - 1, 1 ) eq substr( $s, $i - 2, 1 ) ) {
            my $repeat_len = 3;
            while ( $i + 1 < $n && substr( $s, $i + 1, 1 ) eq substr( $s, $i, 1 ) ) {
                $repeat_len++;
                $i++;
            }
            $repeats_to_fix += int( $repeat_len / 3 );
        }
        $i++;
    }

    my $total_steps;
    if ( $n >= 6 ) {
        $total_steps = ( $missing_types > $repeats_to_fix ) ? $missing_types : $repeats_to_fix;
    }
    else {
        my $insertions_needed = 6 - $n;
        my $sum               = $missing_types + $repeats_to_fix;
        $total_steps = ( $sum > $insertions_needed ) ? $sum : $insertions_needed;
    }
    return $total_steps;
}

Python Solution

import re

def strong_password_steps(s: str) -> int:
    """Calculate the minimum steps to make the password strong."""
    missing_types = 3
    if re.search(r"[a-z]", s):
        missing_types -= 1
    if re.search(r"[A-Z]", s):
        missing_types -= 1
    if re.search(r"\d", s):
        missing_types -= 1

    repeats_to_fix = 0
    i = 2
    n = len(s)
    while i < n:
        if s[i] == s[i - 1] == s[i - 2]:
            repeat_len = 3
            while i + 1 < n and s[i + 1] == s[i]:
                repeat_len += 1
                i += 1
            repeats_to_fix += repeat_len // 3
        i += 1

    if n >= 6:
        total_steps = max(missing_types, repeats_to_fix)
    else:
        total_steps = max(missing_types + repeats_to_fix, 6 - n)
    return total_steps

Task 2: Valid Number

You are given a string, $str.

Write a script to find if the given string is a valid number. A valid number is defined as:

  • An integer number followed by an optional exponent.
  • A decimal number followed by an optional exponent.

An integer has an optional sign (+/-) followed by digits. A decimal number has an optional sign followed by digits with a decimal point (or a dot preceded/followed by digits). An exponent begins with e or E followed by an integer.

Method Explanation

Rather than building a complex state machine manually, this format can be expressed precisely with a regular expression using extended/verbose mode:

  1. ^[+-]?: An optional leading sign.
  2. Mantissa matching:
    • \d+\.\d*: Digits followed by a period and optional trailing decimals (e.g. 12. or 12.34).
    • \.\d+: Leading period followed by at least one digit (e.g. .44).
    • \d+: Standard integer without decimal point (e.g. 123).
  3. ([eE][+-]?\d+)?$: An optional exponent marker (e or E), optional sign, and exponent integer digits.

Both Perl's qr/.../x and Python's re.compile(..., re.VERBOSE) allow inline comments and indentation, keeping the regular expression readable and maintainable.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);

signature_for is_valid_number => (
    method     => 0,
    positional => [ Str ],
);

sub is_valid_number ($s) {
    my $pattern = qr/
        ^                       # Start of string
        [+-]?                   # Optional sign
        (
            (                   # Decimal numbers
                \d+\.\d*        # Digits followed by dot and optional digits
                |
                \.\d+           # Dot followed by digits
                |
                \d+\.           # Digits followed by dot
            )
            |
            \d+                 # Integer numbers
        )
        ([eE][+-]?\d+)?         # Optional exponent
        $                       # End of string
    /x;
    return $s =~ $pattern ? 1 : 0;
}

Python Solution

import re

def is_valid_number(s: str) -> bool:
    """Determine if the given string is a valid number."""
    pattern = r"""
        ^                       # Start of string
        [+-]?                   # Optional sign
        (
            (                   # Decimal numbers
                \d+\.\d*        # Digits followed by dot and optional digits
                |
                \.\d+           # Dot followed by digits
                |
                \d+\.           # Digits followed by dot
            )
            |
            \d+                 # Integer numbers
        )
        ([eE][+-]?\d+)?         # Optional exponent
        $                       # End of string
    """
    regex = re.compile(pattern, re.VERBOSE)
    return bool(regex.match(s))