by Arne Sommer

# Interleaved Factors with Raku

 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, #  Int \$N where \$N > 0, #  :i(:\$include-self), #  :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; #  say "(" ~ %common.keys.sort.join(", ") ~ ")"; #  ```

 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).

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

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

 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, #  Str \$B where \$B.chars > 0, #  Str \$C where \$C.chars > 0, #  :v(:\$verbose)); say do_check(\$A, \$B, \$C) ?? '1' !! '0'; #  sub do_check (\$A, \$B, \$C) #  { say ": Checking A:\$A | B:\$B | C:\$C" if \$verbose; return 1 if \$C eq ""; #  if \$C.contains(\$A) #  { my \$c = \$C.subst(\$A); # [4a] return do_check(\$A, \$B, \$c); # [4b] } if \$C.contains(\$B) #  { my \$c = \$C.subst(\$B); # [5a] return do_check(\$A, \$B, \$c); # [5b] } } ```

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

 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.

 We are successful if we have managed to reduce `\$C` to an empty string.

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

 As , 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.