# 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.
• 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. – Ben Millwood 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. – wrongu May 11 '14 at 17:22
• @bacchusbeale yes, but it's constant extra memory. – Martin Ender 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. – IchBinKeinBaum 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. – Dennis May 13 '14 at 14:17

## 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) – justhalf 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 ;) – primo 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? – primo 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. – justhalf 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. – primo May 14 '14 at 6:42

## 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? – justhalf 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. – justhalf May 12 '14 at 14:40 • I make a comparison against my algorithm in my answer here: codegolf.stackexchange.com/a/26952/16337 – justhalf 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. – primo 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. – IchBinKeinBaum 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] – Thaha kp 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! – bacchusbeale May 12 '14 at 6:23 # 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. – primo 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. – Justin 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). – Martin Ender May 12 '14 at 7:31
• More to the point, it uses lots and lots of additional space. – Ben Millwood May 15 '14 at 20:50