[ Index | Introduction | Base | Recursion | Loops | Summary | RakuConf ]
We compute each word, and skip those that do not satisfy the succession rule. But here we could speed things up quite a bit.
Let us say that we get at the word BBBB***** (where the
stars can be whatever letter). We have four identical letters in
succession, so can skip the entire sequence until we arrive at
BBBC*****. This is impossible with the base approach,
where we had to generate all the values (with base).
But we can do it with loops. Or recursion...
Recursion is much more show-off-y than mere loops, so let us do that.
File: generate-words-rec
#! /usr/bin/env raku
unit sub MAIN (UInt :a(:$alphabet) where 1 <= $alphabet <= 35 = 0,
UInt :c(:$chars) = 0,
UInt :l(:$limit) = 0,
:v(:$verbose));
die "Set one of chars and limit" if $chars == $limit == 0;
my $count = 0;
my $last-word = "";
my $stopped-by = "";
my @alphabet = (1..9, 'A'..'Z').flat.[^$alphabet]; # [1]
say ": Alphabet: { @alphabet.join(", ") }" if $verbose;
recurse($_) for @alphabet; # [2]
sub recurse ($word-so-far is copy)
{
return if $word-so-far ~~ /(.) {} :my $c=$0; /;
{ $stopped-by = 'chars'; return }
if $chars && $word-so-far.chars > $chars;
{ $stopped-by = 'limit'; return } if $limit && $count >= $limit;
$count++;
say ": Word: $word-so-far (#$count)" if $verbose;
$last-word = $word-so-far;
for @alphabet -> $letter # [3]
{
recurse($word-so-far ~ $letter); # [3a]
}
}
say $limit
?? "$count words (last '$last-word' with length { $last-word.chars } \
stopped by $stopped-by target: \
{ (1000000 * $count/$limit).Int / 10000 }%)"
!! "$count words (last '$last-word' with length { $last-word.chars } \
stopped by $stopped-by)";
[1] Get the alphabet, given the specified length.
[2] This bootstrapping of the recursion (once for each letter) is not neat, but it makes the procedure itself neater.
[3] Add one letter at a time to the current word, recursively.
Note that the order of the words are different with this program. It is depth first (i.e. every word starting with the same letter), before any words starting with the next one:
: Alphabet: 1, 2, 3, 4, 5, 6, 7, 8, 9, A
: Word: 1 (#1)
: Word: 11 (#2)
: Word: 111 (#3)
: Word: 1112 (#4)
: Word: 11121 (#5)
: Word: 111211 (#6)
: Word: 1112111 (#7)
: Word: 11121112 (#8)
: Word: 111211121 (#9)
: Word: 111211122 (#10)
: Word: 111211123 (#11)
: Word: 111211124 (#12)
: Word: 111211125 (#13)
: Word: 111211126 (#14)
: Word: 111211127 (#15)
15 words (last '111211127' with length 9 stopped by limit target: 100%)
The order matter in testing, but not for the end result, where we do not actually care about the words - just the number of them.
We'll have a look at a much faster (we hope) version using 9 nested loops in the next part.
[ Index | Introduction | Base | Recursion | Loops | Summary | RakuConf ]