This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions 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:
- ‘a’ can only be followed by ‘e’ and ‘i’.
- ‘e’ can only be followed by ‘i’.
- ‘i’ can only be followed by ‘a’, ‘e’, ‘o’, and ‘u’.
- ‘o’ can only be followed by ‘a’ and ‘u’.
- ‘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.Continue reading “PWC 053 › Vowel Strings”