Perl Weekly Challenge: I could drink a case of you…

Posted on by

Just before our love got lost you said
“I am as constant as Kaprekar”
And I said, “Constantly writing fractions
Where’s that at?
If you want me, I’ll be in the bar…”

In the blue TV screen light, let’s draw a map of Perl Weekly Challenge 357.

Task 1: Kaprekar Constant

Write a function that takes a 4-digit integer and returns how many iterations are required to reach Kaprekar’s constant (6174). For more information about Kaprekar's Constant please follow the wikipedia page.

Example 1

Input: $int = 3524
Output: 3

Iteration 1: 5432 - 2345 = 3087
Iteration 2: 8730 - 0378 = 8352
Iteration 3: 8532 - 2358 = 6174

Example 2

Input: $int = 6174
Output: 0

Example 3

Input: $int = 9998
Output: 5

Iteration 1: 9998 - 8999 = 0999
Iteration 2: 9990 - 0999 = 8991
Iteration 3: 9981 - 1899 = 8082
Iteration 4: 8820 - 0288 = 8532
Iteration 5: 8532 - 2358 = 6174

Example 4

Input: $int = 1001
Output: 4

Iteration 1: 1100 - 0011 = 1089
Iteration 2: 9810 - 0189 = 9621
Iteration 3: 9621 - 1269 = 8352
Iteration 4: 8532 - 2358 = 6174

Example 5

Input: $int = 9000
Output: 4

Iteration 1: 9000 - 0009 = 8991
Iteration 2: 9981 - 1899 = 8082
Iteration 3: 8820 - 0288 = 8532
Iteration 4: 8532 - 2358 = 6174

Example 6

Input: $int = 1111
Output: -1

The sequence does not converge on 6174, so return -1.

Approach

This is basically a recursive algorithm (I mean, I could do it in a loop, but recursion is much more fun). Check to see if the result of the last iteration yielded Kaprekar’s Constant or 0. If it yielded 0, we’re never converging on Kaprekar’s Constant, so we return -1. If we got Kaprekar’s Constant, return the number of times we’ve iterated.

Elixir

Originally, I knew I wanted to do the Elixir solution first because it would use recursion, but once I started writing it, I realized I could use case as well. One thing to note in the Elixir solution that’s not true in the others: while we’re working with the list of digits, they’re numeric elements in the list, because that’s what Integer.digits/2 returns. All the other languages, we’re converting the integer into a string and then splitting into its characters.

def sort_digits(digits, func) do
  digits |> Enum.sort(func) |> Enum.join |> String.to_integer
end

def zero_pad(digits) when length(digits) >= 4, do: digits
def zero_pad(digits) do
  [0] ++ digits
end

def kaprekar_count(int, count \\ 0) do
  case int do
    0    -> -1    # sequence doesn't converge
    6174 -> count # sequence converged in this many iterations
    _    -> digits = Integer.digits(int) |> zero_pad
            num1   = digits |> sort_digits(&(&1 >= &2))
            num2   = digits |> sort_digits(&(&2 >= &1))
            diff   = num1 - num2
            kaprekar_count(diff, count + 1)
  end
end

View the entire Elixir script for this task on GitHub.

$ elixir/ch-1.exs
Example 1:
Input: $ints = 3524
Output: 3

Example 2:
Input: $ints = 6174
Output: 0

Example 3:
Input: $ints = 9998
Output: 5

Example 4:
Input: $ints = 1001
Output: 4

Example 5:
Input: $ints = 9000
Output: 4

Example 6:
Input: $ints = 1111
Output: -1

Raku

Sadly, for the Raku solution, a case statement is given/when, so I didn’t even try to keep that. However, because $int.comb on line 20 produces a List, and lists in Raku are immutable, we cast the list as an Array. When we’re sorting, we’re using Raku’s three-way “smart” operator, cmp.

sub sort_digits(@digits, $func) {
  @digits.sort($func).join.Int;
}

sub zero_pad(@digits) {
  while (@digits.elems < 4) { @digits.unshift("0"); }
  @digits;
}

