Perl Weekly Challenge: And the 2013 Tony Award for Best Coding Challenge goes to…

Posted on by

Perl Weekly Challenge 368‘s tasks are “Make it Bigger” and “Big and Little Omega”.

I swear, Mohammad Sajid Anwar must be teasing me with these titles, since the first one is lifted verbatim from the lyrics of the opening number to the 2013 Tony Awards telecast, “Bigger!” (written by Lin-Manuel Miranda and Tom Kitt and performed by the inimitable Neil Patrick Harris).

Task 1: Make it Bigger

You are given a given a string number and a character digit.

Write a script to remove exactly one occurrence of the given character digit from the given string number, resulting the decimal form is maximised.

Example 1

Input: $str = "15456", $char = "5"
Output: "1546"

Removing the second "5" is better because the digit following it (6) is
greater than 5. In the first case, 5 was followed by 4 (a decrease),
which makes the resulting number smaller.

Example 2

Input: $str = "7332", $char = "3"
Output: "732"

Example 3

Input: $str = "2231", $char = "2"
Output: "231"

Removing either "2" results in the same string here. By removing a "2",
we allow the "3" to move up into a higher decimal place.

Example 4

Input: $str = "543251", $char = "5"
Output: "54321"

If we remove the first "5", the number starts with 4. If we remove the
second "5", the number still starts with 5. Keeping the largest possible
digit in the highest place value is almost always the priority.

Example 5

Input: $str = "1921", $char = "1"
Output: "921"

Approach

I could go through and look at the the examples and develop a set of rules based on the numbers following the character potentially being removed. But it occurs to me that’s an awful lot of testing. The easy way to do this is to just remove each of the matching characters to produce a list of potential outputs with the character removed, and then return the maximum value. For example 1, removing a “5” results in ("1456", "1546"), and the max value is "1546".

I’m adding two trivial cases: when there’s only one occurrence of the target character, and when there are no occurrences of the target character.

Raku

In Raku, we can use the .indices method on the Str class to get all the indices where $char occurs in $str, and then loop through the list of indices and generate a list @possible. Then we use the .max routine to find the biggest one. Because .substr-rw modifies its subject, I do the assignment trick I used last week in the Perl solution for task to assign a temporary variable that’s then modified and pushed onto @possible.

