Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.
share|improve this question
1  
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 at 15:39
1  
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. –  rangu May 11 at 17:22
1  
We would need at least one temporary variable to use for swapping characters. Does this count as extra memory? –  bacchusbeale May 11 at 19:55
3  
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 at 22:54
2  
@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 at 14:17

9 Answers 9

up vote 4 down vote accepted

Python, Score: 2 1.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 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 improvements that 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.

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:

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
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
Enter string: abcd a b a b a b a b a b c
"c b a b a b a b a b a abcd": 27, 26
"c b a b a b a b a b a abcd": 27, 26
Enter string: the best result is yet to be achieved
"achieved be to yet is result best the": 39, 37
"achieved be to yet is result best the": 37, 37

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

share|improve this answer
    
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 at 6:11
1  
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 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 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 at 5:14
1  
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 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.

share|improve this answer
    
Wow, that's cool. Can you explain why putting the character to the mirror position of the space gives correct answer? –  justhalf May 12 at 14:00
    
I think this can be improved to score 1 at the cost of a lot, lot more backtracking –  Niklas B. May 12 at 14:35
1  
@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 at 14:40
1  
I make a comparison against my algorithm in my answer here: codegolf.stackexchange.com/a/26952/16337 –  justhalf May 12 at 14:46
1  
@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 at 2:34

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"
share|improve this answer
    
Why didn't you use a Ruby built-in function to reverse a string? Would it change the score? –  A.L May 12 at 1:52
    
use, s[a], s[b] = s[b], s[a] –  Thaha kp May 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;
}
share|improve this answer
2  
I tested it. Works well! –  bacchusbeale May 12 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"
share|improve this answer
    
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 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;
}
share|improve this answer
3  
This is a code-only answer. Consider adding an explanation of what goes on in your code. –  Quincunx May 12 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))
share|improve this answer

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).

share|improve this answer

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...

share|improve this answer
3  
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 Büttner May 12 at 7:31
    
More to the point, it uses lots and lots of additional space. –  Ben Millwood May 15 at 20:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.