sub kaprekarCount($int, $count = 0) {
  # sequence doesn't converge
  return -1 if $int == 0;

  # sequence converged in this many iterations
  return $count if $int == 6174;

  my @digits = zero_pad($int.Str.comb.Array);
  my $num1   = sort_digits(@digits, { $^b <=> $^a });
  my $num2   = sort_digits(@digits, { $^a <=> $^b });
  my $diff   = $num1 - $num2;
  kaprekarCount($diff, $count + 1);
}

View the entire Raku script for this task on GitHub.

Perl

The big changes in Perl were how the function for sorting got passed and called, and the use of the “spaceship operator” <=> to do the numeric comparisons.

sub sort_digits($digits, $func) {
  join('', sort { $func->() } @$digits);
}

sub zero_pad(@digits) {
  while (@digits < 4) { unshift @digits, "0"; }
  @digits;
}

sub kaprekarCount($int, $count = 0) {
  # sequence doesn't converge
  return -1 if $int == 0;

  # sequence converged in this many iterations
  return $count if $int == 6174;

  my @digits = zero_pad(split //, $int);
  my $num1   = sort_digits(\@digits, sub { $b <=> $a });
  my $num2   = sort_digits(\@digits, sub { $a <=> $b });
  my $diff   = $num1 - $num2;
  kaprekarCount($diff, $count + 1);
}

View the entire Perl script for this task on GitHub.

Python

Happily, in Python I could return to an honest-to-goodness case statement

def sort_digits(digits, reverse=True):
  return int("".join(sorted(digits, reverse=reverse)))

def zero_pad(digits):
  while len(digits) < 4: digits.insert(0, str(0))
  return digits

def kaprekar_count(num, count = 0):
  match num:
    # sequence doesn't converge
    case 0: return -1

    # sequence converged in this many iterations
    case 6174: return count

    case _:
      digits = zero_pad([ d for d in str(num) ])
      num1   = sort_digits(digits, reverse=True)
      num2   = sort_digits(digits, reverse=False)
      diff   = num1 - num2
      return kaprekar_count(diff, count + 1)

View the entire Python script for this task on GitHub.

Task 2: Unique Fraction Generator

Given a positive integer N, generate all unique fractions you can create using integers from 1 to N and follow the rules below:

- Use numbers 1 through N only (no zero)
- Create fractions like numerator/denominator
- List them in ascending order (from smallest to largest)
- If two fractions have the same value (like 1/2 and 2/4),
  only show the one with the smallest numerator

Example 1

Input: $int = 3
Output: 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1

Example 2

Input: $int = 4
Output: 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, 4/3, 3/2, 2/1, 3/1, 4/1

Example 3

Input: $int = 1
Output: 1/1

Example 4

Input: $int = 6
Output: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4,
        4/5, 5/6, 1/1, 6/5, 5/4, 4/3, 3/2, 5/3, 2/1,
        5/2, 3/1, 4/1, 5/1, 6/1

Example 5

Input: $int = 5
Output: 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1,
        5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1

Approach

This one I want to tackle using recursion as well, because the list of fractions for $int is going to be a superset of the list of fractions for $int - 1. The new fractions will be 1 through $int - 1 over $int, and $int over 1 through $int - 1. If we can simplify any fraction (if the numerator isn’t 1 and it’s evenly divisible by the denominator, except when the denominator is 1), the simplified version of that fraction will have already been included in the list from an earlier term.

We can sort the fractions by just sorting them by their numeric value. To make calculating that easy, we’ll store the fraction as a numerator/denominator pair/tuple, and only turn them into strings when we display them.

Elixir

Again, I tackled the Elixir first because I’m doing this recursively. I’m passing the fractions around as tuples, because it makes it really easy to grab the numerator and denominator values.

def fractions(int) when int == 1, do: [ {1, 1} ]
def fractions(int) do
  list   = [ {1, int}, {int,1} ]
  digits = if int == 2, do: [2], else: 2..(int-1)
  Enum.reduce(digits, list, fn digit, list ->
    cond do
      rem(int, digit) != 0 ->
        list ++ [ {digit, int}, {int, digit} ]
      true -> list
    end
  end) ++ fractions(int - 1)
end

def tuple_to_fraction({numerator, denominator}),
  do: numerator / denominator

def tuple_to_fraction_str({numerator, denominator}),
  do: "#{numerator}/#{denominator}"

def uniq_fractions(int) do
  fractions(int)
  |> Enum.sort_by(&tuple_to_fraction/1)
  |> Enum.map(&tuple_to_fraction_str/1)
  |> Enum.join(", ")
end

View the entire Elixir script for this task on GitHub.

$ elixir/ch-2.exs
Example 1:
Input: $int = 3
Output: 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1

Example 2:
Input: $int = 4
Output: 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, 4/3, 3/2, 2/1, 3/1, 4/1

Example 3:
Input: $int = 1
Output: 1/1

Example 4:
Input: $int = 6
Output: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 4/6, 2/3, 3/4,
        4/5, 5/6, 1/1, 6/5, 5/4, 4/3, 6/4, 3/2, 5/3, 2/1,
        5/2, 3/1, 4/1, 5/1, 6/1

Example 5:
Input: $int = 5
Output: 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1,
        5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1

Raku

In Raku, I’m able to make things a little more compact because I don’t need to do anything with the list if I’m not adding to it, and I don’t need to define a function to convert the tuples into stringy fractions. Also, having the function called by the sort function only accept one argument, we can get the same behavior as Elixir’s Enum.sort_by/2 and Python’s sorted(list, key=func).

sub tuple_to_fraction(@t) { @t[0] / @t[1] }

multi fractions($int where $int == 1) { [ (1, 1), ] }
multi fractions($int) {
  my @list   = [ (1, $int), ($int, 1) ];
  my @digits = $int == 2 ?? [ 2 ] !! 2 .. $int-1;
  for @digits -> $digit {
    next unless $int % $digit != 0;
    @list.append( ($int, $digit), ($digit, $int));                      
  }
  @list.append(fractions($int - 1));
}

sub uniqFractions($int) {
  fractions($int)
  .sort(&tuple_to_fraction)
  .map({ $_.join('/') }) # join the tuple with /
  .join(", ");
}

View the entire Raku script for this task on GitHub.

Perl

Like last week, because Perl doesn’t have a list/tuple type, I’m passing around array references. 

sub tuple_to_num($numer,$denom) { $numer/$denom }
sub tuple_to_fraction { tuple_to_num(@$a) <=> tuple_to_num(@$b) }

sub fractions($int) {
  return ( [1, 1], ) if $int == 1;

  my @list   = ( [1, $int], [$int, 1] );
  my @digits = $int == 2 ? 2 : 2 .. $int-1;
  foreach my $digit ( @digits ) {
    next unless $int % $digit != 0;
    push @list, [$int, $digit], [$digit, $int];                      
  }
  push @list, fractions($int - 1);
  @list
}

sub uniqFractions($int) {
  join ', ',
  map { join('/', @{$_}) }
  sort tuple_to_fraction
  fractions($int);
}

View the entire Perl script for this task on GitHub.

Python

The Python solution renames some variables because int, list, and tuple are all keywords in Python. In my tuple_to_fraction function, I have to accept the tuple as the parameter and then unpack it on the next line, but in Python 2 you used to be able to unpack tuples in the function prototype (PEP3113, discussion). 

def fractions(num):
  if num == 1: return [ (1, 1), ]
  lst = [ (1, num), (num, 1) ]
  digits = [2] if num == 2 else range(2, num)
  for digit in digits:
    if num % digit == 0: continue
    lst.extend([(digit, num), (num, digit)])
  lst.extend(fractions(num-1))
  return lst

def tuple_to_fraction(tupl):
  n, d = tupl
  return n / d

def uniq_fractions(num):
  return ", ".join([
    f'{n}/{d}' for n,d in
    sorted(fractions(num), key=tuple_to_fraction)
  ])

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-357/packy-anderson

Leave a Reply