sub bigger($str, $char) {
  my @indices = $str.indices($char);
  return $str unless @indices; # doesn't occur
  my @possible;
  for @indices -> $i {
    (my $tmp = $str).substr-rw($i, 1) = "";
    @possible.push($tmp);
  }
  return @possible.max;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $str = "15456", $char = "5"
Output: "1546"

Example 2:
Input: $str = "7332", $char = "3"
Output: "732"

Example 3:
Input: $str = "2231", $char = "2"
Output: "231"

Example 4:
Input: $str = "543251", $char = "5"
Output: "54321"

Example 5:
Input: $str = "1921", $char = "1"
Output: "921"

Example trivial 1:
Input: $str = "12345", $char = "6"
Output: "12345"

Example trivial 2:
Input: $str = "12345", $char = "1"
Output: "2345"

Perl

Perl’s index function only returns the first occurrence of the character, so we need to loop until we don’t find any more occurrences. I thought about rolling an indices function to work like Raku’s, but it would basically be what I already have here from lines 7-11, and the defining the extra function wouldn’t make it that much more readable.

use List::AllUtils qw( max );

sub bigger($str, $char) {
  my $i = 0;
  my @indices;
  while (($i = index($str, $char, $i)) >= 0) {
    push @indices, $i++;
  }
  return $str unless @indices; # doesn't occur
  my @possible;
  foreach $i ( @indices ) {
    substr((my $tmp = $str), $i, 1) = "";
    push @possible, $tmp;
  }
  return max @possible;
}

View the entire Perl script for this task on GitHub.

Python

In Python, we could use str.find like we’re using index in Perl, but the re.finditer function will return a regular expression match object for each match of the pattern, and we can pass it the character as the pattern.

Also, rather than using a function to eliminate a character from a string at a particular position, we can just use string slicing to build the string without the character we’re taking out.

Finally, because we can easily build the list of possible values through list comprehension, we can just pass that anonymous list to max().

import re

def bigger(string, char):
  indices = [ m.start() for m in re.finditer(char, string) ]
  if not indices: return string # doesn't occur
  return max([
    string[0:i]+string[i+1:] for i in indices
  ])

View the entire Python script for this task on GitHub.

Elixir

In Elixir, we’re using the same approach we used in Python to find all the occurrences of the character, except Regex.scan/3 requires a regular expression (Python automatically converts the string to a regular expression, but in Elixir we have to explicitly compile it into one), The return: :index options tell scan to return a list containing a tuple of the index and length of the match instead of the match itself, which is why on line 13 we have to pass the list element e through hd(e) to get the tuple from the head of the list, and then elem(tuple, 0) to get the first element from the tuple. Then we’re using string slicing to build copies of the string without the target occurrence.

def bigger(str, char) do
  char = Regex.compile!(char)
  indices = Regex.scan(char, str, return: :index)
  if length(indices) == 0 do
    str # doesn't occur
  else
    len = String.length(str)
    indices
    |> Enum.map(fn e ->
         i = elem(hd(e), 0)
         String.slice(str, 0, i) <> String.slice(str, i+1, len)
       end)
    |> Enum.max
  end
end

View the entire Elixir script for this task on GitHub.

Task 2: Big and Little Omega

You are given a positive integer $number and a mode flag $mode. If the mode flag is zero, calculate little omega (the count of all distinct prime factors of that number). If it is one, calculate big omega (the count of all prime factors including duplicates).

Example 1

Input: $number = 100061
       $mode = 0
Output: 3

Prime factors are 13, 43, 179. Count is 3.

Example 2

Input: $number = 971088
       $mode = 0
Output: 3

Prime factors are 2, 2, 2, 2, 3, 20231. Count of distinct numbers is 3.

Example 3

Input: $number = 63640
       $mode = 1
Output: 6

Prime factors are 2, 2, 2, 5, 37, 43. Count including duplicates is 6.

Example 4

Input: $number = 988841
       $mode = 1
Output: 2

Example 5

Input: $number = 211529
       $mode = 0
Output: 2

Approach

Essentially, this is an exercise in calculating the prime factors of a number, and then returning how many factors there are, or how many distinct factors there are. Because I’m tired and I’m not interested in investing a lot of time tonight in implementing a more complex algorithm, I’m implementing the trial division algorithm: we’re successively attempting to divide the number by 2 and then odd integers up to the square root of the number. Once we’ve divided the number by these possible factors, if we have anything greater than 2 left, it means the number is prime and it’s a factor.

Raku

This was fairly straightforward to implement in Raku. At the end, we’re just checking the mode to return either the number of elements in the list of factors, or the number of unique elements in the list of factors.

sub primeFactors($number is copy, $mode) {
  my @possible = (2); # if it's even, 2 is a factor
  @possible.append(3, 5 ... sqrt($number)+1); # odd nums up to √$number
  my @factors;
  for @possible -> $i {
    while ($number % $i == 0) {
      @factors.push($i);
      $number /= $i;
    }
  }
  # if $number is prime
  if ($number > 2) {
    @factors.push($number);
  }
  return $mode == 1 ?? @factors.elems !! @factors.unique.elems;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $number = 100061
       $mode = 0
Output: 3

Example 2:
Input: $number = 971088
       $mode = 0
Output: 3

Example 3:
Input: $number = 63640
       $mode = 1
Output: 6

Example 4:
Input: $number = 988841
       $mode = 1
Output: 2

Example 5:
Input: $number = 211529
       $mode = 0
Output: 2

Perl

Translating to Perl was pretty trivial. 

use List::AllUtils qw( uniq );

sub primeFactors($number, $mode) {
  my @possible = (2); # if it's even, 2 is a factor
  push @possible, (3, 5 ... sqrt($number)+1); # odd nums up to √$number
  my @factors;
  foreach my $i ( @possible ) {
    while ($number % $i == 0) {
      push @factors, $i;
      $number /= $i;
    }
  }
  # if $number is prime
  if ($number > 2) {
    push @factors, $number;
  }
  return $mode == 1 ? scalar(@factors) : scalar(uniq @factors);
}

View the entire Perl script for this task on GitHub.

Python

As was translating to Python. I haven’t had to import the math module before, but that’s where sqrt lives. Also, because range() produces values up to but not including the stop value, I needed to go to n+3\sqrt n + 3 in order to get n+1\sqrt n + 1 included in the range.

import math

def prime_factors(number, mode):
  s = int(math.sqrt(number))
  possible = (
    [2] + # if it's even, 2 is a factor
    [ n for n in range(3, s+3, 2)] # odd nums up to √number
  )
  factors = []
  for i in possible:
    while number % i == 0:
      factors.append(i)
      number /= i
  # if number is prime
  if number > 2: factors.append(number)
  return len(factors) if mode == 1 else len(set(factors))

View the entire Python script for this task on GitHub.

Elixir

And the Elixir solution needs an extra function because of Elixir’s lack of while loops. The add_factors/2 function winds up recursively calling itself and adding n to the list of factors as long as n keeps being a divisor of the number. Once it stops doing so, the function returns the new value of number and the list of factors that were built up.

Oh, and there doesn’t appear to be a native Elixir sqrt function, so we need to call the native Erlang sqrt function,

def add_factors(number, n, factors) do
  if (rem(number, n) == 0) do
    add_factors(trunc(number / n), n, factors ++ [n])
  else
    {number, factors}
  end
end

def prime_factors(number, mode) do
  n = trunc(:math.sqrt(number))+1
  possible = [2] # if it's even, 2 is a factor
          ++ Enum.to_list(Range.new(3, n, 2)) # odd nums up to √number
  {number, factors} = Enum.reduce(
    possible,
    {number, []},
    fn i, {number, factors} ->
      add_factors(number, i, factors)
    end
  )
  factors = if number > 2 do
    factors ++ [number]
  else
    factors
  end
  if mode == 1 do
    factors |> length
  else
    factors |> Enum.uniq |> length
  end
end

Though… I was just looking at this before I went to submit it, and I thought “No. I can do this all with recursion.” And it wound up saving six lines as well. The code from lines 23-27 above collapses into the terminal case on lines 4-5 below, and the Enum.reduce/3 from lines 16-22 above transform into lines 7-15 below.

I’m pulling the first number off the possible factor list on line 9 because it saves me having to do it between lines 9 and 10 with n = hd(possible); if I did, I’d be passing possible on line 11 instead of [n] ++ possible and tl(possible) on line 13 instead of possible. So it wound up saving me one line, and I think Elixir’s idiom of allowing you to specify [head_of_list | tail_of_list] in a function’s arguments is pretty readable.

  def find_factors(number, [], factors) when number > 2, do:
    factors ++ [number]

  def find_factors(_, [], factors), do: factors

  def find_factors(number, [n | possible], factors) do
    if (rem(number, n) == 0) do
      find_factors(trunc(number / n), [n] ++ possible, factors ++ [n])
    else
      find_factors(number, possible, factors)
    end
  end

  def prime_factors(number, mode) do
    n = trunc(:math.sqrt(number))+1
    possible = [2] # if it's even, 2 is a factor
            ++ Enum.to_list(Range.new(3, n, 2)) # odd nums up to √number
    factors = find_factors(number, possible, [])
    if mode == 1 do
      factors |> length
    else
      factors |> Enum.uniq |> length
    end
  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-368/packy-anderson

Leave a Reply