14
\$\begingroup\$

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

Standard loopholes apply.

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Related. \$\endgroup\$
    – Leaky Nun
    Commented May 9, 2017 at 7:42

9 Answers 9

Reset to default
5
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Oops, sorry, that was a conscious design decision, do you think negative inputs should be allowed as well? \$\endgroup\$
    – ASCII-only
    Commented May 10, 2017 at 21:53
  • \$\begingroup\$ @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?) \$\endgroup\$
    – Neil
    Commented May 10, 2017 at 22:34
  • \$\begingroup\$ @Neil wow, I see what you mean that WOULD be annoying. \$\endgroup\$
    – Magic Octopus Urn
    Commented May 11, 2017 at 14:57
3
\$\begingroup\$

Uiua, 31 bytes 32 bytes

Edit: The recur ↬ glyph has been removed from the language

|2+@`;⍥(⎋=0⧻.⊙⬚0+.↘⇌×⍖.△.)∞.↯∶1⊂

Try it online!

Explanation:

                                  ⊂   # Put the dimensions into an array
                               ↯∶1    # Make a matrix of 1s with the dimensions
                              .       # Copy the result
      ⍥(                   )∞        # Repeat forever
                          △.          # Get the shape of the latest matrix
                       ⍖.            # Get the descending indices 
                      ×              # Multiply these with the shape
                                     # (zeros out the larger dimension)
                     ⇌               # Reverse the array
                    ↘                # Remove the largest square from the latest matrix
              ⊙⬚0+.                 # Add the new matrix to the original
                                     # (using 0s where the shape doesn't match)
         ⎋=0⧻.                       # Break if the length of the new matrix is 0
  +@`;                               # Add char ` to the result to get 1=a, b=2, etc.
|2                                   # Signature of function

Example:

Input: 4 2   Stack (top on left):
             # 4 2
⊂            # [4 2]
↯∶1          # ╭─     
             # ╷ 1 1  
             #   1 1  
             #   1 1  
             #   1 1  
             #       ╯
.            # ╭─      ╭─
             # ╷ 1 1   ╷ 1 1  
             #   1 1     1 1  
             #   1 1     1 1  
             #   1 1     1 1  
             #       ╯       ╯
⍥( )∞
△.           # [4 2] ╭─      ╭─
             #       ╷ 1 1   ╷ 1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #             ╯       ╯ 
⍖.          # [0 1] [4 2] ╭─      ╭─
             #             ╷ 1 1   ╷ 1 1  
             #               1 1     1 1  
             #               1 1     1 1  
             #               1 1     1 1  
             #                   ╯       ╯ 
×            # [0 2] ╭─      ╭─
             #       ╷ 1 1   ╷ 1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #             ╯       ╯ 
⇌            # [2 0] ╭─      ╭─
             #       ╷ 1 1   ╷ 1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #         1 1     1 1  
             #             ╯       ╯ 
↘            # ╭─      ╭─
             # ╷ 1 1   ╷ 1 1  
             #   1 1     1 1  
             #       ╯   1 1  
             #           1 1  
             #               ╯
⊙⬚0+.       # ╭─      ╭─
             # ╷ 1 1   ╷ 2 2  
             #   1 1     2 2  
             #       ╯   1 1  
             #           1 1  
             #               ╯
⧻.           # 2 ╭─      ╭─
             #   ╷ 1 1   ╷ 2 2  
             #     1 1     2 2  
             #         ╯   1 1  
             #             1 1  
             #                 ╯
⎋=0          # No break
△.           # [2 2] ╭─      ╭─
             #       ╷ 1 1   ╷ 2 2  
             #         1 1     2 2  
             #             ╯   1 1  
             #                 1 1  
             #                     ╯
⍖.          # [0 1] [2 2] ╭─      ╭─
             #             ╷ 1 1   ╷ 2 2  
             #               1 1     2 2  
             #                   ╯   1 1  
             #                       1 1  
             #                           ╯
×            # [0 2] ╭─      ╭─
             #       ╷ 1 1   ╷ 2 2  
             #         1 1     2 2  
             #             ╯   1 1  
             #                 1 1  
             #                     ╯
⇌           # [2 0] ╭─      ╭─
             #       ╷ 1 1   ╷ 2 2  
             #         1 1     2 2  
             #             ╯   1 1  
             #                 1 1  
             #                     ╯
↘            # [] ╭─
             #    ╷ 2 2  
             #      2 2  
             #      1 1  
             #      1 1  
             #          ╯
