Superimposed triangles

Question

Because \$k^2\$ is the sum of the \$k\$ first odd positive integers, squared numbers can be represented as ASCII-art triangles of height \$k\$ as follows:

1²=1   2²=4   3²=9    4²=16  ...

                        *
                *      ***
         *     ***    *****
  *     ***   *****  *******

Besides, any positive integer \$n\$ can be represented as a sum of squares by iteratively subtracting the highest square less than or equal to \$n\$.

For instance: \$119=10^2+4^2+1^2+1^2+1^2\$

Note that this is a greedy algorithm which is not necessarily the shortest possible sum which, according to Lagrange's four-square theorem, never exceeds 4 terms (e.g. \$119=10^2+3^2+3^2+1^2\$).

Task

Given an integer \$n\ge1\$, output an ASCII-art made by superimposing the triangles representing the squares of the greedy decomposition described above.

The triangles must be bottom-aligned and horizontally centered.

The first triangle is filled with \$1\$'s. The second triangle turns the \$1\$'s into \$2\$'s. The third triangle turns the \$2\$'s into \$3\$'s, and so forth.

It is assumed that the input is such that its greedy decomposition does not exceed \$9\$ squares¹.

Standard I/O rules apply. Extra leading and/or trailing whitespace is acceptable as long as the output is well formatted.

_{1. According to A006892, the smallest integer for which 10 squares are required is \$453694852221687377444001767\$.}

Test cases

Input: 1

1

Input: 9

  1
 111
11111

Input: 13

  1
 121
12221

Input: 119

         1
        111
       11111
      1111111
     111111111
    11111111111
   1111112111111
  111111222111111
 11111122222111111
1111112225222111111

Input: 165

           1
          111
         11111
        1111111
       111111111
      11111111111
     1111111111111
    111111111111111
   11111111211111111
  1111111122211111111
 111111112232211111111
11111111223432211111111

Answer 1

Charcoal, 24 bytes

ＮθＷ⌊₂θ«≧⁻×ιιθＧ←↗↘←ιＩ⊕ΣＫＫ

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

Ｎθ

Input n.

Ｗ⌊₂θ«

Repeat until n's square root is zero. (Floating-point inaccuracy would apply after 2¹⁰⁶.)

≧⁻×ιιθ

Subtract the square of that from n.

Ｇ←↗↘←ιＩ⊕ΣＫＫ

Draw a centred triangle of that size using the next digit.

Answer 2

Jelly,  24  21 bytes

ƽ²ạƊƬIN½r1RṠSz⁶UŒBṚY

A full program that accepts a positive integer and prints the triangle.

Try it online!

How?

Calculate the squares, then for each create half the triangle back-to-front and upside-down using ones, then add these up and rotate and reflect to produce the full, superimposed triangle:

e.g. \$22 = 4^2 + 2^2 + 1^2 + 1^2\$:

       squares: [4,                            2,          1,    1]
half-triangles: [[[1,1,1,1],[1,1,1],[1,1],[1]],[[1,1],[1]],[[1]],[[1]]]
        summed:  [[4,2,1,1],[2,1,1],[1,1],[1]]
 fill & rotate:  [[1,0,0,0],[1,1,0,0],[2,1,1,0],[4,2,1,1]]
       reflect:  [0,0,0,1,0,0,0],[0,0,1,1,1,0,0],[0,1,1,2,1,1,0],[1,1,2,4,2,1,1]]
   print lines:     1   
                   111  
                  11211 
                 1124211

ƽ²ạƊƬIN½r1RṠSz⁶UŒBṚY - Link: positive integer, N
     Ƭ                - collect until a fixed point under:
    Ɗ                 -   last three links as a monad - f(Current):
ƽ                    -     integer square root {Current}
  ²                   -     squared
   ạ                  -     absolute difference {Current}
      I               - forward differences
       N              - negated
        ½             - square rooted
         r1           - range to 1 (vectorises)
           R          - range
            Ṡ         - signs
             S        - sum (vectorises)
              z⁶      - transpose filling with space characters
                U     - reverse each
                 ŒB   - bounce each
                   Ṛ  - reverse
                    Y - join with newline characters

Answer 3

JavaScript (Node.js), 90 bytes

