Task 1: Distinct Average

You are given an array of numbers with even length.

Write a script to return the count of distinct average. The average is calculated by removing the minimum and the maximum, then average of the two.

Example 1

Input: @nums = (1, 2, 4, 3, 5, 6)
Output: 1

Step 1: Min = 1, Max = 6, Avg = 3.5
Step 2: Min = 2, Max = 5, Avg = 3.5
Step 3: Min = 3, Max = 4, Avg = 3.5

The count of distinct average is 1.

Example 2

Input: @nums = (0, 2, 4, 8, 3, 5)
Output: 2

Step 1: Min = 0, Max = 8, Avg = 4
Step 2: Min = 2, Max = 5, Avg = 3.5
Step 3: Min = 3, Max = 4, Avg = 3.5

The count of distinct average is 2.

Example 3

Input: @nums = (7, 3, 1, 0, 5, 9)
Output: 2

Step 1: Min = 0, Max = 9, Avg = 4.5
Step 2: Min = 1, Max = 7, Avg = 4
Step 3: Min = 3, Max = 5, Avg = 4

The count of distinct average is 2.

Approach

I have to admit, it took me a LONG TIME to figure out what the “count of distinct average” was asking me to do. It was pretty clear that I needed to loop over the list, pulling off the min and max values and calculating the average for them, but what I didn’t understand was how those averages related to the number being spit out at the end; how did a list of three 3.5 values produce the number 1? Why was (4, 3.5, 3.5) yielding 2?

Then I saw it: it was counting the number of distinct values in the list of averages.

Even before I figured out what this was asking for, most of it was obvious: I need to sort the list, and then loop until the list is empty. On each loop, I pull out the first and last elements of the list, average them, and then put them into a list of averages. Then I determine how many distinct values this list of averages has.

Raku

Two weeks ago I wanted to use a Bag and wound up not doing so, and it just occurred to me that a Bag would be perfect for determining how many distinct values there are because a bag only stores each key once.

