Interleaved Factors with Raku

[97] Published 18. October 2020.

This is my response to the Perl Weekly Challenge #082.

Challenge #082.1: Common Factors

You are given 2 positive numbers $M and $N.

Write a script to list all common factors of the given numbers.

Example 1

Input:
    $M = 12
    $N = 18

Output:
    (1, 2, 3, 6)

Explanation:
    Factors of 12: 1, 2, 3, 4, 6
    Factors of 18: 1, 2, 3, 6, 9

Example 2

Input:
    $M = 18
    $N = 23

Output:
    (1)

Explanation:
    Factors of 18: 1, 2, 3, 6, 9
    Factors of 23: 1

$N itself?

I do believe that the explanations are wrong, as the number itself should be part of the factor list, like this (for the number 18):

> my $N = 18; say (1..$N).grep({ $N %% $_ });
(1 2 3 6 9 18)

Note that this doesn't affect the outcome for the two examples, only the explanation.

I am not alone with this view; see e.g. www.mathsisfun.com/definitions/common-factor.htm.

We can get the factors without the number itself like this (for the number 18):

> my $N = 18; say (1..$N/2).grep({ $N %% $_ });
(1 2 3 6 9)

I'll do it the way the challenge describes, but support (what I think is) the correct way with a command line option «-i».

File: common-factors

#! /usr/bin/env raku

unit sub MAIN (Int $M where $M > 0,           # [1]
               Int $N where $N > 0,           # [1]
               :i(:$include-self),            # [2]
               :v(:$verbose)) ;

my @M-factors = $include-self
  ?? (1..$M).grep({ $M %% $_ })               # [2a]
  !! (1..$M/2).grep({ $M %% $_ });            # [2b]

my @N-factors = $include-self
  ?? (1..$N).grep({ $N %% $_ })               # [2a]
  !! (1..$N/2).grep({ $N %% $_ });            # [2b]

if $verbose
{
  say "Factors of $M: { @M-factors.join(", ") }";
  say "Factors of $N: { @N-factors.join(", ") }";
}

my %common = @M-factors (&) @N-factors;       # [3]

say "(" ~ %common.keys.sort.join(", ") ~ ")"; # [4]

[1] I could have used a custom type here, as i have done before, but it works equally well to just add on a where clause. (Except that you will get better error messages with custom types - using the type name).

[2] Do you want to include the number itself? Yes [2a], No [2b].

[3] We caluclate the common factors by taking the intersection of the two lists of factors with the intersection operator (&).

[4] The result of the line above is a Set, a hash like data structure. We must use the keys method to get the values. Hash keys are returned in a (for us) random order, so we must sort them.

See docs.raku.org/routine/(&), infix ∩ for more information about the intersection operator (&), also available as the Unicode character ∩.

See docs.raku.org/type/Set for more information about the Set type.

Running it:

$ ./common-factors -v -i 12 18
Factors of 12: 1, 2, 3, 4, 6
Factors of 18: 1, 2, 3, 6, 9
(1, 2, 3, 6)

$ ./common-factors -v 12 18
Factors of 12: 1, 2, 3, 4, 6
Factors of 18: 1, 2, 3, 6, 9
(1, 2, 3, 6)

$ ./common-factors -v 18 23
Factors of 18: 1, 2, 3, 6, 9
Factors of 23: 1
(1)

$ ./common-factors -v -i 18 23
Factors of 18: 1, 2, 3, 6, 9, 18
Factors of 23: 1, 23
(1)

The business of deciding whether or not to include the number itself as a factor can make a difference, as shown here:

$ ./common-factors -v 6 12
Factors of 6: 1, 2, 3
Factors of 12: 1, 2, 3, 4, 6
(1, 2, 3)

$ ./common-factors -v -i 6 12
Factors of 6: 1, 2, 3, 6
Factors of 12: 1, 2, 3, 4, 6, 12
(1, 2, 3, 6)

Challenge #082.2: Interleave String

You are given 3 strings; $A, $B and $C.

Write a script to check if $C is created by interleave $A and $B.

Print 1 if check is success otherwise 0.

Example 1

Input:
    $A = "XY"
    $B = "X"
    $C = "XXY"

Output: 1

Explanation

"X" (from $B) + "XY" (from $A) = $C

Example 2

Input:
    $A = "XXY"
    $B = "XXZ"
    $C = "XXXXZY"

Output: 1

Explanation

"XX" (from $A) + "XXZ" (from $B) + "Y" (from $A) = $C

Example 3

Input:
    $A = "YX"
    $B = "X"
    $C = "XXY"

Output: 0

I'll do this with a recursive procedure, taking the three strings as input. The idea is to reduce the third argument ($C) to an empty string. If we were able to do that, we have an interleaved string.

File: interleave-string

#! /usr/bin/env raku

