# Generate a mantis's head (symmetrical triangle)

Given guaranteed strictly positive integers $$\w\$$ and $$\n\$$, output

• An equilateral triangle array with side length $$\w\$$, filled with two distinct, consistent values. I'll call these 0 and 1 but they do not have to be equal to 0 and 1.
• The number of 1s inside this array must be equal to $$\n\$$.
• The output triangle must be symmetrical, meaning that it is the same when flipped horizontally or diagonally (your choice).
• An equilateral triangle array can be an array with $$\w\$$ elements where for $$\1\$$ to $$\w\$$ (inclusive), there is a sub-array with that number of elements inside of $$\w\$$ (for example, but it may be outputted via ascii-art, see below).

($$\n\$$ values are guaranteed to fit in the triangle)

## Examples

w=3, n=1
1
0 0
0 0 0

w=3, n=2
0
1 1
0 0 0

w=3, n=3
1
1 1
0 0 0

w=3, n=4
0
1 1
1 0 1

w=3, n=5
0
1 1
1 1 1

w=3, n=6
1
1 1
1 1 1


## Valid Output Format List

In this case the distinct values are 1 and 0. Possible output triangles (all considered equivalent) with 1s at their corners and center and a width of 4 are:

   1
0 0
0 1 0
1 0 0 1

1
00
010
1001

[[1],[0,0],[0,1,0],[1,0,0,1]]

1 0 0 1
0 1 0
0 0
1

[[1],[0,0],[0,1,0],[1,0,0,1]]

1
0
00
11
00
0
1

1
0
0 0
1 1
0 0
0
1


here is a test case validator in Jq, takes {"w": w, "n": n, "a": result you wish to check} (in the JSON array format like [[1],[0,0],[0,1,0],[1,0,0,1]])

• Sandboxed May 21 '21 at 15:33
• For w=3, n=1; Why output is 1;0,0;0,0,0 instead of 0;0,0;0,1,0?
– tsh
May 22 '21 at 4:16
• @tsh Both are valid, I guess the former was just easier to type :P May 22 '21 at 21:12

# Jelly, 15 bytes

RØ.ṗŒpFS=ɗƇUƑƇḢ


Try it online!

-1 byte thanks to caird coinheringaahing

RØ.ṗŒpFS=ɗƇUƑƇḢ  Main Link; accepts w as the left argument and n as the right argument
R                Range; [1, 2, ..., w]
Ø.ṗ             [0, 1] ~ cartesian power ~ ^
Œp           Cartesian Product of ^'s items - this gets all valid triangles of the right size
---ɗƇ      Keep elements where
S         the sum of
F          the triangle flattened
=        equals (right argument)
Ƈ   Keep elements where
Ƒ    the element is the same when
U     each sub-list is reversed
Ḣ  Get the first such triangle

• -1 byte May 21 '21 at 15:51
• @cairdcoinheringaahing oh yeah it's not a 0,2 chain so I don't need to specify right argument. i'm dumb lol May 21 '21 at 15:52

# JavaScript (ES6), 54 bytes

A much shorter approach. I think this is equivalent to @ovs' answer.

Expects (n)(w). Returns a list of lists, from bottom to top.

n=>g=w=>w?[Array(w).fill(n<w?0:(n-=w,1)),...g(w-1)]:[]


Try it online!

# JavaScript (ES6),  88  85 bytes

This one inserts $$\1\$$'s as soon as it can.

Expects (n)(w). Returns a list of lists, from bottom to top.

n=>g=w=>w?[(h=q=>k--?k--?[q=n>1?--n/n--:0,...h(),q]:[n&&n/n--]:[])(k=w),...g(w-1)]:[]


Try it online!

# Japt, 20 bytes