f=(m,i=n=r=m,t=(g=v=>i*i>m?--i?v+g(v)+v:v+'':g(-~v,m-=i*i,r-=i+i-1))` `)=>r?f(r,n)+`
`+t:t

Try it online!

f=(
  m,   // number for render
  i=   // loop from width (`n`) to 1
  n=   // width of output
  r=m, // remaining number for next (upper) line
  t=(  // current line
    g= // loop for `i`
    v=> // value for current (most left / right side) character
      i*i>m?
        // do not need another triangle
        // render a single character if it is center
        // or pair of characters with recursive for their center
        --i?v+g(v)+v:v+'':
        // do need another triangle
        // value for render increased
        // update `m` and `r` accordingly
        g(-~v,m-=i*i,r-=i+i-1)
    )` ` // initially, the character for render is a space
  )=>
    r? // if there are number remaining for next (upper) line
      f(r,n)+`\n`+t: // render next (upper) line then current one
      t // that is last line now

Answer 4

05AB1E, 22 bytes

ΔDtïDˆn-}¯üαÅ1ƶ˜η€ûJ.c

Try it online or verify all test cases.

Explanation:

Step 1: Get the greedy list of squares:

Δ        # Loop until the result no longer changes (using the implicit input)
 D       #  Duplicate the current integer
  t      #  Take the square-root of the copy
   ï     #  Floor it to an integer
    Dˆ   #  Add a copy of that to the global array
      n  #  Take the square of that floored square root
       - #  Subtract it from the current integer for the next iteration
}¯       # After the changes-loop: push the global array
         #  e.g. input=119 → [10,4,1,1,1,0]

Try just step 1 online.

Step 2: Create the first halve of the bottom row of the output:

üα       # For each overlapping pair: get its absolute difference
         #  → [6,3,0,0,1]
  Å1     # Convert each value to a list of that many 1s
         #  → [[1,1,1,1,1,1],[1,1,1],[],[],[1]]
    ƶ    # Multiply each inner value with its 1-based index
         #  → [[1,1,1,1,1,1],[2,2,2],[],[],[5]]
     ˜   # Flatten this list of lists
         #  → [1,1,1,1,1,1,2,2,2,5]

Try just the first two steps online.

Step 3: Use it to create the entire triangle and format it to the correct output:

η        # Get the prefixes of this list
         #  → [[1],[1,1],...,[1,1,1,1,1,1,2,2,2,5]]
 €û      # Palindromize each inner list
         #  → [[1],[1,1,1],...,[1,1,1,1,1,1,2,2,2,5,2,2,2,1,1,1,1,1,1]]
   J     # Join each inner list together to a string
         #  → ["1","111",...,"1111112225222111111"]
    .c   # Centralize; join this list by newlines,
         # and add leading spaces to center all lines
         #  → "         1
         #             111
         #             ...
         #     1111112225222111111"
         # (after which it is output implicitly as result)

Answer 5

Uiua, 41 35 33 bytes

⍉⊂⇌⊸↘1⍉⬚@ ⧅⇌+@1⊚⇌°\+[⍥(⊃-√⊸⍜√⌊)∞]

Try it: Uiua pad.

-2 thanks to ovs.

Explanation: Consider the input 119.

The greedy square-finding algorithm is implemented by repeatedly subtracting the greatest square less than N until a fixed point is reached, collecting intermediate square roots in an array. The greatest square less than N is retrieved by ⍜√⌊ - "under square root floor", meaning take the square root, floor it (round it down to an integer), and square it again.

      [⍥(⊃-√⊸⍜√⌊)∞] 119
[0 0 1 1 1 4 10]

We take the consecutive differences:

      °\+
[0 0 1 0 0 3 6]

(ovs suggested °\+ instead of ≡/-◫2)

Reversing this and passing it to ⊚ where, which keeps N[i] copies of each index i of Ns, gives the left-half of the bottom row:

      ⇌
[6 3 0 0 1 0 0]
      ⊚
[0 0 0 0 0 0 1 1 1 4]
      +@1
"1111112225"

Reversing each prefix of this string, padding with spaces, gives the right-half of the triangle:

      ⬚@ ⧅⇌