⊙⬚0+.       # [] ╭─
             #    ╷ 2 2  
             #      2 2  
             #      1 1  
             #      1 1  
             #          ╯
⧻.           # 0 [] ╭─
             #      ╷ 2 2  
             #        2 2  
             #        1 1  
             #        1 1  
             #            ╯
⎋=0          # Break
+@`;         # ╭─
             # ╷ "bb"  
             #   "bb"  
             #   "aa"  
             #   "aa"  
             #        ╯

Previous solution:

+@`!(|1 ⬚0+↬>0/+△.↘⇌×⍖.△..)↯∶1⊂
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – DLosc
    Commented Oct 16, 2023 at 22:19
2
\$\begingroup\$

Pyth, 34 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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:

(['!'..'~']&)
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You need to count import Data.List to use transpose. \$\endgroup\$
    – Anders Kaseorg
    Commented Jul 26, 2017 at 19:34
  • \$\begingroup\$ 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.. \$\endgroup\$
    – ბიმო
    Commented Jul 26, 2017 at 20:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Anders Kaseorg
    Commented Jul 26, 2017 at 20:09
1
\$\begingroup\$

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 ³,⁴.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 78 bytes

>/|:[:u:97+1(0&g@{:]F.:(((g=.$~,~)~1+0{,),(~:#)|:])}:)@}.0}:@{0|:(<.,|@-)/^:a:

Attempt This Online!

Surprisingly tough to golf in J. Tried a few approaches, this was the best of them, but still feels like there's room for improvement.

Basic approach:

  • Generate successive differences until a repeat, eg: 10 6 gives 6 4 2 2.
  • "Roll it up" starting from the smaller squares (ie, stack a 2x2 on a 2x2, then transpose it and put a 4x4 on that, then transpose that and put a 6x6x on top of it). We do transposes as needed to make the side lengths line up. We always stack our new larger square atop the result up to that point. The whole computation is expressed as a fold.
  • The first square starts as a square of zeroes, and as we add each additional square its number increments by one. At the end we have our result but with numbers instead of letters.
  • Convert the numbers to ascii letters.
  • Finally, transpose the entire result if needed, so that the result dimensions match the order of the arguments.
Improve this answer
\$\endgroup\$
1
+100
\$\begingroup\$

J, 30 bytes

[:u:97+0]F.:({.>:)(-/:*|.)^:a:

Attempt This Online!

Saw ... F.: ... ^:a: in Jonah's answer and thought it might work better, and it actually did. Remove the leading [:u:97+ to get a numeric matrix.

[:u:97+0]F.:({.>:)(-/:*|.)^:a:    input: a vector of dimensions
                  (      )^:a:    repeat until convergence and collect iterations:
                   -/:*|.         subtract smaller from larger
                                  (it stops when one side becomes zero)
                      [10,4] becomes [[10,4],[6,4],[2,4],[2,2],[2,0]]
       0]F.:({.>:)    construct the numeric matrix:
       0]F.:(    )    fold from the right, starting with single 0,
             {.>:     increment the input matrix and pad with zeros
                      to the size of the next larger dimensions
[:u:97+    map 0, 1, ... to a, b, ...

J, 37 bytes

[:u:97+f=:$&0`({.1+[:f]-/:*|.)@.(~:/)

Attempt This Online!

Recursive function seems to be the way here. Takes a vector of two positive integers and returns a character matrix. If a numeric matrix is acceptable, 28 bytes: $&0`({.1+[:$:]-/:*|.)@.(~:/).

[:u:97+f=:$&0`({.1+[:f]-/:*|.)@.(~:/)
       f=:$&0`({.1+[:f]-/:*|.)@.(~:/)    inner recursive function
             `                @.(~:/)    if two parts are equal,
          $&0                            create a zero matrix of that dimensions
              (              )      otherwise,
                      ]-/:*|.       subtract the smaller part from the larger part
                   [:f              recurse
               {.1+                 add 1 to each element and pad to the requested size
                                    with zeros
[:u:97+    map 0, 1, ... to a, b, ...
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I was hoping you would improve my answer, and this is just beyond beautiful. Seems obvious in hindsight but I think this insight is brilliant. Going to reward this with a bounty. \$\endgroup\$
    – Jonah
    Commented Oct 16, 2023 at 19:56
0
\$\begingroup\$

JavaScript (V8), 111 bytes

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

Try it online!

Improve this answer
\$\endgroup\$

Your Answer

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

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