ò1 Ô®>V?Zî0:(VµZ,Zî1


Try it

• we start from the biggest row, if n is not smaller than its length we fill the row with 1s

• we can always put the rest of 1s on the next lines.

• filling entire rows gives a specular triangle.

- input: U=w , V=n
ò1 Ô   - range[1..w] reversed
®      - map to Z=>
>V?    - if Z>n
Zî0     * string of Z 0s
:(     - else
VµZ,    * n-=Z and..
Zî1     * string of Z 1s


# Python 3.8, 47 bytes

Returns a nested list of booleans.

f=lambda w,n:w*[1]and[[x:=n>=w]*w]+f(w-1,n-w*x)


Try it online!

• I have limited python experience... and would have assumed that only the right hand side of the and is ever returned. How does w*[1] come into play? May 22 '21 at 6:20
• @Jonah As long as w is positive w*[1] is some non-empty list, which is always truthy, and the right hand side is returned. But as soon as w reaches zero this evaluates to the empty list (falsy) and serves as the base case of the recursion. (I could've used any other value instead of the 1)
– ovs
May 22 '21 at 8:00
• Thanks. Empty list = falsy is the piece I was missing... coming from ruby. May 22 '21 at 8:07

# 05AB1E, 20 12 bytes

Based on the observation that all outputs can be created by having each row as all 1's or all 0's. Check out AZTECCO's answer, which got there an hour earlier.

1ÝIã.ΔƶOQ}ā×


Try it online!

1Ý            # push the range [0..1] == [0, 1]
Iã          # raise this to the first input (w) cartesian power
# this yields all w-tuples of 1's and 0's
.Δ   }    # find the first that satisfies:
ƶ       #   each value multiplied by its 1-based index
O      #   take the sum of that
Q     #   is equal to the second input (n)
ā   # push the range [1..len(value)] == [1..w]
×  # repeat each digit in the select tuple that number of times


Alternative 12 byters (Both find a subset of [1..w] that sums to n and build the triangle from that):

L©æ.ΔOQ}®å®×


Try it online!

LDæIÅœÃнsåā×


Try it online!

• Ehm.. Do you refer to my observation? May 22 '21 at 0:16
• @AZTECCO I didn't read through your answer before, but it seems like you got there first (+1)
– ovs
May 22 '21 at 7:56
• that's fine then. Thanks for giving me credits anyway! May 22 '21 at 15:29

# Charcoal, 4840 28 bytes

ＮηＦ⮌…·¹Ｎ«Ｇ↘↖ιＩ¬‹ηι↓¿¬‹ηι≧⁻ιη


Try it online! Link is to verbose version of code. Takes arguments in the order n, w. Explanation: Port of @AZTECCO's answer.

Ｎη


Input n.

Ｆ⮌…·¹Ｎ«


Count from w down to 1.

Ｇ↘↖ιＩ¬‹ηι↓


Output a line of 1s or 0s depending on whether n is big enough.

¿¬‹ηι≧⁻ιη


Reduce n accordingly.

ＮθＦＮ⊞υ¹Ｅθ⭆Ｅ⌊⟦⊕ι⁻θι⟧‹⁺ιλ⊖θ∧›№υ¹λ⊟Ｅ⊕λ⊟υ‖Ｏ↘


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

Ｎθ


Input w.

ＦＮ⊞υ¹


Input n and make a list of that many 1s.

Ｅθ


Start drawing a triangle of height w.

⭆Ｅ⌊⟦⊕ι⁻θι⟧


Draw the upper left half of the triangle.

‹⁺ιλ⊖θ


Calculate whether this square lies on the diagonal or not.

∧›№υ¹λ⊟Ｅ⊕λ⊟υ


If n is large enough to need both this square and its reflection, then reduce n accordingly and output a 1, otherwise output a 0. This always works because the very last square is on the diagonal.

‖Ｏ↘


Reflect to complete the triangle.

# C (gcc), 62 bytes

f(w,n,c){for(c=n>=w,w&&f(w-1,n-w*c);~w;putchar(w--?48+c:10));}


Try it online!

# Jelly, 13 bytes

ŒPS=¥ƇḢċ⁹xɗⱮ⁸


Try it online!

A dyadic link taking w as its left argument and n as it’s right. Returns a list of lists of 0s and 1s. Based on the observation by @AZTECCO and @ovs that we can compose this solely of rows of 0s and 1s so be sure to upvote their answers too!

# J, 33 bytes

((]echo@#>:)]0>.<:@],~[-]*>:)/^:_


Try it online!

A function whose output (rather than return value) prints what we want.

# Vyxalr, 18 16 bytes

⅛ɾṘƛ¼:n≤:Sn*,[-⅛


Try it Online!

⅛                # (Implicit input) Push to global array
ɾṘ              # (Implicit input) range(1,n+1) reversed
ƛ             # Foreach [n]
¼:           # Push from global array and duplicate [n,r,r]
n≤         # Push n and check if r >= n [n,r,b]
:Sn*,    # Duplicate, coerce to string (0 or 1), multi by n and output.
[   # If ToS is truthy (r >= n) [n,r]
-  # Subtract [r-n] (r flag reverses arguments)
⅛ # Push to global array.


Due to a bug with redefining the register inside a lambda, I'm forced to use the global array. It works well though, and I don't think it'd be any more golfable if the register worked properly.

Based on the insight that everything can be made of rows of 1s and 0s.

# R, 54 bytes

function(w,n)for(i in w:1){show(1:i&(a=n>=i));n=n-i*a}


Try it online!

Using TRUE and FALSE as the values.