# Reverse order of words in a string inplace

• 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 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.
• I'd be a little bit sad if this all came down to tie-breaking score-2 submissions on their memory usage. I mostly posted this question wondering if anyone would manage to score less than 2. May 11 '14 at 15:39
• I don't have a formal proof, but my intuition tells me that with the constant-space restriction, it's impossible to do better than 2. If you only count variable declarations for space, I could cheat and make a recursive function. but that only disguises the little-omega(1) space by putting it on the stack. May 11 '14 at 17:22
• @bacchusbeale yes, but it's constant extra memory. May 11 '14 at 20:22
• If you strictly enforce the rules then it's impossible to write such a program. The string can be of arbitrary length and you will need at least some kind of variable that stores an index. So I just have to make the string long enough to exceed the bounds of your variable. To successfully store at least one index your needed memory will grow with the string length. May 11 '14 at 22:54
• @IchBinKeinBaum is right, it is impossible to perform this task with O(1) additional space. You need O(log n) space to store an index position, since an k-bit integer can only store in them for strings of a length up to 2^k. Limiting the length of the strings makes the challenge rather pointless, since every algorithm would require O(1) space this way. May 13 '14 at 14:17

## Perl, score 1.3̅

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:

1. Spaces directly across from spaces do not need to be swapped.
2. 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̅. #!perl -l use warnings;$words = <>;
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++ <$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 < $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 <$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: 1. 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. 2. 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. • Wow, that's cool. Can you explain why putting the character to the mirror position of the space gives correct answer? May 12 '14 at 14:00 • @Niklas, I don't think that's possible. Because to do the backtracking you need the space position information. If you override that information, you can't do the backtracking. May 12 '14 at 14:40 • I make a comparison against my algorithm in my answer here: codegolf.stackexchange.com/a/26952/16337 May 12 '14 at 14:46 • @justhalf In the final string, all spaces will be in their mirrored position. Therefore, we can safely use this position to store the character that replaces the space, and switch them at the end. May 13 '14 at 2:34 • Well done. I had a similar idea but didn't think of just leaving the spaces in place and then mirroring them. May 13 '14 at 18:25 ### Ruby, score 2 As a starter a very basic algorithm. It first reverses the whole string and then reverses each word in the string again. In the worst case (one word, even number of characters) the score becomes 2. def revstring(s, a, b) while a<b h = s[a] s[a] = s[b] s[b] = h a += 1 b -= 1 end s end def revwords(s) revstring(s, 0, s.length-1) a = 0 while a<s.length b = a+1 b += 1 while b<s.length and s[b]!=" " revstring(s, a, b-1) a = b+1 end s end  Usage: > revwords("hello there everyone") "everyone there hello"  • Why didn't you use a Ruby built-in function to reverse a string? Would it change the score? – A.L May 12 '14 at 1:52 • use, s[a], s[b] = s[b], s[a] May 14 '14 at 8:44 C++: Score 2 #include<iostream> #include<algorithm> void rev(std::string& s) { std::reverse(s.begin(),s.end()); std::string::iterator i=s.begin(),j=s.begin(); while(i!=s.end()) { while(i!=s.end()&&(*i)==' ') i++; j=i; while(i!=s.end()&&(*i)!=' ') i++; std::reverse(j,i); } } int main() { std::string s; getline(std::cin,s); rev(s); std::cout<<s; }  • I tested it. Works well! May 12 '14 at 6:23 ## Python, Score: 21.5 1.25 This is the direct combination between primo's answer and my answer. So credits to him also! The proof is still in progress, but here is the code to play with! If you can find a counter example of score greater than 1.25 (or if there is a bug), let me know! Currently the worst case is: a a ... a a dcb...cbd  where there are exactly n of each the letters "a", "b", "c", and " " (space), and exactly two "d"s. The length of the string is 4n+2 and the number of assignments is 5n+2, giving a score of 5/4 = 1.25. The algorithm works in two steps: 1. Find k such that string[k] and string[n-1-k] are word boundaries 2. Run any word reversing algorithm on string[:k]+string[n-1-k:] (i.e., concatenation of first k and last k chars) with small modification. where n is the length of the string. The improvement this algorithm gives comes from the "small modification" in Step 2. It's basically the knowledge that in the concatenated string, the characters at position k and k+1 are word boundaries (which means they are spaces or first/last character in a word), and so we can directly replace the characters in position k and k+1 with the corresponding character in the final string, saving a few assignments. This removes the worst case from the host word-reversal algorithm There are cases where we can't actually find such k, in that case, we just run the "any word reversal algorithm" on the whole string. The code is long to handle these four cases on running the word reversal algorithm on the "concatenated" string: 1. When k is not found (f_long = -2) 2. When string[k] != ' ' and string[n-1-k] != ' ' (f_long = 0) 3. When string[k] != ' ' and string[n-1-k] == ' ' (f_long = 1) 4. When string[k] == ' ' and string[n-1-k] != ' ' (f_long = -1) I'm sure the code can be shortened. Currently it's long because I didn't have clear picture of the whole algorithm in the beginning. I'm sure one can design it to be represented in a shorter code =) Sample run (first is mine, second is primo's): Enter string: a bc def ghij "ghij def bc a": 9, 13, 0.692 "ghij def bc a": 9, 13, 0.692 Enter string: 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 "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": 50, 50, 1.000 "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": 51, 50, 1.020 Enter string: a b c d e f g hijklmnopqrstuvwx "hijklmnopqrstuvwx g f e d c b a": 38, 31, 1.226 "hijklmnopqrstuvwx g f e d c b a": 38, 31, 1.226 Enter string: a bc de fg hi jk lm no pq rs tu vw xy zc "zc xy vw tu rs pq no lm jk hi fg de bc a": 46, 40, 1.150 "zc xy vw tu rs pq no lm jk hi fg de bc a": 53, 40, 1.325 Enter string: a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd "dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a": 502, 402, 1.249 "dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a": 502, 402, 1.249  You can see that the score is almost the same, except for the worst case of the host word-reversal algorithm in the third example, for which my approach yields score of less than 1.25 DEBUG = False def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long): if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char) if f_long == 0: f_limit = f_end-1 b_limit = b_start elif f_long == 1: f_limit = f_end-1 b_limit = b_start+1 elif f_long == -1: f_limit = f_end-2 b_limit = b_start elif f_long == -2: f_limit = f_end b_limit = b_start if (f_start <= pos < f_limit or b_limit < pos < b_end) and char == ' ': word_start = pos word_end = pos+1 else: if pos < f_limit+1: word_start = f_start if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start elif pos == f_limit+1: word_start = f_limit+1 if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1) elif b_limit <= pos: word_start = b_limit if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit elif b_limit-1 == pos: word_start = b_limit-1 if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1) i = pos while f_start <= i <= f_limit or 0 < b_limit <= i < b_end: if i==f_limit or i==b_limit: cur_char = 'a' elif i!=pos: cur_char = string[i] else: cur_char = char if cur_char == ' ': word_start = i+1 if DEBUG: print 'Assigned word_start from loop' break i -= 1 if b_limit <= pos: word_end = b_end if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end elif b_limit-1 == pos: word_end = b_limit if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit) elif pos < f_limit+1: word_end = f_limit+1 if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1) elif pos == f_limit+1: word_end = f_limit+2 if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2) i = pos while f_start <= i <= f_limit or 0 < b_limit <= i < b_end: if i==f_limit or i==b_limit: cur_char = 'a' elif i!=pos: cur_char = string[i] else: cur_char = char if cur_char == ' ': word_end = i if DEBUG: print 'Assigned word_end from loop' break i += 1 if DEBUG: print 'start, end: %d, %d' % (word_start, word_end) word_len = word_end - word_start offset = word_start-f_start result = (b_end-offset-(word_end-pos)) % b_end if string[result] == ' ' and (b_start == -1 or result not in {f_end-1, b_start}): return len(string)-1-result else: return result def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False): assignments = 0 pos = start_idx tmp = string[pos] processed_something = False count = 0 while pos != start_idx or not processed_something: count += 1 if DEBUG and count > 20: print '>>>>>Break!<<<<<' break new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long) if DEBUG: if dry_run: print 'Test:', else: print '\t', print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos]) if dry_run: tmp = string[new_pos] if new_pos == dry_run: return True elif pos == new_pos: break elif tmp == string[new_pos]: pass else: tmp, string[new_pos] = string[new_pos], tmp assignments += 1 pos = new_pos processed_something = True if dry_run: return False return assignments def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2): if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long) if DEBUG: print if DEBUG: print ''.join(string) assignments = 0 n = len(string) if b_start == -1: for i in range(f_start, f_end): if string[i] == ' ': continue if DEBUG: print 'Starting from i=%d' % i if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i) if string[j] != ' '): continue if DEBUG: print print 'Finished test' assignments += process_loop(string, i, f_start, f_end, -1, f_end) if DEBUG: print if DEBUG: print ''.join(string) for i in range(f_start, (f_start+f_end-1)/2): if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '): string[i], string[n-1-i] = string[n-1-i], string[i] assignments += 2 else: for i in range(f_start, f_end)+range(b_start, b_end): if string[i] == ' ' and i not in {f_end-1, b_start}: continue if DEBUG: print 'Starting from i=%d' % i if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, f_end)+range(b_start, b_end) if j<i and (string[j] != ' ' or j in {f_end-1, b_start})): continue assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long) if DEBUG: print if DEBUG: print ''.join(string) for i in range(f_start, f_end-1): if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '): string[i], string[n-1-i] = string[n-1-i], string[i] assignments += 2 return assignments class SuperList(list): def index(self, value, start_idx=0): try: return self[:].index(value, start_idx) except ValueError: return -1 def rindex(self, value, end_idx=-1): end_idx = end_idx % (len(self)+1) try: result = end_idx - self[end_idx-1::-1].index(value) - 1 except ValueError: return -1 return result def min_reverse(string): assignments = 0 lower = 0 upper = len(string) while lower < upper: front = string.index(' ', lower) % (upper+1) back = string.rindex(' ', upper) while abs(front-lower - (upper-1-back)) > 1 and front < back: if front-lower < (upper-1-back): front = string.index(' ', front+1) % (upper+1) else: back = string.rindex(' ', back) if DEBUG: print lower, front, back, upper if front > back: break if DEBUG: print lower, front, back, upper if abs(front-lower - (upper-1-back)) > 1: assignments += reverse(string, lower, upper, -1) lower = upper elif front-lower < (upper-1-back): assignments += reverse(string, lower, front+1, back+1, upper, -1) lower = front+1 upper = back+1 elif front-lower > (upper-1-back): assignments += reverse(string, lower, front, back, upper, 1) lower = front upper = back else: assignments += reverse(string, lower, front, back+1, upper, 0) lower = front+1 upper = back return assignments def minier_find_new_idx(string, pos, char): n = len(string) try: word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1 except: word_start = 0 try: word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ') except: word_end = n word_len = word_end - word_start offset = word_start result = (n-offset-(word_end-pos))%n if string[result] == ' ': return n-result-1 else: return result def minier_process_loop(string, start_idx, dry_run=False): assignments = 0 pos = start_idx tmp = string[pos] processed_something = False while pos != start_idx or not processed_something: new_pos = minier_find_new_idx(string, pos, tmp) #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos]) if pos == new_pos: break elif dry_run: tmp = string[new_pos] if new_pos == dry_run: return True elif tmp == string[new_pos]: pass else: tmp, string[new_pos] = string[new_pos], tmp assignments += 1 pos = new_pos processed_something = True if dry_run: return False return assignments def minier_reverse(string): assignments = 0 for i in range(len(string)): if string[i] == ' ': continue if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '): continue assignments += minier_process_loop(string, i) n = len(string) for i in range(n/2): if string[i] == ' ' and string[n-i-1] != ' ': string[i], string[n-i-1] = string[n-i-1], string[i] assignments += 2 elif string[n-i-1] == ' ' and string[i] != ' ': string[i], string[n-i-1] = string[n-i-1], string[i] assignments += 2 return assignments def main(): while True: str_input = raw_input('Enter string: ') string = SuperList(str_input) result = min_reverse(string) n = len(string) print '"%s": %d, %d, %.3f' % (''.join(string), result, n, 1.0*result/n) string = SuperList(str_input) result2 = minier_reverse(string) print '"%s": %d, %d, %.3f' % (''.join(string), result2, n, 1.0*result2/n) if __name__ == '__main__': main()  ## Python, Score: 1.5 The exact number of assignments can be approximated by the formula: n <= 1.5*length(string)  with the worst case being: a b c d e f g h i jklmnopqrstuvwxyzzz  with 55 assignments on string with length 37. The idea is similar to my previous one, it's just that in this version I tried to find prefix and suffix at word boundaries with length difference at most 1. Then I run my previous algorithm on that prefix and suffix (imagine them as being concatenated). Then continue on unprocessed part. For example, for the previous worst case: ab| a b| c  we will first do word reversal on "ab" and " c" (4 assignments) to be: c | a b|ab  We know that at the boundary it used to be space (there are many cases to be handled, but you can do that), so we don't need to encode the space at the boundary, this is the main improvement from the previous algorithm. Then finally we run on the middle four characters to get: c b a ab  in total 8 assignments, the optimal for this case, since all 8 characters changed. This eliminates the worst case in previous algorithm since the worst case in previous algorithm is eliminated. See some sample run (and comparison with @primo's answer - his is the second line): Enter string: i can do anything "anything do can i": 20, 17 "anything do can i": 17, 17 Enter string: a b c d e f ghijklmnopqrs "ghijklmnopqrs f e d c b a": 37, 25 "ghijklmnopqrs f e d c b a": 31, 25 Enter string: a b c d e f ghijklmnopqrst "ghijklmnopqrst f e d c b a": 38, 26 "ghijklmnopqrst f e d c b a": 32, 26 Enter string: a b c d e f g h i jklmnozzzzzzzzzzzzzzzzz "jklmnozzzzzzzzzzzzzzzzz i h g f e d c b a": 59, 41 "jklmnozzzzzzzzzzzzzzzzz i h g f e d c b a": 45, 41 Enter string: a b c d e f g h i jklmnopqrstuvwxyzzz "jklmnopqrstuvwxyzzz i h g f e d c b a": 55, 37 "jklmnopqrstuvwxyzzz i h g f e d c b a": 45, 37 Enter string: ab a b a b a b a b a b a b a c "c a b a b a b a b a b a b a ab": 30, 30 "c a b a b a b a b a b a b a ab": 31, 30 Enter string: ab a b a b a b a b a b a b a b c "c b a b a b a b a b a b a b a ab": 32, 32 "c b a b a b a b a b a b a b a ab": 33, 32 Enter string: abc d abc "abc d abc": 0, 9 "abc d abc": 0, 9 Enter string: abc d c a "a c d abc": 6, 9 "a c d abc": 4, 9 Enter string: abc a b a b a b a b a b a b c "c b a b a b a b a b a b a abc": 7, 29 "c b a b a b a b a b a b a abc": 5, 29  primo's answer is generally better, although in some cases I can have 1 point advantage =) Also his code is much shorter than mine, haha. DEBUG = False def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long): if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char) if f_long == 0: f_limit = f_end-1 b_limit = b_start elif f_long == 1: f_limit = f_end-1 b_limit = b_start+1 elif f_long == -1: f_limit = f_end-2 b_limit = b_start elif f_long == -2: f_limit = f_end b_limit = b_start if (f_start <= pos < f_limit or b_limit < pos < b_end) and (char == ' ' or char.isupper()): word_start = pos word_end = pos+1 else: if pos < f_limit+1: word_start = f_start if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start elif pos == f_limit+1: word_start = f_limit+1 if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1) elif b_limit <= pos: word_start = b_limit if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit elif b_limit-1 == pos: word_start = b_limit-1 if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1) i = pos if not (i < f_limit and b_limit < i): i -= 1 while f_start <= i < f_limit or 0 < b_limit < i < b_end: if i!=pos: cur_char = string[i] else: cur_char = char if cur_char == ' ' or cur_char.isupper(): word_start = i+1 if DEBUG: print 'Assigned word_start from loop' break i -= 1 if b_limit <= pos: word_end = b_end if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end elif b_limit-1 == pos: word_end = b_limit if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit) elif pos < f_limit+1: word_end = f_limit+1 if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1) elif pos == f_limit+1: word_end = f_limit+2 if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2) i = pos if not (i < f_limit and b_limit < i): i += 1 while f_start <= i < f_limit or 0 < b_limit < i < b_end: if i!=pos: cur_char = string[i] else: cur_char = char if cur_char == ' ' or cur_char.isupper(): word_end = i if DEBUG: print 'Assigned word_end from loop' break i += 1 if DEBUG: print 'start, end: %d, %d' % (word_start, word_end) word_len = word_end - word_start offset = word_start-f_start return (b_end-offset-(word_end-pos)) % b_end def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False): assignments = 0 pos = start_idx tmp = string[pos] processed_something = False count = 0 while pos != start_idx or not processed_something: count += 1 if count > 20: if DEBUG: print 'Break!' break new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long) #if dry_run: # if DEBUG: print 'Test:', if DEBUG: print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos]) if pos == new_pos: break elif dry_run: tmp = string[new_pos] if new_pos == dry_run: return True elif tmp == string[new_pos]: pass elif tmp == ' ': if b_start!=-1 and new_pos in {f_end-1, b_start}: tmp, string[new_pos] = string[new_pos], tmp else: tmp, string[new_pos] = string[new_pos], '@' assignments += 1 elif string[new_pos] == ' ': if b_start!=-1 and new_pos in {f_end-1, b_start}: tmp, string[new_pos] = string[new_pos], tmp else: tmp, string[new_pos] = string[new_pos], tmp.upper() assignments += 1 else: tmp, string[new_pos] = string[new_pos], tmp assignments += 1 pos = new_pos processed_something = True if dry_run: return False return assignments def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2): if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long) if DEBUG: print if DEBUG: print ''.join(string) assignments = 0 if b_start == -1: for i in range(f_start, (f_start+f_end)/2): if DEBUG: print 'Starting from i=%d' % i if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i)): continue assignments += process_loop(string, i, f_start, f_end, -1, f_end) if DEBUG: print if DEBUG: print ''.join(string) else: for i in range(f_start, f_end): if DEBUG: print 'Starting from i=%d' % i if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, i)): continue assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long) if DEBUG: print if DEBUG: print ''.join(string) for i in range(len(string)): if string[i] == '@': string[i] = ' ' assignments += 1 if string[i].isupper(): string[i] = string[i].lower() assignments += 1 return assignments class SuperList(list): def index(self, value, start_idx=0): try: return self[:].index(value, start_idx) except ValueError: return -1 def rindex(self, value, end_idx=-1): end_idx = end_idx % (len(self)+1) try: result = end_idx - self[end_idx-1::-1].index(value) - 1 except ValueError: return -1 return result def min_reverse(string): # My algorithm assignments = 0 lower = 0 upper = len(string) while lower < upper: front = string.index(' ', lower) % (upper+1) back = string.rindex(' ', upper) while abs(front-lower - (upper-1-back)) > 1 and front < back: if front-lower < (upper-1-back): front = string.index(' ', front+1) % (upper+1) else: back = string.rindex(' ', back) if DEBUG: print lower, front, back, upper if front > back: break if DEBUG: print lower, front, back, upper if abs(front-lower - (upper-1-back)) > 1: assignments += reverse(string, lower, upper, -1) lower = upper elif front-lower < (upper-1-back): assignments += reverse(string, lower, front+1, back+1, upper, -1) lower = front+1 upper = back+1 elif front-lower > (upper-1-back): assignments += reverse(string, lower, front, back, upper, 1) lower = front upper = back else: assignments += reverse(string, lower, front, back+1, upper, 0) lower = front+1 upper = back return assignments def minier_find_new_idx(string, pos, char): n = len(string) try: word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1 except: word_start = 0 try: word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ') except: word_end = n word_len = word_end - word_start offset = word_start result = (n-offset-(word_end-pos))%n if string[result] == ' ': return n-result-1 else: return result def minier_process_loop(string, start_idx, dry_run=False): assignments = 0 pos = start_idx tmp = string[pos] processed_something = False while pos != start_idx or not processed_something: new_pos = minier_find_new_idx(string, pos, tmp) #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos]) if pos == new_pos: break elif dry_run: tmp = string[new_pos] if new_pos == dry_run: return True elif tmp == string[new_pos]: pass else: tmp, string[new_pos] = string[new_pos], tmp assignments += 1 pos = new_pos processed_something = True if dry_run: return False return assignments def minier_reverse(string): # primo's answer for comparison assignments = 0 for i in range(len(string)): if string[i] == ' ': continue if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '): continue assignments += minier_process_loop(string, i) n = len(string) for i in range(n/2): if string[i] == ' ' and string[n-i-1] != ' ': string[i], string[n-i-1] = string[n-i-1], string[i] assignments += 2 elif string[n-i-1] == ' ' and string[i] != ' ': string[i], string[n-i-1] = string[n-i-1], string[i] assignments += 2 return assignments def main(): while True: str_input = raw_input('Enter string: ') string = SuperList(str_input) result = min_reverse(string) print '"%s": %d, %d' % (''.join(string), result, len(string)) string = SuperList(str_input) result2 = minier_reverse(string) print '"%s": %d, %d' % (''.join(string), result2, len(string)) if __name__ == '__main__': main()  ## Python, Score: asymptotically 2, in normal case much less old code removed due to space constraint The idea is to iterate through each index, and for each index i, we take the character, calculate the new position j, memorize the character at position j, assign the character at i to j, and repeat with character at index j. Since we need the space information to calculate the new position, I encode old space as the uppercase version of the new letter, and new space as '@'. • If you can reduce the number of words in the worse case to be in terms of length of the string (say, to length(string)/3 by forcing each word in the worst case to be at least of length 2 somehow), then the score will be less than 2 (in the example above it will be 1.67) May 12 '14 at 6:11 • I added a swap counter to mine; yours does actually beat mine for the worst case (but not the general case). Need to find a way to fix that ;) May 13 '14 at 7:06 • Line 127: if any(process_loop(...) for j in range(...)) Wouldn't the assignments from these process loops need to be counted? May 14 '14 at 5:11 • That doesn't do any assignment. If you see, the dry_run parameter is set to non-zero (the value to i). Inside the process_loop, if dry_run is non-zero, it won't do any assignment. May 14 '14 at 5:14 • I think I have a better picture now. In essense, two distinct methods with different worst case behavior are combined, in order to eliminate the worst case for both. I like it. I think in general, this may be the best approach to take, although it seems likely two (or more) completely different methods could be combined to reduce the worst case even further. May 14 '14 at 6:42 # Rebol reverse-words: function [ "Reverse the order of words. Modifies and returns string (series)" series [string!] "At position (modified)" ][ first-time: on until [ reverse/part series f: any [ if first-time [tail series] find series space tail series ] unless first-time [series: next f] first-time: off tail? series ] series: head series ]  I'm unclear on the scoring for this. There is no direct string assignment in this code. Everything is handled by the one reverse/part which does in-place reversing within and initially on the whole the string. Some detail on the code: • Loop through string (series) until it reaches the tail? • First time in loop do full reverse of string - reverse/part series tail series (which is same as reverse series) • Then reverse every word found on further iterations - reverse/part series find series space • Once exhausted word finds then return tail series so that it will reverse last word in string - reverse/part series tail series Rebol allows traversing of a string via an internal pointer. You can see this at series: next f (move pointer to after space so beginning of next word) and series: head series (resets pointer back to the head). See Series for more info. Usage example in Rebol console: >> reverse-words "everyone there hello" == "hello there everyone" >> x: "world hello" == "world hello" >> reverse-words x == "hello world" >> x == "hello world" >> reverse-words "hello" == "hello"  • On the first pass each character is repositioned once, and on the second pass each non-space character is repositioned again. For an arbitrarily large input with relatively few spaces, the score approaches 2. May 13 '14 at 14:30 C : Score 2 This just flips the entire string once then reverses each word. #include <stdio.h> #include <string.h> void reverse(char *s,unsigned n){ char c; unsigned i=0,r=1; while(i < n){ //no swap function in C c=s[i]; s[i++]=s[n]; s[n--]=c; } } unsigned wordlen(char *s){ unsigned i=0; while (s[i] != ' ' && s[i]) ++i; return i; } int main(int argc, char **argv) { char buf[]="reverse this also"; char *s=buf; unsigned wlen=0,len=strlen(s)-1; reverse(s,len); //reverse entire string while(wlen<len){ // iterate over each word till end of string wlen=wordlen(s); reverse(s,wlen-1); s+=wlen+1; len-=wlen; } printf("%s\n",buf); return 0; }  • This is a code-only answer. Consider adding an explanation of what goes on in your code. May 12 '14 at 7:51 ### Python: score 2 Almost identical to Howard's algorithm, but does the reversal steps in reverse (first flips words then flips the whole string). Additional memory used is 3 byte-size variables: i, j, and t. Technically, find and len are using some internal variables, but they could just as easily re-use i or j without any loss of function. quick edit: saving on string assignments by only swapping when characters differ, so I can grab some extra points from note #2. from sys import stdin def word_reverse(string): # reverse each word i=0 j=string.find(' ')-1 if j == -2: j=len(string)-1 while True: while i<j: if string[i] != string[j]: t = string[i] string[i] = string[j] string[j] = t i,j = i+1,j-1 i=string.find(' ', i)+1 if i==0: break j=string.find(' ', i)-1 if j == -2: j=len(string)-1 # reverse the entire string i=0 j=len(string)-1 while i<j: if string[i] != string[j]: t = string[i] string[i] = string[j] string[j] = t i,j = i+1,j-1 return string for line in stdin.readlines(): # http://stackoverflow.com/a/3463789/1935085 line = line.strip() # no trailing newlines ore spaces to ensure it conforms to '[a-z]+( [a-z]+)*' print word_reverse(bytearray(line))  ## Batch I'll admit to not fully understand the scoring (I think it's two).. but I will say - it does the thing. @echo off setLocal enableDelayedExpansion set c= set s= for %%a in (%~1) do set /a c+=1 & echo %%a >> f!c! for /L %%a in (!c!, -1, 1) do ( set /p t=<f%%a set s=!s!!t! del f%%a ) echo !s!  Input is taken as first standard input value, and so needs to be surrounded by quotation marks - call: script.bat "hello there everyone" out: everyone there hello. Maybe someone else can score me (assuming I haven't, in some other way, disqualified myself). # Javascript function reverseWords(input) { if (input.match(/^[a-z]+( [a-z]+)*$/g)) {
return input.split(' ').reverse().join(' ');
}
}


Usage:

> reverseWords('hello there everyone');
'everyone there hello'


I get the strange feeling I missed something...

• Yes, this is not in place, because you don't modify the input string. As that's not possible in JavaScript you need to emulate strings with an array of characters (i.e. code point integers or single-character strings). May 12 '14 at 7:31
• More to the point, it uses lots and lots of additional space. May 15 '14 at 20:50