Wizualizuj algorytm euklidesowy

17

Algorytm euklidesowy jest powszechnie znanym algorytmem do obliczania największego wspólnego dzielnika (GCD) dwóch dodatnich liczb całkowitych.

Algorytm

Na potrzeby tego wyzwania algorytm opisano poniżej:

  1. Wyświetl dwa wejścia jako sąsiednie linie określonego znaku,
    np. Wejście 3,4może być reprezentowane przez sąsiednie linie 000i0000

  2. Zamień pierwsze length(short_line)znaki w dłuższej linii na inną, powiedz -
    teraz, że wygląda jak 000i---0

  3. Wyeliminuj pierwsze length(short_line)znaki w dłuższej linii.
    teraz 000,0

  4. Powtórzyć kroki 2 i 3 do dwóch mają jednakową długość, z wykorzystaniem krótszych i dłuższych liniach po każdej iteracji, na przykład
    000, 0
    -00, 0
    00, 0
    -0, 0
    0,0

  5. Możesz wybrać, czy chcesz zatrzymać się tutaj, czy kontynuować iterację i zamienić jedną z linii w pustą.

Każdy z tych kroków powinien być oddzielony odstępem między 0,3s a 1,5s.

Wyzwanie

Napisz program, który podając dwie liczby naturalne jako dane wejściowe, tworzy wynik, który wygląda dokładnie tak samo jak wynik powyższego algorytmu. Można używać innych znaków ASCII , które nie można drukować spacjami, niż 0i -, ale należy zachować spójność i używać tylko dwóch znaków. Możesz także użyć alternatywnych algorytmów, pod warunkiem, że dane wyjściowe, w tym taktowanie, są dokładnie takie same, jak w przypadku powyższego algorytmu.

Przykłady

To jest przykład z 24,35danymi wejściowymi , które są koprime, więc ich GCD wynosi 1.

wprowadź opis zdjęcia tutaj

To jest przykład z wejściem 16,42, które mają GCD 2.

wprowadź opis zdjęcia tutaj

Zasady


Wyjaśnienia

  • Linie reprezentujące liczby muszą pozostać w oryginalnej kolejności, tj. Pierwsza i druga linia pierwszej wyświetlanej „ramki” muszą być odpowiednio pierwszą i drugą linią we wszystkich kolejnych ramkach.
  • Po zakończeniu algorytmu nie powinien pojawiać się żaden dodatkowy widoczny element . Oznacza to jednak również, że można wyczyścić linie, jeśli upewnisz się, że ostatnia „klatka” jest wyświetlana przez co najmniej tyle samo czasu, co wszystkie inne klatki przed wygaszeniem.
busukxuan
źródło
@WheatWizard świetna sugestia, na jej temat
busukxuan
Czy linie muszą pozostać w tej samej względnej kolejności? A może można je zmienić między iteracjami? (Sprawdzanie, ponieważ ta ostatnia jest prawdopodobnie bardziej zwięzła w większości języków, dlatego muszę wiedzieć, czy powinienem użyć tej optymalizacji, czy zignorować ją z powodu naruszenia sepc.)
@ ais523 Tak, robią:-)
busukxuan
@ ais523 Tak, można go wyczyścić, ale upewnij się, że ostatnia klatka ma taki sam czas wyświetlania jak inne klatki
busukxuan
1
@busukxuan Osobiście myślę, że pozwoliłbym na końcowe spacje, ale być może nie spację jako jedną z „znaczących” postaci
Luis Mendo

Odpowiedzi:

3

Galaretka , 29 bajtów

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

Wypróbuj online!

Definiuje to funkcję 2Ŀ(nie pełny program; łącze TIO zawiera stopkę przekształcającą funkcję w program), która pobiera listę dwóch elementów jako dane wejściowe i wyświetla dane wyjściowe na ekranie (jedna z naszych legalnych metod we / wy i taki, który jest niezbędny do tego wyzwania, ponieważ mówi o wyglądzie na ekranie). Zakłada się, że program działa w terminalu zgodnym ze standardem ANSI (użyłem, gnome-terminalale większość będzie działać) i że terminal jest początkowo pusty (co wydaje się najbardziej sensownym domyślnym); Uwaga: Wypróbuj online! nie jest zgodny z tymi założeniami, a zatem dane wyjściowe są tam zniekształcone (uruchomiłem program lokalnie, aby sprawdzić, czy animuje zgodnie z oczekiwaniami). Używam 1tam, gdzie używa to pytanie 0, i2w miejsce -.

Wyjaśnienie

Funkcja pomocnicza 1Ŀ (podana lista dwóch list cyfr, wyświetla je w pierwszym i drugim wierszu ekranu, a następnie czeka 0,5 sekundy; zwraca dane wejściowe)

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

Ciąg „\ x1bc” wysłany do terminala kompatybilnego z ANSI jest interpretowany jako kod sterujący do resetowania terminala; powoduje to wyczyszczenie ekranu i przesunięcie kursora do lewego górnego rogu (w ten sposób resetując terminal gotowy do następnego wyjścia).

Funkcja pomocnika jest nazwana 1Ŀ(Jelly automatycznie generuje nazwy tej formy dla funkcji i w rzeczywistości nie ma innego sposobu nazywania ich), ale można ją nazwać po prostu jako Çz programu głównego (ponieważ język ma skrót dla funkcji z liczbami w pobliżu ).

Główna funkcja 2Ŀ (realizuje zadanie wymagane w pytaniu)

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)

źródło
6

JavaScript (ES6), 128 124 bajtów

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
źródło
3

Python 2 , 152 146 bajtów

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)

Wypróbuj online!


Pobiera na wejściu dwie liczby całkowite oddzielone przecinkami