unit sub MAIN (Str $A where $A.chars > 0,  # [1]
               Str $B where $B.chars > 0,  # [1]
               Str $C where $C.chars > 0,  # [1]
               :v(:$verbose));

say do_check($A, $B, $C) ?? '1' !! '0';    # [2]

sub do_check ($A, $B, $C)                  # [2]
{
  say ": Checking A:$A | B:$B | C:$C" if $verbose;

  return 1 if $C eq "";                    # [3]

  if $C.contains($A)                       # [4]
  {
    my $c = $C.subst($A);                  # [4a]
    return do_check($A, $B, $c);           # [4b]
  }
  
  if $C.contains($B)                       # [5]
  {
    my $c = $C.subst($B);                  # [5a]
    return do_check($A, $B, $c);           # [5b]
  }  
}

[1] The three strings. Note the constraint that ensures at least 1 character.

[2] Off we go. The call returns an explicit 1 on success, and an empty list otherwise (as it runs out of code, and simply exits). So we have to fix the 0 output manually.

[3] We are successful if we have managed to reduce $C to an empty string.

[4] If $A is a substring of $C, remove it from $C (with subst) and do a recursive call with the new value.

[5] As [4], but for $B.

See docs.raku.org/routine/contains for more information about contains.

See docs.raku.org/routine/subst for more information about subst.

Running it:

$ ./interleave-string XY X XXY
1

$ ./interleave-string XXY XXZ XXXXZY
1

$ ./interleave-string YX X XXY
0

With verbose mode, to see what is going on:

$ ./interleave-string -v XY X XXY
: Checking A:XY | B:X | C:XXY
: Checking A:XY | B:X | C:X
: Checking A:XY | B:X | C:
1

$ ./interleave-string -v XXY XXZ XXXXZY
: Checking A:XXY | B:XXZ | C:XXXXZY
: Checking A:XXY | B:XXZ | C:XXY
: Checking A:XXY | B:XXZ | C:
1

$ ./interleave-string -v YX X XXY
: Checking A:YX | B:X | C:XXY
: Checking A:YX | B:X | C:XY
: Checking A:YX | B:X | C:Y
0

Some more examples:

$ ./interleave-string -v AB CCC AAACCCBBB
: Checking A:AB | B:CCC | C:AAACCCBBB
: Checking A:AB | B:CCC | C:AAABBB
: Checking A:AB | B:CCC | C:AABB
: Checking A:AB | B:CCC | C:AB
: Checking A:AB | B:CCC | C:
1

$ ./interleave-string -v AB C AAACCCBBB
: Checking A:AB | B:C | C:AAACCCBBB
: Checking A:AB | B:C | C:AAACCBBB
: Checking A:AB | B:C | C:AAACBBB
: Checking A:AB | B:C | C:AAABBB
: Checking A:AB | B:C | C:AABB
: Checking A:AB | B:C | C:AB
: Checking A:AB | B:C | C:
1

$ ./interleave-string -v AB C AAACCCBBBCAABCB
: Checking A:AB | B:C | C:AAACCCBBBCAABCB
: Checking A:AB | B:C | C:AAACCCBBBCACB
: Checking A:AB | B:C | C:AAACCBBBCACB
: Checking A:AB | B:C | C:AAACBBBCACB
: Checking A:AB | B:C | C:AAABBBCACB
: Checking A:AB | B:C | C:AABBCACB
: Checking A:AB | B:C | C:ABCACB
: Checking A:AB | B:C | C:CACB
: Checking A:AB | B:C | C:ACB
: Checking A:AB | B:C | C:AB
: Checking A:AB | B:C | C:
1

$ ./interleave-string -v AB CD EF
: Checking A:AB | B:CD | C:EF
0

$ ./interleave-string -v AB B ABABABABABBBBABAABABABABAAB
: Checking A:AB | B:B | C:ABABABABABBBBABAABABABABAAB
: Checking A:AB | B:B | C:ABABABABBBBABAABABABABAAB
: Checking A:AB | B:B | C:ABABABBBBABAABABABABAAB
: Checking A:AB | B:B | C:ABABBBBABAABABABABAAB
: Checking A:AB | B:B | C:ABBBBABAABABABABAAB
: Checking A:AB | B:B | C:BBBABAABABABABAAB
: Checking A:AB | B:B | C:BBBAABABABABAAB
: Checking A:AB | B:B | C:BBBAABABABAAB
: Checking A:AB | B:B | C:BBBAABABAAB
: Checking A:AB | B:B | C:BBBAABAAB
: Checking A:AB | B:B | C:BBBAAAB
: Checking A:AB | B:B | C:BBBAA
: Checking A:AB | B:B | C:BBAA
: Checking A:AB | B:B | C:BAA
: Checking A:AB | B:B | C:AA
0

And that's it.

Interleaved Factors with Raku

Challenge #082.1: Common Factors

$N itself?

Challenge #082.2: Interleave String

Links