Perl Weekly Challenge: We’re Talkin’ Algebra

Posted on by

Perl Weekly Challenge 386‘s tasks are “Reverse Base” and “Rational Numbers”.

I figured, since both tasks are all about Algebra, we should listen to some Tom Lehrer (lyrics & sheet music).

Task 1: Reverse Base

You are given a string representing a number, and an integer specifying the base of that representation.

Write a function to convert this string to an integer. (For bases greater than 10, use characters A-Z, a-z, + and / in that order.)

Example 1

Input: $num = "101010", $base = 2
Output: 42

Example 2

Input: $num = "EEADEE", $base = 16
Output: 15642094

Example 3

Input: $num = "755", $base = 8
Output: 493

Example 4

Input: $num = "1BRJB", $base = 36
Output: 2228519

Example 5

Input: $num = "7MyqL", $base = 64
Output: 123456789

Approach

This is just the reverse of PWC 384’s Task 1: that was take a base-10 number and convert it to base-N, this is take a base-N number and convert it to base-10. We’re just going to reverse the process:

  1. Break the string up into the individual characters.
  2. Map the character to the numeric value for that character.
  3. Multiply the numeric value by the N-power for that place in the number.
  4. Add the values up.

For example, in example 2, we break up the string into ["E", "E", "A", "D", "E", "E"], then map it to [14, 14, 10, 13, 14, 14], multiply the values by [1048576, 65536, 4096, 256, 16, 1] to get [14680064, 917504, 40960, 3328, 224, 14], then add them all to get 15642094.

Raku

One of the things I realized as I was writing this in Raku, there would be an easy way to get the exponent values in step 3: if I reversed the list, the index of the value would be the exponent I’m raising $base to! And if I invoked .pairs on the list, I could get both the key and the value to use in my .map call.

The charmap flips what we did two weeks ago: instead of having an array where the index points to the character used to represent that value, I’m creating a Hash to map the character to the numeric value. And I’m using the List .antipairs routine to get value => key pairs from the list that make the hash fairly automatically.

# map chars => values like 'A' => 10, 'a' => 37
my %chars = (0...9,'A'...'Z','a'...'z','+','/').antipairs.Hash;

