Perl Weekly Challenge 395‘s tasks are “Complex Number” and “Word Squares”.
Complex Number, the night we met,
There was magic abroad in the air,
There were angels dining at the Ritz
And a nightingale sang in a Word Square.
Task 1: Complex Number
You are given two complex numbers as string.
Write a script to return the multiplication of the given complex numbers.
Using the formula: (a + bi) x (c + di) = (ac – bd) + (ad + bc)i
Input: $num1 = "1+1i", $num2 = "1+1i"
Output: "0+2i"Input: $num1 = "1+(-1)i", $num2 = "1+(-1)i"
Output: "0+(-2)i"Input: $num1 = "0+3i", $num2 = "0+4i"
Output: "-12+0i"Input: $num1 = "3+4i", $num2 = "3+(-4)i"
Output: "25+0i"Input: $num1 = "50+(-20)i", $num2 = "-10+30i"
Output: "100+1700i"Approach
I looked at this problem and thought that it looked like a job for a regular expression. What we’re doing is parsing out values for a, b, c, and d from complex numbers in the form a + bi or c + (di) where any of these numbers could be negative. Fortunately, we know that all the real portions of the complex numbers are integers, so we don’t need parse out decimals, only integers.
In PCRE, we can match & capture an integer with [+-]?\d+, but we also want to match integers in parentheses, so we want to make it [+-]?\d+|\(\[+-]?\d+). If we store that in a variable $integer, then matching the real portions of complex numbers in this challenge would look like
/ ($integer) \s* ([+-]) \s* ($integer) \s* i/x
We’re capturing both the real portions, and, for good measure, the operator used to join the portions. This way, in addition to recognizing a + bi, we can also recognize a - bi.
After that, it’s just following the roadmap laid out in the challenge description, and then re-format the resulting number the way the challenge asks.
Raku
Of course, for me, because I’ve been writing Perl-compatible regular expressions for the past 30 years, I had to work backwards to Raku Regexes. Enumerated character classes are <[ ]> instead of [ ], and interpolating variables requires angle brackets like this: <$var>. Alternation is two pipes (||) instead of just one (|), and whitespace is ignored by default.
One thing, because I was capturing any parentheses used in the numbers, they needed to be stripped out before I converted them to integers.
sub parseComplex($c) {
my $integer = rx/<[+-]>? \d+ || \( \s* <[+-]>? \d+ \s* \)/;
$c.match(/ (<$integer>) \s* (<[+-]>) \s* (<$integer>) \s* i/);
my ($real, $op, $imag) = ($0, $1, $2);
$real ~~ s:g/<[()]>//; # strip parens
$imag ~~ s:g/<[()]>//;
$real = $real.Int;
$imag = $op eq '-' ?? -1 * $imag.Int !! $imag.Int;
($real, $imag)
}
sub complexMult($num1, $num2) {
my ($a, $b) = parseComplex($num1);
my ($c, $d) = parseComplex($num2);
my $e = ($a * $c) - ($b * $d);
my $f = ($a * $d) + ($b * $c);
$f = $f < 0 ?? "({$f})" !! $f.Str;
"{$e}+{$f}i"
}View the entire Raku script for this task on GitHub.
$ raku/ch-1.raku
Example 1:
Input: $num1 = "1+1i", $num2 = "1+1i"
Output: "0+2i"
Example 2:
Input: $num1 = "1+(-1)i", $num2 = "1+(-1)i"
Output: "0+(-2)i"
Example 3:
Input: $num1 = "0+3i", $num2 = "0+4i"
Output: "-12+0i"
Example 4:
Input: $num1 = "3+4i", $num2 = "3+(-4)i"
Output: "25+0i"
Example 5:
Input: $num1 = "50+(-20)i", $num2 = "-10+30i"
Output: "100+1700i"
Example 6:
Input: $num1 = "-2+5i", $num2 = "5-5i"
Output: "15+35i"Perl
The Perl solution is just like the Raku solution, except that it uses the regular expression syntax I originally wrote the regexes in, not the funky Raku syntax.
sub parseComplex($c) {
my $integer = qr/[+-]? \d+ | \( \s* [+-]? \d+ \s* \)/x;
$c =~ / ($integer) \s* ([+-]) \s* ($integer) \s* i/x;
my ($real, $op, $imag) = ($1, $2, $3);
$real =~ s/[()]//g; # strip parens
$imag =~ s/[()]//g;
$real = int($real);
$imag = $op eq '-' ? -1 * int($imag) : int($imag);
($real, $imag)
}
sub complexMult($num1, $num2) {
my ($a, $b) = parseComplex($num1);
my ($c, $d) = parseComplex($num2);
my $e = ($a * $c) - ($b * $d);
my $f = ($a * $d) + ($b * $c);
$f = $f < 0 ? "(@{[$f]})" : $f;
"@{[$e]}+@{[$f]}i"
}View the entire Perl script for this task on GitHub.
Python
As I learned last week, in Python if you want to use interpolation in a regex, you need to build the regex as a string and compile it. I opted against it last week, but this week I embraced it. I also decided to name the captures that the regex was doing, so it would be easy grabbing the right ones later.
import re
def parse_complex(c):
integer = '[+-]? \\d+ | \\( \\s* [+-]? \\d+ \\s* \\)'
parse = re.compile(
f'(?P<real>{integer})' +
f'\\s* (?P<op>[+-]) \\s*' +
f'(?P<imag>{integer}) \\s* i', re.X
)
no_parens = re.compile(r'[()]')
m = parse.match(c)
if m:
real = no_parens.sub("", m.group('real')) # strip parens
imag = no_parens.sub("", m.group('imag'))
real = int(real)
imag = -1 * int(imag) if m.group('op') == '-' else int(imag)
return (real, imag)
def complex_mult(num1, num2):
a, b = parse_complex(num1)
c, d = parse_complex(num2)
e = (a * c) - (b * d)
f = (a * d) + (b * c)
f = f'({f})' if f < 0 else f
return f'{e}+{f}i'View the entire Python script for this task on GitHub.
Elixir
And I carried over that regex code into the Elixir solution. However, the code to get the named capture, strip the parentheses, and convert to integer wound up taking multiple lines, so I decided to employ a trick I’ve been using at work: anonymous functions. It’s a trick I’ve used in Perl a lot, but haven’t had to in the Weekly Challenge yet…
def parse_complex(c) do
integer = "[+-]? \\d+ | \\( \\s* [+-]? \\d+ \\s* \\)"
parse = Regex.compile!(
"(?<real>" <> integer <> ")" <>
"\\s* (?<op>[+-]) \\s*" <>
"(?<imag>" <> integer <> ") \\s* i", "x"
)
m = Regex.named_captures(parse, c)
if m do
strip_parens = fn name ->
Regex.replace(~r/[()]/, Map.get(m, name), "")
|> String.to_integer
end
real = strip_parens.("real")
imag = strip_parens.("imag")
imag = if Map.get(m, "op") == "-", do: -1 * imag,
else: imag
{real, imag}
end
end
def complex_mult(num1, num2) do
{a, b} = parse_complex(num1)
{c, d} = parse_complex(num2)
e = (a * c) - (b * d)
f = (a * d) + (b * c)
f = if f < 0, do: "(#{f})", else: f
"#{e}+#{f}i"
endView the entire Elixir script for this task on GitHub.
Task 2: Word Squares
You are given a list of equal lengths words.
Write a script to arrange a set of words into a grid that reading across any row gives the exact same word as reading down its corresponding column.
Input: @words = ("MA", "AM", "MY", "ME")
Output: ("MA", "AM")
M A
A MInput: @words = ("SUN", "USE", "NET", "SEE", "TEN")
Output: ("SUN", "USE", "NET")
S U N
U S E
N E TInput: @words = ("BOAT", "TEAL", "AREA", "TSAR", "OGRE")
Output: ("BOAT", "OGRE", "AREA", "TEAL")
B O A T
O G R E
A R E A
T E A LInput: @words = ("CARD", "AREA", "REAR", "DART")
Output: ("CARD", "AREA", "REAR", "DART")
C A R D
A R E A
R E A R
D A R TInput: @words = ("HEART", "TREND", "EMBER", "RESIN", "ABUSE")
Output: ("HEART", "EMBER", "ABUSE", "RESIN", "TREND")
H E A R T
E M B E R
A B U S E
R E S I N
T R E N DApproach
Initially, I thought the best way to approach this was to go through the words and assign some kind of ranking to the words based on how many of the other words in the list they shared letters with, giving higher ranking to words that contained only the first letters of other words… and I wasted several hours trying to make that approach work. I finally walked away for a while.
When I came back, I decided to just brute-force it: determine all the permutations of the words (and I soon realized that for examples 1-3, I would need to generate all the n-word combinations, and then the combinations of those), and check each permutation to see if it was a word square. The checking, I realized, was pretty trivial: have two nested loops, i -> 0 .. wordlen-2 and j -> i+1 .. wordlen-1, and compare square[i][j] with square[j][i]. If any of them differed, it wasn’t a word square.
Look at a 5×5 square. It’s going to look like this:
Whole Diagonal Bottom Top
Square Group Group
A B C D E A B C D E
B F G H I F B G H I
C G J K L J C G K L
D H K M N M D H K N
E I L N O O E I L N There’s nothing to match on the diagonal: those letters are both from the same word, both horizontally and vertically. So we just need to match letters from the bottom group with their corresponding position in the top group. If any of these don’t match, it’s not a word square, and we can stop checking.
Raku
Building the matrix of the word square from a list of words was easy, just map each word to a list of the characters in the word, and make a list of those lists. It’s a one liner (line 5). Then we use Raku’s built-in List class’ combinations and permutations routines.
sub isSquare(@words) {
my @square = [ @words.map({$_.comb}) ];
my $len = @words[0].chars - 1;
for 0 .. $len -> $i {
for $i+1 .. $len -> $j {
return False unless @square[$i][$j] eq @square[$j][$i];
}
}
return True;
}
sub wordSquare(@words) {
for @words.combinations(@words[0].chars) -> @list {
for @list.permutations -> $perm {
return $perm if isSquare($perm);
}
}
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1:
Input: @words = ("MA", "AM", "MY", "ME")
Output: ("MA", "AM")
M A
A M
Example 2:
Input: @words = ("SUN", "USE", "NET", "SEE", "TEN")
Output: ("SUN", "USE", "NET")
S U N
U S E
N E T
Example 3:
Input: @words = ("BOAT", "TEAL", "AREA", "TSAR", "OGRE")
Output: ("BOAT", "OGRE", "AREA", "TEAL")
B O A T
O G R E
A R E A
T E A L
Example 4:
Input: @words = ("CARD", "AREA", "REAR", "DART")
Output: ("CARD", "AREA", "REAR", "DART")
C A R D
A R E A
R E A R
D A R T
Example 5:
Input: @words = ("HEART", "TREND", "EMBER", "RESIN", "ABUSE")
Output: ("HEART", "EMBER", "ABUSE", "RESIN", "TREND")
H E A R T
E M B E R
A B U S E
R E S I N
T R E N DPerl
In Perl, however, we need to pull in the Algorithm::Combinatorics module from CPAN for combinations and permutations routines.
use Algorithm::Combinatorics qw( combinations permutations );
sub isSquare(@words) {
my @square = map { [ split //, $_ ] } @words;
my $len = length($words[0]) - 1;
for my $i ( 0 .. $len ) {
for my $j ( $i+1 .. $len ) {
return false unless $square[$i][$j] eq $square[$j][$i];
}
}
return true;
}
sub wordSquare(@words) {
for my $list ( combinations(\@words, length($words[0])) ) {
for my $perm ( permutations($list) ) {
return @$perm if isSquare(@$perm);
}
}
}View the entire Perl script for this task on GitHub.
Python
And in Python, combinations and permutations come from the itertools module.
from itertools import combinations, permutations
def is_square(words):
square = [ [ c for c in w] for w in words ]
length = len(words[0]) # because range() stops before this
for i in range(length):
for j in range(i+1, length):
if square[i][j] != square[j][i]: return False
return True
def word_square(words):
for lst in combinations(words, len(words[0])):
for perm in permutations(lst):
if is_square(perm): return permView the entire Python script for this task on GitHub.
Elixir
Elixir doesn’t have a built-in combinatorics module, so I found one on Hex.pm (documentation link). One of the things I decided was because it’s really difficult to do a nested loop with an early exit in Elixir, I would just produce a List of all the permutations of n-word lists, and then just use Enum.find/3 to return the first one that passed is_square/1.
Similarly, in the other languages I’m returning early from is_square once I find a comparison that doesn’t match, but that’s difficult to do in Elixir without recursion, so instead I’m doing all the comparisons in a nested list comprehension that returns a nested list of booleans. For example, when words = ["HEART", "TREND", "EMBER", "RESIN", "ABUSE"], the comprehensions from lines 9-15 return [[false, false, true, false], [false, false, false], [false, false], [false]]. Calling List.flatten/1 makes the list flat, and Enum.all?/1 returns true only if all the elements of the list are true.
I did, however, decide to employ another anonymous function to make accessing the elements of the square matrix a little clearer.
Mix.install([ :combinatorics ])
def is_square(words) do
square = Enum.into(words, [], & String.codepoints(&1) )
get_square = fn x, y -> Enum.at(square, x) |> Enum.at(y) end
len = hd(words) |> String.length
for i <- 0..len-2 do
for j <- i+1..len-1 do
get_square.(i, j) == get_square.(j, i)
end
end
|> List.flatten
|> Enum.all?
end
def word_square(words) do
len = String.length(Enum.at(words, 0))
Combinatorics.n_combinations(len, words)
|> Enum.reduce([], fn lst, combos ->
combos ++ Combinatorics.permutations(lst)
end)
|> Enum.find(& is_square(&1))
endView the entire Elixir script for this task on GitHub.
Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-395-packy-anderson/challenge-395/packy-anderson