Algoritma Euclidean adalah algoritma yang dikenal luas untuk menghitung pembagi umum terbesar (GCD) dari dua bilangan bulat positif.

Algoritma

Untuk tujuan tantangan ini, algoritme tersebut dijelaskan sebagai berikut:

1. Tampilkan dua input sebagai garis yang berdekatan dari karakter tertentu
   misalnya input 3,4dapat diwakili oleh garis yang berdekatan 000dan0000

2. Ubah length(short_line)karakter pertama di baris yang lebih panjang menjadi karakter lain, katakan -
   sekarang sepertinya 000dan---0

3. Hilangkan length(short_line)karakter pertama di baris yang lebih panjang.
   sekarang 000,0

4. Ulangi langkah 2 dan 3 sampai keduanya memiliki panjang yang sama, menggunakan garis yang lebih pendek dan lebih panjang setelah setiap iterasi, misalnya
   000,0
-00 , 0
00, 0
-0, 0
0,0

5. Anda dapat memilih apakah akan berhenti di sini atau melanjutkan iterasi dan mengubah salah satu garis menjadi garis kosong.

Masing-masing langkah ini harus dipisahkan oleh interval antara 0,3 dan 1,5.

Tantangan

Tulis program yang, diberi dua bilangan asli sebagai input, membuat output yang terlihat persis sama dengan output dari algoritma di atas. Anda dapat menggunakan karakter ASCII non-spasi putih yang dapat dicetak selain 0dan -, tetapi konsisten dan gunakan hanya dua karakter. Anda juga dapat menggunakan algoritma alternatif asalkan output, termasuk waktunya, persis sama dengan yang akan dihasilkan oleh algoritma di atas.

Contohnya

Ini adalah contoh dengan input 24,35 , yang merupakan koprimes sehingga GCD mereka adalah 1.

Ini adalah contoh dengan input 16,42 , yang memiliki GCD 2.

Aturan

• Ini adalah sebuah kode-golf , sehingga byte terpendek menang
• Celah standar berlaku
• Anda dapat menganggap input sebagai bilangan desimal positif
  • Kecuali jika Anda menggunakan sed, Retina, ///, dll, dalam hal ini Anda dapat menggunakan unary

Klarifikasi

• Garis-garis yang mewakili angka-angka harus tetap dalam urutan aslinya, yaitu baris pertama dan kedua dari "bingkai" pertama yang ditampilkan masing-masing harus menjadi baris pertama dan kedua, di semua bingkai berikutnya.
• Setelah algoritma berakhir, tidak ada entitas tambahan yang terlihat yang muncul. Namun, ini juga berarti tidak apa-apa untuk mengosongkan garis, jika Anda memastikan bahwa "bingkai" terakhir ditampilkan setidaknya untuk jumlah waktu yang sama seperti semua bingkai lainnya sebelum dikosongkan.

Jelly , 29 byte

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

Cobalah online!

Ini mendefinisikan fungsi 2Ŀ(bukan program lengkap; tautan TIO berisi catatan kaki yang mengubah fungsi menjadi program) yang mengambil daftar dua elemen sebagai input, dan menampilkan output di layar (salah satu metode I / O resmi kami , dan yang agak diperlukan untuk tantangan ini karena berbicara tentang penampilan di layar). Ini mengasumsikan bahwa program dijalankan di terminal yang sesuai dengan standar ANSI (saya menggunakan gnome-terminaltetapi sebagian besar akan bekerja), dan bahwa terminal pada awalnya kosong (yang tampak seperti standar yang paling masuk akal); perhatikan bahwa Coba online! tidak tidak sesuai dengan asumsi ini, dan dengan demikian output terdistorsi sana (aku berlari program lokal untuk memverifikasi bahwa itu menjiwai seperti yang diharapkan). Saya menggunakan 1tempat menggunakan pertanyaan 0, dan2di tempat -.

Penjelasan

Fungsi helper 1Ŀ (diberi daftar dua daftar digit, mengeluarkannya pada baris pertama dan kedua layar, lalu menunggu 0,5 detik; mengembalikan inputnya)

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

String "\ x1bc", ketika dikirim ke terminal yang kompatibel dengan ANSI, ditafsirkan sebagai kode kontrol untuk mengatur ulang terminal; ini membersihkan layar dan memindahkan kursor ke sudut kiri atas (sehingga mengatur ulang terminal siap untuk output berikutnya).

