Perl Weekly Challenge: Root It All You Reduce

Posted on by

Perl Weekly Challenge 359‘s tasks are “Digital Root” and “String Reduction”, but the entire time I was writing these solutions all I heard in my head was Chuck Mangione’s Give It All You Got. 1

Task 1: Digital Root

You are given a positive integer, $int.

Write a function that calculates the additive persistence of a positive integer and also return the digital root.

Digital root is the recursive sum of all digits in a number until a single digit is obtained.

Additive persistence is the number of times you need to sum the digits to reach a single digit.

Example 1

Input: $int = 38
Output: Persistence  = 2
        Digital Root = 2

38 => 3 + 8 => 11
11 => 1 + 1 => 2

Example 2

Input: $int = 7
Output: Persistence  = 0
        Digital Root = 7

Example 3

Input: $int = 999
Output: Persistence  = 2
        Digital Root = 9

999 => 9 + 9 + 9 => 27
27  => 2 + 7 => 9

Example 4

Input: $int = 1999999999
Output: Persistence  = 3
        Digital Root = 1

1999999999 => 1 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 => 82
82 => 8 + 2 => 10
10 => 1 + 0 => 1

Example 5

Input: $int = 101010
Output: Persistence  = 1
        Digital Root = 3

101010 => 1 + 0 + 1 + 0 + 1 + 0 => 3

Approach

It says it right there in the description: the recursive sum of all digits in a number. If I’m doing this recursively, I’m starting off in Elixir. Basically, we just break apart the number into it’s digits, sum those digits, and then recursively call ourselves until the result is < 10, keeping track of how many iterations we make.

Elixir

One of the great things about Elixir is the Integer.digits/2 function, which breaks apart an integer into its digits, not the characters representing its digits. In line 4, I’m defining a header with the default value for persistence.

def digital_root(int, persistence \\ 0)

def digital_root(int, persistence) when int < 10, do:
  {persistence, int}

def digital_root(int, persistence) do
  sum = Integer.digits(int) |> Enum.sum()
  digital_root(sum, persistence + 1)
end

Though I could code it this way

def digital_root(int, persistence \\ 0) do
  cond do
    int < 10 -> {persistence, int}
    true -> digital_root(
      Integer.digits(int) |> Enum.sum, persistence + 1
    )
  end
end

View the entire Elixir script for this task on GitHub.

$ elixir/ch-1.exs
Example 1:
Input: $int = 38
Output: Persistence  = 2
        Digital Root = 2

Example 2:
Input: $int = 7
Output: Persistence  = 0
        Digital Root = 7

Example 3:
Input: $int = 999
Output: Persistence  = 2
        Digital Root = 9

Example 4:
Input: $int = 1999999999
Output: Persistence  = 3
        Digital Root = 1

Example 5:
Input: $int = 101010
Output: Persistence  = 1
        Digital Root = 3

Raku

In Raku, we can be a little more terse. The stopping condition only takes up line 5, Strictly speaking, we don’t need to do all the machinations on line 6 of converting $int into a Str, then breaking it apart into characters by combing it, and then mapping those into integers; just [+] $int.comb accomplishes the same thing, but with a lot more implicit type conversion happening behind the scenes. I’m going to be relying on that in the Perl solution, so I’m enjoying my ability to be explicit in Raku.

sub digitalRoot($int, $persistence = 0) {
  return ($persistence, $int) if $int < 10 ;
  my $sum = [+] $int.Str.comb.map({ .Int });
  digitalRoot($sum, $persistence + 1);
}

View the entire Raku script for this task on GitHub.

Perl

Conversely, in Perl I could have written sum(map { $_ + 0 } split //, "$int") to explicitly convert $int to a string, split it into the characters, then convert each of those characters back into integers before summing them, but just writing sum split //, $int feels much more Perlish.

use List::AllUtils qw( sum );

sub digitalRoot($int, $persistence = 0) {
  return ($persistence, $int) if $int < 10 ;
  my $sum = sum split //, $int;
  digitalRoot($sum, $persistence + 1);
}

View the entire Perl script for this task on GitHub.

Python

The Python solution is just as terse as the Raku and Perl solutions, but Python needs the explicit type conversions.

def digital_root(my_int, persistence=0):
  if my_int < 10: return (persistence, my_int)
  my_sum = sum(int(digit) for digit in str(my_int))
  return digital_root(my_sum, persistence + 1)

View the entire Python script for this task on GitHub.

Task 2: String Reduction

You are given a word containing only alphabets,

Write a function that repeatedly removes adjacent duplicate characters from a string until no adjacent duplicates remain and return the final word.

Example 1

Input: $word = "aabbccdd"
Output: ""

Iteration 1: remove "aa", "bb", "cc", "dd" => ""

Example 2

Input: $word = "abccba"
Output: ""

Iteration 1: remove "cc" => "abba"
Iteration 2: remove "bb" => "aa"
Iteration 3: remove "aa" => ""

Example 3

Input: $word = "abcdef"
Output: "abcdef"

No duplicate found.

Example 4

Input: $word = "aabbaeaccdd"
Output: "aea"

Iteration 1: remove "aa", "bb", "cc", "dd" => "aea"

Example 5

Input: $word = "mississippi"
Output: "m"

Iteration 1: Remove "ss", "ss", "pp" => "miiii"
Iteration 2: Remove "ii", "ii" => "m"

Approach

This task again calls for recursion, but it also calls for a regular expression: /(.)\1/. This will match a pair of the same character next to each other.

Elixir

In Elixir, Regex.replace/4 does regular expression replacements, and by default it does it globally for all occurrences, but it doesn’t return any status indicating whether the replacement succeeded or not, so we need to compare the output of the function to the input string to see if any replacements were made.

def string_reduction(word) do
  replaced = Regex.replace(~r/(.)\1/, word, "")
  cond do
    replaced == word -> replaced
    true -> string_reduction(replaced)
  end
end

View the entire Elixir script for this task on GitHub.

$ elixir/ch-2.exs
Example 1:
Input: $word = "aabbccdd"
Output: ""

Example 2:
Input: $word = "abccba"
Output: ""

Example 3:
Input: $word = "abcdef"
Output: "abcdef"

Example 4:
Input: $word = "aabbaeaccdd"
Output: "aea"

Example 5:
Input: $word = "mississippi"
Output: "m"

Raku

Raku, however, returns whether or not the substitution succeeded, meaning I could dispense withe the recursion entirely and just loop until the substitution stopped substituting anything. Raku doesn’t use the normal \1 for the backreference, so I used Raku’s version, $0.

sub stringReduction($word is copy) {
  while ($word ~~ s:g/(.)$0//) {  }
  $word
}

View the entire Raku script for this task on GitHub.

Perl

But in Perl I was both able to loop while the substitution returned true and use \1.

sub stringReduction($word) {
  while ($word =~ s/(.)\1//g) { }
  $word
}

View the entire Perl script for this task on GitHub.

Python

Python, has re.sub to just do the substitution and return the result, and re.subn to do the substitution and return a tuple of the result and the number of substitutions performed. This lets us repeatedly do the substitution until no more substitutions occur, and then break out of our loop.

import re

def string_reduction(word):
  while True:
    word, n = re.subn(r'(.)\1', '', word)
    if n == 0: break
  return word

View the entire Python script for this task on GitHub.

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

  1. Because this past weekend my wife was watching the Netflix documentary Miracle: The Boys of ’80, and she was sorely disappointed that in the entire film, nowhere did it feature the official theme song of the 1980 winter olympics.

    So we had to listen to it once the movie was over. 😁 ↩︎

Leave a Reply