# Visualize the Euclidean algorithm again

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 . Shortest answer in bytes wins.

Standard loopholes apply.

• – Leaky Nun May 9 '17 at 7:42

# 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).

• Oops, sorry, that was a conscious design decision, do you think negative inputs should be allowed as well? – ASCII-only May 10 '17 at 21:53
• @ASCII-only What's the current behaviour (both for 0 and negative)? My best idea would be that negative would draw to the left/top instead of right/bottom. (Also, if I use Ｗ×γδ, how do I print a different letter each time?) – Neil May 10 '17 at 22:34
• @Neil wow, I see what you mean that WOULD be annoying. – Magic Octopus Urn May 11 '17 at 14:57

# Pyth, 34 bytes

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


Try it online!

(['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! # 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 ³,⁴. # 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:

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

• You need to count import Data.List to use transpose. – Anders Kaseorg Jul 26 '17 at 19:34
• I did but it's (to my knowledge) not possible to do that import when I use a pointfree function. But I included it in the byte count, please see the TIO where the byte count is actually 164.. – ბიმო Jul 26 '17 at 20:04
• Oh. You could play wacky preprocessor games, but at some point it makes more sense to simply edit the code in your post manually after copying from TIO. – Anders Kaseorg Jul 26 '17 at 20:09