Reverse order of words in a string inplace

17

4

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.

Ben Millwood

Posted 2014-05-11T14:08:39.473

Reputation: 281

What do you mean by "number of assigments you make to string elements"? E.g. in C, str[0]='A'; counts as one? Or str[]="FOOBAR"; counts as one? – user12205 – 2014-05-11T14:15:01.440

@ace I would think that str[a:b] = str[c:d], for example, should count as b-a. – primo – 2014-05-11T14:20:22.490

str[0]='A' counts as one assignment. The latter case is only possible in initialisation, right? And with a string literal on the RHS? In that case I'm not sure it's going to help you very much. I say make it seven assignments (including the implicit null byte) (so primo is correct) – Ben Millwood – 2014-05-11T14:22:50.297

So we will end up with answers with the same score of 2 but different tie-breaks? – A.L – 2014-05-11T15:08:23.753

1I'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 – 2014-05-11T15:39:47.010

1I 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 – 2014-05-11T17:22:04.947

1We would need at least one temporary variable to use for swapping characters. Does this count as extra memory? – bacchusbeale – 2014-05-11T19:55:08.303

2@bacchusbeale yes, but it's constant extra memory. – Martin Ender – 2014-05-11T20:22:35.777

4If 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 – 2014-05-11T22:54:12.320

1@IchBinKeinBaum, the rule reads "You are not permitted to use more than a constant amount of additional memory." A single index takes constant memory, and is independent of the size of the string. Also nobody actually worries about strings exceeding RAM size or integer overflow with indices. – wrongu – 2014-05-12T00:49:27.017

1I found this question really hard to understand. Maybe because English is not my mother tongue. I have read the score calculation 3 times but still can't figure out how to apply these rules to the answers. Proving bounds or fewer assignments is neither simple nor code golfing IMHO. – A.L – 2014-05-12T01:58:34.687

1Probably the scoring can be better formulated if you can provide (or hide) some test strings for which the scores of all programs will be calculated. The lowest number of assignments wins. That will be very objective. To count the number of assignments, you can create an function for people should use to modify the string, then you can count the number of assignments by counting the number of calls to the function. – justhalf – 2014-05-12T06:53:13.473

1@IchBinKeinBaum In the RAM model, which is usually used in algorithm analysis, it is assumed that for the machine word width w, we have n << 2^w. This is also practical. For w = 64 it's highly unlikely that the input size will ever be larger than what a word can address – Niklas B. – 2014-05-12T11:38:39.697

Do you mean a mutable or immutable string? – The Guy with The Hat – 2014-05-12T11:43:56.667

1@TheGuywithTheHat Mutable. The description specifically says that if your language doesn't support mutable strings, character arrays are acceptable. – IchBinKeinBaum – 2014-05-12T11:58:26.740

@NiklasB. @rangu To make it concrete: If I use Java I have to use char arrays because Strings are immutable - kind of. Am I allowed to assume that the string length is < 2^31 because otherwise I can't fit the string into a single char array?

– IchBinKeinBaum – 2014-05-12T13:20:40.557

@IchBinKeinBaum I would assume so. That Java does not allow you to use the full word size to index an array is a rather arbitrary restriction of the language, not a theoretical problem (you can always use 64-bit indexing) – Niklas B. – 2014-05-12T13:24:22.200

Certainly I am missing something here. Which part of the rule prohibits Perl s///? http://pastebin.com/A2z7PESK

– manatwork – 2014-05-13T09:05:16.007

@manatwork I suppose one would be disinclined, due to having to wade through the perl source to show that a) additional memory usage is bounded by a constant for any arbitrary string (is it?), and b) that the number of inplace string operation is bounded by the length of the string (it probably is). – primo – 2014-05-13T11:11:45.130

3@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 – 2014-05-13T14:17:28.440

1In all seriousness, an unsigned 256 bit integer is nearly large enough to enumerate every electron in the observable universe. For all practicality, the space required to store such an index can safely be considered to be constant. – primo – 2014-05-14T03:44:37.763

I'm curious. OP, is there any practical system where string assignment is the most costly part, hence you're willing to sacrifice time to save some assignments? It's cool that we can actually achieve a score of 1.25 =D – justhalf – 2014-05-14T09:58:53.497

Thanks to the people who pointed out my sloppiness wrt constant memory. I indeed intended for indices into the string to count as constant size. I pondered clarifying it to "constant number of unbounded integers" but them some smart-alec would encode the entire string into a single integer and operate on it there :) I suspect just weakening to "logarithmic space overhead" would be fine, but since everyone seems to be interpreting the challenge as I intended, I will make no changes. In response to justhalf, there is no intended practical application, "cool" was all I hoped for :) – Ben Millwood – 2014-05-15T20:58:05.817

