Perl Weekly Challenge: Strong but Valid

Posted on by

This week the peek into my brain comes via the first task, Strong Password. Immediately, I thought of David Wilcox’s, Strong Chemistry. Likening passwords to the emotional pull of an ex-lover is probably strange, but, hey, I never claimed to be normal.

With the musical setting out of the way, let’s dive right into Perl Weekly Challenge 287.

Task 1: Strong Password

You are given a string, $str.

Write a program to return the minimum number of steps required to make the given string 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 lowercase letter, at least one upper case letter and at least one digit.
- It shouldn't contain 3 repeating characters in a row.

Following can be considered as one step:

- Insert one character
- Delete one character
- Replace one character with another

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

Approach

As I usually state, there’s probably a clever way to do this, but I’m not going to try to find it. What I’m going to do is process the password character by character, keeping track of which positive (must have) and negative (must not have) criteria as I go along, and then counting how many characters need to change/be added to correct.

One thing I noted while thinking about this: if you have a run of the same character that’s between 3n and 3n+2 characters long, it will take n changes to correct it. Example 5 has 5 ‘a’s, so replacing one in position 3 will break it up into two runs of 2 ‘a’s each. But if we have a run of 6 ‘a’s, the best one character substitution can get us is a run of 2 and a run of 3; we need to do two replacements.

Raku

I’ve got the usual stuff here: using .comb to break the string into its characters, using .substr to check if the last character of a string is equal to another character. The interesting bit here is how I’m checking to see whether a given character is uppercase, lowercase, or a digit: I’m checking it’s Unicode property.

For example, <:Lu> matches a single, uppercase letter.

This way, passwords can have more than the usual A-Z, a-z, 0-9 characters.

