Der Euklidische Algorithmus ist ein weit verbreiteter Algorithmus zur Berechnung des größten gemeinsamen Divisors (GCD) zweier positiver Ganzzahlen.

Der Algorithmus

Für diese Herausforderung wird der Algorithmus wie folgt beschrieben:

1. Zeigen Sie die beiden Eingaben als benachbarte Zeilen eines bestimmten Zeichens an,
   z. B. kann eine Eingabe von 3,4durch die benachbarten Zeilen 000und dargestellt werden0000

2. Verwandeln Sie die ersten length(short_line)Zeichen in der längeren Zeile in ein anderes Zeichen, sagen -
   Sie , jetzt sieht es aus wie 000und---0

3. Beseitigen Sie die ersten length(short_line)Zeichen in der längeren Zeile.
   jetzt 000,0

4. Wiederholen Sie Schritt 2 und 3 , bis die beiden gleich Länge haben, mit den kürzeren und längeren Linien nach jeder Iteration, beispielsweise
   000, 0
-00, 0
00, 0
-0, 0
0,0

5. Sie können wählen, ob Sie hier anhalten oder die Iteration fortsetzen und eine der Zeilen in eine leere Zeile umwandeln möchten.

Jeder dieser Schritte sollte durch ein Intervall zwischen 0,3 und 1,5 Sekunden getrennt sein.

Die Herausforderung

Schreiben Sie ein Programm, das mit zwei natürlichen Zahlen als Eingabe eine Ausgabe erstellt, die genau so aussieht wie die Ausgabe des obigen Algorithmus. Sie können andere druckbare Nicht-Whitespace-ASCII-Zeichen als 0und verwenden. Seien Sie -jedoch konsistent und verwenden Sie nur zwei Zeichen. Sie können auch alternative Algorithmen verwenden, sofern die Ausgabe, einschließlich des Timings, genau so ist, wie dies mit dem obigen Algorithmus möglich wäre.

Beispiele

Dies ist ein Beispiel für eine Eingabe 24,35, bei der es sich um Koprime handelt, sodass der GCD-Wert 1 ist.

Dies ist ein Beispiel mit Eingängen 16,42, die den GCD 2 haben.

Regeln

• Dies ist ein Code-Golf , also gewinnt das kürzeste Byte
• Es gelten Standardlücken
• Sie können davon ausgehen, dass es sich bei der Eingabe um positive Dezimalzahlen handelt
  • Wenn Sie nicht sed, Retina, /// usw. verwenden, können Sie unary verwenden

Klarstellungen

• Die Zeilen, die die Zahlen darstellen, müssen in ihrer ursprünglichen Reihenfolge bleiben, dh die erste und die zweite Zeile des ersten angezeigten "Frames" müssen in allen nachfolgenden Frames die erste bzw. die zweite Zeile sein.
• Nach Beendigung des Algorithmus sollte keine weitere sichtbare Entität angezeigt werden. Dies bedeutet jedoch auch, dass es in Ordnung ist, die Zeilen auszublenden, wenn Sie sicherstellen, dass der letzte "Frame" mindestens so lange angezeigt wird wie alle anderen Frames vor dem Ausblenden.

Gelee , 29 Bytes

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

Probieren Sie es online!

Dies definiert eine Funktion 2Ŀ(kein vollständiges Programm; der TIO-Link enthält eine Fußzeile, die eine Funktion in ein Programm konvertiert), die eine Liste von zwei Elementen als Eingabe verwendet und die Ausgabe auf dem Bildschirm anzeigt (eine unserer zulässigen E / A-Methoden) , und eine, die für diese Herausforderung irgendwie notwendig ist, weil es um das Erscheinen auf dem Bildschirm geht). Dies setzt voraus, dass das Programm auf einem Terminal ausgeführt wird, das dem ANSI-Standard entspricht (ich habe es verwendet, gnome-terminalaber die meisten funktionieren), und dass das Terminal anfangs leer ist (was als die vernünftigste Standardeinstellung erscheint). Beachten Sie, dass es online versuchen! entspricht nicht diesen Annahmen und daher ist die Ausgabe dort verzerrt (ich habe das Programm lokal ausgeführt, um zu überprüfen, ob es wie erwartet animiert ist). Ich benutze, 1wo die Frage verwendet 0, und2anstelle von -.

Erläuterung

Hilfsfunktion 1Ŀ (gibt eine Liste mit zwei Ziffernlisten aus, gibt sie in der ersten und zweiten Zeile des Bildschirms aus und wartet dann 0,5 Sekunden; gibt ihre Eingabe zurück)

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

Die Zeichenfolge "\ x1bc" wird beim Senden an ein ANSI-kompatibles Terminal als Steuercode zum Zurücksetzen des Terminals interpretiert. Dadurch wird der Bildschirm gelöscht und der Cursor in die linke obere Ecke bewegt (wodurch das Terminal für die nächste Ausgabe zurückgesetzt wird).

Die Hilfsfunktion heißt 1Ŀ(Jelly generiert automatisch Namen dieser Form für Funktionen, und tatsächlich gibt es keine andere Möglichkeit, sie zu benennen), kann jedoch einfach als Çaus dem Hauptprogramm bezeichnet werden (da die Sprache eine Kurzform für Funktionen mit benachbarten Zahlen hat) ).

