| 11 September 2026 | Challenge 390 |
Decoded Permutations
Task 1: Decode String
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: $str = "2[3[a]]"
Output: "aaaaaa"
3[a] => aaa
2[3[a]] => aaa aaa
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"
Solution
This task is similar to task 2 from week 387.
Identify inner encoded strings, decode these and proceed until all are resolved.
Perl
use strict;
use warnings;
use experimental 'signatures';
sub decode_string ($str) {
1 while $str =~ s/(\d+)\[([^][]+)\]/$2 x $1/ge;
$str;
}
See the full solution to task 1.
J
rxapply is similar to Perl’s s///er.
Need an extra match to access the capture groups, though.
NB. decode (nested) strings in the format 'K[str]'
decode_str =: _(adverb define)
NB. matches inner encodings, capturing K and string
rh =. rxcomp '(\d+)\[([^][]+)\]'
NB. - convert x to numeric
NB. - repeat y x-times
NB. - remove boxing
repeat =. ;@(".@>@[ # ])
NB. match K and str and apply "repeat" between them
decode =. [: repeat/ ] rxfrom~ (rh; 1 2) rxmatch ]
NB. find inner encodings and decode until all are resolved
NB. "f:" requires J9.8, which is still beta!
rh&(decode rxapply)^:_ f: 'private' : [:
)
decode_str '1[a]2[b3[c]]'
abcccbccc
See the full solution.
Task 2: Order Characters
Submitted by: Mohammad Sajid Anwar
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.
Example 1
Input: $str = "dbca", $k = 1
Output: "adbc"
Move 1: "bcad"
Move 2: "cadb"
Move 3: "adbc"
Example 2
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"
Example 3
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")
Example 4
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")
Example 5
Input: $str = "perl", $k = 1
Output: "erlp"
Move 1: "erlp" (move "p")
Example 6
Input: $str = "oloolooo", $k = 1
Output: "looloooo"
Example 7
Input: $str = "oloooolo", $k = 1
Output: "looloooo"
Solution
\(k\) defines a set of valid moves, where a move is a permutation. In my understanding, the aim of this task is to find the lexicographically smallest string that can be generated by applying any number of valid permutations in any order to the origin string.
The characters of a string arranged in ascending order form the lexicographically smallest string made of these characters. When the length \(n\) of the string is less than three, the task is trivial. One or two characters can always be brought into ascending order regardless of \(k\).
Therefore in the following the string shall have a length of at least three.
Let us distinguish between an arrangement of a (multi-)set’s elements, which shall be an (ordered) \(n\)-tuple of all elements of the (multi-)set, and a permutation, which is a function.
A permutation may be applied to any \(n\)-tuple and produces an arrangement if applied to an arrangement.
If the base object of the arrangements is a set, then every ordered pair of arrangements defines a unique permutation. Furthermore, every permutation may be represented by a pair of arrangements, though this representation is not unique.
In case of a true multi-set, the above is not true: A pair of arrangements does not define a unique permutation and not every permutation can be represented as a pair of arrangements. However, for every pair of arrangements there exists a permutation that transforms one into the other.
These considerations are useful because a string may be regarded as an arrangement of a multi-set.
Case 1: \(k = 1\):
The only operation in this case is a (left) rotation of the string by moving the first character to the end of the string.
This corresponds to the permutation \(\sigma_1 = (n \, 1 \, 2 \cdots n - 1)\) in cycle notation.
After \(n\) rotations, the original string is recovered. We need to find the lexicographically smallest from the string itself and all its rotations, which are \(n\) strings in total.
Case 2: \(k > 1\):
In addition to \(\sigma_1\), we consider moving the second character to the end.
This corresponds to the permutation \(\sigma_2 = (n \, 2 \cdots n - 1)\) in cycle notation.
It can be shown that the subgroup of permutations generated from \(\sigma_1\) and \(\sigma_2\) span the complete symmetric group \(S_n\):
Consider an arbitrary permutation \(\sigma^* \in S_n\) with a representation by the arrangements \(p = (p_1,\cdots,p_n)\) and \(q\) of a set with \(n\) elements such that \(p = \sigma^* \, q\).
Starting with \(q\).
We will show, that the subsequence \(p_1,\cdots,p_i\) can be generated by applying \(\sigma_1\) and \(\sigma_2\) on an arrangement containing the subsequence \(p_1,\cdots,p_{i-1}\).
Choosing \(i\), \(1 < i < n\) and suppose we have an arrangement that contains the sequence \(p_1,\cdots,p_{i-1}\) of length \(i - 1\) as a subsequence. This is trivially satisfied for \(i = 2\) as the starting arrangement \(q\) must contain the “sequence” \(p_1\).
We may repeatedly apply \(\sigma_1\) until \(p_i\) is at position \(1\), while the sequence \(p_1,\cdots,p_{i-1}\) is preserved: \((p_i,\ldots,p_1,\cdots,p_{i-1},\ldots)\)
Now we may repeatedly apply \(\sigma_2\) until \(p_{i-1}\) is at position \(n\), preserving the sequence \(p_1,\cdots,p_{i-1}\) and keeping \(p_i\) at position \(1\): \((p_i,\ldots,p_1,\cdots,p_{i-1})\)
Then applying \(\sigma_1\) results in: \((\ldots,p_1,\cdots,p_{i-1},p_i)\), i.e. the subsequence \(p_1,\cdots,p_i\) of length \(i\) has been created from the subsequence of length \(i - 1\).
This process may be repeated while \(i < n\). After the last process step there is only one free slot left for \(p_n\) at position \(1\): \((p_n,p_1,\cdots,p_{n-1})\). A final application of \(\sigma_1\) produces the desired result \((p_1,\cdots,p_n)\).
This proves that an arbitrary permutation \(\sigma^* \in S_n\) can be generated by \(\sigma_1\) and \(\sigma_2\).
Result
As any arrangement can be produced by applying permitted moves, we may choose the arrangement where the characters of the given string are in ascending order.
This is the lexicographically smallest possible string.
Therefore the string formed by the sorted characters of the origin string is the result for \(k > 1\).
As the sequence of moves is not required in the output, we may just present the known result without actually performing any moves when \(k > 1\).
Perl
For \(k = 1\):
PDL comes with a
rotate method that comes handy for this task,
but it lacks a method that finds the lexicographically smallest vector.
Taking the first element from the sorted vectors as a workaround.
For \(k > 1\):
Sort the characters.
use strict;
use warnings;
use experimental 'signatures';
use PDL;
use PDL::Char;
sub order_characters ($str, $k) {
my $s = PDL::Char->new($str);
($k > 1 ? $s->qsort : $s->rotate(sequence $s->indx)->qsortvec)->atstr(0);
}
See the full solution to task 2.
J
J has a primitive verb (|.) to rotate a list, too.
And neither does it have a predefined verb to find the lexicographically smallest element.
Again, taking the first from the sorted elements as a workaround.
NB. find lexicographically smallest result
NB. of applying permitted moves specified by x on y
order_characters =: _(adverb define)
NB. find the lexicographically smallest from
NB. all rotations of y
min_rot =. [: {. [: /:~ i.@# |."0 _ ]
NB. if x > 1: sort y
NB. otherwise apply "min_rot"
[: : ((min_rot@])`(/:~@])@.(1&<@[) f.)
)
3 order_characters 'cbaed'
abcde
1 order_characters 'oloooolo'
looloooo
See the full solution.