Perl Weekly Challenge 390‘s tasks are “Decode String” and “Order Characters”.
Remember back in April, when PWC 369 had a task “Group Division”, and that made me think of the group Joy Division? Yeah, well “Order Characters” made me think of New Order, which is the band Joy Division turned into. So while we’re enjoying this coding challenge, enjoy all seven and a half minutes of Blue Monday.
Task 1: Decode String
You are given an encoded string.
Write a script to return the decoded string of the given encoded string.
The encoding rule is: K[encoded_string], where the encoded_string inside the square brackets is repeated exactly K > 0 times.
Input: $str = "2[3[a]]"
Output: "aaaaaa"
3[a] => aaa
2[3[a]] => aaa aaaInput: $str = "10[a]"
Output: "aaaaaaaaaa"Input: $str = "a2[b]c3[d]e"
Output: "abbcddde"Input: $str = "2[a2[b]c]"
Output: "abbcabbc"Input: $str = "1[a]2[b3[c]]"
Output: "abcccbccc"Approach
This is very much like PWC 387’s task 2, where we had to expand atoms in order to count them; the big difference here is we don’t have to count up the letters once we’ve expanded them. We just have to expand the K[string] notations until there aren’t any more.
Like with PWC 387, I’m going to use regular expressions to do that.
Raku
One of the things I had forgotten about Raku: if I’m interpolating a string $m into a regular expression, it does not interpret it as a regular expression. If I wanted to interpret it as a regular expression, I would have to interpolate <$m> into the regular expression. So unlike the Perl solution, I don’t have to do anything special to make sure 3[a] isn’t interpreted as a regular expression in line 10.
sub decodeString($str is copy) {
while (my $match = $str ~~ m:g/(\d+)\[(<-[\[\]]>+)\]/) {
for $match.list -> $m {
my $r = $m[1] x $m[0];
$str ~~ s/$m/$r/;
}
}
$str
}View the entire Raku script for this task on GitHub.
$ raku/ch-1.raku
Example 1:
Input: $str = "2[3[a]]"
Output: "aaaaaa"
Example 2:
Input: $str = "10[a]"
Output: "aaaaaaaaaa"
Example 3:
Input: $str = "a2[b]c3[d]e"
Output: "abbcddde"
Example 4:
Input: $str = "2[a2[b]c]"
Output: "abbcabbc"
Example 5:
Input: $str = "1[a]2[b3[c]]"
Output: "abcccbccc"Perl
However, in Perl I definitely had to take an extra step to make sure 3[a] isn’t interpreted as a regular expression; that’s what the quotemeta call is doing.
sub decodeString($str) {
while ($str =~ m/((\d+)\[([^\[\]]+)\])/) {
my $r = $3 x $2;
my $m = quotemeta($1);
$str =~ s/$m/$r/;
}
$str
}View the entire Perl script for this task on GitHub.
Python
In Python, string repetition is done using *, and I have to assign the search results to a match variable and then use .group to extract the different capture groups.
import re
def decode_string(string):
while match := re.search(r'((\d+)\[([^\[\]]+)\])', string):
r = match.group(3) * int(match.group(2))
string = string.replace(match.group(1), r)
return stringView the entire Python script for this task on GitHub.
Elixir
Again, because the loop is unbounded (I’m repeating until the regex doesn’t match any results), I’m using recursion to do the looping in Elixir.
@k_notation ~r/((\d+)\[([^\[\]]+)\])/
def decode_string(str) do
if Regex.match?(@k_notation, str) do
[m, k, s] = Regex.run(@k_notation, str,
capture: :all_but_first)
r = String.duplicate(s, String.to_integer(k))
decode_string(String.replace(str, m, r))
else
str
end
endView the entire Elixir script for this task on GitHub.
Task 2: Order Characters
You are given a string $s (containing only alphabetic characters) and an integer $k > 0.
Write a script to choose one of the first $k letters of given string and append it at the end of the string. You keep doing this until you have lexicographically smallest string and return the string.
Input: $str = "dbca", $k = 1
Output: "adbc"
Move 1: "bcad"
Move 2: "cadb"
Move 3: "adbc"Input: $str = "geeks", $k = 2
Output: "eegks"
First 2 letters: "g", "e"
Move 1: "gekse" (move second letter "e")
Move 2: "gksee" (move second letter "e")
Move 3: "kseeg"
Move 4: "seegk"
Move 5: "eegks"Input: $str = "cbaed", $k = 3
Output: "abcde"
First 3 letters: "c", "b", "a"
Move 1: "cbeda" (move "a")
Move 2: "cedab" (move "b")
Move 3: "edabc" (move "c")
Move 4: "eabcd" (move "d")
Move 5: "abcde" (move "e")Input: $str = "fedcba", $k = 4
Output: "abcdef"
First 4 letters: "f", "e", "d", "c"
Move 1: "fdcbae" (move "e")
Move 2: "dcbaef" (move "f")
Move 3: "dcbefa" (move "a")
Move 4: "dcefab" (move "b")
Move 5: "defabc" (move "c")
Move 6: "efabcd" (move "d")
Move 7: "fabcde" (move "e")
Move 8: "abcdef" (move "f")Input: $str = "perl", $k = 1
Output: "erlp"
Move 1: "erlp" (move "p")Input: $str = "oloolooo", $k = 1
Output: "looloooo"Input: $str = "oloooolo", $k = 1
Output: "looloooo"Approach
I think the best way to do this is to walk the tree of different strings that can be produced by this, keeping a hash of results we’ve seen already so we don’t endless traverse down the tree, and then just sort the keys and take the first result.
Since there’s a possibility of deep recursion, I implemented the tree walking algorithm as a loop with a stack of possibilities. We start out with the %seen hash pre-populated with the starting string, and @stack initialized with the starting string. Then we loop while there are strings in the stack, and for each string, we generate new strings for each character we’re pulling out of the source string from 0 to $k-1. If the new string isn’t one we’ve seen already, we push it on @stack and move on to the next step.
Raku
sub orderCharacters($str is copy, $k) {
my %seen = ($str => 1);
my @stack = ($str);
while ($str = @stack.shift) {
for (0 .. $k-1) -> $i {
my $char = $str.substr($i,1);
my $new = $str.substr(0..$i-1)~$str.substr($i+1)~$char;
next if %seen{$new}:exists;
%seen{$new}++;
@stack.push($new);
}
}
return %seen.keys.sort.head;
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1:
Input: $str = "dbca", $k = 1
Output: "adbc"
Example 2:
Input: $str = "geeks", $k = 2
Output: "eegks"
Example 3:
Input: $str = "cbaed", $k = 3
Output: "abcde"
Example 4:
Input: $str = "fedcba", $k = 4
Output: "abcdef"
Example 5:
Input: $str = "perl", $k = 1
Output: "erlp"
Example 6:
Input: $str = "oloolooo", $k = 1
Output: "looloooo"
Example 7:
Input: $str = "oloooolo", $k = 1
Output: "looloooo"Perl
sub orderCharacters($str, $k) {
my %seen = ($str => 1);
my @stack = ($str);
while ($str = shift @stack) {
for my $i (0 .. $k-1) {
my $char = substr($str,$i,1);
my $new = substr($str,0,$i) . substr($str,$i+1) . $char;
next if exists $seen{$new};
$seen{$new}++;
push @stack, $new;
}
}
return (sort keys %seen)[0];
}View the entire Perl script for this task on GitHub.
Python
In Python, rather than use a dict, I made seen a list, because we can use new not in seen to check to see if a string new is in the list seen just as easily as checking a dict key for existence.
def order_characters(string, k):
seen = [string]
stack = [string]
while stack:
string = stack.pop(0)
for i in range(0, k):
char = string[i:i+1]
new = string[0:i] + string[i+1:] + char
if new not in seen:
seen.append(new)
stack.append(new)
return sorted(seen)[0]View the entire Python script for this task on GitHub.
Elixir
But in Elixir, I had to use recursion because the loop is unbounded. But we’re still passing a stack to the recursive call, so it’s similar to the other implementations.
def order_characters([], _, seen), do: seen
def order_characters([str | stack], k, seen) do
Enum.reduce(0..k-1, seen, fn i, seen ->
char = String.slice(str, i, 1)
new = String.slice(str, 0, i)
<> String.slice(str, i+1, String.length(str))
<> char
if not Map.has_key?(seen, new) do
order_characters(
stack ++ [new], k, Map.put(seen, new, 1)
)
else
seen
end
end)
end
def order_characters(str, k) do
order_characters([str], k, Map.put(%{}, str, 1))
|> Map.keys |> Enum.sort |> List.first
endView the entire Elixir script for this task on GitHub.
Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-390-packy-anderson/challenge-390/packy-anderson