21
\$\begingroup\$

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 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
\$\endgroup\$
7
  • \$\begingroup\$ Sounds knapsacky. \$\endgroup\$
    – Adám
    Jun 23 at 7:55
  • 1
    \$\begingroup\$ @Adám It's basically a scheduling problem. :) \$\endgroup\$
    – Wheat Wizard
    Jun 23 at 7:56
  • \$\begingroup\$ Sounds like a graph coloring problem. \$\endgroup\$
    – alephalpha
    Jun 23 at 8:21
  • \$\begingroup\$ May I use 1-indexed height? May I use other value for cells where no mushroom is there? For example [3, 1, 2, null, null, 3, null, 1, 2, 3] (or something like it) instead. \$\endgroup\$
    – tsh
    Jun 23 at 10:33
  • 1
    \$\begingroup\$ @JonathanAllan They can have any height but they are part of the total height consideration. So if the input is [0,2,2] you can put the 0 at height 0 or 1 but not 2 or larger. Put another way: they should be on row 0 if there are only 0s in the input, and otherwise they can be in any row that another non-0 occupies. \$\endgroup\$
    – Wheat Wizard
    Jun 24 at 8:45

9 Answers 9

3
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ "For any input there are a wide variety of valid answers, you are allowed to output any 1 of them or all of them." So you can remove the trailing ṀÞḢ \$\endgroup\$ Jun 24 at 7:27
  • \$\begingroup\$ @KevinCruijssen I'm not 100% sure but I think that since the 0s mean "no mushrooom" that they must have minimal height \$\endgroup\$ Jun 24 at 8:38
  • 1
    \$\begingroup\$ @KevinCruijssen ...actually they may be any height, but without the this code would include solutions that have mushrooms that are too tall (e.g. input [0,0]) \$\endgroup\$ Jun 24 at 8:51
  • 1
    \$\begingroup\$ Ah ok, I didn't realize [0,0] and similar test cases would give too tall mushrooms. In that case it's indeed invalid to remove those last three bytes, since "Your task is to ... and they occupy the fewest total rows." Mb. \$\endgroup\$ Jun 24 at 9:22
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 4**w/2-1<<x>>w seems as if it should work to save 15 bytes. (It doesn't matter how far the caps get cut off to the left since they would overlap at bit 0 anyway.) \$\endgroup\$
    – Neil
    Jun 24 at 16:48
  • \$\begingroup\$ @Neil That's a great insight indeed. Thank you! \$\endgroup\$
    – Arnauld
    Jun 24 at 16:59
  • 1
    \$\begingroup\$ Well, the revised formula saves me 3 bytes too, so it's win-win! \$\endgroup\$
    – Neil
    Jun 24 at 18:38
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 115 112 102 bytes

≔⟦⟦⟦⟧⟦⟧⟧⟧ηFEθ÷×÷⊖X⁴ι²X²κX²ι«≔⟦⟧ζFη«≔§κ¹εFΦLε¬&§ελι⊞ζ⟦⁺§κ⁰⟦λ⟧Eε⎇⁼νλ⁺μιμ⟧⊞§κ⁰Lε⊞ει⊞ζκ»≔ζη»≔EηL⊟ιζI§η⌕ζ⌊ζ

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

≔⟦⟦⟦⟧⟦⟧⟧⟧η

Start with no mushrooms placed.

FEθ÷×÷⊖X⁴ι²X²κX²ι«

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.

Fη«

Loop over the existing placements.

≔§κ¹ε

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

FΦLε¬&§ελι

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

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

Generate a placement for putting this mushroom at that height.

⊞§κ⁰Lε⊞ει⊞ζκ

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

»≔ζη

Save the new placements as the current placements.

≔EηL⊟ιζ

Get the heights of all of the placements.

I§η⌕ζ⌊ζ

Output one of the placements with minimal height.

Previous less inefficient 112-byte version:

≔⟦⟦⟦⟧⟦⟧⟧⟧ηFEθ÷×÷⊖X⁴ι²X²κX²ι¿ι«≔⟦⟧ζFη«≔§κ¹εFΦLε¬&§ελι⊞ζ⟦⁺§κ⁰⟦λ⟧Eε⎇⁼νλ⁺μιμ⟧⊞§κ⁰Lε⊞ει⊞ζκ»≔ζη»Fη⊞§κ⁰¦⁰≔EηL⊟ιζI§η⌕ζ⌊ζ

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ +1+i can be -~i for -1 \$\endgroup\$ Jun 23 at 9:57
  • 3
    \$\begingroup\$ Umm.. you've modified your i+=1 to -~i instead of +1+i (at range(-x+1+i,x+i) on the fourth line I meant..) :/ \$\endgroup\$ Jun 23 at 10:08
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 28 bytes

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

Try it Online!

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

\$\endgroup\$
1
\$\begingroup\$

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)))))
\$\endgroup\$
2
  • \$\begingroup\$ Interesting, I thought this wouldn't happen since the algorithm tries to use the lowest possible max-height first. Maybe there is a bug in the range generation or something. I'll try to fix this later today. \$\endgroup\$
    – NikoNyrh
    Jun 23 at 14:12
  • 1
    \$\begingroup\$ This is fixed now, I had to revert one optimization round. \$\endgroup\$
    – NikoNyrh
    2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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