Combinations

This is a solution to the 67th Perl Weekly Challenge, written in Raku.

Task #1 › Number Combinations

You are given two integers $m and $n. Write a script print all possible combinations of $n numbers from the list 1 2 3 … $m.

Every combination should be sorted i.e. [2,3] is valid combination but [3,2] is not.

Example: Input: $m = 5, $n = 2

Output: [ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ]

The problem can be solved with a Raku builtin:

  (1..5).combinations(2).say
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))

The task gives an example that uses brackets to show the combinations, not parentheses. We can take advantage of Array stringification to produce more or less the same output.

  (1..5).combinations(2).map({ .Array }).Array.raku.say
[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

Let's say we don't want to rely on the Array stringification and want to provide our own. This solution uses .rotor to wrap the output to a configurable width.

  sub number-combinations($m, $n, :$width = 96) {
      my @combinations =
          (1..$m).combinations($n)           # generate the combinations
                 .map({ "[{.join: ','}]" }); # format each combination

      my $per-line = $width div @combinations.map({ .chars + 2 }).max;

      ('[ ' ~
          @combinations
               .rotor($per-line, :partial)   # split into n per line
               .map({ .join(', ') })         # join items on same line
               .join(",\n  ")                # join the lines
       ~ ' ]').say
  }

  number-combinations(8, 3)
[ [1,2,3], [1,2,4], [1,2,5], [1,2,6], [1,2,7], [1,2,8], [1,3,4], [1,3,5], [1,3,6], [1,3,7],
  [1,3,8], [1,4,5], [1,4,6], [1,4,7], [1,4,8], [1,5,6], [1,5,7], [1,5,8], [1,6,7], [1,6,8],
  [1,7,8], [2,3,4], [2,3,5], [2,3,6], [2,3,7], [2,3,8], [2,4,5], [2,4,6], [2,4,7], [2,4,8],
  [2,5,6], [2,5,7], [2,5,8], [2,6,7], [2,6,8], [2,7,8], [3,4,5], [3,4,6], [3,4,7], [3,4,8],
  [3,5,6], [3,5,7], [3,5,8], [3,6,7], [3,6,8], [3,7,8], [4,5,6], [4,5,7], [4,5,8], [4,6,7],
  [4,6,8], [4,7,8], [5,6,7], [5,6,8], [5,7,8], [6,7,8] ]

Task #2 › Letter Phone

You are given a digit string $S. Write a script to print all possible letter combinations that the given digit string could represent.

keypad.png

Example: Input: $S = '35'

Output: ["dj", "dk", "dl", "ej", "ek", "el", "fj", "fk", "fl"].

The core part of this problem can be solved with the X~ cross product operator.

  say < d e f > X~ < j k l >
(dj dk dl ej ek el fj fk fl)

We can use X~ with the reduction metaoperator [ ] to handle input for an arbitrary number of key presses.

say [X~] ( < d e f >, < g h i >, < j k l> )
(dgj dgk dgl dhj dhk dhl dij dik dil egj egk egl ehj ehk ehl eij eik eil fgj fgk fgl fhj fhk fhl fij fik fil)

The complete soltion applies the [X~] cross product reduce operator to a slice of key presses, with some output formatting.

    sub phone-combinations(Str $digits) {
        my %keys =
            1 => < _ , @ >,   2 => < a b c >, 3 => < d e f >,
            4 => < g h i >,   5 => < j k l >, 6 => < m n o >,
            7 => < p q r s >, 8 => < t u v >, 9 => < w x y z >,
            '*' => (' ',);

        ('[' ~
         (
             [X~] %keys{ $digits.comb }
         )
         .map({ "\"{$_}\"" })
         .rotor(10, :partial).map({ .join(', ') })
         .join("\n ")
         ~ ']').say
    }

    phone-combinations '417'
["g_p", "g_q", "g_r", "g_s", "g,p", "g,q", "g,r", "g,s", "g@p", "g@q"
 "g@r", "g@s", "h_p", "h_q", "h_r", "h_s", "h,p", "h,q", "h,r", "h,s"
 "h@p", "h@q", "h@r", "h@s", "i_p", "i_q", "i_r", "i_s", "i,p", "i,q"
 "i,r", "i,s", "i@p", "i@q", "i@r", "i@s"]
comments powered by Disqus