How tall are the mushrooms?

Question

In this challenge you will receive a list of non-negative integers. Each one represents a mushroom with a cap of that radius centered at that location. So a 0 means that it occupies no space at all, a 1 means that its cap only occupies space above it, a 2 means it occupies space above it and one unit to the left and right etc. More generally for size \$n\$ a total of \$2n-1\$ spaces are occupied, with the exception of 0 which occupies 0 spaces (i.e. there's no mushroom at all).

Mushroom caps can't occupy the same space as each other but mushrooms can have different heights to avoid collisions.

So for example here we have two mushrooms. They can't be in the same row since they would occupy the same space but if they are given different heights there is no issue:

          =-=-=
            |
  =-=-=-=-= |
      |     |
[ 0,0,3,0,0,2,0 ]

^{(Stems are drawn with | for clarity, but can't collide)}

Your task is to take as input a list of mushrooms and output a list of heights, one for each input mushroom, such that there is no collisions between mushrooms and they occupy the fewest total rows.

For example here we have a worked case:

=-=-= =-=-=-=-=-=-= =
  |         |       |
  | =-=-=   |   =-=-=
  |   |     |     | |
  =-=-=     =-=-=-=-=
  | | |     |   | | |
[ 2,2,2,0,0,4,0,3,2,1 ] <- Widths
[ 2,0,1,0,0,2,0,0,1,2 ] -> Heights

^{(Stems are drawn with |, and extra spacer rows are added between layers for clarity)}

For any input there are a wide variety of valid answers, you are allowed to output any 1 of them or all of them. You may also consistently use 1-indexed heights instead of 0-indexed heights if you wish.

This is code-golf so the goal will be to minimize the size of your source code as measured in bytes.

Selected examples

Here are some selected examples with possible solutions:

This one defeats a certain greedy algorithm:

  =-=-= =
    |   |
=-=-= =-=-=-=-=
  | |   | |
[ 2,2,0,1,3 ] <- Width
[ 0,1,0,1,0 ] -> Height

This one requires everything to be on its own row:

    =-=-=-=-=-=-=
          |
  =-=-=-=-=-=-=
        | |
    =-=-= |
      | | |
    = | | |
    | | | |
=-=-= | | |
  | | | | |
[ 2,1,2,4,4 ] <- Width
[ 0,1,2,3,4 ] -> Height

Answer 1

Jelly, 23 bytes

Ḥ’R_"+"JJṗL;Ɱ"ẎQƑɗƇƲṀÞḢ

A monadic Link that accepts a list of non-negative integers and yields a list of positive integers specifying the levels (i.e. 1-indexed heights).

Try it online!

How?

Inefficient brute-force...

Ḥ’R_"+"JJṗL;Ɱ"ẎQƑɗƇƲṀÞḢ - Link: cap sizes
Ḥ                       - double (the cap sizes)
 ’                      - decrement (these)
  R                     - range (those) - i.e. [[1..2*n-1] for each cap size, n]
    "                   - zip (those) and (cap sizes) applying:
   _                    -   subtraction - i.e. make these offsets like [...,-1,0,1,...]
       J                - range of length (cap sizes) -> [1..length(cap sizes)]
      "                 - zip (the offsets) with (the range) applying:
     +                  -   addition -> covered indices of each mushroom, "covers"
                   Ʋ    - last four links as a monad - f(covers):
        J               -   range of length -> same as [1..length(cap sizes)]
          L             -   length -> same as length(cap sizes)
         ṗ              -   (range) Cartesian power (length)
                              -> all lists of the same length as cap sizes
                                 using alphabet [1..length(cap sixes)] 
                  Ƈ     -   filter keep those (arrangements) for which:
                 ɗ      -     last three links as a dyad - f(arrangement, covers):
             "          -       zip with:
            Ɱ           -         map with:
           ;            -           concatenate -> coordinates
              Ẏ         -       tighten
                Ƒ       -       is invariant under?:
               Q        -         deduplicate
                     Þ  - sort by:
                    Ṁ   -   maximum value
                      Ḣ - head

Answer 2

JavaScript (ES7),  146 131  129 bytes

Saved 15 bytes thanks to @Neil!

Returns a single solution as a space-separated string.

f=(a,...B)=>(F=(x,b,o,w=a[x])=>1/w&&b.every((v,i,[...c])=>v&(c[i]|=m=4**w/2-1<<x>>w,m)||F(x+1,c,O=[o]+i+' ')))(0,B)?f(a,...B,0):O

Try it online!

How?

We generate one bitmask per mushroom cap and attempt to dispatch them among \$N\$ rows without any collision, trying all possible distributions. We start with \$N=0\$ (which is obviously unlikely to work) and increment \$N\$ until a solution is found.

The pattern for a mushroom cap of width \$w\$ and position \$x\$ is computed with:

$$\left\lceil\frac{4^w}{2}-1\right\rceil$$

which generates \$max(0,2w-1)\$ consecutive \$1\$'s.

The final bitmask is obtained by shifting this pattern by \$x\$ positions to the left and \$w\$ positions to the right.

Answer 3

Python3, 248 bytes:

from itertools import*
E=enumerate
C=lambda x,c,I:[i for i,a in E(x)if a*((a-1+i>=I-c+1 and i<I)or(i-a+1<=I+c-1 and i>I))]
f=lambda x:min([i for i in product(*[range(j+1)for j in x])if all(all(i[t]!=m for t in C(x,x[n],n))for n,m in E(i))],key=max)

Try it online!

Heights are 0-indexed.

A longer, no-import solution:

E=enumerate
def F(x):r={j:a for a,b in min(f(x),key=len).items()for j in b};return[r[i]*(a>0)for i,a in E(x)]
C=lambda x,c,I:{*[i for i,a in E(x)if a*((a-1+i>=I-c+1 and i<I)or(i-a+1<=I+c-1 and i>I))]+[I]}
def f(x,c=0,d={0:[]}):
 if len(x)==c:yield d;return
 for i in d:
  if not C(x,x[c],c)&set(d[i]):yield from f(x,c+1,{**d,i:d[i]+[c]})
 yield from f(x,c+1,{**d,max(d)+1:[c]})

Try it online!

Answer 4

Charcoal, 115 112 102 bytes

≔⟦⟦⟦⟧⟦⟧⟧⟧ηＦＥθ÷×÷⊖Ｘ⁴ι²Ｘ²κＸ²ι«≔⟦⟧ζＦη«≔§κ¹εＦΦＬε¬＆§ελι⊞ζ⟦⁺§κ⁰⟦λ⟧Ｅε⎇⁼νλ⁺μιμ⟧⊞§κ⁰Ｌε⊞ει⊞ζκ»≔ζη»≔ＥηＬ⊟ιζＩ§η⌕ζ⌊ζ

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

≔⟦⟦⟦⟧⟦⟧⟧⟧η

Start with no mushrooms placed.

ＦＥθ÷×÷⊖Ｘ⁴ι²Ｘ²κＸ²ι«

For each mushroom, calculate a bitmask corresponding to the space that it occupies. Edit: Saved 3 bytes by using my golf to @Arnauld's formula.

≔⟦⟧ζ

Start collecting placements that include this mushroom.

Ｆη«

Loop over the existing placements.

≔§κ¹ε

Get the bitmasks for the heights as this gets used a lot.

ＦΦＬε¬＆§ελι

Find whether this mushroom can be placed at any existing height.

⊞ζ⟦⁺§κ⁰⟦λ⟧Ｅε⎇⁼νλ⁺μιμ⟧

Generate a placement for putting this mushroom at that height.

⊞§κ⁰Ｌε⊞ει⊞ζκ

Generate a placement for putting this mushroom at a new height.

»≔ζη

Save the new placements as the current placements.

≔ＥηＬ⊟ιζ

Get the heights of all of the placements.

Ｉ§η⌕ζ⌊ζ

Output one of the placements with minimal height.

Previous less inefficient 112-byte version:

≔⟦⟦⟦⟧⟦⟧⟧⟧ηＦＥθ÷×÷⊖Ｘ⁴ι²Ｘ²κＸ²ι¿ι«≔⟦⟧ζＦη«≔§κ¹εＦΦＬε¬＆§ελι⊞ζ⟦⁺§κ⁰⟦λ⟧Ｅε⎇⁼νλ⁺μιμ⟧⊞§κ⁰Ｌε⊞ει⊞ζκ»≔ζη»Ｆη⊞§κ⁰¦⁰≔ＥηＬ⊟ιζＩ§η⌕ζ⌊ζ

Try it online! Link is to verbose version of code. Explanation: Always places zero-width mushrooms at zero height instead of at all possible heights.

Answer 5

05AB1E, 45 43 bytes

εD(Ÿ¦¨N+}[DN.Œ.Δε˜DÙQ}P}Zd#\}ε€ÅsIgݨåN*}øO

Brute-force approach.

Try it online or verify both test cases.

Explanation:

Step 1: Change each value in the input to a list of indices it can reach:

ε            # Map over each value of the (implicit) input-list:
 D(          #  Create a negative copy
   Ÿ         #  Pop both, and push a list in the range [n,-n]
    ¦¨       #  Remove the first and last to make the range (n,-n)
             #  (or empty the list if n=0)
      N+     #  Add the current map-index as offset
}            # Close the map

Try just this first step.

Step 2: Indefinitely loop up from \$N=0\$ and get all \$N\$-element combinations of the list of lists. Stop as soon as we've found a partition for which all inner indices are unique.

[            # Start an infinite loop:
 D           #  Duplicate the list we've created in step 1
  N          #  Push the loop-index `N`
   .Π       #  Pop both, and get all N-sized partitions of the list
     .Δ      #  Find the first partition that's truthy for:
             #  (or -1 if none are truthy)
       ε     #   Map over each part:
        ˜    #    Flatten the list of lists of indices
         DÙQ #    Check whether all indices are unique:
         D   #     Duplicate it
          Ù  #     Uniquify this copy
           Q #     Check if both lists are still the same
       }P    #   After the map: check if all parts were truthy
      }Z     #  After the find_first: push the maximum (without popping)
             #  (which results in "-" for -1)
        d    #  If this is a non-negative integer (0 for "-", 1 otherwise)
         #   #   Stop the infinite loop, since we have a hit
         \   #  (else:) discard the -1 that's still on the stack
}            # Close the infinite loop

