3
\$\begingroup\$

The Euclidean GCD Algorithm is an algorithm that efficiently computes the GCD of two positive integers, by repeatedly subtracting the smaller number from the larger number until they become equal. It can be visualised as such:

We start with a MxN grid, where M and N are the numbers. In this example I'll use M=12, N=5:

       12
  ____________
 |
 |
5|
 |
 |

We then, going from the top left, remove a square with a side length of the smaller of the two values, 5, leaving a 7x5 rectangle. This is visualised by replacing the last column of the 5x5 square with a column of |s.

          7
  ____________
 |    |
 |    |
5|    |
 |    |
 |    |

We then remove another 5x5 square, leaving a 2x5 rectangle:

            2
  ____________
 |    |    |
 |    |    |
5|    |    |
 |    |    |
 |    |    |

Next, we remove two 2x2 squares, leaving a 2x1 rectangle. As these squares are added when the rectangle is taller than it is wide, their bottom rows are replaced with rows of _s.

            2
  ____________
 |    |    |
 |    |    |__
 |    |    |
 |    |    |__
1|    |    | 

And finally, we remove a 1x1 square, leaving a 1x1 square, whose last and only column is replaced with a |. As this is a square, the two sides are equal, so the GCD of 12 and 5 is 1.

The final visualisation looks like this. Note that the numbers are not included, those were just visual indicators.

    |    |
    |    |__
    |    |
    |    |__
    |    ||

Here's a larger example for M=16, N=10. (I'm not going to go through all the steps here).

         |
         |
         |
         |
         |
         |______
         |   |
         |   |__
         |   |
         |   |

Note that, as gcd(16, 10) = 2, the algorithm ends with a 2x2 square.

Your challenge is to implement this visualisation, given two numbers M and N where M > N. Your output may have any amount of leading/trailing whitespace.

Testcases

12, 5 ->
    |    |
    |    |__
    |    |
    |    |__
    |    ||

10, 16 ->
         |
         |
         |
         |
         |
         |______
         |   |
         |   |__
         |   |
         |   |
25, 18 ->
                 |       
                 |       
                 |       
                 |       
                 |       
                 |       
                 |_______
                 |       
                 |       
                 |       
                 |       
                 |       
                 |       
                 |_______
                 |   |   
                 |   |   
                 |   |___
                 |   ||| 

25, 10 ->
         |         |     
         |         |     
         |         |     
         |         |     
         |         |_____
         |         |     
         |         |     
         |         |     
         |         |     
         |         |     

34, 15 ->
              |              |    
              |              |    
              |              |    
              |              |____
              |              |    
              |              |    
              |              |    
              |              |____
              |              |    
              |              |    
              |              |    
              |              |____
              |              |  |_
              |              |  |_
              |              |  | 

89, 55 ->
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |                                  
                                                      |__________________________________
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |             
                                                      |                    |_____________
                                                      |                    |       |     
                                                      |                    |       |     
                                                      |                    |       |     
                                                      |                    |       |     
                                                      |                    |       |_____
                                                      |                    |       |  |  
                                                      |                    |       |  |__
                                                      |                    |       |  || 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Quite similar: codegolf.stackexchange.com/q/119714/15469 \$\endgroup\$
    – Jonah
    Commented Oct 12, 2023 at 21:42
  • \$\begingroup\$ @Jonah I would call this a dupe of that, though they might be different enough to stay separate. \$\endgroup\$ Commented Oct 12, 2023 at 23:34

2 Answers 2

2
\$\begingroup\$

Charcoal, 43 bytes

NθNηBθη W⁻θη¿›θη«≧⁻ηθM⊖η→P↓η→»«≧⁻θηM⊖θ↓⟦×_θ

Try it online! Link is to verbose version of code. Explanation:

NθNη

Input M and N.

Bθη 

Draw an M×N box. This solves two problems; firstly, in case one value divides the other, as I assume I'm not allowed -N trailing white space; secondly, in case M>N, as I assume I'm not allowed 1-N leading white space.

W⁻θη

Repeat until M=N.

¿›θη«

If M>N, then:

≧⁻ηθ

Subtract N from M.

M⊖η→

Move N-1 to the right.

P↓η

Draw N |s downwards.

Move to the right.

»«

Otherwise, if N>M:

≧⁻θη

Subtract M from N.

M⊖θ↓

Move M-1 down.

⟦×_θ

Draw M _s and move down.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (V8), 128 bytes

x=>h=(y,i=x,j=y)=>j?(g=(x,y)=>i?y-j+1|x<i?x-i+1|y<j?x>y?g(x-y,y):x<y?g(x,y-x):' ':'|':'_':`
`)(x,y)+(i?h(y,i-1,j):h(y,x,j-1)):''

Try it online!

\$\endgroup\$

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