Visualize the Euclidean algorithm again

Question

Task

Given two positive integers:

1. Draw the rectangle with dimensions specified by the two integers.
2. Repeat Step 3 until there is no more space.
3. Draw and fill the largest square touching three sides of the (remaining) rectangle.
4. Output the resulting rectangle.

Example

For example, our input is 6 and 10.

We draw the hollow rectangle of size 6 x 10:

xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx

After repeatedly filling squares, this is what we would obtain:

aaaaaabbbb
aaaaaabbbb
aaaaaabbbb
aaaaaabbbb
aaaaaaccdd
aaaaaaccdd

There are 4 squares here (a, b, c, d), each with side length 6, 4, 2, 2 respectively.

Rules and freedom

1. You must use a different letter for each square.
2. You can choose which letters to support, as long as the letters supported are all printable characters and there are at least 10 characters supported.
3. In each iteration of Step 3 above, you have two choices (except in the last iteration, where you only have one choice). Both choices are valid.
4. The number of squares required will not exceed the number of letters you support.
5. You can fill in the squares with the letters you support in any order.

Testcases

Input: 6, 10

Output:

aaaaaabbbb
aaaaaabbbb
aaaaaabbbb
aaaaaabbbb
aaaaaaccdd
aaaaaaccdd

or

aaaaaaccdd
aaaaaaccdd
aaaaaabbbb
aaaaaabbbb
aaaaaabbbb
aaaaaabbbb

or

bbbbaaaaaa
bbbbaaaaaa
bbbbaaaaaa
bbbbaaaaaa
ccddaaaaaa
ccddaaaaaa

or

ccddaaaaaa
ccddaaaaaa
bbbbaaaaaa
bbbbaaaaaa
bbbbaaaaaa
bbbbaaaaaa

or

ddddddaaaa
ddddddaaaa
ddddddaaaa
ddddddaaaa
ddddddbbcc
ddddddbbcc

Input: 1,1

Output:

a

Input: 1,10

Output:

abcdefghij

Input: 10,1

Output:

a
b
c
d
e
f
g
h
i
j

Note that there are more possibilities than I can include for the testcases above.

Scoring

This is code-golf. Shortest answer in bytes wins.

Standard loopholes apply.

Answer 1

Charcoal, 30 bytes

ＮδＮγＦβ¿×γδ«ＵＯγδι¿‹γδＡ⁻δγδＡ⁻γδγ

Try it online! Explanation:

Ｎδ      Input d
Ｎγ      Input g
Ｆβ      For i In ['a' ... 'z']
 ¿×γδ«   If g * d
  ＵＯγδι   Oblong g, d, i
  ¿‹γδ    If g < d
   Ａ⁻δγδ   d = d - g
   Ａ⁻γδγ   Else g = g - d

Annoyingly Charcoal's Oblong command won't take 0 for a dimension, which costs me 4 bytes. The other approach would be to loop while g * d, but then I couldn't work out how to iterate over b (which is predefined to the lowercase letters).

Answer 2

Pyth, 34 bytes

M?*GH?<HGCgHG+*G]jk*G]~hZgG-HGYjgF

Try it online!

Answer 3

Haskell, 90 bytes

(['a'..]!)
a?x=a<$[1..x]
((a:b)!y)x|x*y<1=""?y|x>y=map(a?y++)$b!y$x-y|z<-y-x=a?x?x++(b!z)x

Try it online!

Answer 4

Jelly, 32 bytes

Ṁ,ạ/y
³,⁴ÇÐĿp/€Fs2
pµ¢ṣLµ€+95ỌsY

Try it online!

Ṁ,ạ/y you want an explanation? Here it is.

Ṁ,ạ/y          - perform one step of the Euclidean Algorithm, input 2-element list
 ,             - pair of the following two:
Ṁ              -  maximum of the the input list
  ạ/           -  absolute difference of the two elements
    y          - use this as a mapping on the input.

³,⁴ÇÐĿp/€Fs2   - apply Euclidean Algorithm
³,⁴            - start with the pair [input 1, input 2]
   Ç           - apply a step of the Euclidean Algorithm
    ÐĿ         - repetitively until the results repeat
      p/€      - take the Cartesian product of each step
         Fs2   - flatten and split into all coordinate pairs of letters

pµ¢ṣLµ€+95ỌsY
p              - Cartesian product of inputs: provides all possible coordinate pairs.
 µ   µ€       - for each coordinate
   ṣL         - find the number of times it is included in
  ¢           - the above list of covered coordinates.
       +95Ọ   - convert number of times to letters
           s  - split into rows
            Y - join by newlines.

I can likely golf a little more by using implicit arguments instead of ³,⁴.

Answer 5

Haskell, 181 bytes

import Data.List
(['!'..'~']&)
a#[]=a
a#b=zipWith(++)a$transpose b
(s&a)b|b<1=[]|b>a=transpose$s&b$a|n<-div a b,(t,u)<-splitAt n s=foldl1(#)((<$[1..b]).(<$[1..b])<$>t)#(u&b$mod a b)

Try it online!

For 10 bytes more you get a nice spiral instead :)

!!!!!!!!!!!!!$$$#####
!!!!!!!!!!!!!$$$#####
!!!!!!!!!!!!!$$$#####
!!!!!!!!!!!!!%%'#####
!!!!!!!!!!!!!%%&#####
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""
!!!!!!!!!!!!!""""""""

Try it online!

Ungolfed

The (#) operator puts two matrices next to each other, but transposes the right one, eg:

!!!                !!!"
!!! # "#$    ->    !!!#
!!!                !!!$

a # [] = a
a # b  = zipWith (++) a $ transpose b

This is basically the recursive version of Euclid's algorithm, but instead of forgetting the divisors&remainders and returning the gcd, it builds squares from it and accumulates these with (#). The s variable are the remaining characters that we can use:

(s & a) b
  | b == 0 = []                     -- Base case
  | b > a = transpose $ (s & b) a   -- In this case we can just flip the arguments and rotate the result by 90 degrees
  | n <- div a b                    -- set n to the number of squares we need
  , (t,u) <- splitAt n s =          -- take n characters, ..
               ((<$[1..b]).(<$[1..b]) <$> t)                     -- .. build squares from them and ..
    foldl1 (#)                                                   -- put them next to each other
                                             (u & b $ mod a b)   -- recursively build the smaller squares with the remaining characters..
                                            #                    -- .. flip them and put them next to the previous one(s)

The actual function just calls the function from above with a string of all printable characters:

(['!'..'~']&)