Perl Weekly Challenge: My subset is-a missing a letter…

Posted on by

Perl Weekly Challenge 371‘s tasks are “Missing Letter” and “Subset Equilibrium”. Immediately, I heard The Box Tops in my head.

Task 1: Missing Letter

You are given a sequence of 5 lowercase letters, with one letter replaced by ‘?’. Each letter maps to its position in the alphabet (‘a = 1’, ‘b = 2’, …, ‘z = 26’). The sequence follows a repeating pattern of step sizes between consecutive letters. The pattern is either a constant step (e.g., ‘+2, +2, +2, +2’) or a simple alternating pattern of two distinct steps (e.g., ‘+2, +3, +2, +3’).

Example 1

Input: @seq = qw(a c ? g i)
Output: e

The pattern of the sequence is +2,+2,+2,+2.
1: a
3: c
5: e
7: g
9: i

Example 2

Input: @seq = qw(a d ? j m)
Output: g

The pattern of the sequence is +3,+3,+3,+3.
1: a
4: d
7: g
10: j
13: m

Example 3

Input: @seq = qw(a e ? m q)
Output: i

The pattern of the sequence is +4,+4,+4,+4.
1: a
5: e
9: i
13: m
17: q

Example 4

Input: @seq = qw(a c f ? k)
Output: h

The pattern of the sequence is +2,+3,+2,+3.
1: a
3: c
6: f
8: h
11: k

Example 5

Input: @seq = qw(b e g ? l)
Output: j

The pattern of the sequence is +3,+2,+3,+2.
2: b
5: e
7: g
10: j
12: l

Approach

This problem brings me back to school, when we had to find the missing numbers in an arithmetic sequence. The approach is the same: we find the differences between the known elements in the sequence, and then we use that to fill in the missing value. The only wrinkle is that the steps aren’t necessarily constant: it’s either a constant difference, or an alternating difference.

So what we’ll do is calculate the differences between the values we have. Since there are five values, there are four differences in the sequence, and since the differences will either be a constant step or an alternating sequence, then they will either be all the same, or differences 1 and 3 will be the same and differences 2 and 4 will be the same. Once we’ve calculated the differences we know, we can use this to fill in those we don’t.

If the 2nd through 5th character is missing, we add the difference just before it to the character just before it. For example, if the 3rd character is missing, we add the 2nd difference to the 2nd character. If it’s the 1st character missing, that’s a special case: we subtract the 1st difference from the 2nd character.

Raku

This is a fairly straightforward implementation of the approach. Lines 7-10 calculate the differences between characters that aren’t missing, 12-14 fill in the missing differences, and then we return the missing character.

