17
\$\begingroup\$

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.

enter image description here

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

enter image description here

Rules


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.
\$\endgroup\$
14
  • \$\begingroup\$ @WheatWizard great suggestion, on it \$\endgroup\$
    – busukxuan
    Feb 18, 2017 at 14:48
  • \$\begingroup\$ Do the lines have to stay in the same relative order? Or can they be reordered between iterations? (Checking because the latter is likely to be much more concise in most languages, and thus I need to know whether I should use that optimization or ignore it due to violating the sepc.) \$\endgroup\$
    – user62131
    Feb 18, 2017 at 15:12
  • \$\begingroup\$ @ais523 Yes they do :-) \$\endgroup\$
    – busukxuan
    Feb 18, 2017 at 15:17
  • \$\begingroup\$ @ais523 Yes it's okay to blank it, but make sure the last frame is given the same display time as the other frames \$\endgroup\$
    – busukxuan
    Feb 18, 2017 at 15:31
  • 1
    \$\begingroup\$ @busukxuan Personally I think I would allow trailing spaces, but perhaps not space as one of the "meaningful" characters \$\endgroup\$
    – Luis Mendo
    Feb 18, 2017 at 17:08

8 Answers 8

6
\$\begingroup\$

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>

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ That's a nice answer. \$\endgroup\$
    – ElPedro
    Feb 19, 2017 at 14:02
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should be able to save some bytes using import time, s=time.sleep and s(1) instead of a loop for the delay \$\endgroup\$ Feb 19, 2017 at 12:39
  • \$\begingroup\$ Thanks @math_junkie - I tried most combinations using time.sleep but missed that one. Will give it a go. \$\endgroup\$
    – ElPedro
    Feb 19, 2017 at 13:01
  • \$\begingroup\$ @math_junkie - comes to 215 for me. Maybe I am missing something stupid. Can you post an example on Try it Online? \$\endgroup\$
    – ElPedro
    Feb 19, 2017 at 13:06
  • 1
    \$\begingroup\$ Try it here \$\endgroup\$ Feb 19, 2017 at 13:29
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The -M5.010 flag to perl is free, so you can save a few bytes by using say over print…\n. Additionally, I'm pretty sure it's terser to give your anonymous subroutine a name, rather than storing it in a variable. \$\endgroup\$
    – user62131
    Feb 18, 2017 at 23:10
  • \$\begingroup\$ Thx to ais523 for tips to shave off 12 bytes \$\endgroup\$
    – Kjetil S
    Feb 18, 2017 at 23:33
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Do you really need the ending ò? \$\endgroup\$
    – user41805
    Feb 28, 2017 at 19:43
  • \$\begingroup\$ It hangs without it, unsure why. Going to wait until I have a computer with V on it to debug any \$\endgroup\$
    – nmjcman101
    Feb 28, 2017 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.