Perl Weekly Challenge: Double Your Pleasure, Double Your Luhn

Posted on by

Not every time is the music that the Perl Weekly Challenge inspires going to be a Broadway show tune, a banger from classic rock, or even a baroque fugue. Sometimes, it’s going to be a marketing jingle: 🎶 Double your pleasure, double your fun, with double good, double good, Doublemint Gum! 🎶

See, it’s because “Luhn” rhymes with fun. No? Fine, let’s chew on Perl Weekly Challenge 290 for a little bit.

Task 1: Double Exist

You are given an array of integers, @ints.

Write a script to find if there exist two indices $i and $j such that:

1) $i != $j
2) 0 <= ($i, $j) < scalar @ints
3) $ints[$i] == 2 * $ints[$j]

Example 1

Input: @ints = (6, 2, 3, 3)
Output: true

For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 =>  2 * $ints[$j]

Example 2

Input: @ints = (3, 1, 4, 13)
Output: false

Example 3

Input: @ints = (2, 1, 4, 2)
Output: true

For $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 =>  2 * $ints[$j]

Approach

Stipulations 1 and 2 just mean that $i and $j have to be different and in the range of the array. It’s the third one, that $ints[$j] is twice $ints[$i], that we need to worry about. There may be a clever way to do this, but I’m always coding these late at night, and I’m striving for “clear and concise” over “clever and elegant”. This feels like a double loop to me.

We can do some optimization, however. If we’re looking at a candidate for $i, if it’s odd, we know that value can’t be $i because it has to be twice one of the other integer values in the array, and twice any integer value has to be even. So if we loop over the array for $i, skipping odd values, and then loop over the array again for $j, skipping where $j == $i, something like this:

for $i from 0 to scalar(@ints)-1 {
  next if $ints[$i] is odd;
  for $j from 0 to scalar(@ints)-1 {
    next if $j == $i;
    next if $ints[$j] * 2 != $ints[$i];
    return true;
  }
}
return false;

Raku