sub missing(@seq) {
  my @diff;
  # determine the differences we know
  for 0..3 -> $i {
    next if @seq[$i] eq '?' || @seq[$i+1] eq '?';
    @diff[$i] = @seq[$i+1].ord - @seq[$i].ord;
  }
  # fill in the missing differences
  for 0..3 -> $i {
    @diff[$i] = @diff[($i +2) mod 4] unless @diff[$i].defined;
  }
  # special case: the first letter is missing
  if (@seq[0] eq '?') {
    return (@seq[1].ord - @diff[0]).chr;
  }
  # calculate the missing letter
  for 1..4 -> $i {
    next unless @seq[$i] eq '?';
    return (@seq[$i-1].ord + @diff[$i-1]).chr;
  }
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @arr = qw(a c ? g i)
Output: e

Example 2:
Input: @arr = qw(a d ? j m)
Output: g

Example 3:
Input: @arr = qw(a e ? m q)
Output: i

Example 4:
Input: @arr = qw(a c f ? k)
Output: h

Example 5:
Input: @arr = qw(b e g ? l)
Output: j

Example 6:
Input: @arr = qw(? t v x z)
Output: r

Example 7:
Input: @arr = qw(l m o p ?)
Output: r

Perl

The Perl solution is just the Raku solution with Perl variable syntax and functions.

sub missing(@seq) {
  my @diff;
  # determine the differences we know
  foreach my $i (0..3) {
    next if $seq[$i] eq '?' || $seq[$i+1] eq '?';
    $diff[$i] = ord($seq[$i+1]) - ord($seq[$i]);
  }
  # fill in the missing differences
  foreach my $i (0..3) {
    $diff[$i] = $diff[($i +2) % 4] unless defined $diff[$i];
  }
  # special case: the first letter is missing
  if ($seq[0] eq '?') {
    return chr(ord($seq[1]) - $diff[0]);
  }
  # calculate the missing letter
  foreach my $i (1..4) {
    next unless $seq[$i] eq '?';
    return chr(ord($seq[$i-1]) + $diff[$i-1]);
  }
}

View the entire Perl script for this task on GitHub.

Python

Because Python doesn’t really have a concept of undefined array values, I pre-initialized each of the diff elements to None. Otherwise, it looks a lot like the Perl solution.

def missing(seq):
  diff = [None, None, None, None]
  # determine the differences we know
  for i in range(4):
    if seq[i] == '?' or seq[i+1] == '?': continue
    diff[i] = ord(seq[i+1]) - ord(seq[i])

  # fill in the missing differences
  for i in range(4):
    if diff[i] == None: diff[i] = diff[(i+2) % 4]

  # special case: the first letter is missing
  if seq[0] == '?':
    return chr(ord(seq[1]) - diff[0])

  # calculate the missing letter
  for i in range(1,5):
    if seq[i] == '?': return chr(ord(seq[i-1]) + diff[i-1])

View the entire Python script for this task on GitHub.

Elixir

I had some fun playing with things in Elixir. Since there’s so much I had to do to get a particular character from the list and then calculate the numeric value of that character, I defined an ord/2 function to abstract that away. I made diff a map because maps let me randomly replace elements, where lists have to be rebuilt in order to replace elements. I’m using recursion to do all my looping because it’s actually shorter than doing a bunch of Enum.map_reduce/3 statements.

def ord(seq, i), do: to_charlist(Enum.at(seq, i)) |> hd

# fill in the missing differences
def missing_diff(diff, i) when i == 4, do: diff
def missing_diff(diff, i) do
  if is_nil(diff[i]) do
    missing_diff(Map.put(diff, i, diff[rem(i+2, 4)]), i+1)
  else
    missing_diff(diff, i+1)
  end
end

# determine the differences we know
def fill_in_diff(_, diff, i) when i == 4, do: diff
def fill_in_diff(seq, diff, i) do
  if Enum.at(seq, i) == "?" or Enum.at(seq, i+1) == "?" do
    fill_in_diff(seq, diff, i+1)
  else
    diff = Map.put(diff, i, ord(seq, i+1) - ord(seq, i))
    fill_in_diff(seq, diff, i+1)
  end
end

def missing(seq, diff, i, [h | _]) when i == 0 and h == "?" do
  # special case: the first letter is missing
  ord(seq,1) - diff[0] |> then(fn x -> [x] end)
end

def missing(seq, diff, i, [h | _]) when h == "?" do
  # calculate the missing letter
  ord(seq,i-1) + diff[i-1] |> then(fn x -> [x] end)
end

def missing(seq, diff, i, [_ | t]) do
  missing(seq, diff, i+1, t)
end

def missing(seq) do
  diff = missing_diff(fill_in_diff(seq, %{}, 0), 0)
  missing(seq, diff, 0, seq)
end

View the entire Elixir script for this task on GitHub.

Task 2: Subset Equilibrium

You are given an array of numbers.

Write a script to find all proper subsets with more than one element where the sum of elements equals the sum of their indices.

Example 1

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

Subset 1: (2, 1)
Values: 2 + 1 = 3
Positions: 1 + 2 = 3

Subset 2: (1, 4)
Values: 1 + 4 = 5
Positions: 2 + 3 = 5

Subset 3: (4, 3)
Values: 4 + 3 = 7
Positions: 3 + 4 = 7

Subset 4: (2, 3)
Values: 2 + 3 = 5
Positions: 1 + 4 = 5

Example 2

Input: @nums = (3, 0, 3, 0)
Output: (3, 0), (3, 0, 3)

Subset 1: (3, 0)
Values: 3 + 0 = 3
Positions: 1 + 2 = 3

Subset 2: (3, 0, 3)
Values: 3 + 0 + 3 = 6
Positions: 1 + 2 + 3 = 6

Example 3

Input: @nums = (5, 1, 1, 1)
Output: (5, 1, 1)

Subset 1: (5, 1, 1)
Values: 5 + 1 + 1 = 7
Positions: 1 + 2 + 4 = 7

Example 4

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

Subset 1: (3, 2)
Values: 3 + 2 = 5
Positions: 1 + 4 = 5

Subset 2: (3, -1, 4)
Values: 3 + (-1) + 4 = 6
Positions: 1 + 2 + 3 = 6

Example 5

Input: @nums = (10, 20, 30, 40)
Output: ()

Approach

Well, the first thing I’m going to do is convert the list of integers into a list of { index => value } tuples so when I generate the possible subsets, I have the indices the values came from tightly coupled to the values. Then I’ll generate the possible subsets (the Power Set), toss out the candidates that don’t match the criteria, and list out the remaining subsets.

Raku

Now, since Raku doesn’t have a tuple type, I’m going to implement them as two-element lists, where the index is the first element and the value is the second element is the value.

I decided to define a subsets function to make the code a little easier to read. It also handles only generating subsets with a minimum and maximum number of elements, so we only need to worry about checking the sums.

sub properSubsets(@array, $min) {
  return @array.combinations: $min .. @array.elems -1;
}

sub equilibrium(@nums) {
  my $i = 1; # start with index 1
  my @tuples = @nums.map({ [ $i++, $_ ] });
  my (@results, @explain, $count);
  # loop over the subsets with 2 or more elements
  for properSubsets(@tuples, 2) -> @s {
    my @indices = @s.map({ $_[0] });
    my @values  = @s.map({ $_[1] });
    next unless @indices.sum == @values.sum;
    $count++;
    my $explanation
      = "Subset $count: ({ @values.join(', ') })\n"
      ~ "Values: { @values.join(' + ') } = { @values.sum }\n"
      ~ "Positions: { @indices.join(' + ') } = { @indices.sum }";
    @explain.push: $explanation;
    @results.push: @values;
  }
  return @explain.join("\n\n"), [@results];
}

View the entire Raku script for this task on GitHub.

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

Subset 1: (2, 1)
Values: 2 + 1 = 3
Positions: 1 + 2 = 3

Subset 2: (2, 3)
Values: 2 + 3 = 5
Positions: 1 + 4 = 5

Subset 3: (1, 4)
Values: 1 + 4 = 5
Positions: 2 + 3 = 5

Subset 4: (4, 3)
Values: 4 + 3 = 7
Positions: 3 + 4 = 7

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

Subset 1: (3, 0)
Values: 3 + 0 = 3
Positions: 1 + 2 = 3

Subset 2: (3, 0, 3)
Values: 3 + 0 + 3 = 6
Positions: 1 + 2 + 3 = 6

Example 3:
Input: @nums = (5, 1, 1, 1)
Output: (5, 1, 1)

Subset 1: (5, 1, 1)
Values: 5 + 1 + 1 = 7
Positions: 1 + 2 + 4 = 7

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

Subset 1: (3, 2)
Values: 3 + 2 = 5
Positions: 1 + 4 = 5

Subset 2: (3, -1, 4)
Values: 3 + -1 + 4 = 6
Positions: 1 + 2 + 3 = 6

Example 5:
Input: @nums = (10, 20, 30, 40)
Output: ()

Perl

In Perl, I’m using Algorithm::Combinatorics‘s subsets function that I last used back in PWC324. Because that returns a power set (including the set itself and the empty set), on line 14 I’m filtering out the subsets that don’t have the proper number of elements (not more than 1, not the set itself).

use Algorithm::Combinatorics qw( subsets );
use List::AllUtils qw( sum );

sub equilibrium(@nums) {
  my $i = 1; # start with index 1
  my @tuples = map { [ $i++, $_ ] } @nums;
  my (@results, @explain, $count);
  # loop over the subsets
  foreach my $s (subsets(\@tuples)) {
    # only consider PROPER subsets with 2 or more elements
    next unless @$s > 1 && @$s < @tuples;
    my @indices = map { $_->[0] } @$s;
    my @values  = map { $_->[1] } @$s;
    next unless sum(@indices) == sum(@values);
    $count++;
    my $plus_values  = join(' + ', @values);
    my $plus_indices = join(' + ', @indices);
    my $explanation
      = "Subset $count: (@{[ join(', ', @values) ]})\n"
      . "Values: $plus_values = @{[ sum(@values) ]}\n"
      . "Positions: $plus_indices = @{[ sum(@indices) ]}";
    push @explain, $explanation;
    push @results, \@values;
  }
  return join("\n\n", @explain), [@results];
}

View the entire Perl script for this task on GitHub.

Python

The Python solution sees more code reuse from PWC324 in the form of the powerSet (here renamed subsets) function to produce the power set of our tuples. Really, when you look at them side-by-side, the Python solution looks a lot like the Perl solution.

from functools import reduce

def subsets(arr):
  return reduce(lambda r, i: r + [s + [i] for s in r], arr, [[]])

def int_join(joiner, arr):
  return joiner.join(map(str, arr))

def equilibrium(nums):
  tuples = [ (i, v) for i, v in enumerate(nums, start=1) ]
  results = []
  explain = []
  count = 0
  # loop over the subsets
  for s in subsets(tuples):
    # only consider PROPER subsets with 2 or more elements
    if len(s) < 2 or len(s) == len(tuples): continue
    indices = [ e[0] for e in s ]
    values  = [ e[1] for e in s ]
    if not sum(indices) == sum(values): continue
    count += 1
    plus_values  = int_join(' + ', values)
    plus_indices = int_join(' + ', indices)
    explanation = (
      f"Subset {count}: ({ int_join(', ', values) })\n" +
      f"Values: {plus_values} = { sum(values) }\n" +
      f"Positions: {plus_indices} = { sum(indices) }"
    )
    explain.append(explanation)
    results.append(values)
  return "\n\n".join(explain), results

View the entire Python script for this task on GitHub.

Elixir

As always, the fun in Elixir is deciding whether or not to use recursion for the looping. I decided that I’d make an equilibrium/4 to handle checking each of the subsets rather than try to fit everything into an Enum.map_reduce/3 statement. Not that it wouldn’t work; I just find that if a map_reduce has too many statements in it, it gets harder to read.

Again, I recycled the powerSet function from PWC324 (back before I learned that using camelCase in Python or Elixir was considered bad form).

def subsets([]), do: []
def subsets([i | rest]) do
  list = subsets(rest)
  [[i] | Enum.reduce(list, list, &[[i | &1] | &2])]
end

def equilibrium([], results, explain, _),
  do: {results, explain}

def equilibrium([s | remain], results, explain, count) do
  indices = s |> Enum.map(fn e -> elem(e, 0) end)
  values  = s |> Enum.map(fn e -> elem(e, 1) end)
  i_sum   = indices |> Enum.sum
  v_sum   = values  |> Enum.sum
  {explain, results, count} = if i_sum == v_sum do
    value_list   = values  |> Enum.join(", ")
    plus_values  = values  |> Enum.join(" + ")
    plus_indices = indices |> Enum.join(" + ")
    {
      explain ++ [
        "Subset #{count}: (#{value_list})\n" <>
        "Values: #{plus_values} = #{v_sum}\n" <>
        "Positions: #{plus_indices} = #{i_sum}"
      ],
      results ++ [values],
      count + 1
    }
  else
    {explain, results, count}
  end
  equilibrium(remain, results, explain, count)
end

def proper(tuples), do: subsets(tuples)
  |> Enum.filter(fn s ->
    length(s) > 1 and length(s) < length(tuples)
  end)

def equilibrium(nums) do
  {_, tuples} = Enum.reduce(nums,
    {1, []}, fn n, {i,l} -> {i+1, l ++ [{i,n}]} end
  )
  # only consider PROPER subsets with 2 or more elements
  {results, explain} = equilibrium(proper(tuples), [], [], 1)
  { Enum.join(explain, "\n\n"), results }
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/challenge-371-packy-anderson/challenge-371/packy-anderson

Leave a Reply