Visualisez l'algorithme euclidien

17

L'algorithme euclidien est un algorithme largement connu pour calculer le plus grand diviseur commun (GCD) de deux entiers positifs.

L'algorithme

Aux fins de ce défi, l'algorithme est décrit ci-dessous:

  1. Affichez les deux entrées sous forme de lignes adjacentes d'un certain caractère,
    par exemple une entrée de 3,4peut être représentée par les lignes adjacentes 000et0000

  2. Transformez les premiers length(short_line)caractères de la ligne la plus longue en un autre personnage, dites -
    maintenant à quoi il ressemble 000et---0

  3. Éliminez les premiers length(short_line)caractères de la ligne la plus longue.
    maintenant 000,0

  4. Répétez l' étape 2 et 3 jusqu'à ce que les deux ont une longueur égale, en utilisant les lignes courtes et plus longues après chaque itération, par exemple
    000, 0
    -00, 0
    00, 0
    -0, 0
    0,0

  5. Vous pouvez choisir de vous arrêter ici ou de continuer l'itération et de transformer l'une des lignes en ligne vide.

Chacune de ces étapes doit être séparée par un intervalle compris entre 0,3 s et 1,5 s.

Le défi

Écrivez un programme qui, étant donné deux nombres naturels en entrée, crée une sortie qui ressemble exactement à la sortie de l'algorithme ci-dessus. Vous pouvez utiliser d'autres caractères ASCII imprimables non blancs que 0et -, mais soyez cohérent et n'utilisez que deux caractères. Vous pouvez également utiliser des algorithmes alternatifs à condition que la sortie, y compris la synchronisation, soit exactement la même que celle produite par l'algorithme ci-dessus.

Exemples

Ceci est un exemple avec entrée 24,35, qui sont des nombres premiers, donc leur GCD est 1.

entrez la description de l'image ici

Ceci est un exemple avec entrée 16,42, qui ont le GCD 2.

entrez la description de l'image ici

Règles


Clarifications

  • Les lignes qui représentent les nombres doivent rester dans leur ordre d'origine, c'est-à-dire que les première et deuxième lignes de la première "trame" affichée doivent être respectivement la première et la deuxième lignes, dans toutes les trames suivantes.
  • Une fois l'algorithme terminé, aucune entité visible supplémentaire ne doit apparaître. Cependant, cela signifie également qu'il est correct de vider les lignes, si vous vous assurez que la dernière "trame" est affichée pendant au moins la même durée que toutes les autres trames avant la suppression.
busukxuan
la source
@WheatWizard grande suggestion, à ce sujet
busukxuan
Les lignes doivent-elles rester dans le même ordre relatif? Ou peuvent-ils être réorganisés entre les itérations? (Vérification car ce dernier est susceptible d'être beaucoup plus concis dans la plupart des langues, et donc j'ai besoin de savoir si je dois utiliser cette optimisation ou l'ignorer en raison de la violation du sepc.)
@ ais523 Oui, ils le font:-)
busukxuan
@ ais523 Oui, il est normal de le vider, mais assurez-vous que la dernière image a le même temps d'affichage que les autres images
busukxuan
1
@busukxuan Personnellement, je pense que j'autoriserais les espaces de fin, mais peut-être pas l'espace comme l'un des personnages "significatifs"
Luis Mendo

Réponses:

3

Gelée , 29 octets

VY“ñc‘ỌœS.⁸
1ẋǵ+M¦ṚÇt€2ǵ⁻/¿

Essayez-le en ligne!

Cela définit une fonction 2Ŀ(pas un programme complet; le lien TIO contient un pied de page qui convertit une fonction en programme) qui prend une liste de deux éléments en entrée et affiche la sortie à l'écran (l'une de nos méthodes légales d'E / S , et qui est en quelque sorte nécessaire pour ce défi car il parle de l'apparence à l'écran). Cela suppose que le programme est exécuté dans un terminal qui est conforme à la norme ANSI (j'ai utilisé gnome-terminalmais la plupart fonctionnera) et que le terminal est initialement vide (ce qui semble être le défaut le plus judicieux); notez que Essayez-le en ligne! n'est pas conforme à ces hypothèses, et donc la sortie y est déformée (j'ai exécuté le programme localement pour vérifier qu'il s'anime comme prévu). J'utilise 1où la question utilise 0, et2à la place de -.

Explication

Fonction d'assistance 1Ŀ (étant donné une liste de deux listes de chiffres, les affiche sur les première et deuxième lignes de l'écran, puis attend 0,5 seconde; renvoie son entrée)

