RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved manipulations of word lists. (Note that this ends today.)

Task 1: Replace Words

You are given an array of words and a sentence.

Write a script to replace all words in the given sentence that start with any of the words in the given array.

This feels like a tour of language features more than a problem to solve: split a string to words, find matching starts, assemble a list of words to a string. So that could be done fairly conventionally in Kotlin:

fun replacewords(ww: List<String>, a: String): String {
    var out = ArrayList<String>()
    for (w in a.split(" ")) {
        var r = false
        for (lw in ww) {
            if (w.startsWith(lw)) {
                out.add(lw)
                r = true
                break
            }
        }
        if (!r) {
            out.add(w)
        }
    }
    return out.joinToString(" ")
}

or more amusingly (to me) in PostScript:

/replacewords {
    0 dict begin
    exch
    /ww exch def
    [ exch
      ( ) strsplit {
          /w exch def
          /r false def
          ww {
              /lw exch def
              w lw anchorsearch {
                  pop pop
                  lw
                  /r true def
                  exit
              } {
                  pop
              } ifelse
          } forall
          r not {
              w
          } if
      } forall
    ] ( ) strjoin
    end
} bind def

Task 2: Word Search

You are given a grid of characters and a string.

Write a script to determine whether the given string can be found in the given grid of characters. You may start anywhere and take any orthogonal path, but may not reuse a grid cell.

Something I've been playing with recently is to use a hash for grid traversal problems, rather than a list of lists. That way I just need to check whether a neighbour cell exists rather than worry about boundary conditions.

For languages that don't have a hashable sequence type (most of them), I arbitrarily decide that the grid won't exceed 64 cells in row length.

Perl:

sub encode($x, $y) {
    return $x * 64 + $y;
}

sub decode($z) {
    return [int($z / 64), $z % 64];
}

Construct the coordinate grid of characters.

sub wordsearch($grid0, $word0) {
  my %grid;
  while (my ($y, $row) = each @{$grid0}) {
    while (my ($x, $c) = each @{$row}) {
      $grid{encode($x, $y)} = $c;
    }
  }

Split the target word into an array of characters.

  my @word = split '', $word0;

Iterate over each grid cell as a starting point.

  while (my ($start, $firstletter) = each %grid) {

If it has the right letter, let's look deeper.

    if ($firstletter eq $word[0]) {

Initialise the queue.

      my @queue = ([$start]);
      while (scalar @queue > 0) {
        my @pos = @{shift @queue};
        if (scalar @pos == scalar @word) {

If we've found the full length of the word, we have a success.

          return 1;
        } else {

Try in each orthogonal direction.

          foreach my $dir ([0, 1], [1, 0], [0, -1], [-1, 0]) {
            my $lpos = decode($pos[-1]);
            my $npos = [$lpos->[0] + $dir->[0], $lpos->[1] + $dir->[1]];
            my $np = encode(@{$npos});
            my %posmap = map {$_ => 1} @pos;

If there is a grid cell there, and it's a grid cell that we haven't already visited in this word, and it has the right letter in it, add it to the queue.

            if (exists $grid{$np} &&
                !exists $posmap{$np} &&
                $grid{$np} eq $word[scalar @pos]) {
              push @queue, [@pos, $np];
            }
          }
        }
      }
    }
  }

If we exhausted all possibilities, return false.

  0;
}

Full code on github.