ovs
źródło
To miła odpowiedź.
ElPedro,
2

JavaScript (ES6), 215 194 ... 135 129 127 bajtów

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)

Stosowanie

Wymaga to odmiany curry. Aby go użyć, najpierw przypisz funkcję do zmiennej (na przykład G), a następnie wywołaj ją w następujący sposób:

G(5)(6)()

Wyjaśnienie

Nieco rekurencyjna funkcja, która wywołuje się po 1 sekundzie, dopóki algorytm się nie skończy. Śledzi trzeciej zmiennej c, która określa, czy ai bpowinien być zmieniony (jeśli cjest 1, że nadszedł czas na zmiany).

Po pierwsze, funkcja zapisuje coś na konsoli. Jeśli ctak 0, zapisuje dwa ciągi zer z nową linią między nimi. Ponieważ cjest inicjowany do 0, możemy skorzystać z tego i skonfigurować zmienne globalne fi gktóre posiadają pewne ciągi musimy często (jak 0i repeat).

W przeciwnym razie tworzy ciąg z zerami i minusami. Wszystkie takie ciągi składają się z dwóch części: najpierw niektóre Aminusy (zadzwoń do tej kwoty ), następnie niektóre Bzera (zadzwoń do tej kwoty ), następnie znak nowej linii, potem Dminusy (zadzwoń do tej kwoty ) i na końcu niektóre Ezera (zadzwoń do tej kwoty ).

Jeśli pierwsze wejście jest mniejsze niż drugie wejście, musimy usunąć zera z drugiego wejścia, więc Awynosi zero, Brówna się pierwsze wejście, Drówna się pierwsze wejście i Erówna się drugie wejście minus pierwsze wejście. Jeśli pierwsze wejście nie jest mniejsze niż drugie wejście, obowiązuje odwrotność ( Ato drugie wejście, Bto pierwsze wejście minus drugie wejście itp.).

Z tymi nowymi wartościami wejściowymi i zmienną przełączaną cfunkcja ma być wywoływana ponownie w 1e3milisekundach, co równa się jednej sekundzie.

Notatki

  • Wykorzystuje alertdane wyjściowe
  • Używa 0i -, podobnie jak w przykładach
  • Opóźnienie między krokami wynosi 1000 ms (1 sekunda)
  • Po pierwszym kroku funkcja zwróci (z uwagi na naturę JavaScript) pewną liczbę, którą należy zignorować
  • Wersja na TIO generuje wszystko na raz, wklejenie kodu w konsoli przeglądarki odpowiednio uwzględni opóźnienia

Wypróbuj online

Wypróbuj tutaj!

Łukasz
źródło
2

Python 2 , 208 204 194 bajtów

-4 dzięki dzięki @math_junkie za podstępną sztuczkę z time.sleep

-10 dzięki dzięki @busukxuan za wyjaśnienie zasady „wyczyść ekran”.

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)

Wypróbuj online!

Jestem prawie pewien, że to może być bardziej golf. Boli mnie, powielać printi forpętlę, aby utworzyć pauzę, ale nie mogę znaleźć sposób wokół niego w tej chwili.

Notatki

  • Pauza korzysta teraz z podpowiedzi @math_junkie
  • Nie działa w pełni w TIO, ponieważ przechowuje dane wyjściowe i zrzuca je po zakończeniu programu. Działa dobrze w konsoli.
ElPedro
źródło
1
Powinieneś być w stanie zapisać niektóre bajty za pomocą import time, s=time.sleepa s(1)zamiast pętli dla opóźnienia
matematyka ćpun
Dzięki @math_junkie - próbowałem większości kombinacji, time.sleepale tęskniłem. Spróbuje.
ElPedro,
@ mat_junkie - przychodzi do 215 dla mnie. Może brakuje mi czegoś głupiego. Czy możesz zamieścić przykład na Wypróbuj online ?
ElPedro,
1
Spróbuj tutaj
ćpun matematyki
1

perl, 161 149 bajtów

... bez wcięć i znaków nowej linii:

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

Umieść go w pliku gcd.pl i uruchom tak:

perl -M5.010 gcd.pl 16 42
Kjetil S.
źródło
1
-M5.010Flag Perl jest wolny, dzięki czemu można zaoszczędzić kilka bajtów za pomocą sayciągu print…\n. Ponadto jestem prawie pewien, że łatwiej jest nadać swojej anonimowej podprogramowi nazwę, niż przechowywać w zmiennej.
Dziękuję ais523 za wskazówki, jak zgolić 12 bajtów
Kjetil S.
1

GNU Sed (z erozszerzeniem xec), 88

Wynik obejmuje +3 dla -zrfopcji do 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

Dane wejściowe są podawane jako dwie oddzielne liczby całkowite oddzielone znakiem nowej linii, przy użyciu wielkich liter Ojako cyfr.

Na przykład przykład 16, 42 można uruchomić jako:

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

Zgodnie z najnowszymi komentarzami nie usuwam ekranu między iteracjami.

Cyfrowa trauma
źródło
0

V , 47 44 bajtów

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

Wypróbuj online!

Nagłówek i stopka w TIO wystarczy zmodyfikować, gsaby skopiować bieżące dwa wiersze na dole ekranu, a następnie usunąć pierwsze dwa na końcu. To wizualizuje operację dla TIO, ale jeśli uruchomiłeś ją w V (bez nagłówka i stopki), to po prostu poczekałby sekundę między każdą operacją.

Àé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
źródło
Czy naprawdę potrzebujesz zakończenia ò?
Kritixi Lithos
Wisi bez niego, nie wiem dlaczego. Będę czekać, aż będę mieć komputer z V do debugowania
nmjcman101