Fungsi helper dinamai 1Ŀ(Jelly autogenerates nama formulir ini untuk fungsi, dan sebenarnya tidak ada cara lain untuk menamai mereka), tetapi itu bisa disebut sebagai hanya Çdari program utama (karena bahasa memiliki singkatan untuk fungsi dengan angka di dekatnya ).

Fungsi utama 2Ŀ (mengimplementasikan tugas yang diminta dalam pertanyaan)

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 byte

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)

Cobalah online!

Mengambil dua bilangan bulat yang dipisahkan koma sebagai input

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

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)

Pemakaian

Ini membutuhkan input dalam variasi pada kari. Untuk menggunakannya, kepalan menetapkan fungsi ke variabel (misalnya G), lalu panggil seperti ini:

G(5)(6)()

Penjelasan

Agak fungsi rekursif yang memanggil dirinya sendiri setelah 1 detik selama algoritma belum selesai. Ini melacak variabel ketiga cyang menentukan apakah adan bharus diubah (jika cadalah 1, waktu itu untuk perubahan).

Pertama, fungsi menulis sesuatu ke konsol. Jika cadalah 0, itu menulis dua string dari nol dengan peralihan baris baru. Sejak cdiinisialisasi 0, kita dapat mengambil keuntungan dari ini, dan mengatur variabel global fdan gyang memiliki beberapa string yang sering kita butuhkan (seperti 0dan repeat).

Kalau tidak, itu membangun string dengan nol dan minus. Semua string tersebut terdiri dari dua bagian: pertama beberapa (sebutlah jumlah ini A) minus, kemudian beberapa (panggil jumlah ini B) nol, kemudian baris baru, lalu beberapa (panggil jumlah ini D) minus dan terakhir beberapa (panggil jumlah ini E) nol.

Jika input pertama lebih kecil dari input kedua, kita perlu menghapus nol dari input kedua, jadi Anol, Bsama dengan input pertama, Dsama dengan input pertama dan Esama dengan input kedua dikurangi input pertama. Jika input pertama tidak lebih kecil dari input kedua, kebalikannya berlaku ( Aadalah input kedua, Badalah input pertama dikurangi input kedua dll.).

Dengan nilai-nilai baru untuk input dan variabel yang diaktifkan c, fungsi dijadwalkan untuk dipanggil lagi dalam 1e3milidetik, yang sama dengan satu detik.

Catatan

• Penggunaan alertuntuk output
• Penggunaan 0dan -, sama seperti dalam contoh
• Keterlambatan antar langkah adalah 1000 ms (1 detik)
• Setelah langkah pertama, fungsi tersebut akan (karena sifat JavaScript) mengembalikan beberapa nomor yang harus diabaikan
• Versi TIO menampilkan semuanya sekaligus, menempelkan kode di konsol browser dengan benar akan mempertimbangkan penundaan

Cobalah online

Coba di sini!

Python 2 , 208 204 194 byte

-4 dengan terima kasih kepada @math_junkie untuk trik liciknya time.sleep

-10 dengan terima kasih kepada @busukxuan untuk mengklarifikasi aturan "hapus layar".

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)

Cobalah online!

Cukup yakin ini bisa lebih golf. Menyakitkan saya untuk menduplikasi printdanfor loop untuk membuat jeda tapi saya tidak dapat menemukan cara memutarnya saat ini.

Catatan

• Jeda sekarang menggunakan petunjuk dari @math_junkie
• Tidak sepenuhnya bekerja pada TIO karena menyimpan output dan membuangnya ketika program selesai. Bekerja dengan baik di konsol sekalipun.

perl, 161 149 byte

... tanpa lekukan dan baris baru:

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

Masukkan ke dalam file gcd.pl dan jalankan seperti ini:

perl -M5.010 gcd.pl 16 42

GNU Sed (with e ekstensi xec), 88

Skor termasuk +3 untuk -zrfopsi 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

Input diberikan sebagai dua bilangan bulat unaris yang dipisahkan oleh baris baru, menggunakan huruf besar O sebagai digit.

Misalnya, contoh 16, 42 dapat dijalankan sebagai:

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

Sesuai komentar terbaru, saya tidak membersihkan layar di antara iterasi.

V , 47 44 byte

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

Cobalah online!

Header dan footer di TIO hanya memodifikasi gsuntuk menyalin dua baris saat ini ke bagian bawah layar, dan kemudian menghapus dua yang pertama di akhir. Ini memvisualisasikan operasi untuk TIO, tetapi jika Anda menjalankannya di V (tanpa header dan footer), itu hanya akan menunggu sebentar di antara setiap operasi.

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