sub reverseBase($num, $base) {
  $num.Str.comb        # break the number into digits
  .map({ %chars{$_} }) # map character to numeric equivalent
  .reverse             # reverese the string so place -> power
  .pairs               # make a seq of pairs with position as key
  .map({ ($base ** $_.key) * $_.value }) # multiply by power
  .sum                 # add it all up
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: $num = "101010", $base = 2
Output: 42

Example 2:
Input: $num = "EEADEE", $base = 16
Output: 15642094

Example 3:
Input: $num = "755", $base = 8
Output: 493

Example 4:
Input: $num = "1BRJB", $base = 36
Output: 2228519

Example 5:
Input: $num = "7MyqL", $base = 64
Output: 123456789

Perl

The Perl solution is pretty much the same as the Raku solution, but instead of chaining operations front to back, we have to execute them back-to-front. Also, because I don’t know of a routine to generate pairs from a list, I’m using List::AllUtils’ zip_by with a range to do the same thing.

use List::AllUtils qw( sum zip_by );

# map chars => values like 'A' => 10, 'a' => 37
my %chars = zip_by { $_[0] => $_[1] }
  [0...9,'A'...'Z','a'...'z','+','/'], [0..63];

sub reverseBase($num, $base) {
  my $p = 0;         # start with $base ** 0
  sum                # add it all up
  map { ($base ** $p++) * $_ } # multiply by power
  reverse            # reverese the string so place -> power
  map { $chars{$_} } # map character to numeric equivalent
  split //, $num;    # break the number into digits
}

View the entire Perl script for this task on GitHub.

Python

I took inspiration from Mohammad Sajid Anwar’s solution to PWC 384 Task 1 to tighten up my method of generating the list of characters for the conversion, and I’m doing the same zip trick to map positions to indexes like I am in Perl. Also like the Perl solution, it’s mostly back-to-front.

# map chars => values like 'A': 10, 'a': 37
chars = {
  x: y for x, y in zip(
    [
      *"0123456789",
      *"ABCDEFGHIJKLMNOPQRSTUVWXYZ",
      *"abcdefghijklmnopqrstuvwxyz",
      "+", "/"
    ],
    range(64)
  )
}

def reverse_base(num, base):
  return sum( # add it all up
    [ base ** k * v for k,v in # multiply by power
      zip(
        range(len(num)), # range of powers from 0 -> len(num)-1
        [ chars[c] for c # map character to numeric equivalent
          in list(num)   # break the number into digits
          [::-1] ]       # reverese the string so place -> power
      )
    ]
  )

View the entire Python script for this task on GitHub.

Elixir

In Elixir, however, I’m once again able to pipe the output of one statement into the input for the next, so the code reads front to back again. Instead of building a list in the Enum.reduce/3 on lines 19-21, I just add the values I’m calculating so I don’t have to sum them later.

# map chars => values like 'A' => 10, 'a' => 37
@chars Enum.to_list(?0..?9) ++
       Enum.to_list(?A..?Z) ++
       Enum.to_list(?a..?z) ++
       [ ?+, ?/ ] |> Enum.map(&( <<&1 :: utf8>> )) |>
       Enum.zip(Range.to_list(0..63)) |> Map.new

def reverse_base(num, base) do
  num
  # break the number into digits
  |> String.codepoints
  # map character to numeric equivalent
  |> Enum.map(fn c -> Map.get(@chars, c) end)
  # reverese the string so place -> power
  |> Enum.reverse
  |> Enum.reduce({0, 0}, fn val, {pow, sum} ->
    { pow+1, (base ** pow * val) + sum } # multiply by power
  end)
  |> elem(1) # Enum.reduce returns {pow, sum}
end

View the entire Elixir script for this task on GitHub.

Task 2: Rational Numbers

You are given two strings representing non-negative rational numbers.

Write a script to return true if the two given rational numbers are same otherwise false.

Example 1

Input: $rat1 = "0.(12)"
       $rat2 = "0.(121)"
Output: false

Expansion of "0.(12)"  = 0.12 12 12 12
Expansion of "0.(121)" = 0.121 121 121

Example 2

Input: $rat1 = "0.1(23)"
       $rat2 = "0.12(32)"
Output: true

Expansion of "0.1(23)"  = 0.1 23 23 23
Expansion of "0.12(32)" = 0.12 32 32 32

Example 3

Input: $rat1 = "0.1(234)"
       $rat2 = "0.12(342)"
Output: true

Expansion of "0.1(234)"  = 0.1 234 234 234
Expansion of "0.12(342)" = 0.12 342 342 342

Example 4

Input: $rat1 = "12.99(99)"
       $rat2 = "13."
Output: true

Example 5

Input: $rat1 = "0.(123)"
       $rat2 = "0.1(231)"
Output: true

Approach

Ok, the only way I know to approach this is to convert each rational number into a normalized ratio of two integers. If the numerators and denominators of the ratios are the same, the two rational numbers are the same.

The algorithm to convert a decimal number into a ratio is as follows:

  1. Separate the number into the integer portion (before the decimal point) (call this int), the non-repeating decimal portion (call this nr), and the repeating decimal portion (call this rep).
  2. Calculate the power of 10 for the number of non-repeating decimal digits (i.e., if the non repeating digits are 12, the power of 10 we’ll use is 100). Call this pow1.
  3. Calculate the number of 9s for the number of repeating digits (i.e., if the repeating digits are (121), the number we want is 999, which is 103-1). Call this pow2. If there are no repeating digits, assign 1 to this.
  4. The ratio is (int * pow1 + nr) * pow2 + rep / pow1 * pow2.
  5. By finding the greatest common divisor of both the numerator and the denominator, we can normalize the ratio.

Raku

I decided to use a regular expression to separate the number into the parts I needed. However, unlike Perl, which would return a list of the captured fields, Raku returns a Match object. So, to get the fields, I have to call .list on the object. If there’s no non-repeating or repeating digits, the regex will return either an empty string or undef, so I make them explicitly have the value 0 so Raku doesn’t need to coerce those into 0 when I later use the values in addition.

Fortunately, when it came time to normalize the fraction, Raku has an operator for finding the greatest common divisor of two numbers: gcd.

I decided to return the normalized fractions as part of the explanatory text so it’s easy to see why the rational numbers are either equal or not equal.

sub rationalToFraction($rat is copy) {
  my ($int, $nr, $rep) = ($rat ~~ /(\d*)\.(\d*)?(\(\d*\))?/).list;
  $nr  ||= 0; # if no non-repeating digits, use 0 in addition
  $rep ||= 0; # if no repeating digits, use 0 in addition
  my $pow1  = $nr  ?? 10 ** $nr.chars        !! 1;
  my $pow2  = $rep ?? 10 ** ($rep.chars) - 1 !! 1;
  my $num   = ($int * $pow1 + $nr) * $pow2 + $rep;
  my $denom = $pow2 * $pow1;
  my $d     = $num gcd $denom;
  ($num / $d, $denom / $d);
}

sub rationalEqual($rat1, $rat2) {
  my ($n1, $d1) = rationalToFraction($rat1);
  my ($n2, $d2) = rationalToFraction($rat2);
  my $len = max($rat1.chars, $rat2.chars);
  return (
    $n1 == $n2 && $d1 == $d2 ?? 'true' !! 'false',
    sprintf("%*s is %d/%d\n%*s is %d/%d",
            $len, $rat1, $n1, $d1,
            $len, $rat2, $n2, $d2)
  );
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $rat1 = "0.(12)"
       $rat2 = "0.(121)"
Output: false

 0.(12) is 4/33
0.(121) is 121/999

Example 2:
Input: $rat1 = "0.1(23)"
       $rat2 = "0.12(32)"
Output: true

 0.1(23) is 61/495
0.12(32) is 61/495

Example 3:
Input: $rat1 = "0.1(234)"
       $rat2 = "0.12(342)"
Output: true

 0.1(234) is 137/1110
0.12(342) is 137/1110

Example 4:
Input: $rat1 = "12.99(99)"
       $rat2 = "13."
Output: true

12.99(99) is 13/1
      13. is 13/1

Example 5:
Input: $rat1 = "0.(123)"
       $rat2 = "0.1(231)"
Output: true

 0.(123) is 41/333
0.1(231) is 41/333

Perl

The big difference from the Raku to the Perl solution is how regexes work; instead of returning an object, I’m able to directly get the captured values (and non-capturing grouping is (?:pat) instead of Raku’s [pat]; fortunately, all the other languages use Perl’s regex syntax). There isn’t a native max or gcd function, so I have to import List::AllUtils’ max and Math::Utils’ gcd functions.

use List::AllUtils qw( max );
use Math::Utils qw( gcd );

sub rationalToFraction($rat) {
  my ($int, $nr, $rep) = $rat =~ /(\d*)\.(\d*)?(?:\((\d*)\))?/;
  $nr  ||= 0; # if no non-repeating digits, use 0 in addition
  $rep ||= 0; # if no repeating digits, use 0 in addition
  my $pow1  = $nr  ? 10 ** length($nr)      : 1;
  my $pow2  = $rep ? 10 ** length($rep) - 1 : 1;
  my $num   = ($int * $pow1 + $nr) * $pow2 + $rep;
  my $denom = $pow2 * $pow1;
  my $d     = gcd $num, $denom;
  ($num / $d, $denom / $d);
}

sub rationalEqual($rat1, $rat2) {
  my ($n1, $d1) = rationalToFraction($rat1);
  my ($n2, $d2) = rationalToFraction($rat2);
  my $len = max(length($rat1), length($rat2));
  return (
    $n1 == $n2 && $d1 == $d2 ? 'true' : 'false',
    sprintf("%*s is %d/%d\n%*s is %d/%d",
            $len, $rat1, $n1, $d1,
            $len, $rat2, $n2, $d2)
  );
}

View the entire Perl script for this task on GitHub.

Python

Python, like Raku, returns a Match object, I have to go back to extracting the values I need from the object to assign them to variables. Python, however, needs any strings to be int values before it can perform any arithmetic on them, so on lines 13-15 I do that. The gcd function needs to be imported from math.gcd.

import math
import re
pat = re.compile(r'(\d*)\.(\d*)?(?:\((\d*)\))?')

def rational_to_fraction(rat):
  int_v, nr_v, rep_v = pat.match(rat).group(1,2,3)
  if not nr_v:  nr_v = 0  # if no non-repeating digits, use 0
  if not rep_v: rep_v = 0 # if no repeating digits, use 0
  pow1  = 10 ** len(nr_v)      if nr_v  else 1
  pow2  = 10 ** len(rep_v) - 1 if rep_v else 1
  int_v = int(int_v) # convert strings to integers
  nr_v  = int(nr_v)
  rep_v = int(rep_v)
  num   = (int_v * pow1 + nr_v) * pow2 + rep_v
  denom = pow2 * pow1
  d     = math.gcd(num, denom)
  return (num // d, denom // d)

def rational_equal(rat1, rat2):
  n1, d1 = rational_to_fraction(rat1)
  n2, d2 = rational_to_fraction(rat2)
  length = max(len(rat1), len(rat2))
  fmt = ('{:>' + str(length) + '} is {}/{}' +
         '\n'  +
         '{:>' + str(length) + '} is {}/{}')
  return (
    'true' if n1 == n2 and d1 == d2 else 'false',
    fmt.format(rat1, n1, d1, rat2, n2, d2)
  )

View the entire Python script for this task on GitHub.

Elixir

One of the first things I ran into when converting the code to Elixir is that in order to assign a list to a list of variables, the source list had to have the same number of elements. So when there wasn’t a repeating portion to the decimal, my regular expression only returned two values in the list.

$ iex
Erlang/OTP 28 [erts-16.2] [source] [64-bit] [smp:16:16] [ds:16:16:10] [async-threads:1] [dtrace]

Interactive Elixir (1.19.5) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Regex.run(~r/(\d*)\.(\d*)?(?:\((\d*)\))?/, "13.", capture: :all_but_first)
["13", ""]
iex(2)> [int, nr, rep] = Regex.run(~r/(\d*)\.(\d*)?(?:\((\d*)\))?/, "13.", capture: :all_but_first)
** (MatchError) no match of right hand side value:

    ["13", ""]

    (stdlib 7.2) erl_eval.erl:672: :erl_eval.expr/6
    iex:2: (file)
iex(2)> [int, nr, rep] = Regex.run(~r/(\d*)\.(\d*)?(?:\((\d*)\))?/, "13.", capture: :all_but_first) ++ [""]
["13", "", ""]

But then I discovered that if I used a regex with named captures I could call Regex.named_captures/3 and get back a Map with all the names in it:

iex(4)> Regex.named_captures(~r/(?<int>\d*)\.(?<nr>\d*)?(?:\((?<rep>\d*)\))?/, "13.")
%{"int" => "13", "nr" => "", "rep" => ""}
iex(5)> %{"int" => int, "nr" => nr, "rep" => rep} = Regex.named_captures(~r/(?<int>\d*)\.(?<nr>\d*)?(?:\((?<rep>\d*)\))?/, "13.")
%{"int" => "13", "nr" => "", "rep" => ""}
iex(6)> rep
""
iex(7)> nr
""
iex(8)> int
"13"

This allowed me to keep the logic I was using in my other implementations and not have to test to see if there was a repeating portion to the number and then assign the list differently (which, to be honest, is the first thing I did before going back and thinking about it a little more).

One of the things I discovered is I couldn’t just say if var, do: ; I needed to actually test to see if it had a particular value, hence the tweaks on lines 16-19.

Like Python, Elixir really needs the values to be numeric before it performs any arithmetic using them, so I convert the int, nr, and rep values to ints explicitly. Because String.to_integer/1 complains if you pass it something that’s already an integer, I rolled my own int function that just returned the value it was being passed unchanged if Kernel.is_integer/1 returned true for the value.

The gcd function we need to normalize the fractions comes from Integer.gcd/2.

@pat ~r/(?<int>\d*)\.(?<nr>\d*)?(?:\((?<rep>\d*)\))?/

def int(val) when is_integer(val), do: val
def int(val), do: String.to_integer(val)

def rational_to_fraction(rat) do
  %{"int" => int, "nr" => nr, "rep" => rep}
    = Regex.named_captures(@pat, rat)
  nr    = if nr != "",  do: nr,  else: 0 # no non-repeating digits
  rep   = if rep != "", do: rep, else: 0 # no repeating digits
  pow1  = if nr != 0,  do: 10 ** String.length(nr),    else: 1
  pow2  = if rep != 0, do: 10 ** String.length(rep)-1, else: 1
  int   = int(int) # convert strings to integers
  nr    = int(nr)
  rep   = int(rep)
  num   = (int * pow1 + nr) * pow2 + rep
  denom = pow2 * pow1
  d     = Integer.gcd(num, denom)
  { div(num, d), div(denom, d) }
end

def rational_equal(rat1, rat2) do
  {n1, d1} = rational_to_fraction(rat1)
  {n2, d2} = rational_to_fraction(rat2)
  len = Enum.max([String.length(rat1), String.length(rat2)])
  rat1 = String.pad_leading(rat1, len)
  rat2 = String.pad_leading(rat2, len)
  {
    (if n1 == n2 and d1 == d2, do: "true", else: "false"),
    "#{rat1} is #{n1}/#{d1}\n#{rat2} is #{n2}/#{d2}"
  }
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-386-packy-anderson/challenge-386/packy-anderson

Leave a Reply