RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a string decompression and permutations. (Note that this ends today.)

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.

This is a job for regular expressions! But constructing the replacement is a little fiddly.

In Perl:

sub decodestring($a) {

This is the core of it. This regexp will match an inner block, i.e. a K[x] where x contains no further replacement elements.

  while ($a =~ /(([0-9]+)\[([^\[\]]*)\])/) {

We have a match. So extract orig, the full text of the match, ct, the count, and rep, the unit to be repeated.

    my $orig = $1;
    my $ct = $2;
    my $rep = $3;

Build dest, the repeated unit, and note the length of orig.

    my $dest = $rep x $ct;
    my $l = length($orig);

While we can find orig in the string, replace it with dest. (This doesn't need to be a regexp any more.)

    while (1) {
      my $ix = index($a, $orig);
      if ($ix == -1) {
        last;
      } else {
        substr($a, $ix, $l) = $dest;
      }
    }

And then try again, until the regexp doesn't match.

  }
  $a;
}

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.

Sadly this is a bit simpler than it looks. If k == 1 then it's a rotation of the string; if k > 1 then it's the characters of the string in order. But I pretended I didn't know that so as to have an excuse to use a data structure I don't often employ.

In Rust:

use std::collections::BTreeSet;

fn ordercharacters(a: &str, k: usize) -> String {

Split the string into a list of characters. That's what I'll be working with internally.

    let cc = a.chars().collect::<Vec<char>>();

Initialise the stack.

    let mut stack = Vec::new();
    stack.push(cc.clone());

Initialise the list of combinations we've seen.

    let mut seen = BTreeSet::new();

Standard DFS pattern, pop off the top of the stack…

    while let Some(s) = stack.pop() {

and iterate over the possible transformations of it.

        for i in 0 .. k {
            let mut sp = s.clone();
            let c = sp.remove(i);
            sp.push(c);

If it's a result we haven't seen before, store it, and push it onto the stack for further transformation.

            if !seen.contains(&sp) {
                seen.insert(sp.clone());
                stack.push(sp);
            }
        }
    }

And here's where it gets cunning, because the BTreeSet guarantees that all the entries are in sorted order. So all I need to do is to take the first one, convert it back into a string, and return it.

    seen.into_iter().nth(0).unwrap().into_iter().collect()
}

In PostScript I don't have a BTreeSet. (Though I should learn how they work and write one.)

/ordercharacters {
    0 dict begin

Store k and initialise the stack. (I don't need to keep the initial string around after that.)

    /k exch def
    dup length /l exch def
    /stack exch
    [ exch
    ] def

Initialise the seen list, just a plain dict which I'll use as a set.

    /seen 0 dict def

Usual DFS loop.

    {
        stack length 0 eq {
            exit
        } if
        /stack stack apop.right /s exch def def

Iterate over the possible transformations of this string.

        0 1 k 1 sub {
            /i exch def

Convert the string to an array (which makes a fresh copy of it)

            s s2a

Move that arracy onto the stack.

            aload pop

Transform it.

            l i sub -1 roll

Pack it up into an array again, and convert that into a string.

            l array astore a2s
            /sn exch def

If we haven't seen it, store it, as above in the Rust code.

            seen sn known not {
                seen sn 1 put
                /stack stack sn apush.right def
            } if
        } for
    } loop

Now I have a dict with all the available permutations. But string keys in dicts are automatically converted to names. So I'll get out the keys.

    seen keys

Convert them all to strings (we know the length in advance, which makes life easy)

    { l string cvs } map

Sort them.

    quicksort

And return the first one.

    0 get
    end
} bind def

Full code in all tagged languages is on codeberg.