sub doubleExist(@ints) {
  for 0 .. @ints.end -> $i {
    next unless @ints[$i] %% 2;
    for 0 .. @ints.end -> $j {
      next if $j == $i;
      next if @ints[$j] * 2 != @ints[$i];
      return 'true',
        "For \$i = $i, \$j = $j\n" ~
        "\$ints[\$i] = @ints[$i] => 2 * @ints[$j] => " ~
        "2 * \$ints[\$j]";
    }
  }
  return 'false';
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @ints = (6, 2, 3, 3)
Output: true

For $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 => 2 * $ints[$j]

Example 2:
Input: @ints = (3, 1, 4, 13)
Output: false

Example 3:
Input: @ints = (2, 1, 4, 2)
Output: true

For $i = 0, $j = 1
$ints[$i] = 2 => 2 * 1 => 2 * $ints[$j]

Note that my solution finds an alternate solution to example 3.

Perl

sub doubleExist(@ints) {
  foreach my $i ( 0 .. $#ints ) {
    next unless $ints[$i] % 2 == 0;
    foreach my $j ( 0 .. $#ints ) {
      next if $j == $i;
      next if $ints[$j] * 2 != $ints[$i];
      return 'true',
        "For \$i = $i, \$j = $j\n" .
        "\$ints[\$i] = $ints[$i] => 2 * $ints[$j] => " .
        "2 * \$ints[\$j]";
    }
  }
  return 'false';
}

View the entire Perl script for this task on GitHub.

Python

def doubleExist(ints):
  for i in range(len(ints)):
    if ints[i] % 2 != 0:
      continue
    for j in range(len(ints)):
      if j == i:
        continue
      if ints[j] * 2 != ints[i]:
        continue
      explain = (
        f"For $i = {i}, $j = {j}\n" +
        f"$ints[$i] = {ints[i]} => 2 * {ints[j]} => " +
        "2 * $ints[$j]"
      )
      return 'true', explain
  return 'false', False

View the entire Python script for this task on GitHub.

Elixir

Because Elixir is a functional language, if I want to be able to exit out of a loop early, I need to do the loop via recursion. Also, remember that because Integer.is_even/1 and Integer.is_odd/1 are defined as macros so they can be used as guards, we have to require the module before we can use the functions.

  require Integer # so we can use is_odd/1 as function

  def doubleExist(ints) do
    iLoop(ints, 0)
  end

  def iLoop(ints, i) when i >= length(ints), do: {false, false}
  def iLoop(ints, i) do
    iVal = Enum.at(ints, i)
    # we can't use Enum functions in a guard,
    # so we need this test here
    {answer, explain} = if Integer.is_odd(iVal) do
      {false, false}
    else
      # start the j loop
      jLoop(ints, i, 0)
    end
    if answer do
      # found an answer, return it
      {answer, explain}
    else
      # go to the next possible i value
      iLoop(ints, i + 1)
    end
  end

  def jLoop(ints, _, j) when j >= length(ints), do: {false, false}
  # skip when i == j
  def jLoop(ints, i, j) when i == j, do: jLoop(ints, i, j + 1)
  def jLoop(ints, i, j) do
    iVal = Enum.at(ints, i)
    jVal = Enum.at(ints, j)
    if jVal * 2 == iVal do
      # we found an answer!
      {
        true,
        "For $i = #{i}, $j = #{j}\n" <>
        "$ints[$i] = #{iVal} => 2 * #{jVal} => " <>
        "2 * $ints[$j]"
      }
    else
      # go to the next possible j value
      jLoop(ints, i, j + 1)
    end
  end

View the entire Elixir script for this task on GitHub.

Task 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits.

For each value now greater than 9, sum its digits.

The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero.

Return true if and only if the payload is equal to the correct check digit.

It was originally posted on reddit.

Example 1

Input: "17893729974"
Output: true

Payload is 4.

Digits from the right:

7 * 2 = 14, sum = 5
9 = 9
9 * 2 = 18, sum = 9
2 = 2
7 * 2 = 14, sum = 5
3 = 3
9 * 2 = 18, sum = 9
8 = 8
7 * 2 = 14, sum = 5
1 = 1

Sum of all values = 56, so 4 must be added to bring the
total mod 10 to zero. The payload is indeed 4.

Example 2

Input: "4137 8947 1175 5904"
Output: true

Example 3

Input: "4137 8974 1175 5904"
Output: false

Approach

One of the first things I did was look at the Reddit post, and then I looked at the Wikipedia post for the Luhn Algorithm, but I stopped reading when I got to the heading “Pseudocode implementation” (because I don’t want Wikipedia to do my work for me). One thing I noticed is that really what we’re doing is alternating between multiplying the digits by 2 and by 1, and then summing all the digits. So, another way to do example 1 is to just run through the multiplications and generate the digits 149182143188141, and then add those up to get 56.

Raku

sub luhnCheck($num) {
  # just the numeric digits of the number
  my @digits = $num.comb.grep( /\d/ );
  # the last digit is the payload/checksum
  my $payload = @digits.pop;

  my $to_be_summed;
  my $multiplier = 2; # we'll alternate between 2 & 1

  # pull the last digit off the number
  for @digits.reverse -> $digit {
    $to_be_summed ~= $digit.Int * $multiplier;
    # alternate the multiplier
    $multiplier = ($multiplier == 2) ?? 1 !! 2;
  }
  # add up the digits
  my $sum = [+] $to_be_summed.comb;
  # add the payload back in
  $sum += $payload;
  # is it a multiple of 10
  return $sum %% 10;
}

View the entire Raku script for this task on GitHub.

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

Example 2:
Input: "4137 8947 1175 5904"
Output: True

Example 3:
Input: "4137 8974 1175 5904"
Output: False

Perl

use List::AllUtils qw( sum );

sub luhnCheck($num) {
  # just the numeric digits of the number
  my @digits = grep { /\d/ } split //, $num;
  # the last digit is the payload/checksum
  my $payload = pop @digits;

  my $to_be_summed;
  my $multiplier = 2; # we'll alternate between 2 & 1
  
  # pull the last digit off the number
  foreach my $digit (reverse @digits) {
    $to_be_summed .= $digit * $multiplier;
    # alternate the multiplier
    $multiplier = ($multiplier == 2) ? 1 : 2;
  }
  # add up the digits
  my $sum = sum(split //, $to_be_summed);
  # add the payload back in
  $sum += $payload;
  # is it a multiple of 10
  return $sum % 10 == 0 ? 'true' : 'false';
}

View the entire Perl script for this task on GitHub.

Python

def luhnCheck(num):
  # just the numeric digits of the number
  digits = [ d for d in num if d.isnumeric() ]
  # the last digit is the payload/checksum
  payload = digits.pop()

  to_be_summed = ''
  multiplier = 2 # we'll alternate between 2 & 1

  digits.reverse() # reverse the digits
  # pull the last digit off the number
  for digit in digits:
    to_be_summed += str(int(digit) * multiplier)
    # alternate the multiplier
    multiplier = 1 if multiplier == 2 else 2

  # add up the digits
  digitSum = sum([ int(d) for d in to_be_summed ])
  # add the payload back in
  digitSum += int(payload)
  # is it a multiple of 10
  return digitSum % 10 == 0

View the entire Python script for this task on GitHub.

Elixir

For this solution, I stopped pulling the payload off the end of the number and just started my alternation of the multiplier at 1

  def sumDigits(num) do
    {_, data} = num
    |> Integer.to_string # turn number into string
    |> String.codepoints # break into chars
    |> Enum.map(fn d -> String.to_integer(d) end) # convert to int
    |> Enum.map_reduce(%{ sum: 0 }, fn digit, data ->
      { digit, Map.put(data, :sum, digit + data[:sum])}
    end)
    data[:sum]
  end

  def luhnCheck?(num) do
    digits = num
    |> String.codepoints # break into chars
    |> Enum.filter(fn d -> Regex.match?(~r/\d/, d) end) # just numeric
    |> Enum.map(fn d -> String.to_integer(d) end) # convert to int
    |> Enum.reverse # reverse the digits

    data = %{
      multiplier: 1, # we'll alternate between 2 & 1
      sum: 0 # let's add the numbers as we process them
    }
    alternate = [0, 2, 1] # trick for alternating between 2 & 1
    {_, data} =
      Enum.map_reduce(digits, data, fn digit, data ->
        multiplier = data[:multiplier]
        product = digit * multiplier
        data = data
        |> Map.put(:multiplier, Enum.at(alternate, multiplier)) # alternate the multiplier
        |> Map.put(:sum, data[:sum] + sumDigits(product))
        { product, data }
      end)
    Kernel.rem(data[:sum], 10) == 0
  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-290/packy-anderson