sub strongPassword($str) {
  my ($hasUpper, $hasLower, $hasDigit, @runs) = (0, 0, 0);

  for $str.comb -> $char {
    # identify runs of characters
    if (@runs == 0 || @runs[*-1].substr(*-1,1) ne $char) {
      # we have no previous run of characters, or the last
      # character of the last run doesn't match this character
      @runs.push($char);
    }
    else {
      # append the latest character to the run
      @runs[*-1] ~= $char;
    }

    # count the character classes we're interested in
    if    ($char ~~ / <:Lu> /) { $hasUpper++ }
    elsif ($char ~~ / <:Ll> /) { $hasLower++ }
    elsif ($char ~~ / <:N> /)  { $hasDigit++ }
  }

  # count how many characters need to be REPLACED
  my $replacements = 0;
  for @runs -> $run {
    # the run isn't 3 or more characters
    next unless $run.chars >= 3;
    # we need one replacement per multiple of 3
    $replacements += ($run.chars / 3).Int;
  }

  # figure out how many changes are needed
  my $changes = 0;
  my $length  = $str.chars;

  for [$hasUpper, $hasLower, $hasDigit] -> $has {
    if ($has == 0) {
      $changes++; # we need to add a character of this type

      # if we have characters that need to be REPLACED, we don't
      # need to add to the string length to make the change
      if ($replacements > 0) {
        $replacements--;
      }
      else {
        # we need to add characters to make the change
        $length++;
      }
    }
  }
  if ($length < 6) {
    # not enough characters, we need MORE!
    $changes += 6 - $length;
  }
  if ($replacements > 0) {
    # if we need more replacements, add them to the total
    $changes += $replacements;
  }

  return $changes;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Example 6:
Input: $str = "aaaaaabbbb"
Output: 3

Example 7:
Input: $str = "voilÀ३"
Output: 0

Perl

To handle the unicode characters I’m including directly in the script in my last example, I need to add use utf8; to my script

If your Perl script is itself encoded in UTF-8, the use utf8 pragma must be explicitly included to enable recognition of that (in string or regular expression literals, or in identifier names). This is the only time when an explicit use utf8 is needed. (See utf8).

And then, because I’m writing these unicode characters to STDOUT, I need to set the binmode of that handle to :utf8. If I don’t, I get the warning Wide character in say at perl/ch-1.pl line 68.

use utf8;
binmode STDOUT, ':utf8';

sub strongPassword($str) {
  my ($hasUpper, $hasLower, $hasDigit, @runs) = (0, 0, 0);

  foreach my $char ( split //, $str ) {
    # identify runs of characters
    if (@runs == 0 || substr($runs[-1],-1,1) ne $char) {
      # we have no previous run of characters, or the last
      # character of the last run doesn't match this character
      push @runs, $char;
    }
    else {
      # append the latest character to the run
      $runs[-1] .= $char;
    }

    # count the character classes we're interested in
    if    ($char =~ /\p{Lu}/) { $hasUpper++ }
    elsif ($char =~ /\p{Ll}/) { $hasLower++ }
    elsif ($char =~ /\p{N}/)  { $hasDigit++ }
  }

  # count how many characters need to be REPLACED
  my $replacements = 0;
  foreach my $run ( @runs ) {
    # the run isn't 3 or more characters
    next unless length($run) >= 3;
    # we need one replacement per multiple of 3
    $replacements += int(length($run) / 3);
  }

  # figure out how many changes are needed
  my $changes = 0;
  my $length  = length($str);

  foreach my $has ($hasUpper, $hasLower, $hasDigit) {
    if ($has == 0) {
      $changes++; # we need to add a character of this type

      # if we have characters that need to be REPLACED, we don't
      # need to add to the string length to make the change
      if ($replacements > 0) {
        $replacements--;
      }
      else {
        # we need to add characters to make the change
        $length++;
      }
    }
  }
  if ($length < 6) {
    # not enough characters, we need MORE!
    $changes += 6 - $length;
  }
  if ($replacements > 0) {
    # if we need more replacements, add them to the total
    $changes += $replacements;
  }

  return $changes;
}

View the entire Perl script for this task on GitHub.

Python

Really, the biggest thing in translating this into Python is that the stock re module doesn’t have support for unicode properties. But have no fear! Just a quick pip install regex got me an alternative regular expression module, regex, that does support unicode properties.

import regex

def strongPassword(str):
  hasUpper = 0
  hasLower = 0
  hasDigit = 0
  runs = []

  for char in str:
    # identify runs of characters
    if len(runs) == 0 or runs[-1][-1] != char:
      # we have no previous run of characters, or the last
      # character of the last run doesn't match this character
      runs.append(char)
    else:
      # append the latest character to the run
      runs[-1] += char

    # count the character classes we're interested in
    if   regex.match(r"\p{Lu}", char):
      hasUpper += 1
    elif regex.match(r"\p{Ll}", char):
      hasLower += 1
    elif regex.match(r"\p{N}", char):
      hasDigit += 1

  # count how many characters need to be REPLACED
  replacements = 0
  for run in runs:
    # if the run is 3 or more characters
    if len(run) >= 3:
      # we need one replacement per multiple of 3
      replacements += int(len(run) / 3)

  # figure out how many changes are needed
  changes = 0
  length  = len(str)

  for has in [hasUpper, hasLower, hasDigit]:
    if has == 0:
      changes += 1 # we need to add a character of this type

      # if we have characters that need to be REPLACED, we don't
      # need to add to the string length to make the change
      if replacements > 0:
        replacements -= 1
      else:
        # we need to add characters to make the change
        length += 1

  if length < 6:
    # not enough characters, we need MORE!
    changes += 6 - length

  if replacements > 0:
    # if we need more replacements, add them to the total
    changes += replacements

  return changes

View the entire Python script for this task on GitHub.

Elixir

Elixir was also pretty straightforward to translate, especially using my new favorite trick of using Enum.map_reduce/3 to loop over enumerable list and not produce a map of the input list, but once I got my initial pass done, I was getting a count of 1 for my last example. It was pretty clear it wasn’t recognizing “३” as a number. That’s when I dug deeper and found out that I needed to add the :unicode modifier to my regular expressions so they would match Unicode characters.

  defp countHas(has, data) when has != 0, do: data

  defp countHas(_, data) do
    # we need to add a character of this type
    data = Map.put(data, :changes, data[:changes]+1)

    if data[:replacements] > 0 do
      # if we have characters that need to be REPLACED,
      # we don't need to add to the string length to
      # make the change
      Map.put(data, :replacements, data[:replacements]-1)
    else
      # we need to add characters to make the change
      Map.put(data, :length, data[:length]+1)
    end
  end

  defp putIf(map, condition, _, _) when not condition,
  do: map

  defp putIf(map, _, key, value) do
    Map.put(map, key, value)
  end

  def strongPassword(str) do
    data = %{
      hasUpper: 0,
      hasLower: 0,
      hasDigit: 0,
      runs: []
    }

    chars = String.graphemes(str)

    {_, data} =
      Enum.map_reduce(chars, data, fn char, data ->
        # identify runs of characters
        runs = data[:runs]
        runs = cond do
          # we have no previous run of characters, or the last
          # character of the last run doesn't match this character
          length(runs) == 0
          or
          List.last(runs) |> String.last != char ->
            runs ++ [ char ]

          # append the latest character to the run
          true ->
            List.replace_at(runs, -1, List.last(runs) <> char)
        end

        # put the runs back in the data map
        data = Map.put(data, :runs, runs)

        # count the character classes we're interested in
        # and return the data map to Enum.map_reduce/3
        {
          char,
          cond do
            Regex.match?(~r/\p{Lu}/u, char) ->
              Map.put(data, :hasUpper, data[:hasUpper]+1)
            Regex.match?(~r/\p{Ll}/u, char) ->
              Map.put(data, :hasLower, data[:hasLower]+1)
            Regex.match?(~r/\p{N}/u, char) ->
              Map.put(data, :hasDigit, data[:hasDigit]+1)
          end
        }
      end)

    # count how many characters need to be REPLACED
    {_, replacements} =
      Enum.map_reduce(data[:runs], 0, fn run, replacements ->
        {
          run,
          if String.length(run) >= 3 do
            replacements + trunc(String.length(run) / 3)
          else
            replacements
          end
        }
      end)

    # store some more stuff in our data map
    data = data
    |> Map.put(:changes, 0)
    |> Map.put(:length, String.length(str))
    |> Map.put(:replacements, replacements)

    hasList = [
      data[:hasUpper], data[:hasLower], data[:hasDigit]
    ]

    # figure out how many changes are needed
    {_, data} =
      Enum.map_reduce(hasList, data, fn has, data ->
        { has, countHas(has, data) }
      end)

    data
    |> putIf(data[:length] < 6, :changes,
             data[:changes] + 6 - data[:length] )
    |> putIf(data[:replacements] > 0, :changes,
             data[:changes] + data[:replacements])
    |> Map.get(:changes)
  end

View the entire Elixir script for this task on GitHub.

Task 2: Valid Number

You are given a string, $str.

Write a script to find if it is a valid number.

Conditions for a valid number:

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

Integer Number:

An integer number is defined with an optional sign '-' or '+'
followed by digits.

Decimal Number:

A decimal number is defined with an optional sign '-' or '+'
followed by one of the following definitions:
- Digits followed by a dot '.'.
- Digits followed by a dot '.' followed by digits.
- A dot '.' followed by digits.

Exponent:

An exponent is defined with an exponent notation 'e' or 'E'
followed by an integer number.

Example 1

Input: $str = "1"
Output: true

Example 2

Input: $str = "a"
Output: false

Example 3

Input: $str = "."
Output: false

Example 4

Input: $str = "1.2e4.2"
Output: false

Example 5

Input: $str = "-1."
Output: true

Example 6

Input: $str = "+1E-8"
Output: true

Example 7

Input: $str = ".44"
Output: true

Approach

Well, it hasn’t happened since PWC 259 Task 2, but we’ve got another task perfectly suited to a GRAMMAR!

I mean, the problem is stated as a grammar. How can we implement it any other way?

Raku

Fortunately, Grammars in Raku are fairly easy.

grammar IsNumber {
  rule TOP { [
    <integerNumber><exponent>? | <decimalNumber><exponent>?
  ] }

  token sign { <[ + \- ]> }

  token digits { \d+ }

  token integerNumber { <sign>? <digits> }

  token decimalNumber {
    <sign>? [ <digits> '.' | <digits> '.' <digits> | '.' <digits> ]
  }

  token exponent { [ "e" | "E" ] <integerNumber> }
}

sub solution($str) {
  say qq{Input: \$str = "$str"};
  say 'Output: ' ~ (IsNumber.parse($str) ?? True !! False);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str = "1"
Output: True

Example 2:
Input: $str = "a"
Output: False

Example 3:
Input: $str = "."
Output: False

Example 4:
Input: $str = "1.2e4.2"
Output: False

Example 5:
Input: $str = "-1."
Output: True

Example 6:
Input: $str = "+1E-8"
Output: True

Example 7:
Input: $str = ".44"
Output: True

Example 8:
Input: $str = "-३.१"
Output: True

Perl

Perl doesn’t have grammars, but with named regexs we can accomplish much the same thing.

use utf8;
binmode STDOUT, ':utf8';

my $sign = qr/ [+\-] /x;

my $digits = qr/ \d+ /x;

my $integerNumber = qr/ $sign? $digits /x;

my $decimalNumber = qr/
  $sign? (?: $digits\. | $digits\.$digits | \.$digits)
/x;

my $exponent = qr/(?: [eE] $integerNumber )/x;

my $TOP = qr/
  ^ (?: $integerNumber$exponent? | $decimalNumber$exponent? ) $
/x;

sub solution($str) {
  say qq{Input: \$str = "$str"};
  say 'Output: ' . ($str =~ /$TOP/ ? 'True' : 'False');
}

View the entire Perl script for this task on GitHub.

Python

I don’t know if Python supports grammars the way Raku does (I looked but didn’t find anything), but I do know it has decent regex support. The one thing I didn’t know was how to interpolate variables within a regular expression definition, which is pretty necessary if I’m building a grammar-like series of regexes out of atoms. Then I stumbled across this StackOverflow answer that pointed out you can combine f-strings and raw strings to build regexes.

import re

sign = r'[+\-]'

digits = r'\d+'

integerNumber = fr' {sign}? {digits} '

decimalNumber = fr"""
  {sign}? (?: {digits}\. | {digits}\.{digits} | \.{digits} )
"""

exponent = fr'(?:[eE]{integerNumber})'

TOP = re.compile(fr"""
  ^ (?:
      {integerNumber}{exponent}? |
      {decimalNumber}{exponent}?
    ) $
  """,
  re.VERBOSE
)

def solution(str):
    print(f'Input: $str = "{str}"')
    match = True if re.search(TOP, str) else False
    print(f'Output: {match}')

View the entire Python script for this task on GitHub.

Elixir

I tried mightily to figure out how to build the regular expression from atoms in Elixir, but eventually I just got tired and said “screw it”… I used IO.inspect to dump the contents of the yop-level regular expression I’d built, and then copied that back into my source file as a hard-coded expression. I formatted it a bit, though…

  def top() do
    ~r/
      ^
        (?:
          [+-]? \p{N}+ (?: [eE] (?: [+-]? \p{N}+ ) )?
          |
          [+-]? (?: \p{N}+ \. | \p{N}+ \. \p{N}+ | \. \p{N}+ )
          (?: [eE] (?: [+-]? \p{N}+ ) )?
        )
      $
    /ux
  end

  def solution(str) do
    IO.puts("Input: $str = \"#{str}\"")
    IO.puts("Output: #{ String.match?(str, top()) }")
  end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-287/packy-anderson

Leave a Reply