This is my response to The Weekly Challenge #307.
@ints.
Input: @ints = (5, 2, 4, 3, 1)
Output: (0, 2, 3, 4)
Before: (5, 2, 4, 3, 1)
After : (1, 2, 3, 4, 5)
Difference at indices: (0, 2, 3, 4)
Input: @ints = (1, 2, 1, 1, 3)
Output: (1, 3)
Before: (1, 2, 1, 1, 3)
After : (1, 1, 1, 2, 3)
Difference at indices: (1, 3)
Input: @ints = (3, 1, 3, 2, 3)
Output: (0, 1, 3)
Before: (3, 1, 3, 2, 3)
After : (1, 2, 3, 3, 3)
Difference at indices: (0, 1, 3)
#! /usr/bin/env raku
unit sub MAIN (*@ints where @ints.elems >= 2 && all(@ints) ~~ Int, # [1]
:v(:$verbose));
my @ordered = @ints.sort; # [2]
my @indices; # [3]
for ^@ints.elems -> $index # [4]
{
if @ints[$index] == @ordered[$index] # [5]
{
say ": Index $index: @ints[$index] == @ordered[$index] *" if $verbose;
}
else # [6]
{
@indices.push: $index; # [7]
say ": Index $index: @ints[$index] != @ordered[$index]" if $verbose;
}
}
say "({ @indices.join(", ") })"; # [8]
[1] At least two elements, all of which must be integers.
[2] A sorted copy of the input.
[3] The resulting indices will end up here.
[4] Iterate over the indices of the input array.
[5] Are the sorted value in the original location? (Note that e.g.
(1,1) is the same as 1,1 even if the order may have
changed...) If so, do nothing.
[6] If not,
[7] add the current index to the result.
[8] Pretty print the indices.
Running it:
$ ./check-order 5 2 4 3 1
(0, 2, 3, 4)
$ ./check-order 1 2 1 1 3
(1, 3)
$ ./check-order 3 1 3 2 3
(0, 1, 3)
Looking good.
With verbose mode:
$ ./check-order -v 5 2 4 3 1
: Index 0: 5 != 1
: Index 1: 2 == 2 *
: Index 2: 4 != 3
: Index 3: 3 != 4
: Index 4: 1 != 5
(0, 2, 3, 4)
$ ./check-order -v 1 2 1 1 3
: Index 0: 1 == 1 *
: Index 1: 2 != 1
: Index 2: 1 == 1 *
: Index 3: 1 != 2
: Index 4: 3 == 3 *
(1, 3)
$ ./check-order -v 3 1 3 2 3
: Index 0: 3 != 1
: Index 1: 1 != 2
: Index 2: 3 == 3 *
: Index 3: 2 != 3
: Index 4: 3 == 3 *
(0, 1, 3)
@words.
Input: @words = ("acca", "dog", "god", "perl", "repl")
Output: 3
Step 1: "dog" and "god" are anagrams, so dropping "dog" and keeping
"god" => ("acca", "god", "perl", "repl")
Step 2: "perl" and "repl" are anagrams, so dropping "perl" and keeping
"repl" => ("acca", "god", "repl")
Input: @words = ("abba", "baba", "aabb", "ab", "ab")
Output: 2
Step 1: "abba" and "baba" are anagrams, so dropping "abba" and keeping
"baba" => ("baba", "aabb", "ab", "ab")
Step 2: "baba" and "aabb" are anagrams, so dropping "baba" and keeping
"aabb" => ("aabb", "ab", "ab")
Step 3: "ab" and "ab" are anagrams, so dropping "ab" and keeping
"ab" => ("aabb", "ab")
Finding anagrams is tedious, but finding out if two strings are anagrams of each other is much easier; just sort the letters in the two strings alphabetically and compare the result. (I presented this canonical form in part 2 of my United States of Anagrams article series.)
File: find-anagrams
#! /usr/bin/env raku
unit sub MAIN (*@words where @words.elems > 0, :v(:$verbose)); # [1]
my %canonical; # [2]
@words.map({ %canonical{$_} = $_.lc.comb.sort.join }); # [3]
@words.map({ say ": Canonical of: $_ -> %canonical{$_}" }) if $verbose;
my $index = 0; # [4]
loop # [5]
{
last if @words.elems == 0; # [6]
last if @words.end == $index; # [7]
if %canonical{@words[$index + 0]} eq %canonical{@words[$index + 1]} # [8]
{
print ": Dropping @words[$index + 0] (index $index)" if $verbose;
@words.splice($index,1); # [9]
say " -> ({ @words.join(",") })" if $verbose;
}
else # [10]
{
$index++; # [10a]
}
}
say @words.elems; # [11]
[1] At least one word.
[2] Mapping between words and their canonical form.
[3] Set up the canonical mapping. Note the ls so
that any uppercase letter will be lowered.
See docs.raku.org/routine/lc for more information about lc.
[4] The current location, starting at the very first.
[5] As long as,
[6] • we have more elements in the array.
[7] • we have not reached the end.
[8] Are the word at the current location and the next one anagrams? If so,
[9] • Remove the first word (with splice).
See docs.raku.org/routine/splice for more information about splice.
[10] If not, advance the location one step to the right.
[11] Print the number of remaining words.
Running it:
$ ./find-anagrams acca dog god perl repl
3
$ ./find-anagrams abba baba aabb ab ab
2
Looking good.
With verbose mode:
$ ./find-anagrams -v acca dog god perl repl
: Canonical of: acca -> aacc
: Canonical of: dog -> dgo
: Canonical of: god -> dgo
: Canonical of: perl -> elpr
: Canonical of: repl -> elpr
: Dropping dog (index 1) -> (acca,god,perl,repl)
: Dropping perl (index 2) -> (acca,god,repl)
3
$ ./find-anagrams -v abba baba aabb ab ab
: Canonical of: abba -> aabb
: Canonical of: baba -> aabb
: Canonical of: aabb -> aabb
: Canonical of: ab -> ab
: Canonical of: ab -> ab
: Dropping abba (index 0) -> (baba,aabb,ab,ab)
: Dropping baba (index 0) -> (aabb,ab,ab)
: Dropping ab (index 1) -> (aabb,ab)
2
And that's it.