sub distinctAverages(@nums) {
  @nums = @nums.sort;
  my ($explain, $step) = (q{}, 0);
  my %averages = Bag.new;
  while (@nums) {
    my ($min, $max) = (@nums.shift, @nums.pop);
    my $avg = ($min + $max) / 2;
    $step++;
    $explain ~= "Step $step: Min = $min, "
             ~  "Max = $max, Avg = $avg\n";
    %averages{$avg}++;
  }
  $explain ~= "\nThe count of distinct average is "
           ~  %averages.elems ~ ".";
  return %averages.elems, $explain;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @nums = (1, 2, 4, 3, 5, 6)
Output: 1

Step 1: Min = 1, Max = 6, Avg = 3.5
Step 2: Min = 2, Max = 5, Avg = 3.5
Step 3: Min = 3, Max = 4, Avg = 3.5

The count of distinct average is 1.

Example 2:
Input: @nums = (0, 2, 4, 8, 3, 5)
Output: 2

Step 1: Min = 0, Max = 8, Avg = 4
Step 2: Min = 2, Max = 5, Avg = 3.5
Step 3: Min = 3, Max = 4, Avg = 3.5

The count of distinct average is 2.

Example 3:
Input: @nums = (7, 3, 1, 0, 5, 9)
Output: 2

Step 1: Min = 0, Max = 9, Avg = 4.5
Step 2: Min = 1, Max = 7, Avg = 4
Step 3: Min = 3, Max = 5, Avg = 4

The count of distinct average is 2.

Example 4:
Input: @nums = (1, 9, 2, 6, 3, 4)
Output: 3

Step 1: Min = 1, Max = 9, Avg = 5
Step 2: Min = 2, Max = 6, Avg = 4
Step 3: Min = 3, Max = 4, Avg = 3.5

The count of distinct average is 3.

Perl

Sadly, Perl doesn’t have Bags, but a hash works just as well. Evaluating keys %hash in a scalar context will give the number of keys in the hash. All in all, the Perl solution looks a lot like the Raku solution (probably because my Raku looks like Perl).

sub distinctAverages(@nums) {
  @nums = sort @nums;
  my ($explain, $step) = (q{}, 0);
  my %averages =();
  while (@nums) {
    my ($min, $max) = (shift(@nums), pop(@nums));
    my $avg = ($min + $max) / 2;
    $step++;
    $explain .= "Step $step: Min = $min, "
             .  "Max = $max, Avg = $avg\n";
    $averages{$avg}++;
  }
  my $count = scalar(keys %averages);
  $explain .= "\nThe count of distinct average is $count.";
  return $count, $explain;
}

View the entire Perl script for this task on GitHub.

Python

I keep saying the Counter datatype in the collections module is essentially the same as a Bag.

from collections import Counter

def distinctAverages(nums):
  nums.sort() # list.sort() works in place
  explain, step = "", 0
  averages = Counter()
  while nums:
    min, max = nums.pop(0), nums.pop(-1)
    avg = (min + max) / 2
    # since in Python, this will always produce a real number,
    # we need to do a little more work to make sure avg is an
    # integer when it has no fractional component
    if avg == int(avg):
      avg = int(avg)
    step += 1
    explain += (
      f"Step {step}: Min = {min}, Max = {max}, Avg = {avg}\n"
    )
    averages[avg] += 1
  count = len(list(averages))
  explain += (
    f"\nThe count of distinct average is {count}."
  )
  return count, explain

View the entire Python script for this task on GitHub.

Elixir

As usual, in Elixir we need to use recursion to do the heavy lifting a while loop would do in other languages. The first definition of distinctAverages defines the stopping condition when the list is empty, the second definition of distinctAverages does the work of popping off the min/max and calculating the average and stashing that in a Map so we can count the number of distinct averages we get. The final definition of distinctAverages is the one we initially call with just the list of integers, and it sorts the list and counts the keys in the averages map returned by the recursive call to the second distinctAverages.

  def distinctAverages([], step, explain, averages),
    do: {explain, averages}

  def distinctAverages(nums, step, explain, averages) do
    {min, nums} = List.pop_at(nums, 0)
    {max, nums} = List.pop_at(nums, -1)
    avg = (min + max) / 2
    # since in Elixir, this will always produce a float,
    # we need to do a little more work to make sure avg is an
    # integer when it has no fractional component
    avg = cond do
      avg == trunc(avg) -> trunc(avg)
      true              -> avg
    end
    explain = explain <> "Step #{step}: Min = #{min}, "
    explain = explain <> "Max = #{max}, Avg = #{avg}\n"
    averages = averages |> Map.put(avg, 1)
    distinctAverages(nums, step+1, explain, averages)
  end

  def distinctAverages(nums) do
    {explain, averages} =
        distinctAverages(Enum.sort(nums), 1, "", %{})
    count = averages |> Map.keys |> length
    {
      count,
      explain <> "\nThe count of distinct average is #{count}."
    }
  end

View the entire Elixir script for this task on GitHub.

Task 2: Backspace Compare

You are given two strings containing zero or more #.

Write a script to return true if the two given strings are same by treating # as backspace.

Example 1

Input: $str1 = "ab#c"
       $str2 = "ad#c"
Output: true

For first string,  we remove "b" as it is followed by "#".
For second string, we remove "d" as it is followed by "#".
In the end both strings became the same.

Example 2

Input: $str1 = "ab##"
       $str2 = "a#b#"
Output: true

Example 3

Input: $str1 = "a#b"
       $str2 = "c"
Output: false

Approach

This problem screams regular expressions to me. We match any character followed by a #, and remove both the character and the #, and repeat until we run out of #.

Raku

At first, I did the replacement as a single s:g/.\#// per string, but I discovered that only making a single pass with a global replace on ab## yielded a# (because in the one pass, it only matched the b followed by the #; once we removed the b#, the pointer to the remainder of the string only had the single #, so it didn’t match. I realized that a single s/.\#// match run repeatedly until it stopped matching anything would produce the result I wanted.

sub backspaceCompare($str1, $str2) {
  # if we pass in these as 'is rw', it expects to be passed
  # a writable container, which a string literal is not.
  # it's just easier to copy it to a writable container.
  my $s1 = $str1; while ($s1 ~~ s/.\#//) {}
  my $s2 = $str2; while ($s2 ~~ s/.\#//) {}
  return $s1 eq $s2;
} 

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $str1 = "ab#c"
       $str2 = "ad#c"
Output: True

Example 2:
Input: $str1 = "ab##"
       $str2 = "a#b#"
Output: True

Example 3:
Input: $str1 = "a#b"
       $str2 = "c"
Output: False

Perl

Perl worked almost exactly the same, except I didn’t need to worry about the parameters being writable.

sub backspaceCompare($str1, $str2) {
  while ($str1 =~ s/.\#//) {}
  while ($str2 =~ s/.\#//) {}
  return $str1 eq $str2 ? 'true' : 'false';
}

View the entire Perl script for this task on GitHub.

Python

Python proved to be slightly trickier; since re.sub doesn’t return whether or not the substitution was successful, it returns the modified string. So I needed to save the result in a new variable, and then compare that to the original value. If it was different, replace the original variable with the new variable, and then repeat.

import re

def backspaceCompare(str1, str2):
  s1 = re.sub(r'.\#', "", str1)
  while s1 != str1:
    str1 = s1
    s1 = re.sub(r'.\#', "", str1)
  s2 = re.sub(r'.\#', "", str2)
  while s2 != str2:
    str2 = s2
    s2 = re.sub(r'.\#', "", str2)
  return s1 == s2

View the entire Python script for this task on GitHub.

Elixir

Elixir has the same problem as Python in that Regex.replace/4 returns the resulting string, but defining a little recursive private function allowed me to handle that easily.

  defp repeatReplace(str) do
    s = Regex.replace(~r/.\#/, str, "")
    cond do
      s != str -> repeatReplace(s)
      true     -> s
    end
  end

  def backspaceCompare(str1, str2) do
    repeatReplace(str1) == repeatReplace(str2)
  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-321/packy-anderson