Visualisieren Sie den euklidischen Algorithmus

17

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.

Bildbeschreibung hier eingeben

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

Bildbeschreibung hier eingeben

Regeln


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.
busukxuan
quelle
@ WheatWizard toller Vorschlag, drauf
busukxuan
Müssen die Zeilen in der gleichen relativen Reihenfolge bleiben? Oder können sie zwischen den Iterationen neu angeordnet werden? (Überprüfung, da letztere wahrscheinlich in den meisten Sprachen sehr viel prägnanter ist und ich daher wissen muss, ob ich diese Optimierung verwenden oder aufgrund von Verstößen gegen den sepc ignorieren soll.)
@ ais523 Ja, das tun sie:-)
busukxuan
@ ais523 Ja, es ist in Ordnung, es auszublenden, aber stellen Sie sicher, dass das letzte Bild dieselbe Anzeigezeit hat wie die anderen Bilder
busukxuan
1
Persönlich denke ich, ich würde nachgestellte Leerzeichen zulassen, aber vielleicht nicht Leerzeichen als eines der "bedeutungsvollen" Zeichen
Luis Mendo

Antworten:

3

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)

quelle
6

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>

Neil
quelle
3

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

ovs
quelle
Das ist eine schöne Antwort.
ElPedro
2

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!

Luke
quelle
2

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.
ElPedro
quelle
1
Sie sollten einige Bytes speichern können , verwenden import time, s=time.sleepund s(1)statt einer Schleife für die Verzögerung
Mathe -
Danke @math_junkie - Ich habe die meisten Kombinationen ausprobiert, time.sleepaber diese verpasst. Ich werde es versuchen.
ElPedro
@math_junkie - kommt für mich auf 215. Vielleicht fehlt mir etwas Dummes. Können Sie ein Beispiel auf Try it Online posten ?
ElPedro
1
Versuchen Sie es hier
Math Junkie
1

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
Kjetil S.
quelle
1
Das -M5.010Flag für Perl ist kostenlos, sodass Sie mit sayover ein paar Bytes sparen können print…\n. Ich bin mir außerdem ziemlich sicher, dass es schwieriger ist, Ihrem anonymen Unterprogramm einen Namen zu geben, als es in einer Variablen zu speichern.
Vielen Dank an ais523 für Tipps zum Rasieren von 12 Bytes
Kjetil S.
1

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.

Digitales Trauma
quelle
0

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
nmjcman101
quelle
Brauchen Sie wirklich das Ende ò?
Kritixi Lithos
Es hängt ohne es, unsicher warum. Ich werde warten, bis ich einen Computer mit V darauf habe, um irgendetwas zu debuggen
nmjcman101