Inverser l'ordre des mots dans une chaîne en place

17

La tâche

  • Vous obtenez une chaîne mutable qui correspond [a-z]+( [a-z]+)*.
  • Vous devez le muter dans la chaîne qui contient les mêmes mots, mais dans l'ordre inverse, pour que "bonjour tout le monde" devienne "tout le monde bonjour".
  • Vous n'êtes pas autorisé à utiliser plus d'une quantité constante de mémoire supplémentaire (donc pas de copier la chaîne entière ou un mot entier dans un tampon que vous venez d'allouer).
  • Il n'y a pas de contraintes de temps. Être désespérément inefficace ne nuira pas à votre score.
  • Si la langue de votre choix ne permet pas la mutation des chaînes, les tableaux de caractères sont un substitut acceptable.

Ton score

  • Votre score est compté uniquement sur le nombre d'assignations que vous faites aux éléments de chaîne (les petits scores sont les meilleurs). Si vous utilisez une fonction de bibliothèque qui écrit dans la chaîne, ses écritures comptent également.
  • Supposons que le nombre d'affectations dont vous avez besoin pour l'entrée s soit n (s) . Votre score est alors le maximum (pédantiquement, supremum) sur toutes les entrées s (correspondant à l'expression régulière spécifiée ci-dessus) de n (s) / longueur (s) . Si vous ne pouvez pas calculer cela avec précision, vous pouvez utiliser la borne supérieure la plus basse que vous pouvez prouver.
  • Vous pouvez rompre une égalité si vous pouvez prouver que votre algorithme utilise asymptotiquement moins d'affectations (cela peut arriver même si vous avez le même score, voir ci-dessous). Si vous ne pouvez pas le faire, vous pouvez rompre une égalité en montrant que vous utilisez moins de mémoire supplémentaire. Cependant, la première condition de départage est toujours prioritaire.
  • Pour certaines entrées, chaque personnage doit changer, il n'est donc pas possible de marquer moins de 1.
  • Je peux penser à un algorithme simple avec un score de 2 (mais je n'y entre pas).

Notes sur suprema et liens

  • Un supremum d'un ensemble de nombres est le plus petit nombre qui n'est pas inférieur à aucun d'entre eux. Cela ressemble beaucoup au maximum d'un ensemble, sauf que certains ensembles infinis comme {2/3, 3/4, 4/5, 5/6, ...} n'ont pas d'élément maximum unique, mais auront toujours un supremum, dans ce cas 1.
  • Si vous parvenez à «enregistrer» seulement un nombre constant d'affectations sur mon algorithme de score 2 (disons), votre score sera toujours de 2, car vous obtiendrez arbitrairement près de 2 plus votre entrée sera importante. Cependant, vous gagnez au tie-break s'il s'agit de cela.
code-challenge Ben Millwood
la source
1
Je serais un peu triste si tout cela se résumait à des soumissions brisantes de score 2 sur leur utilisation de la mémoire. J'ai surtout posté cette question en me demandant si quelqu'un réussirait à marquer moins de 2.
Ben Millwood
1
Je n'ai pas de preuve formelle, mais mon intuition me dit qu'avec la restriction d'espace constant, il est impossible de faire mieux que 2. Si vous ne comptez que les déclarations de variables pour l'espace, je pourrais tricher et créer une fonction récursive. mais cela ne fait que masquer l' little-omega(1)espace en le mettant sur la pile.
falseu
2
@bacchusbeale oui, mais c'est une mémoire supplémentaire constante.
Martin Ender
4
Si vous appliquez strictement les règles, il est impossible d'écrire un tel programme. La chaîne peut être de longueur arbitraire et vous aurez besoin d'au moins une sorte de variable qui stocke un index. Il me suffit donc de rendre la chaîne suffisamment longue pour dépasser les limites de votre variable. Pour stocker avec succès au moins un index, votre mémoire nécessaire augmentera avec la longueur de la chaîne.
IchBinKeinBaum
3
@IchBinKeinBaum a raison, il est impossible d'effectuer cette tâche avec O(1)un espace supplémentaire. Vous avez besoin d' O(log n)espace pour stocker une position d'index, car un entier de k bits ne peut y être stocké que pour des chaînes d'une longueur allant jusqu'à 2^k. Limiter la longueur des chaînes rend le défi plutôt inutile, car chaque algorithme nécessiterait de l' O(1)espace de cette façon.
Dennis

Réponses:

4

Python, Score: 2 1,5 1,25

Ceci est la directe combinaison entre la réponse de primo et ma réponse. Alors merci aussi à lui!

La preuve est toujours en cours, mais voici le code avec lequel jouer! Si vous pouvez trouver un contre-exemple de score supérieur à 1,25 (ou s'il y a un bug), faites le moi savoir!

Actuellement, le pire des cas est:

aa ... aa dcb ... cbd

où il y a exactement n de chacune des lettres "a", "b", "c" et "" (espace), et exactement deux "d" s. La longueur de la chaîne est 4n + 2 et le nombre d'affectations est 5n + 2 , ce qui donne un score de 5/4 = 1,25 .

L'algorithme fonctionne en deux étapes:

  1. Trouvez ktel que string[k]etstring[n-1-k] sont des limites de mots
  2. Exécutez n'importe quel algorithme d'inversion de mot string[:k]+string[n-1-k:](c'est-à-dire, concaténation des premier ket dernier kcaractères) avec une petite modification.

où nest la longueur de la chaîne.

L'amélioration apportée par cet algorithme provient de la "petite modification" à l'étape 2. C'est essentiellement la connaissance que dans la chaîne concaténée, les caractères en position k et k+1sont des limites de mot (ce qui signifie qu'ils sont des espaces ou le premier / dernier caractère d'un mot), et nous pouvons donc remplacer directement les caractères en position ket k+1par le caractère correspondant dans la chaîne finale, en économisant quelques affectations. Cela supprime le pire des cas de l'algorithme d'inversion de mot hôte

Il y a des cas où nous ne pouvons pas réellement trouver un tel k, dans ce cas, nous exécutons simplement "n'importe quel algorithme d'inversion de mot" sur la chaîne entière.

Le code est long pour gérer ces quatre cas lors de l'exécution de l'algorithme d'inversion de mot sur la chaîne "concaténée":

  1. Quand kest introuvable ( f_long = -2)
  2. Quand string[k] != ' ' and string[n-1-k] != ' ' ( f_long = 0)
  3. Quand string[k] != ' ' and string[n-1-k] == ' ' ( f_long = 1)
  4. Quand string[k] == ' ' and string[n-1-k] != ' ' ( f_long = -1)

Je suis sûr que le code peut être raccourci. Actuellement, c'est long parce que je n'avais pas une image claire de tout l'algorithme au début. Je suis sûr que l'on peut le concevoir pour être représenté dans un code plus court =)

Sample run (le premier est le mien, le second est celui de primo):

Entrez la chaîne: a bc def ghij
"ghij def bc a": 9, 13, 0,692
"ghij def bc a": 9, 13, 0,692
Entrez la chaîne: ab cdefghijklmnopqrstuvw xyz
"zyxwvutsrqponmlkjihgf edc ab": 50, 50, 1.000
"zyxwvutsrqponmlkjihgf edc ab": 51, 50, 1.020
Entrez la chaîne: abcdefg hijklmnopqrstuvwx
"hijklmnopqrstuvwx gfedcb a": 38, 31, 1.226
"hijklmnopqrstuvwx gfedcb a": 38, 31, 1.226
Entrez la chaîne: 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
Entrez chaîne: aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd
"Dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaa a": 502, 402, 1.249
"Dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaa a": 502, 402, 1.249

Vous pouvez voir que le score est presque le même, à l'exception du pire cas de l'algorithme d'inversion de mot hôte dans le troisième exemple, pour lequel mon approche donne un score inférieur à 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

Le nombre exact d'affectations peut être approximé par la formule:

n <= 1,5 * longueur (chaîne)

le pire des cas étant:

abcdefghi jklmnopqrstuvwxyzzz

avec 55 affectations sur une chaîne de longueur 37.

L'idée est similaire à la précédente, c'est juste que dans cette version j'ai essayé de trouver le préfixe et le suffixe aux limites des mots avec une différence de longueur au plus 1. Ensuite, je lance mon algorithme précédent sur ce préfixe et ce suffixe (imaginez-les comme étant concaténés) . Continuez ensuite sur la partie non traitée.

Par exemple, pour le pire des cas précédent:

ab | ab | c

nous allons d'abord faire l'inversion des mots sur "ab" et "c" (4 affectations) pour être:

c | ab | ab

Nous savons qu'à la frontière, c'était de l'espace (il y a beaucoup de cas à gérer, mais vous pouvez le faire), nous n'avons donc pas besoin de coder l'espace à la frontière, c'est la principale amélioration par rapport à l'algorithme précédent .

Enfin, nous courons sur les quatre caractères du milieu pour obtenir:

cba ab

au total 8 affectations, l'optimum pour ce cas, puisque les 8 caractères ont changé.

Cela élimine le pire des cas dans l'algorithme précédent puisque le pire des cas dans l'algorithme précédent est éliminé.

Voir un exemple d'exécution (et comparaison avec la réponse de @ primo - c'est la deuxième ligne):

Entrez une chaîne: je peux tout faire
"je peux tout faire": 20, 17
"je peux tout faire": 17, 17
Entrez la chaîne: abcdef ghijklmnopqrs
"ghijklmnopqrs fedcb a": 37, 25
"ghijklmnopqrs fedcb a": 31, 25
Entrez la chaîne: abcdef ghijklmnopqrst
"ghijklmnopqrst fedcb a": 38, 26
"ghijklmnopqrst fedcb a": 32, 26
Entrez une chaîne: abcdefghi jklmnozzzzzzzzzzzzzzzzzzz
"jklmnozzzzzzzzzzzzzzzzz ihgfedcb a": 59, 41
"jklmnozzzzzzzzzzzzzzzzz ihgfedcb a": 45, 41
Entrez la chaîne: abcdefghi jklmnopqrstuvwxyzzz
"jklmnopqrstuvwxyzzz ihgfedcb a": 55, 37
"jklmnopqrstuvwxyzzz ihgfedcb a": 45, 37
Entrez la chaîne: ab ababababababac
"cababababababa ab": 30, 30
"cababababababa ab": 31, 30
Entrez une chaîne: ab abababababababc
"cbababababababa ab": 32, 32
"cbababababababa ab": 33, 32
Entrez la chaîne: abc d abc
"abc d abc": 0, 9
"abc d abc": 0, 9
Entrez la chaîne: abc dca
"acd abc": 6, 9
"acd abc": 4, 9
Entrez la chaîne: abc ababababababc
"abc cababababababa": 7, 29
"abc cababababababa": 5, 29

la réponse de primo est généralement meilleure, bien que dans certains cas, je puisse avoir un avantage de 1 point =)

De plus, son code est beaucoup plus court que le mien, 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: asymptotiquement 2, en cas normal beaucoup moins

l'ancien code a été supprimé en raison d'une contrainte d'espace

L'idée est de parcourir chaque index, et pour chaque index i, nous prenons le caractère, calculons la nouvelle position j, mémorisons le caractère à la position j, assignons le caractère à ià jet répétons avec le caractère à l'index j. Puisque nous avons besoin des informations d'espace pour calculer la nouvelle position, j'encode l'ancien espace comme la version majuscule de la nouvelle lettre et le nouvel espace comme '@'.

juste la moitié
la source
Si vous pouvez réduire le nombre de mots dans le pire des cas en termes de longueur de la chaîne (par exemple, length(string)/3en forçant chaque mot dans le pire des cas à être au moins de longueur 2 d'une manière ou d'une autre), alors le score sera inférieur à 2 (dans l'exemple ci-dessus ce sera 1,67)
juste la moitié
1
J'ai ajouté un compteur de swap au mien; le vôtre bat le mien pour le pire des cas (mais pas le cas général). Besoin de trouver un moyen de résoudre ce problème;)
primo
Ligne 127: if any(process_loop(...) for j in range(...))les affectations de ces boucles de processus ne devraient-elles pas être comptées?
primo
Cela ne fait aucune tâche. Si vous voyez, le dry_runparamètre est défini sur non nul (la valeur à i). À l'intérieur du process_loop, s'il dry_runest différent de zéro, il ne fera aucune affectation.
moitié
1
Je pense que j'ai une meilleure image maintenant. En substance, deux méthodes distinctes avec des comportements de pire cas différents sont combinées, afin d'éliminer le pire des deux cas. Je l'aime. Je pense qu'en général, c'est peut-être la meilleure approche à adopter, bien qu'il semble probable que deux (ou plus) méthodes complètement différentes pourraient être combinées pour réduire encore plus le pire des cas.
primo
14

Perl, score 1,3̅

Pour chaque caractère non espace, une affectation est effectuée et pour chaque caractère espace deux affectations. Étant donné que les caractères d'espace ne peuvent pas représenter plus de la moitié du nombre total de caractères, le score le plus défavorable est de 1,5 .

L'algorithme n'a pas changé, mais je peux prouver une limite supérieure inférieure. Faisons deux observations:

  1. Les espaces situés directement en face des espaces n'ont pas besoin d'être échangés.
  2. Les mots à caractère unique directement en face des espaces ne sont pas échangés pendant la phase principale, mais une seule fois à la fin.

On peut alors voir que le «pire cas» théorique avec 1/2 espace asymptotique n'est pas du tout le pire: 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

En fait, c'est un assez bon cas.

Afin d'empêcher l'observation un et deux ci-dessus, chaque mot d'un caractère devrait être repositionné au milieu d'un mot de trois caractères ou plus. Cela suggérerait un pire cas contenant 1/3 espaces asymptotiquement: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

Ou de manière équivalente, seuls les mots à deux caractères: 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

Parce que le pire des cas contient asymptotiquement 1/3 d'espaces, le score du pire cas devient 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;

Modifier: Ajout d'un compteur de swap et du ratio.

L'entrée provient de stdin. Exemple d'utilisation:

$ 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

Méthode

Pour commencer, le premier caractère de la chaîne est déplacé vers sa destination finale. Le personnage qui vient d'être remplacé est ensuite déplacé vers sa destination, etc. Cela continue jusqu'à ce que l'une des deux conditions soit remplie:

  1. Le personnage doit être échangé avec un espace.
    Lorsque cela se produit, le personnage n'est pas échangé avec l'espace, mais plutôt dans la position miroir de l'espace. L'algorithme continue à partir de cette position.
  2. Un cycle a été atteint.
    Lorsque la cible revient à la position de départ initiale du cycle en cours, le prochain caractère non permuté (ou plutôt, n'importe quel caractère non permuté ferait) doit être trouvé. Pour ce faire, sous des contraintes de mémoire constantes, tous les échanges qui ont été effectués jusqu'à ce point sont retracés.

Après cette phase, chaque personnage non-espace a été déplacé au plus une fois. Pour terminer, tous les caractères d'espace sont échangés avec les caractères à leur position miroir, ce qui nécessite deux opérations d'affectation par espace.

primo
la source
Wow, c'est cool. Pouvez-vous expliquer pourquoi mettre le personnage à la position miroir de l'espace donne une réponse correcte?
moitié
1
@Niklas, je ne pense pas que ce soit possible. Parce que pour faire le retour en arrière, vous avez besoin des informations sur la position de l'espace. Si vous remplacez ces informations, vous ne pouvez pas faire de retour en arrière.
juste la moitié
1
Je fais une comparaison avec mon algorithme dans ma réponse ici: codegolf.stackexchange.com/a/26952/16337
juste la moitié
1
@justhalf Dans la chaîne finale, tous les espaces seront dans leur position miroir. Par conséquent, nous pouvons utiliser cette position en toute sécurité pour stocker le caractère qui remplace l'espace et les changer à la fin.
primo
1
Bien joué. J'ai eu une idée similaire, mais je n'ai pas pensé à laisser les espaces en place et à les refléter.
IchBinKeinBaum
7

Ruby, score 2

En entrée un algorithme très basique. Il inverse d'abord la chaîne entière puis inverse à nouveau chaque mot de la chaîne. Dans le pire des cas (un mot, nombre pair de caractères) le score devient 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
la source
Pourquoi n'avez-vous pas utilisé une fonction intégrée Ruby pour inverser une chaîne? Cela changerait-il le score?
AL
utilisation, s [a], s [b] = s [b], s [a]
Thaha kp
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
la source
2
Je l'ai testé. Fonctionne bien!
bacchusbeale
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
]

Je ne suis pas clair sur le score pour cela. Il n'y a pas d'affectation de chaîne directe dans ce code. Tout est géré par l'unreverse/part qui fait la réversibilité en place à l'intérieur et initialement sur l'ensemble de la chaîne.

Quelques détails sur le code:

  • Boucle à travers la chaîne ( series) jusqu'à ce qu'elle atteigne letail?

  • Première fois en boucle, inversez complètement la chaîne - reverse/part series tail series(ce qui est le même que reverse series)

  • Inversez ensuite chaque mot trouvé sur les itérations suivantes - reverse/part series find series space

  • Une fois le mot épuisé trouvé, retournez-le tail seriesafin qu'il inverse le dernier mot de la chaîne -reverse/part series tail series

Rebol permet de parcourir une chaîne via un pointeur interne . Vous pouvez le voir à series: next f(déplacer le pointeur vers l'espace après le début du mot suivant) et series: head series(réinitialise le pointeur à la tête).

Voir la série pour plus d'informations.

Exemple d'utilisation dans la console Rebol:

>> 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
la source
Lors de la première passe, chaque personnage est repositionné une fois, et lors de la deuxième passe, chaque caractère non spatial est repositionné à nouveau. Pour une entrée arbitrairement grande avec relativement peu d'espaces, le score approche 2.
primo
2

C: Score 2

Cela retourne une fois la chaîne entière puis inverse chaque mot.

#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
la source
3
Ceci est une réponse uniquement en code. Pensez à ajouter une explication de ce qui se passe dans votre code.
Justin
1

Python: score 2

Presque identique à l'algorithme d'Howard, mais effectue les étapes d'inversion dans le sens inverse (retourne d'abord les mots puis retourne la chaîne entière). Occasion mémoire supplémentaire est de 3 octets des variables de taille: i, j, et t. Techniquement, findet lenutilisent certaines variables internes, mais elles pourraient tout aussi bien être réutilisées iou jsans perte de fonction.

édition rapide: économiser sur les affectations de chaînes en n'échangeant que lorsque les caractères diffèrent, donc je peux récupérer quelques points supplémentaires de la 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))
falseu
la source
1

Lot

J'avoue ne pas bien comprendre le score (je pense que c'est deux) .. mais je dirai - ça fait le truc .

@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!

L'entrée est considérée comme la première valeur d'entrée standard et doit donc être entourée de guillemets -
appelez: script.bat "hello there everyone"
out:everyone there hello .

Peut-être que quelqu'un d'autre peut me marquer (en supposant que je ne me suis pas disqualifié d'une autre manière).

dégrader
la source
-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'

J'ai l'impression étrange d'avoir raté quelque chose ...

Spedwards
la source
3
Oui, ce n'est pas en place, car vous ne modifiez pas la chaîne d'entrée. Comme cela n'est pas possible en JavaScript, vous devez émuler des chaînes avec un tableau de caractères (c'est-à-dire des entiers de point de code ou des chaînes à un seul caractère).
Martin Ender
Plus précisément, il utilise beaucoup, beaucoup d'espace supplémentaire.
Ben Millwood