Hauptfunktion 2Ŀ (implementiert die in der Frage angeforderte Aufgabe)

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)

JavaScript (ES6), 128 124 Byte

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>

Python 2 , 152 146 Bytes

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)

Probieren Sie es online!

Nimmt zwei durch Kommas getrennte Ganzzahlen als Eingabe

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

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)

Verwendung

Dies nimmt Eingaben in eine Variation des Currys vor. Um es zu benutzen, weisen Sie zuerst die Funktion einer Variablen zu (zum Beispiel G) und rufen Sie es dann wie folgt auf:

G(5)(6)()

Erläuterung

Etwas rekursive Funktion, die sich nach 1 Sekunde selbst aufruft, solange der Algorithmus noch nicht beendet ist. Es verfolgt eine dritte Variable c, die festlegt, ob aund bsollte geändert werden (wenn cja 1, ist es Zeit für Änderungen).

Zunächst schreibt die Funktion etwas in die Konsole. Wenn dies der Fall cist 0, werden zwei Zeichenfolgen mit Nullen und dazwischen eine neue Zeile geschrieben. Da czu initialisiert wird 0, können wir dies nutzen und globale Variablen einrichten fund gdass einige Saiten oft halten wir brauchen (wie 0und repeat).

Andernfalls wird eine Zeichenfolge mit Nullen und Minuspunkten aufgebaut. Alle diese Zeichenfolgen bestehen aus zwei Teilen: erst einige AMinuspunkte (nennen Sie diesen Betrag ), dann einige (nennen Sie diesen Betrag B) Nullen, dann eine neue Zeile, dann einige Minuspunkte (nennen Sie diesen Betrag D) und zuletzt einige (nennen Sie diesen Betrag E) Nullen.

Wenn der erste Eingang kleiner als der zweite Eingang ist, müssen wir Nullen aus dem zweiten Eingang entfernen. Ist also ANull, Bentspricht dem ersten Eingang, Dentspricht dem ersten Eingang und Eentspricht dem zweiten Eingang minus dem ersten Eingang. Wenn der erste Eingang nicht kleiner als der zweite Eingang ist, gilt das Gegenteil ( Aist der zweite Eingang, Bist der erste Eingang minus dem zweiten Eingang usw.).

Mit diesen neuen Werten für den Eingang und eine geschaltete Variable csoll die Funktion in 1e3Millisekunden, was einer Sekunde entspricht, erneut aufgerufen werden .

Anmerkungen

• Verwendet alertfür die Ausgabe
• Verwendet 0und -, genau wie in den Beispielen
• Die Verzögerung zwischen den Schritten beträgt 1000 ms (1 Sekunde).
• Nach dem ersten Schritt gibt die Funktion (aufgrund der Art von JavaScript) eine Zahl zurück, die ignoriert werden soll
• Die Version auf TIO gibt alles auf einmal aus. Wenn Sie den Code in die Browserkonsole einfügen, werden die Verzögerungen ordnungsgemäß berücksichtigt

Probieren Sie es online aus

Probieren Sie es hier aus!

Python 2 , 208 204 194 Bytes

-4 danke an @math_junkie für den hinterhältigen Trick mit time.sleep

-10 danke an @busukxuan für die Klarstellung der "clear screen" -Regel.

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)

Probieren Sie es online!

Ziemlich sicher, dass dies mehr Golf könnte. Es tut mir weh, die printund die forSchleife zu duplizieren , um die Pause zu erzeugen, aber ich kann es im Moment nicht umgehen.

Anmerkungen

• In der Pause wird jetzt ein Hinweis von @math_junkie verwendet
• Funktioniert nicht vollständig mit TIO, da es die Ausgabe speichert und sie ausgibt, wenn das Programm beendet ist. Funktioniert aber gut in der Konsole.

Perl, 161 149 Bytes

... ohne Einrückungen und Zeilenumbrüche:

($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
}

Lege es in eine Datei gcd.pl und starte wie folgt:

perl -M5.010 gcd.pl 16 42

GNU Sed (mit exec-Erweiterung), 88

Die Punktzahl enthält +3 für -zrfOptionen auf 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

Die Eingabe erfolgt als zwei durch Zeilenumbrüche getrennte ganze Zahlen, wobei Großbuchstaben Oals Ziffern verwendet werden.

Beispielsweise kann das Beispiel 16, 42 ausgeführt werden als:

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

Gemäß den neuesten Kommentaren lösche ich den Bildschirm zwischen den Iterationen nicht.

V , 47 44 Bytes

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

Probieren Sie es online!

Die Kopf- und Fußzeile von TIO werden nur so geändert gs, dass die aktuellen zwei Zeilen in den unteren Bildschirmbereich kopiert werden und die ersten beiden Zeilen am Ende gelöscht werden. Dies visualisiert die Operation für TIO, aber wenn Sie sie in V ausführen (ohne Kopf- und Fußzeile), würde sie zwischen jeder Operation nur eine Sekunde warten.

Àé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