╭─              
╷ "          "  
  "1         "  
  "11        "  
  "111       "  
  "1111      "  
  "11111     "  
  "111111    "  
  "2111111   "  
  "22111111  "  
  "222111111 "  
  "5222111111"  
               ╯

The last thing to do is reflect the array horizontally, and the task is complete:

      ⍉⊂⇌⊸↘1⍉
╭─                       
╷ "                   "  
  "         1         "  
  "        111        "  
  "       11111       "  
  "      1111111      "  
  "     111111111     "  
  "    11111111111    "  
  "   1111112111111   "  
  "  111111222111111  "  
  " 11111122222111111 "  
  "1111112225222111111"  
                        ╯

Answer 6

JavaScript (Node.js), 131 bytes

f=(n,i=m=n,A=(e=[...Array(2*m)]).fill(e))=>n?i*i>n?f(n,i-1,A):f(n-i*i,i,A.map((r,y)=>r.map((c,x)=>-~c-(x+y<3*m-i|y-x<m-i)||' '))):A

Try it online!

Answer 7

Retina, 81 80 bytes

.+
*
L$`(\G_|\1__)+
$#1*
\G_(?<=(_+))(?=(_*¶\1)*)
$.(_$#2*
L^$`\d
$.`* $^$%'$<%'

Try it online! Link includes test cases. Explanation:

.+
*

Convert n to unary.

L$`(\G_|\1__)+
$#1*

Greedily decompose n into positive squares, still in unary.

\G_(?<=(_+))(?=(_*¶\1)*)
$.(_$#2*

Count the number of squares that overlap each position, starting from the centre working out, in decimal.

L^$`\d
$.`* $^$%'$<%'

Turn the string of counts into the final triangle; this is the main reason I've used Retina 1 since mirroring is tricky at best in Retina 0.8.2.

Answer 8

J, 59 bytes

[:|.' 123456789'{~[:+/@(i.@->/0{|@i:)1+2%:2-/\(-<.&.%:)^:a:

Try it online!

• Greedily finds the biggest squares
• Successive differences
• Take first (largest) square, say 4, and create 4 3 2 1 0 1 2 3 4, then create a "less than table" between that and, say 3 2 1 0, where one list is constructed counting down for each of the squares. This results in a "plane" for each square, consisting of the triangular pattern we want, but upside down.
• Add the planes together
• Convert to ascii
• Reverse

Answer 9

APL+WIN, 97 bytes

Prompts for integer

r←0⍴0
n←⎕
:while n≠0
r←r,i←⌊n*.5
n←n-i*2
:end
(' ',(⍕⍳⌈/,n)~' ')[1+(0 ¯1↓⌽n),n←⊖+⌿⊃m∘.≤¨⌽¨m←⍳¨,r]

Try it online! Thanks to Dyalog Classic

Answer 10

Japt -R, 33 29 bytes

AƵV=U¬f ²V¬Ãä- ËçEÄìå+ mê û

Try it

Thanks to Shaggy for -4 with some nice Japt knowledge.

I haven't used Japt in quite a while and I remembered that it had functions to palindromize a string and center-pad an array, so this seemed like a good opportunity to pick it back up.

Answer 11

Japt -R, 29 bytes

Was tapping away at this over the weekend and then got beaten to the punch by a very similar solution.

9ƵNpU¬f)̲ÃNäa ËçEÃŬå+ ù Ëê

Try it

9ƵNpU¬f)̲ÃNäa ËçEÃŬå+ ù Ëê     :Implicit input of integer U
9Æ                                :Map the range [0,9)
 µ                                :  Decrement U by
  N                               :    Array of all inputs (i.e., [U] initially)
   p                              :    Push
    U¬                            :      Square root of U
      f                           :      Floor
       )                          :    End push
        Ì                         :    Last element
         ²                        :    Squared
          Ã                       :End map
           Nä                     :Consecutive pairs of array reduced by
             a                    :  Absolute difference
               Ë                  :Map each D at 0-based index E
                çE                :  E repeated D times
                  Ã               :End map
                   Å              :Slice off first element
                    ¬             :Join
                     å+           :Cumulatively reduce by concatenating
                        ù         :Left pad each with spaces to the length of the longest
                          Ë       :Map
                           ê      :  Palindromise
                                  :Implicit output joined with newlines