Answers

4

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

justhalf

Posted 2014-05-11T14:08:39.473

Reputation: 2 070

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 – 2014-05-12T06:11:41.017

1I 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 – 2014-05-13T07:06:50.537

Line 127: if any(process_loop(...) for j in range(...)) Wouldn't the assignments from these process loops need to be counted? – primo – 2014-05-14T05:11:15.587

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 – 2014-05-14T05:14:06.090

Ahh, I see now. Perhaps you could explain the algorithm used, so that it would be easier to confirm the worst case ;) – primo – 2014-05-14T05:15:40.813

I already explained it in the previous version of my answer. Basically I try to find a sequence of first few words and a sequence of last few words which lengths differ by at most one, then perform the reversal on the concatenation of those two sequences, with additional advantage that, depending on the case (there are 4 possible cases), we know in some positions that the original position is a space or not. Hence we can directly swap the characters in those places, saving a few assignments. =) – justhalf – 2014-05-14T05:19:34.657

@primo: explanation added :) – justhalf – 2014-05-14T06:26:54.487

1I 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 – 2014-05-14T06:42:43.623

Hmm, I think it's not about combining two distinct methods, as there is only one single "word reversal algorithm" (which is yours, in my latest update) in my algorithm. My algorithm can be regarded as "the framework to improve any word reversal algorithm", which is the finding of position k as described. – justhalf – 2014-05-14T08:30:40.693

14

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.

primo

Posted 2014-05-11T14:08:39.473

Reputation: 30 891

Wow, that's cool. Can you explain why putting the character to the mirror position of the space gives correct answer? – justhalf – 2014-05-12T14:00:21.243

I think this can be improved to score 1 at the cost of a lot, lot more backtracking – Niklas B. – 2014-05-12T14:35:14.300

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 – 2014-05-12T14:40:53.167

@justhalf I'm thinking to find the position, virtually (but not actually) reverse all the work you have done before, which of course again involves recreating the cycles that are no longer valid, so you need to backtrack again etc. All in all it's super expensive, and I'm not really sure if it would actually work – Niklas B. – 2014-05-12T14:42:08.607

1

I make a comparison against my algorithm in my answer here: http://codegolf.stackexchange.com/a/26952/16337

– justhalf – 2014-05-12T14:46:41.530

@justhalf nvm, can't be done in constant space of course – Niklas B. – 2014-05-12T14:55:24.053

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 – 2014-05-13T02:34:54.180

1Well done. I had a similar idea but didn't think of just leaving the spaces in place and then mirroring them. – IchBinKeinBaum – 2014-05-13T18:25:44.477

Bravo for the new proven upper bound of 1.33! =D – justhalf – 2014-05-14T01:36:56.430

@justhalf I need to thank you for pointing out that the theoretical worst case wasn't worst case after all. – primo – 2014-05-14T03:46:32.683

I'm working on a hybrid approach of yours and mine. I'm trying to prove that the score is 1.25 =D – justhalf – 2014-05-14T03:52:28.373

7

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"

Howard

Posted 2014-05-11T14:08:39.473

Reputation: 23 109

Why didn't you use a Ruby built-in function to reverse a string? Would it change the score? – A.L – 2014-05-12T01:52:20.040

use, s[a], s[b] = s[b], s[a] – Thaha kp – 2014-05-14T08:44:11.793

5

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;
}

Anmol Singh Jaggi

Posted 2014-05-11T14:08:39.473

Reputation: 221

2I tested it. Works well! – bacchusbeale – 2014-05-12T06:23:39.627

2

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;
}

technosaurus

Posted 2014-05-11T14:08:39.473

Reputation: 231

3This is a code-only answer. Consider adding an explanation of what goes on in your code. – Justin – 2014-05-12T07:51:03.130

2

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"

draegtun

Posted 2014-05-11T14:08:39.473

Reputation: 1 592

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 – 2014-05-13T14:30:07.890

1

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

wrongu

Posted 2014-05-11T14:08:39.473

Reputation: 754

1

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

unclemeat

Posted 2014-05-11T14:08:39.473

Reputation: 2 302

-2

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

Spedwards

Posted 2014-05-11T14:08:39.473

Reputation: 159

3Yes, 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 – 2014-05-12T07:31:39.543

More to the point, it uses lots and lots of additional space. – Ben Millwood – 2014-05-15T20:50:51.017

Asked: 2014-05-11T14:08:39.473

Viewed: 2 845 times

Active: 2015-12-16T02:40:57.657