Reverse order of words in a string inplace The Task


You are given a mutable string that matches [a-z]+( [a-z]+)*.
You must mutate it into the string which contains the same words, but in reverse order, so that "hello there everyone" becomes "everyone there hello".
You are not permitted to use more than a constant amount of additional memory (so no copying the entire string or any whole word into a buffer you just allocated).
There are no time constraints. Being hopelessly inefficient will not harm your score.
If your language of choice does not permit mutation of strings, arrays of characters are an acceptable substitute.


Your Score


Your score is counted purely on the number of assigments you make to string elements (small scores are best). If you use a library function that writes to the string, its writes also count.
Suppose the number of assignments you need for input s is n(s). Then your score is the maximum (pedantically, supremum) over all inputs s (matching the regex specified above) of n(s)/length(s). If you cannot calculate this precisely, you can use the lowest upper bound that you can prove.
You can break a tie if you can prove that your algorithm uses asymptotically fewer assignments (this can happen even if you have the same score, see below). If you can't do this, you can break a tie by showing that you use less additional memory. However, the first tie-break condition always takes precedence.
For some inputs every character needs to change, so it is not possible to score less than 1.
I can think of a simple algorithm with score 2 (but I'm not entering it).


Notes on suprema and ties


A supremum of a set of numbers is the smallest number that is not smaller than any of them. This is much like the maximum of a set, except that some infinite sets like {2/3, 3/4, 4/5, 5/6, ...} have no single maximum element, but will still have a supremum, in this case 1.
If you manage to "save" only a constant number of assignments over my algorithm of score 2 (say), your score will still be 2, because you'll get arbitrarily close to 2 the larger your input gets. However, you win on the tie-break if it comes to that.
Perl, score 1.3&#x0305;

For each non-space character one assignment is performed, and for each space character two assignments. Because space characters cannot amount to more than one half the total number of characters, the worst case score is 1.5.

The algorithm hasn't changed, but I can prove a lower upper bound. Let us make two observations:


Spaces directly across from spaces do not need to be swapped.
Single character words directly across from spaces are not swapped during the main phase, but only once at the end.


It can then be seen that the theoretical 'worst case' with asymptotically 1/2 spaces is not worst case at all: ab c d e f g h i ...

$ echo ab c d e f g h i j k l m n o p q r s t u v w x y z|perl reverse-inplace.pl
z y x w v u t s r q p o n m l k j i h g f e d c ab
swaps: 51; len: 50
ratio: 1.02


In fact, it's quite a good case.

In order to prevent observation one and two above, each one-character word would need to be repositioned into the middle of a word three or more characters long. This would suggest a worst case containing asymptotically 1/3 spaces: a bcd a bcd a ... bc 

$ echo a bcd a bcd a bcd a bcd a bcd a bc|perl reverse-inplace.pl
bc a bcd a bcd a bcd a bcd a bcd a
swaps: 45; len: 34
ratio: 1.32352941176471


Or equivalently, only two-character words: a bc de fg hi jk ...

$ echo a bc de fg hi jk lm no pq rs tu vx xy|perl reverse-inplace.pl
xy vx tu rs pq no lm jk hi fg de bc a
swaps: 49; len: 37
ratio: 1.32432432432432


Because the worst case contains asymptotically 1/3 spaces, the worst case score becomes 1.3&#x0305;.



#!perl -l
use warnings;

$words = &lt;&gt;;
chomp($words);
$len = length($words);
$words .= ' ';
$spaces = 0;
# iterate over the string, count the spaces
$spaces++ while $words =~ m/ /g;

$origin = 0;
$o = vec($words, $origin, 8);
$cycle_begin = $origin;
$swaps = 0;

# this possibly terinates one iteration early,
# if the last char is a one-cycle (i.e. moves to its current location)
# one-cycles previous to the last are iterated, but not swapped.
while ($i++ &lt; $len - $spaces || !$was_cycle) {
  $w_start = rindex($words, ' ', $origin);
  $w_end = index($words, ' ', $origin);
  $pos = ($origin - $w_start) - 1;
  $target = $len - ($w_end - $pos);
  $t = vec($words, $target, 8);

  if ($t == 32) {
    $target = $len - $target - 1;
    $t = vec($words, $target, 8);
  }

  # char is already correct, possibly a one-cycle
  if ($t != $o) {
    $swaps += 1;
    vec($words, $target, 8) = $o;
  }

  $origin = $target;
  $o = $t;
  if ($origin == $cycle_begin) {
    if ($i &lt; $len - $spaces) {
      # backtrack through everything we've done up to this point
      # to find the next unswapped char ...seriously.
      $origin += 1;
      if (vec($words, $origin, 8) == 32) {
        $origin += 1;
      }
      $bt_origin = 0;
      $bt_cycle_begin = 0;
      while ($bt_cycle_begin &lt; $origin) {
        $w_start = rindex($words, ' ', $bt_origin);
        $w_end = index($words, ' ', $bt_origin);
        $pos = ($bt_origin - $w_start) - 1;
        $target = $len - ($w_end - $pos);
        $t = vec($words, $target, 8);

        if ($t == 32) {
          $target = $len - $target - 1;
          $t = vec($words, $target, 8);
        }

        if ($target == $bt_cycle_begin) {
          $bt_origin = ++$bt_cycle_begin;
          if (vec($words, $bt_origin, 8) == 32) {
            $bt_origin = ++$bt_cycle_begin;
          }
        } else {
          $bt_origin = $target;
        }

        if ($target == $origin) {
          $origin += 1;
          if (vec($words, $origin, 8) == 32) {
            $origin += 1;
          }
          $bt_origin = $bt_cycle_begin = 0;
        }
      }
    }

    $cycle_begin = $origin;
    $o = vec($words, $origin, 8);
    $was_cycle = 1;
  } else {
    $was_cycle = 0;
  }
}

for $i (0..$len/2-1) {
  $mirror = $len - $i - 1;
  $o = vec($words, $i, 8);
  $m = vec($words, $mirror, 8);
  # if exactly one is a space...
  if (($o == 32) ^ ($m == 32)) {
    $swaps += 2;
    vec($words, $mirror, 8) = $o;
    vec($words, $i, 8) = $m;
  }
}

chop($words);
print $words;
print "swaps: $swaps; len: $len";
print 'ratio: ', $swaps/$len;


Edit: Added a swap counter, and the ratio.

Input is taken from stdin. Sample usage:

$ echo where in the world is carmen sandiego|perl reverse-inplace.pl
sandiego carmen is world the in where
swaps: 35; len: 37
ratio: 0.945945945945946




Method

To begin, the first character of the string is moved to its final destination. The character just replaced is then moved to its destination, etc. This continues until one of two conditions is met:


The character should be swapped with a space.
When this occurs, the character is not swapped with the space, but rather into the mirror position of the space. The algorithm continues from that position.
A cycle has been reached.
When the target returns to the initial starting position of the current cycle, the next unswapped character (or rather, any unswapped character would do) needs to be found. To do this under constant memory constraints, all swaps that have been made up to this point are back-tracked.


After this phase, each non-space character has been moved at most once. To finish, all space characters are swapped with the characters at their mirror positions, requiring two assignment operations per space.