The complex square

Weekly Challenge 395

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

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.

My solution

The last time I used complex numbers was high school. As a quick refresher, a complex number has two parts: 1) a real number and 2) an imaginary number (square root of -1).

Python has builtin support for complex numbers. I have a function called to_complex which converts the provided value to a complex number.

def to_complex(s: str) -> complex:
    if m := re.search(r"^(-?\d+)\+(\d+)i$", s):
        return complex(int(m.group(1)), int(m.group(2)))
    if m := re.search(r"^(-?\d+)\+\((-\d+)\)i$", s):
        return complex(int(m.group(1)), int(m.group(2)))
    raise ValueError("Unexpected input: %s", s)

The main function converts the two strings into complex numbers, performs the multiplication, and returns the string in the expected format.

def complex_number(num1: str, num2: str) -> str:
    c1 = to_complex(num1)
    c2 = to_complex(num2)

    result = c1 * c2
    result_real = int(result.real)
    result_imag = int(result.imag)

    return (
        f"{result_real}+{'('+str(result_imag)+')' if result_imag < 0 else result_imag}i"
    )

For the Perl solution, I went old school and performed the multiplication manually.

sub to_complex($s) {
    if ( $s =~ /^(-?\d+)\+(\d+)i$/ ) {
        return $1, $2;
    }
    if ( $s =~ /^(-?\d+)\+\((-\d+)\)i$/ ) {
        return $1, $2;
    }
    die "Unexpected input: $s\n";
}

sub main ( $num1, $num2 ) {
    my ( $r1, $i1 ) = to_complex($num1);
    my ( $r2, $i2 ) = to_complex($num2);

    my $result_real = $r1 * $r2 - $i1 * $i2;
    my $result_imag = $r1 * $i2 + $i1 * $r2;
    if ( $result_imag >= 0 ) {
        say "$result_real+${result_imag}i";
    }
    else {
        say "$result_real+($result_imag)i";
    }
}

Examples

$ ./ch-1.py 1+1i 1+1i
0+2i

$ ./ch-1.py "1+(-1)i" "1+(-1)i"
0+(-2)i

$ ./ch-1.py 0+3i 0+4i
-12+0i

$ ./ch-1.py 3+4i "3+(-4)i"
25+0i

$ ./ch-1.py "50+(-20)i" -10+30i
100+1700i

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

My solution

My solution for this task has a recursive function called find_word_squares, it takes two lists (array in Perl). The first list is called words which has the list of words provided by the user. The second parameter is words_so_far which is a list of words that make up the solution.

I start by setting the words_so_far variable as an empty list on the first call. If a valid solution is found, I return that to the calling function.

def find_word_squares(
    words: list[str], words_so_far: list[str] | None = None
) -> list[str] | None:
    if words_so_far is None:
        words_so_far = []

    length = len(words[0])
    if len(words_so_far) == length:
        return words_so_far

The next step is to find possible next words. For this I generate the starts_with value with the letters the next word must start with. I also exclude any words already used. For each possible word (if any), I call the function again with an update words_so_far value.

    this_pos = len(words_so_far)
    starts_with = "".join(word[this_pos] for word in words_so_far)
    possible_next_words = [
        word
        for word in words
        if word not in words_so_far and word.startswith(starts_with)
    ]

    for word in possible_next_words:
        result = find_word_squares(words, words_so_far + [word])
        if result:
            return result

If no solution is found, I return None.

    return None

The main function checks that all words are the same length and calls the recursive function for the first time.

def word_squares(words: list[str]) -> list[str] | None:
    # Check all words are the same length
    if any(len(word) != len(words[0]) for word in words):
        raise ValueError("All words must be the same length")

    # Call a recursive function to find the correct word order
    return find_word_squares(words)

The Perl solution follows the same logic.

Alternate solution

An alternative option would be to calculate all permutations and see if it is valid. This is relatively inexpensive for the provided examples. There are only 120 permutations of 5 words. However if there were 17 words, that blows out to 355 trillion permutations. My solution still computes a large list quickly.

$ time ./ch-2.py ABC CDE EFG GHI IJK KLM MNO OPQ QRS STU UVW WZY SUN USE NET SEE TEN
['SUN', 'USE', 'NET']

real    0m0.021s
user    0m0.014s
sys 0m0.006s

Examples

$ ./ch-2.py MA AM MY ME
['MA', 'AM']

$ ./ch-2.py SUN USE NET SEE TEN
['SUN', 'USE', 'NET']

$ ./ch-2.py BOAT TEAL AREA TSAR OGRE
['BOAT', 'OGRE', 'AREA', 'TEAL']

$ ./ch-2.py CARD AREA REAR DART
['CARD', 'AREA', 'REAR', 'DART']

$ ./ch-2.py HEART TREND EMBER RESIN ABUSE
['HEART', 'EMBER', 'ABUSE', 'RESIN', 'TREND']