The Weekly Challenge #395

Task 1: Complex Number

Method Explanation

The challenge specifies a particular string format for complex numbers, including negative components like 1+(-1)i or 50+(-20)i.

1. Parsing: We use regular expressions to extract the real part $a$ and imaginary coefficient $b$. The regex accommodates both positive coefficients (3+4i) and parenthesized negative coefficients (3+(-4)i).
2. Arithmetic: We evaluate: $$\text{Real part} = ac - bd$$ $$\text{Imaginary part} = ad + bc$$
3. Formatting: If the resulting imaginary part is negative, we format it as Real+(-Imag)i, otherwise as Real+Imagi to conform precisely to the test suite format.

Perl Implementation

sub _parse_complex ($s) {
    if ( $s =~ /\A\s*([+-]?\d+)\s*\+\s*(?:\(([-+]?\d+)\)|([-+]?\d+))\s*i\s*\z/ ) {
        my $real = $1;
        my $imag = defined $2 ? $2 : $3;
        return ( int($real), int($imag) );
    }
    die "Invalid complex number format: $s";
}

sub _format_complex ( $real, $imag ) {
    if ( $imag < 0 ) {
        return "$real+($imag)i";
    }
    return "$real+${imag}i";
}

sub multiply_complex ( $num1, $num2 ) {
    ( $num1, $num2 ) = $STRS_CHECK->( $num1, $num2 );

    my ( $a, $b ) = _parse_complex($num1);
    my ( $c, $d ) = _parse_complex($num2);

    my $real = $a * $c - $b * $d;
    my $imag = $a * $d + $b * $c;

    return _format_complex( $real, $imag );
}

Python Implementation

def _parse_complex(s: str) -> tuple[int, int]:
    """Parse complex string in format a+bi or a+(-b)i."""
    match = re.match(r"^\s*([+-]?\d+)\s*\+\s*(?:\(([-+]?\d+)\)|([-+]?\d+))\s*i\s*$", s)
    if not match:
        raise ValueError(f"Invalid complex number format: {s}")
    real_str = match.group(1)
    imag_str = match.group(2) if match.group(2) is not None else match.group(3)
    return int(real_str), int(imag_str)


def _format_complex(real: int, imag: int) -> str:
    """Format complex number to match specification."""
    if imag < 0:
        return f"{real}+({imag})i"
    return f"{real}+{imag}i"


def multiply_complex(num1: str, num2: str) -> str:
    """Multiply two complex numbers and return formatted product."""
    a, b = _parse_complex(num1)
    c, d = _parse_complex(num2)

    real = a * c - b * d
    imag = a * d + b * c

    return _format_complex(real, imag)

Task 2: Word Squares

Method Explanation

An $N \times N$ word square requires that for all $0 \le r, c < N$, the character at grid position $(r, c)$ equals the character at $(c, r)$.

This property gives us an immediate search pruning strategy:

• Suppose we have successfully selected the first $k$ rows of the word square.
• The $(k+1)$-th row must start with the prefix formed by taking column $k$ of the already chosen rows: $$\text{required\_prefix} = \text{grid}[0][k] + \text{grid}[1][k] + \dots + \text{grid}[k-1][k]$$
• By pre-indexing all dictionary words by every possible prefix (using a hash map or Trie), we can instantly filter candidates for row $k$ in $O(1)$ lookup time.
• We use depth-first backtracking to find the first complete square configuration.

Perl Implementation

sub word_squares ($words) {
    ($words) = $WORDS_CHECK->($words);
    return [] if !@$words;

    my $n = length( $words->[0] );
    for my $w (@$words) {
        die 'All words must have the same length' if length($w) != $n;
    }

    my %prefix_map;
    for my $w (@$words) {
        for my $len ( 0 .. $n ) {
            my $p = substr( $w, 0, $len );
            push @{ $prefix_map{$p} }, $w;
        }
    }

    my @current_square;
    my $result;

    my $search;
    $search = sub ($step) {
        return 1 if defined $result;
        if ( $step == $n ) {
            $result = [@current_square];
            return 1;
        }

        my $required_prefix = '';
        for my $row ( 0 .. $step - 1 ) {
            $required_prefix .= substr( $current_square[$row], $step, 1 );
        }

        my $candidates = $prefix_map{$required_prefix} // [];
        for my $word (@$candidates) {
            push @current_square, $word;
            $search->( $step + 1 );
            return 1 if defined $result;
            pop @current_square;
        }
        return 0;
    };

    $search->(0);
    return $result // [];
}

Python Implementation

def word_squares(words: Sequence[str]) -> list[str]:
    """Find an N x N word square from the given words."""
    if not words:
        return []

    n = len(words[0])
    for w in words:
        if len(w) != n:
            raise ValueError("All words must have the same length")

    prefix_map: dict[str, list[str]] = defaultdict(list)
    for w in words:
        for length in range(n + 1):
            prefix_map[w[:length]].append(w)

    current_square: list[str] = []
    result: list[str] | None = None

    def search(step: int) -> bool:
        nonlocal result
        if result is not None:
            return True
        if step == n:
            result = list(current_square)
            return True

        required_prefix = "".join(current_square[row][step] for row in range(step))
        for word in prefix_map.get(required_prefix, []):
            current_square.append(word)
            if search(step + 1):
                return True
            current_square.pop()
        return False

    search(0)
    return result if result is not None else []