RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string parsing and reassembly, and word squares. (Note that this ends today.)

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

Amusingly, Typst stringifies negative integers with U+2212 MINUS SIGN rather than U+002D HYPHEN-MINUS, which while technically correct (and indeed what I'd want it to do when typesetting) isn't what everything else expects.

The first part of this is a parser function, for which I used regexps where available (everywhere except Lua and PostScript). In Perl:

sub parsecomplex($a) {
    if ($a =~ /^\(?([-0-9]+)\)?\+\(?([-0-9]+)\)?i$/) {
        [$1 + 0, $2 + 0];
    } else {
        [0, 0];
    }
}

Then get the numbers:

sub complexnumber($aa, $bb) {
    my ($a, $b) = @{parsecomplex($aa)};
    my ($c, $d) = @{parsecomplex($bb)};

Calculate the new ones:

    my $ca = $a *$c - $b * $d;
    my $cb = $a *$d + $b * $c;

And format the output string (parentheses round a negative imaginary part).

    if ($cb < 0) {
        $cb = "($cb)";
    }
    "$ca+${cb}i";
}

Lua's patterns are almost regular expressions, but PostScript was more of a challenge:

Parse just one term (with optional parentheses and "i"):

/parseone {
    0 dict begin

Get the string.

    /a exch def

If there's an open-paren, keep only everything after it.

    a (\() search {
        pop
        pop
        /a exch def
    } {
        pop
    } ifelse

If there's a close-paren, keep only everything before it.

    a (\)) search {
        /a exch def
        pop
        pop
    } {
        pop
    } ifelse

If there's an "i", keep only everything before it.

    a (i) search {
        /a exch def
        pop
        pop
    } {
        pop
    } ifelse

Turn what's left into an integer. (And this is why we like regular expressions.)

    a cvi
} bind def

Now to parse the composite term:

/parsecomplex {

Split on the "+" sign and put the components on the stack.

    (+) strsplit
    aload pop

Parse each of them.

    parseone
    exch
    parseone
    exch

Put them into an array.

    2 array astore
} bind def

By the time we get here the code looks almost familiar.

/complexnumber {
    0 dict begin

Parse each term into its constituent variables.

    parsecomplex
    aload pop
    /d exch def
    /c exch def
    parsecomplex
    aload pop
    /b exch def
    /a exch def

Do the calculation.

    /ca a c mul b d mul sub def
    /cb a d mul b c mul add def

Build up the output string bit by bit.

    ca alloccvs
    (+) strconcat
    cb 0 lt {
        (\() strconcat
    } if
    cb alloccvs strconcat
    cb 0 lt {
        (\)) strconcat
    } if
    (i) strconcat
    end
} bind def

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.

This was surprisingly easy with a BFS. In Typst:

#let wordsquares(a) = {

Store the word length for later comparison.

  let l = a.at(0).len()

Build a set of words.

  let words = a.map(w => (w, true)).to-dict()

Set up the queue with each word in a list on its own.

  let queue = ()
  for w in a {
    queue.push((w,))
  }
  let ret = []

Standard BFS scaffolding.

  while queue.len() > 0 {
    let p = queue.remove(0)

If we have enough words, return the result. (If there are multiple possible results it'll return one of them.)

    if p.len() == l {
      ret = p
      break
    }

Check each word that hasn't already been used.

    let pd = p.map(w => (w, true)).to-dict()
    for ca in words.keys() {
      if not(ca in pd) {

Check each character in that word.

        let valid = true
        for (i, c) in ca.clusters().enumerate() {

If we've gone beyond the characters defined by previous entries, drop out.

          if i >= p.len() {
            break
          }

If the i-th word's character in the right spot doesn't match this word's i-th character, this can't be the next word in the square.

          if c != p.at(i).at(p.len()) {
            valid = false
            break
          }
        }

If the word was valid, build another queue entry.

        if valid {
          let pw = p
          pw.push(ca)
          queue.push(pw)
        } 
     }
    }
  }
  ret
}

Full code in all tagged languages is on codeberg.