Try just the first two steps.

Step 3: Convert this found result of parts of index-ranges to a list of heights to output:

ε            # Map over each part in this partition:
 €           #  Inner map over each inner index-range (-n,n):
  Ås         #   Pop and leave just the middle value
             #   (this is the offset we've added in step 1,
             #    or [] if the list was empty for n=0)
    Igݨ     #  Push a list in the range [0, input-length):
    I        #   Push the input-list
     g       #   Pop and push its length
      Ý      #   Pop and push a list in the range [0,length]
       ¨     #   Remove the last item to make the range [0,length)
        å    #  Check for each if it's in the earlier list
         N*  #  Multiply each by the 0-based map-index,
             #  which are the heights
}ø           # After the map: zip/transpose; swapping rows/columns
  O          # Sum each inner list (mapping each to its max, since each inner
             # list will only contain (at most) one non-0 height)
             # (after which this list of heights is output implicitly)

Note: It outputs the first result it can find, so for the second example test case, it outputs this list of mushroom-heights:

    =-=-=       =-=-=
      |           |
  =-=-=     =-=-=-=-=
    | |         | |
=-=-= =-=-=-=-=-=-= =
[ 2,2,2,0,0,4,0,3,2,1 ] <- Widths
[ 0,1,2,0,0,0,0,1,2,0 ] -> Heights

