Visualize the Euclidean algorithm

Question

The Euclidean algorithm is a widely known algorithm for calculating the greatest common divisor (GCD) of two positive integers.

The algorithm

For the purpose of this challenge, the algorithm is described as below:

1. Display the two input as adjacent lines of a certain character
   e.g. an input of 3,4 can be represented by the adjacent lines 000 and 0000

2. Turn the first length(short_line) characters in the longer line into another character, say -
   now it looks like 000 and ---0

3. Eliminate the first length(short_line) characters in the longer line.
   now 000, 0

4. Repeat step 2 and 3 until the two have equal length, using the shorter and longer lines after each iteration, e.g.
   000,0
-00,0
00,0
-0,0
0,0

5. You can choose whether to stop here or continue the iteration and turn one of the lines into an empty line.

Each of these steps should be separated by an interval between 0.3s and 1.5s.

The challenge

Write a program that, given two natural numbers as input, creates an output that looks exactly the same as the output of the algorithm above. You can use other non-whitespace printable ASCII characters than 0 and -, but be consistent and use only two characters. You can also use alternative algorithms provided the output, including the timing, is exactly the same as would be produced by the algorithm above.

Examples

This is an example with input 24,35, which are coprimes so their GCD is 1.

This is an example with input 16,42, which have the GCD 2.

Rules

• This is a code-golf, so shortest bytes wins
• Standard loopholes apply
• You can assume input to be positive decimal integers
  • Unless you are using sed, Retina, ///, etc, in which case you can use unary

---

Clarifications

• The lines that represent the numbers need to stay in their original order, i.e. the first and second lines of the first displayed "frame" need to be the first and second lines respectively, in all subsequent frames.
• After the algorithm ends, no additional visible entity should appear. However, this also means that it is okay to blank the lines, if you make sure that the last "frame" is displayed for at least the same amount of time as did all other frames before blanking out.

Answer 1

Jelly, 29 bytes

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

Try it online!

This defines a function 2Ŀ (not a full program; the TIO link contains a footer that converts a function into a program) that takes a list of two elements as input, and displays the output on the screen (one of our legal I/O methods, and one that is kind-of necessary for this challenge because it talks about the appearance on screen). This assumes that the program is run in a terminal that complies with the ANSI standard (I used gnome-terminal but most will work), and that the terminal is initially empty (which seems like the most sensible default); note that Try it online! does not conform to these assumptions, and thus the output is distorted there (I ran the program locally to verify that it animates as expected). I use 1 where the question uses 0, and 2 in place of -.

Explanation

Helper function 1Ŀ (given a list of two lists of digits, outputs them on the first and second lines of the screen, then waits 0.5 seconds; returns its input)

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

The string "\x1bc", when sent to an ANSI-compatible terminal, is interpreted as a control code to reset the terminal; this clears the screen and moves the cursor to the top left corner (thus resetting the terminal ready for the next output).

The helper function is named 1Ŀ (Jelly autogenerates names of this form for functions, and in fact there's no other way to name them), but it can be referred to simply as Ç from the main program (because the language has shorthand for functions with numbers nearby).

Main function 2Ŀ (implements the task requested in the 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)

Answer 2

JavaScript (ES6), 128 124 bytes

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>

Answer 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)

Try it online!

---

Takes two comma-separated integers as input

Answer 4

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)

Usage

This takes input in a variation on currying. To use it, fist assign the function to a variable (for example G), then call it like this:

G(5)(6)()

Explanation

Somewhat recursive function that calls itself after 1 second as long as the algorithm hasn't finished. It keeps track of a third variable c that determines whether a and b should be changed (if c is 1, it's time for change).

First, the function writes something to the console. If c is 0, it writes two strings of zeroes with a newline inbetween. Since c is initialised to 0, we can take advantage of this, and set up global variables f and g that hold some strings we need often (like 0 and repeat).

Otherwise, it builds up a string with zeroes and minuses. All such strings consist of two parts: first some (call this amount A) minuses, then some (call this amount B) zeroes, then a newline, then some (call this amount D) minuses and lastly some (call this amount E) zeroes.

If the first input is smaller than the second input, we need to remove zeroes from the second input, so A is zero, B equals the first input, D equals the first input and E equals the second input minus the first input. If the first input is not smaller than the second input, the reverse applies (A is the second input, B is the first input minus the second input etc.).

With these new values for the input and a switched variable c, the function is scheduled to be called again in 1e3 milliseconds, which equals one second.

Notes

• Uses alert for output
• Uses 0 and -, just like in the examples
• Delay between steps is 1000 ms (1 second)
• After the first step, the function will (due to the nature of JavaScript) return some number which is to be ignored
• The version on TIO outputs everything at once, pasting the code in the browser console will properly take the delays into account

Try it online

Try it here!

Answer 5

Python 2, 208 204 194 bytes

-4 with thanks to @math_junkie for the sneaky trick with time.sleep

-10 with thanks to @busukxuan for clarifying the "clear screen" rule.

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)

Try it online!

Pretty sure this could be more golfed. It pains me to duplicate the print and the for loop to create the pause but I can't find a way round it at the moment.

Notes

• The pause now uses a hint from @math_junkie
• Doesn't fully work on TIO as it stores the output and dumps it out when the program finishes. Works fine in the console though.

Answer 6

perl, 161 149 bytes

...without indentations and newlines:

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

Put it into a file gcd.pl and run like this:

perl -M5.010 gcd.pl 16 42

Answer 7

GNU Sed (with exec extension), 88

Score includes +3 for -zrf options to 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 is given as two newline separated unary integers, using the upper case O as digits.

For example, the 16, 42 example may be run as:

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

As per the latest comments, I am not clearing the screen between iterations.

Answer 8

V, 47 44 bytes

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

Try it online!

The header and footer on TIO just modify gs to copy the current two lines to the bottom of the screen, and then delete the first two at the end. This visualizes the operation for TIO, but if you ran it in V (without the header and footer), it would just wait a second between each operation.

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