Implémenter QuickSort dans BrainF *** [fermé]

32

Comme discuté dans le salon sur Stack Overflow:

si vous ne pouvez pas implémenter l'algorithme Quicksort donné en.wikipedia.org/wiki/Quicksort dans n'importe quelle langue que vous avez une connaissance minimale, vous voudrez peut-être envisager une profession différente. @sbi

mais SBI a également noté que BrainF *** était peut-être une exception.

Voici donc le puzzle / défi: implémentez QuickSort dans BrainF *** . La mise en œuvre doit

  • être interprété par ceci et / ou par les interprètes ici (pour les gros scripts)
  • implémenter l'algorithme comme décrit sur Wikipedia - si possible comme un tri sur place
  • trier la liste suivante d'entiers: [0,4,6,4,2,3,9,2,3,6,5,3] et imprimer le résultat
Ronald
la source
En cherchant un peu, je suis en mesure de trouver une implémentation , mais elle est de 6 Ko (et compilée à partir de Haskell).
Peter Taylor
@Peter en fait, l'implémentation de brainfuck est de 474,2 K à l'intérieur de l'archive - ce qui est un peu plus grand que ce à quoi je m'attendais (et trop grand pour l'interprète en ligne). Peut - être que je devrais changer l'interprète cible .. (mais j'aime voir écrit à la main quelque chose)
Ronald
22
Je parie que je pourrais faire le tri à la place à la place et que personne ne regardant le code ne connaîtrait la différence ...
Peter Olson
1
@Keith l'idée est d'implémenter vraiment QuickSort, pas n'importe quel type qui fonctionnera ... :-)
Ronald
1
@Peter Of The Corn: Nous découvririons une sorte de bulle par la mauvaise performance.
utilisateur inconnu

Réponses:

55

BrainF * (697 octets)

>>>>>>>>,[>,]<[[>>>+<<<-]>[<+>-]<+<]>[<<<<<<<<+>>>>>>>>-]<<<<<<<<[[>>+
>+>>+<<<<<-]>>[<<+>>-]<[>+>>+>>+<<<<<-]>[<+>-]>>>>[-<->]+<[>->+<<-[>>-
<<[-]]]>[<+>-]>[<<+>>-]<+<[->-<<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+>>>>]>[-<
<+[-[>+<-]<-[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<]<<[>>+<<-]>[>[>+>
>+<<<-]>[<+>-]>>>>>>[<+<+>>-]<[>+<-]<<<[>+>[<-]<[<]>>[<<+>[-]+>-]>-<<-
]>>[-]+<<<[->>+<<]>>[->-<<<<<[>+<-]<[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]
<<]>[[-]<<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-]>>>>>[-[>>[<<<+>>>-]<[>+<-]
<-[>+<-]>]<<[[>>+<<-]<]]>]<<<<<<-]>[>>>>>>+<<<<<<-]<<[[>>>>>>>+<<<<<<<
-]>[<+>-]<+<]<[[>>>>>>>>+<<<<<<<<-]>>[<+>-]<+<<]>+>[<-<<[>+<-]<[<]>[[<
+>-]>]>>>[<<<<+>>>>-]<<[<+>-]>>]<[-<<+>>]>>>]<<<<<<]>>>>>>>>>>>[.>]

Voici une version annotée. Afin de garder une trace de ce qui devait se produire lors de son développement, j'ai utilisé une notation de commentaire qui ressemble à ceci:|a|b=0|c=A0|@d|A0|A1|```|

|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)

La mémoire est disposée avec une pile croissante de partitions à traiter à gauche, un espace de travail au centre et le tableau trié à droite. L'indexation des tableaux est gérée en déplaçant un "bus de données" contenant l'index et l'espace de travail à travers le tableau. Ainsi, par exemple, un bus à 3 voies de |i|data|0|A0|A1|A2, deviendra |A0|i-1|data|0|A1|A2après un décalage d'un. Le partitionnement est effectué en gardant le bus entre les éléments haut et bas.
Voici la version complète:

Get input
>>>>>>>> ,[>,]                      |A0|A1|```|An|@0|
Count items
<[ [>>>+<<<-]>[<+>-]<+ <]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
>[<<<<<<<<+>>>>>>>>-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
<<<<<<<<[
  Copy K1 to a&c via Z
  [>>+>+>>+<<<<<-]>>[<<+>>-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&d via Z
  <[>+>>+>>+<<<<<-]>[<+>-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  >>>>[-<->]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +<[>- >+<<-[>>-<<[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  >[<+>-]>[<<+>>-]<+<      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [->-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    <<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  >>>>]>[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    <<+[ -[>+<-]<-[>+<-]>>>>>>>>      (dec J as we move)
      [<<<<<<<<+>>>>>>>>-]<<<<<< ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    <<[>>+<<-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    >[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      >[>+>>+<<<-]>[<+>-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      >>>>>>[<+<+>>-]<[>+<-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g 
      <<<[ >+>[<-]<[<]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g 
        >>[<<+>[-]+>-]>-<<-]
      set g to 1; if d: set f 
      >>[-]+<<< [->>+<<]
      If Aq LT Ap move Aq across Bus
      >>[->- <<<<<[>+<-] <[>+<-] >>>>>>>>
        [<<<<<<<<+>>>>>>>>-] <<]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq                
      >[[-] <<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      >>>>>[-
        & While J shuttle right
        [>>[<<<+>>>-]<[>+<-]<-[>+<-]>] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        <<[ [>>+<<-] < ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]>]
    Either bus moved or last element swapped; reduce J in either case
    <<<<<<-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    >[>>>>>>+<<<<<<-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    <<[ [>>>>>>>+<<<<<<<-]>[<+>-]<+ <]     
    <[ [>>>>>>>>+<<<<<<<<-]>>[<+>-]<+ <<] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    >+>[<-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      <<[>+<-] <[<]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p| 
      shift left until return to 0 at K0;
      >[ [<+>-] >]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      >>>[<<<<+>>>>-]<<[<+>-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty) 
    >>]<[- <<+>>]              
  >>>]  End if !empty
<<<<<<] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
>>>>>>>>>>>[.>]
AShelly
la source
Je travaillais sur une solution similaire mais je ne pouvais pas vraiment la faire fonctionner. Super idée de faire le partitionnement de cette façon. Je retirais un élément à la fois et le remplaçais, et il est devenu assez lourd assez rapidement. J'étais également à 1,5 km, donc vous m'avez aussi détruit sur l'efficacité.
captncraig
1
Tout dans BF devient assez lourd assez rapidement :) Même des choses apparemment simples comme comment faire un travail efficace ont if (i<j) {} else {}pris plusieurs tentatives pour bien faire les choses . Et les cas marginaux sont des tueurs. Je ne sais pas combien de fois j'ai pensé "juste cette petite chose qui restait ...", puis j'ai découvert un cas de test qui a causé un autre travail de plusieurs heures. Je pense que je peux le réduire de quelques dizaines de caractères, mais je ne suis pas sûr de vouloir faire l'effort.
AShelly
Un mot: wow! Honnêtement, je ne pensais pas que c'était humainement possible. Je vais exécuter quelques entrées pour voir comment cela fonctionne :-)
Ronald
Épique! Juste épique!
vsz
la seule chose à dire est "putain de merde!"
Math chiller
11

brainfuck (178 octets)

Même si le brainfuck est lourd, cela aide à travailler avec le grain de la langue. Demandez-vous "Dois-je stocker cette valeur explicitement dans une cellule?" Vous pouvez souvent gagner en vitesse et en concision en faisant quelque chose de plus subtil. Et lorsque la valeur est un index de tableau (ou un nombre naturel arbitraire), elle peut ne pas tenir dans une cellule. Bien sûr, vous pouvez simplement accepter cela comme une limite de votre programme. Mais la conception de votre programme pour gérer de grandes valeurs l'améliorera souvent par d'autres moyens.

Comme d'habitude, ma première version de travail était deux fois plus longue que nécessaire - 392 octets. De nombreuses modifications et deux ou trois réécritures majeures ont produit cette version relativement gracieuse de 178 octets. (Bien qu'amusamment, une sorte de temps linéaire n'est que de 40 octets.)

>+>>>>>,[>+>>,]>+[--[+<<<-]<[[<+>-]<[<[->[<<<+>>>>+<-]<<[>>+>[->]<<[<]
<-]>]>>>+<[[-]<[>+<-]<]>[[>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]<<[<<<]>[>>[>>
>]<+<<[<<<]>-]]+<<<]]+[->>>]>>]>[brainfuck.org>>>]

Les valeurs d'entrée sont espacées toutes les trois cellules: pour chaque cellule de valeur (V), il y a une cellule (L) abel (utilisée pour la navigation) et une cellule de plus pour (S) l'espace de capture. La disposition générale du tableau est

0 1 0 0 0 SVLSVL ... SVL 0 0 0 0 0 0 ...

Initialement, toutes les cellules L sont définies sur 1, pour marquer les parties du tableau qui doivent encore être triées. Lorsque nous avons terminé de partitionner un sous-tableau, nous le divisons en sous-réseaux plus petits en définissant la cellule L de son pivot sur 0, puis localisons la cellule L la plus à droite qui est toujours 1 et partitionnons ce sous-tableau suivant. Curieusement, c'est toute la comptabilité dont nous avons besoin pour gérer correctement le traitement récursif des sous-réseaux. Lorsque toutes les cellules L ont été mises à zéro, l'ensemble du tableau est trié.

Pour partitionner un sous-tableau, nous tirons sa valeur la plus à droite dans une cellule S pour agir comme pivot, et l'amener (et la cellule V vide correspondante) à gauche, en le comparant aux autres valeurs du sous-tableau et en échangeant si nécessaire. À la fin, le pivot est de nouveau échangé, en utilisant le même code de swap (ce qui économise environ 50 octets). Pendant le partitionnement, deux cellules L supplémentaires sont maintenues à 0, pour marquer les deux cellules qui peuvent avoir besoin d'être échangées l'une avec l'autre; à la fin du partitionnement, le 0 gauche fusionnera avec le 0 à gauche du sous-tableau, et le 0 droit finira par marquer son pivot. Ce processus laisse également un 1 supplémentaire dans la cellule L à droite du sous-tableau; la boucle principale commence et se termine à cette cellule.

>+>>>>>,[>+>>,]>+[                      set up; for each subarray:
    --[+<<<-]<[                         find the subarray; if it exists:
        [<+>-]<[                        S=pivot; while pivot is in S:
            <[                          if not at end of subarray
                ->[<<<+>>>>+<-]         move pivot left (and copy it) 
                <<[>>+>[->]<<[<]<-]>    move value to S and compare with pivot
            ]>>>+<[[-]<[>+<-]<]>[       if pivot greater then set V=S; else:
                [>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]     swap smaller value into V
                <<[<<<]>[>>[>>>]<+<<[<<<]>-]        swap S into its place
            ]+<<<                       end else and set S=1 for return path
        ]                               subarray done (pivot was swapped in)
    ]+[->>>]>>                          end "if subarray exists"; go to right
]>[brainfuck.org>>>]                    done sorting whole array; output it
Daniel Cristofani
la source
1
Impressionnant. C'est tellement plus propre lorsque vous travaillez avec les idiomes de BF, au lieu d'essayer de le forcer à agir comme un langage procédural, comme je l'ai fait.
AShelly
C'est; mais la version 4 à 392 octets était également idiomatique. Il s'agit de la version 39 ou plus. :)
Daniel Cristofani