RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved run-length encoding and knapsack-style fitting. (Note that this ends today.)

Task 1: String Compression

You are given a string of alphabetic characters, $chars.

Write a script to compress the string with run-length encoding, as shown in the examples.

A compressed unit can be either a single character or a count followed by a character.

BONUS: Write a decompression function.

This is a straightforward encoding: "a" becomes "a", "aa" becomes "2a", and any longer sequence saves space.

Since there will be two places where I can generate a compressed unit from a count and a character, that goes into a function. Perl:

sub compressedunit($count, $letter) {
  my $out = '';
  if ($count > 1) {
    $out .= $count;
  }
  $out .= $letter;
  $out;
}

The compressor:

sub stringcompression($a) {
  my $out = '';
  my $lastchar = '';
  my $count = 0;

Go through one character at a time.

  foreach my $c (split '',$a) {

If it's the first character, or it's a different character…

    if ($count == 0 || $c ne $lastchar) {

If there have been different characters before this, emit them as a compressed unit.

      if ($count > 0) {
        $out .= compressedunit($count, $lastchar);
      }

In any case, set the new character and zero the count.

      $lastchar = $c;
      $count = 0;
    }

Then, whatever we saw, increment the count.

    $count++;
  }

There will be at least one character left at the end of the loop, so emit that compressed unit too.

  if ($count > 0) {
    $out .= compressedunit($count, $lastchar);
  }

And that's a compressed string.

  $out;
}

For decompression, there's an ambiguity: can you have a two-digit length? I assumed yes, because it was more fun to write.

sub stringdecompression($a) {
  my $out = '';
  my $count = 0;

For each character in the input string,

  foreach my $c (split '', $a) {

If it's a number,

    if ($c ge '0' && $c le '9') {

decimal-shift the count left and increment with the number.

      $count *= 10;
      $count += $c;
    } else {

Otherwise it's a letter.

count has to start at zero so that we can do the decimal shift left, so set it to 1 if needed.

      if ($count == 0) {
        $count = 1;
      }

Emit that many copies of the letter. (Every language I'm using has a string repetition function, except for PostScript. But in PostScript I'm using an array of integer characters anyway, and count { c } repeat is nearly as compact anyway.)

      $out .=  $c x $count;

And reset the count to zero for future use.

      $count = 0;
    }
  }
  $out;
}

Task 2: Matchstick Square

You are given an array of integers, @ints.

Write a script to find if it is possible to make one square using the sticks as in the given array @ints where $ints[ì] is the length of ith stick.

This is a Knapsack problem of sorts. and so I cheat a bit. This example is in Ruby.

def matchsticksquare(a)

First see whether the total is divisible by 4, because if not it can't be done.

  perimeter = a.sum
  if perimeter % 4 != 0
    return false
  end

Establish the target side length, and sort the elements long to short.

  side = perimeter / 4
  ss = a.sort.reverse
  sidesleft = 4
  lengthleft = side

Then loop a lot.

  while true do
    leftover = []
    ss.each do |m|

If there's a stick too long to make a side, bail out because this can't work.

      if m > side
        return false
      end

If this stick will fit into the current side, fit it.

      if m <= lengthleft
        lengthleft -= m
        if lengthleft == 0
          sidesleft -= 1
          lengthleft = side
        end

Otherwise put it in the leftovers list.

      else
        leftover.push(m)
      end
    end

If there's anything in the leftovers list, go round and do that again; otherwise leave.

    if leftover.length == 0
      break
    end
    ss = leftover
  end

If all the sticks have filled in the right number of sides of the right length, we have a valid fit.

  sidesleft == 0 && lengthleft == side
end

(Scala and PostScript don't allow early returns from functions, which makes it a bit more fiddly.)

Full code on github.