VY“ñc‘ỌœS.⁸
V                   Convert each list of digits to an integer
 Y                  Separate these integers by newlines
  “ñc‘              {Output that; then restart with} the list [27, 99]
      Ọ             Convert codepoints to characters (i.e. "\x1bc"
       œS.          Wait (œS) 0.5 (.) seconds
          ⁸         {Output that; then return} the initial argument

La chaîne "\ x1bc", lorsqu'elle est envoyée à un terminal compatible ANSI, est interprétée comme un code de contrôle pour réinitialiser le terminal; cela efface l'écran et déplace le curseur dans le coin supérieur gauche (réinitialisant ainsi le terminal prêt pour la sortie suivante).

La fonction d'assistance est nommée 1Ŀ(Jelly génère automatiquement les noms de cette forme pour les fonctions, et en fait il n'y a pas d'autre moyen de les nommer), mais elle peut être désignée simplement comme à Çpartir du programme principal (car le langage a un raccourci pour les fonctions avec des nombres à proximité ).

Fonction principale 2Ŀ (implémente la tâche demandée dans la question)

1ẋǵ+M¦ṚÇt€2ǵ⁻/¿
1ẋ                  Convert input to unary
  Ç                 Call helper function (producing one animation frame)
   µ         µ  ¿   While
              ⁻/      the elements differ:
     M¦               Change the largest element
    +  Ṛ                by adding corresponding elements of the other element
        Ç             Call helper function (producing one animation frame)
         t€2          Delete all 2s from each side of each element
            Ç         Call helper function (producing one animation frame)

la source
6

JavaScript (ES6), 128 124 octets

t=0
f=
(a,b,o,c,d)=>setInterval(e=>{e=[b,d,a,c];o.data=`-0
-0`.replace(/./g,c=>c.repeat(e.pop()));c|d?c=d=0:a>b?a-=c=b:b-=d=a},1e3)
<form><input id=a><input id=b><button onclick=clearTimeout(t),t=f(+a.value,+b.value,o.firstChild)>Go!</button><pre id=o>

Neil
la source
3

Python 2 , 152 146 octets

import time
s,o='-0'
a,b=input()
while a*b:
 d,e=o*a,o*b
 if a>b:a=a-b;d=s*b+o*a
 elif b>a:b=b-a;e=s*a+o*b
 else:a=0
 print d+'\n'+e;time.sleep(1)

Essayez-le en ligne!


Prend deux entiers séparés par des virgules comme entrée

ovs
la source
Voilà une belle réponse.
ElPedro
2

Javascript (ES6), 215 194 ... 135 129 127 octets

a=>b=>F=(c=0)=>alert('-'[d='repeat'](e=c&a>b&&b)+'0'[d](a-=e)+`
`+'-'[d](f=c&a<b&&a)+'0'[d](b-=f))|a-b|c&&setTimeout(F,1e3,1-c)

Usage

Cela prend en compte une variation sur le curry. Pour l'utiliser, affectez d'abord la fonction à une variable (par exemple G), puis appelez-la comme ceci:

G(5)(6)()

Explication

Fonction quelque peu récursive qui s'appelle après 1 seconde tant que l'algorithme n'est pas terminé. Il garde une troisième variable cqui détermine si aet bdoit être modifié (si cest1 , il est temps de changer).

Tout d'abord, la fonction écrit quelque chose sur la console. Sic c'est le0 , il écrit deux chaînes de zéros avec une nouvelle ligne entre les deux. Puisque cest initialisé à 0, nous pouvons en profiter, et configurer des variables globales fet gqui contiennent souvent certaines chaînes dont nous avons besoin (comme 0etrepeat ).

Sinon, il crée une chaîne avec des zéros et des inconvénients. Toutes ces chaînes se composent de deux parties: d'abord certains (appelez ce montant A) moins, puis certains (appelez ce montant B) zéros, puis une nouvelle ligne, puis certains (appelez ce montant D) moins et enfin certains (appelez ce montant)E ) zéros.

Si la première entrée est plus petite que la deuxième entrée, nous devons supprimer les zéros de la deuxième entrée, donc A zéro, Bégal à la première entrée, Dégal à la première entrée et Eégal à la deuxième entrée moins la première entrée. Si la première entrée n'est pas inférieure à la deuxième entrée, l'inverse s'applique (A est la deuxième entrée, Best la première entrée moins la deuxième entrée, etc.).

Avec ces nouvelles valeurs pour l'entrée et une variable commutée c, il est prévu de rappeler la fonction dans1e3 millisecondes, ce qui équivaut à une seconde.

Remarques

  • Les usages alert pour la sortie
  • Les usages 0 et- , comme dans les exemples
  • Le délai entre les étapes est de 1000 ms (1 seconde)
  • Après la première étape, la fonction retournera (en raison de la nature de JavaScript) un certain nombre qui doit être ignoré
  • La version sur TIO sort tout en même temps, coller le code dans la console du navigateur prendra correctement en compte les retards

Essayez-le en ligne

Essayez-le ici!

Luc
la source
2

Python 2 , 208 204 194 octets

-4 avec merci à @math_junkie pour l'astuce sournoise avec time.sleep

-10 avec merci à @busukxuan pour avoir clarifié la règle "écran clair".

def z(a,b,y='-',w=1):
 import time;c,d,n,s='0'*a,'0'*b,'\n',time.sleep
 if w:print c+n+d;s(1)
 if b>a:d=y*a+d[a:]
 else:c=y*b+c[b:]
 print c+n+d;s(1)
 if c!=d:z(len(c),len(d),('','-')[y!='-'],0)

Essayez-le en ligne!

Je suis sûr que cela pourrait être plus joué. Cela me fait mal de dupliquer le printet la forboucle pour créer la pause mais je ne trouve pas de solution pour le moment.

Remarques

  • La pause utilise maintenant un indice de @math_junkie
  • Ne fonctionne pas entièrement sur TIO car il stocke la sortie et la vide à la fin du programme. Fonctionne bien dans la console.
ElPedro
la source
1
Vous devriez être capable d'enregistrer quelques octets en utilisant import time, s=time.sleepet s(1)au lieu d'une boucle pour le délai
math junkie
Merci @math_junkie - J'ai essayé la plupart des combinaisons en utilisant time.sleepmais j'ai manqué celle-là. Je vais essayer.
ElPedro
@math_junkie - vient à 215 pour moi. Peut-être que je manque quelque chose de stupide. Pouvez-vous publier un exemple sur Try it Online ?
ElPedro
1
Essayez-le ici
math junkie
1

perl, 161 149 octets

... sans indentations ni nouvelles lignes:

($a,$b)=map 0 x$_,@ARGV;
sub p{say"\n$a\n$b";sleep 1}p;
while($a ne$b){
  ($A,$B)=$b lt$a?(\$a,\$b):(\$b,\$a);
  map$$A=~s/0/-/,1..length$$B;
  p;
  $$A=~s/-//g;
  p
}

Mettez-le dans un fichier gcd.pl et exécutez comme ceci:

perl -M5.010 gcd.pl 16 42
Kjetil S.
la source
1
Le -M5.010drapeau de perl est gratuit, vous pouvez donc économiser quelques octets en utilisant sayover print…\n. De plus, je suis presque sûr qu'il est plus simple de donner un nom à votre sous-programme anonyme, plutôt que de le stocker dans une variable.
Thx à ais523 pour des conseils pour raser 12 octets
Kjetil S.
1

GNU Sed (avec eextension xec), 88

Le score inclut +3 pour les -zrfoptions sed.

p
:
x
esleep 1
g
ta
:a
s/o+//p
t
s/^((O+)(O+)\n\2\b|(O+)\n\4\B)/\L\2\U\3\4\n\2\L\4\U/p
t

L'entrée est donnée sous la forme de deux entiers unaires séparés par une nouvelle ligne, en utilisant les majuscules O comme chiffres.

Par exemple, l'exemple 16, 42 peut être exécuté comme:

printf "%0*d\n%0*d\n" 16 0 42 0 | tr 0 O | sed -znrf euclidvis.sed

Selon les derniers commentaires, je n'efface pas l'écran entre les itérations.

Traumatisme numérique
la source
0

V , 47 44 octets

Àé0á
Àé0Hqwmmjlhmmkl@wqòHî@w
gs`mlhv0r-gsÓ-ò

Essayez-le en ligne!

L'en-tête et le pied de page sur TIO se modifient simplement gspour copier les deux lignes actuelles au bas de l'écran, puis supprimez les deux premières à la fin. Cela visualise l'opération pour TIO, mais si vous l'exécutiez en V (sans l'en-tête et le pied de page), il attendrait juste une seconde entre chaque opération.

Àé0                     " Print (Arg1) zeroes
   á                    " Newline
Àé0                     " Print (Arg2) zeroes
   H                    " Go home
    qwmmjlhmmkl@wq      " Store a recursive macro in w that finds the shorter line
                  ò     " recursively
                   Hî@w " find the longest line
gs                      " wait a second
  `mlhv0r-              " replace the zeroes of the long line with -
          gs            " wait a second
            Ó-          " delete all -
              ò         " end recursion
nmjcman101
la source
Avez-vous vraiment besoin de la fin ò?
Kritixi Lithos
Il se bloque sans lui, je ne sais pas pourquoi. Je vais attendre d'avoir un ordinateur avec V dessus pour déboguer n'importe quoi
nmjcman101