PWC 053 › Vowel Strings

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week has us construct “vowel strings,” as described by Mohammad:

Write a script to accept an integer 1 ≤ N ≤ 5 that would print all possible strings of size N formed by using only vowels (a, e, i, o, u).

The string should follow the following rules:

1. ‘a’ can only be followed by ‘e’ and ‘i’.
2. ‘e’ can only be followed by ‘i’.
3. ‘i’ can only be followed by ‘a’, ‘e’, ‘o’, and ‘u’.
4. ‘o’ can only be followed by ‘a’ and ‘u’.
5. ‘u’ can only be followed by ‘o’ and ‘e’. [Note this set is not in lexical order -RJT]

This is a task tailor made for breadth first search (BFS). If you notice, each of the “rules” is essentially an edge in a directed graph, and the nodes are the vowels, a e i o u. We can use BFS to traverse the graph from five different starting points (each vowel), and explore every path of length N, and that will give us our strings.

Perl

First, let’s set up our edges in a hash, where the key is the current node, and the value is an array ref of nodes we can go to from that current node:

my %edges = ( a => ['i','e'],  e => ['i'],    i => ['u','o','e','a'],
              o => ['u','a'],  u => ['e','o'] );

I reversed the order of the vowels in the arrays, because I’m going to use for and push together, which reverses the order again. This way the output won’t need sorting.

Now I will show you a couple of different ways to structure the solution.

Looping

For this, we simply maintain a queue, initialize it with all of the vowels (those are our starting nodes), and then keep looping, following the %edges as we go, and build up the result in @vstrs:

sub vowel_string {
    my ($len) = @_;
    my @queue = sort keys %edges; # Pre-load queue

    my @vstrs;
    while (my $str = shift @queue) {
        push @vstrs, $str    and next if $len <= length $str;
        push @queue, $str.$_ for @{$edges{ substr $str, -1 }}
    }
    @vstrs;
}

This is a perfectly fine approach, and may be preferable in certain scenarios. However, there is another option: an iterator.

Iterator

You can make an effective iterator by returning a closure around some data. The caller then repeatedly calls that sub reference to get the next element in sequence. (For more information on closures, I refer you to perlfaq7, and I may do a blog post on them in the future.)

Here is the iterator version:

sub vowel_iter {
    my ($len) = @_;
    my @queue = sort keys %edges;
    sub {
        while (my $str = shift @queue) {
            return $str if $len <= length $str;
            push @queue, $str.$_ for @{$edges{ substr $str, -1 }}
        }
    }
}

Here is how each of these functions would be used to print out the N=4 vowel strings:

say for vowel_string(4);

my $it = vowel_iter(4);
say while $_ = $it->();

Whether you use the iterator version not would really depend on the problem you are trying to solve, and what you are trying to optimize. For example, I would tend towards the iterator version if N was large or I knew I did not need the entire result set. On the other hand, I’d use the looping version if I knew I was going to stuff everything in an array anyway, or refer to elements out of order.

Raku

Our edges can be specified more concisely and cleanly in Raku:

my %next = :a<e i>, :e<i>, :i<a e o u>, :o<a u>, :u<o e>;

I’ll just implement the iterator version in Raku (the other version has the same basic internals anyway):

sub vowel-string-iter( Int $len where $len > 0 ) {
    my @queue = %next.keys.sort;
    sub {
        while (my $str = @queue.shift) {
            return $str if $str.chars ≥ $len;
            @queue.push: |$str «~« %edges{ $str.substr(*-1) };
        }
    }
}

Of note here is the «~« hyper-operator on line 16. That line could have been written:

            @queue.push: $str~$_ for |%edges{ $str.substr(*-1) };

The hyper-operator is good practice, here, as Raku may parallelize it (not worth it with such small lists, but in general this can make a big difference), yet the results are always returned in order. (With for, the partial results would have been in reverse order, which is manageable, but annoying.)