Answer 6

Python, 293 264 263 262 bytes

-1 bytes thanks to @Kevin Cruijssen

j=lambda h:min((((n:=h.copy()).__setitem__(a+b,n.pop(a)|n.pop(b)))or j(n)for a in h for b in h if not h[a]&h[b]),default=h,key=len)
def f(w):
    r=[0]*len(w);i=0
    for K in j({(i,):set(range(-x-~i,x+i))for i,x in enumerate(w)}):
        for k in K:r[k]=i
        i+=1
    return r

Attempt This Online!

Note: it's extremely inefficient.

A slightly more efficient (and longer) variant:

from itertools import*
j=lambda h:min((((n:=h.copy()).__setitem__(a+b,n.pop(a)|n.pop(b)))or j(n) for a,b in combinations(h,2)if not h[a]&h[b]),default=h,key=len)
def f(w):
    r=[0]*len(w);i=0
    for K in j({(i,):set(range(-x+1+i,x+i))for i,x in enumerate(w) if x}):
        for k in K:r[k]=i
        i+=1
    return r

Attempt This Online!

Answer 7

JavaScript (Node.js), 143 142 bytes

f=(a,i=x=[])=>(g=y=>1/a[y.length]?x.some(i=>g(O=[...y,i])):!a.some((P,p)=>a.some((Q,q)=>y[p]==y[q]&p<q&P+Q>q-p+1&&P*Q)))([])?O:f(a,x.push(+i))

Try it online!

Answer 8

Vyxal, 28 bytes

d‹ɾ-:ż+:£₌żLÞẊ'¥¨£v"ÞfÞu;⁽G∵

Try it Online!

Port of Jelly. Outputs a list of 1-indexed heights.

Answer 9

Clojure, 214 227 bytes

(defn f([W](:H(nth(flatten(for[m(range)](f m 0 W[][1])))0)))([m i W H O](if-let[w(nth W i nil)](for[h(range(if(= w 0)1 m))O[(into O(for[d(range(+(- w)1)w)][(+ i d)h]))]:when(apply distinct? O)](f m(inc i)W(conj H h)O)){:H H})))

TIO.

Buggy code:

(defn f([W](:H(nth(flatten(f 0 W[][1]))0)))([i W H O](if-let[w(nth W i nil)](for[m(range)h(range(if(= w 0)1 m))O[(into O(for[d(range(+(- w)1)w)][(+ i d)h]))]:when(apply distinct? O)](f(inc i)W(conj H h)O)){:H H})))

I thought I could move the for[m(range)... from the initial function call inside the recursion, but apparently it leads to a wrong output in come cases.

Less golfed:

(defn f
  ([widths] (first (flatten (for [max-height (range)] (f max-height 0 widths [] [])))))

  ([max-height ix widths heights occupied]
   (if (-> widths count (= ix))
     {:heights heights :occupied occupied}
     (for [w [(widths ix)]
           h (range (if (= w 0) 1 max-height))
           :let [new-occupied (for [dx (range (-> w - inc) w)] [(+ ix dx) h])
                 occupied (into occupied new-occupied)]
           :when (apply distinct? nil occupied)] ; Cannot call `distinct?` without any arguments, thus the `nil` is there.
       (f max-height (inc ix) widths
          (conj heights h)
          occupied)))))