19
\$\begingroup\$

In this challenge you will receive a list of pairs of non-negative integers representing a mushroom forest. Each pair represents a mushroom whose center is at that horizontal coordinate. The only part of the mushroom we care about is the cap (the flat bit at the top).

The first integer in each pair represents which row the cap is placed in. i.e. the height of the mushroom.

The second integer represents the radius of the cap. If it's zero then there just isn't a mushroom in that position. Other for size \$n\$ a total of \$2n-1\$ spaces are occupied centered at the index of the pair. For example 1 means that its cap only occupies a space above it, a 2 means it occupies a space above it and the spaces one unit to the left and right.

As an example here's an example with the forest drawn:

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

(For clarity, stems are drawn with | and extra spacer rows are added between layers)

Your task is to determine from an input list whether there are any collisions between mushroom caps. That is if there is any pair of mushrooms that both occupy 1 or more common spaces.

You should output one of two distinct values. One if there is a collision and the other if there is not.

You may take input instead of a list of pairs as two separate lists of the same length.

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

Test cases

Test cases are provided with an illustration.

No collision

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

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

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

With Collisions

Locations with a collision are marked with X.

 =-X-X-=
   | |
   | |
   | |
[0,1,1] <- Heights
[0,2,2] <- Widths

   X-=-=-=-=-=-=
   |     |
[0,0,0,0,0] <- Heights
[0,1,0,0,4] <- Widths

 =-=-X-=-=-=-=
   |     |
[0,0,0,0,0] <- Heights
[0,2,0,0,3] <- Widths
```
\$\endgroup\$
1

16 Answers 16

5
\$\begingroup\$

K (ngn/k), 31 bytes

{a~?a:,/x,''(!#y)+(?,/-:\!:)'y}

Try it online!

-4 bytes thanks to @ovs! Golfed even more with inspiration from @UnrelatedString's approach.

Explanation

Height list is x, width list is y.

  • (?,/-:\!:)'y convert each width to range (-width, width)
  • (!#y)+ add indices
  • x,'' add corresponding height to each index in each width range
  • a~?a:,/ flatten, check for duplicates
\$\endgroup\$
0
3
\$\begingroup\$

MathGolf, 22 bytes

mÆ╤╞╡ï+m▐ò┤\h?a*^~]_▀=

Port of my 05AB1E answer (the 19-bytes version; since the 22-bytes version was using a group-by, which MathGolf lacks and I also couldn't find any suitable alternative for with its available builtins after some trial-and-error for more than an hour.. :/)

Just like my 05AB1E answer: input as two separated (equal-length) lists, first being the list of widths, second the heights.

Try it online.

Explanation:

Basically the same three steps as my 05AB1E answer:

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

m          # Map over the first (implicit) input-list of widths,
 Æ         # using 5 bytes as inner code-block:
  ╤        #  Convert it to a list in the range [-n,n]
   ╞╡      #  Remove the first/last items to change it to range (-n,n)
     ï+    #  Add the 0-based map index to each value as offset

Try just this first step.

Step 2: Pair each inner index with the height of the second input:

m▐         # Append each value in the second (implicit) input-list of heights to
           # the (-n,n)-list at the same position
  ò        # Loop over the lists, using 8 bytes as inner code-block:
   ┤       #  Extract tail; push remainder-list and last item separated
    \      #  Swap so the remainder-list is at the top
     h     #  Push its length (without popping)
      ?    #  Triple-swap the [tail,list,length] to [list,length,tail]
       a   #  Wrap the tail into a list
        *  #  Repeat it the length amount of times
         ^ #  Zip to create pairs of the list with these repeated tails

Try just the first two steps.

Step 3: Check if all (flattened) pairs are unique, and output the result:

   ~       #  Still in the loop of step 2: dump the pairs to the stack
]          # After the loop: wrap all pairs on the stack into a list
 _▀=       # Check if all pairs are unique:
 _         #  Duplicate the list of pairs
  ▀        #  Uniquify the copy
   =       #  Check if both lists are still the same
           # (after which the entire stack is output implicitly as result)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You get bonus points for spelling out mATH \$\endgroup\$
    – Jonah
    Jun 24 at 14:19
  • \$\begingroup\$ @Jonah Ah lol, hand't even noticed that. :D \$\endgroup\$ Jun 24 at 15:20
2
\$\begingroup\$

Python, 153 105 86 bytes

-19 bytes thanks to @Unrelated String

lambda l:len(d:=[(h,z)for i,(h,x)in enumerate(l)for z in range(-x-~i,x+i)])==len({*d})

Attempt This Online!

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

05AB1E, 22 19 bytes

εD(Ÿ¦¨N+INèδ‚}€`DÙQ

-3 bytes using a similar approach as @UnrelatedString's Python answer

Input as two separated (equal-length) lists, first being the list of widths, second the heights.

Try it online or verify all test cases.

Explanation:

Step 1: Exact same first step as in the previous related challenge: 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

Try just this first step.

Step 2: Pair each inner index with the height of the second input:

 I        #  Push the second input-list of heights
  Nè      #  Use the map-index to get the current height
    δ     #  Apply double-vectorized:
     ‚    #   Pair this height with each index in the (n,-n) range
}         # Close the map

Try just the first two steps.

Step 3: Check if all (flattened) pairs are unique, and output the result:

€`        # Flatten the list of lists of pairs one level down
  DÙQ     # Check if all pairs are unique:
  D       #  Duplicate the list
   Ù      #  Uniquify this copy
    Q     #  Check if both lists are still the same
          # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Haskell, 112 85 75 bytes

-37 bytes thanks to @Wheat Wizard's tips

import Data.List
f k|z<-do(i,(y,x))<-zip[0..]k;(y,)<$>[2-x+i..x+i]=z==nub z

Attempt This Online!

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

Pyth, 22 21 18 bytes

{Is.e,RGtr-keAb+kH

Try it online! or Verify all test cases

Explanation

.e enumerates over the implicit input with index k and value b.

Ab sets G and H to the elements of b (in this case, height and width respectively)

tr-keAb+kH builds a range from k-H+1 to k+H (half inclusive)

,RG appends the height to each element of that list, resulting in a list of coordinates for the current mushroom.

s flattens the list by one level. And {I checks whether the list remains invariant under deduplication, meaning that no two mushrooms share a coordinate.

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

JavaScript (ES6), 58 bytes

Expects (heights)(widths). Returns a Boolean value.

h=>w=>w.some((w,x)=>h[H=~h[x]]&(h[H]|=m=4**w/2-1<<x>>w,m))

Try it online!

How?

This is using the same method as in my answer to the other challenge. But since there's no search involved, we can just store the bitmasks in one of the input arrays with negative indices.


JavaScript (ES6), 65 bytes

Expects (heights)(widths). Returns a Boolean value.

h=>w=>w.some((p,i)=>w.some((q,j)=>p*q&&h[i]==h[j]&j>i&i+p-1>j-q))

Try it online!

Commented

h =>                // h[] = array of heights
w =>                // w[] = array of widths
w.some((p, i) =>    // for each mushroom of width p at index i:
  w.some((q, j) =>  //   look for another mushroom of width q at index j:
    p * q           //     such that they both actually exist,
    && h[i] == h[j] //     they have the same height,
    & j > i         //     the 2nd one is located after the 1st one,
    & i + p - 1     //     and the right part of the 1st one intersects
      > j - q       //     with the left part of the 2nd one
  )                 //   end of inner some()
)                   // end of outer some()
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

⊙η∧ι⊙…ηκ∧λ∧⁼§θκ§θμ›⁺ιλ⊕⁻κμ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if there's a collision, nothing if not. Explanation:

 η                          Input widths
⊙                           Any element satisfies
   ι                        Current width
  ∧                         Logical And
      η                     Input widths
     …                      Truncated to length
       κ                    Outer index
    ⊙                       Any element satisfies
         λ                  Current width
        ∧                   Logical And
             θ              Input heights
            §               Indexed by
              κ             Outer index
           ⁼                Equals
                θ           Input heights
               §            Indexed by
                 μ          Inner index
          ∧                 Logical And
                    ι       Outer width
                   ⁺        Plus
                     λ      Inner width
                  ›         Is greater than
                        κ   Outer index
                       ⁻    Minus
                         μ  Inner index
                      ⊕     Incremented

Bonus program!

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

Factor + math.unicode, 100 bytes

[ [ swap dup neg (a,b) n+v ] map-index zip expand-keys-push-at values [ concat dup members = ] ∀ ]

Attempt This Online!

Oh how I wish there was a word for expand-keys-push-at values that was around 6 bytes instead of 26. This uses the algorithm described in Kevin Cruijssen's 05AB1E answer.

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

R, 100 bytes

\(h,w,a=\(x,y,z)`if`(z>=0,complex(0,x,-z:z+y),y),p=mapply(a,h+1,seq(!h),w-1))any(table(unlist(p))>1)

Attempt This Online!

Complex numbers!

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

BQN, 36 bytes

(∨˝⍟2((∧´+´>≠⋈⌈´)¨·∾´↑¨∘↓)˘)∘⍉=⌜⟜⍷⊸×

Dyadic function; takes a list of heights as its left argument and a list of widths as its right argument. Returns 0 for no collisions or 1 for one or more collisions, wrapped in a unit array.

Try it at BQN online!

Explanation

=⌜⟜⍷⊸×

Splay the widths out into different columns of a 2D array, one column for each distinct height in the heights list.

(...)∘⍉

Transpose so each list of widths-at-a-given-height is now a row. Then:

(...)˘

Map over each row:

·∾´↑¨∘↓

Generate a list of all sublists; then:

(...)¨

Map this function to each sublist:

∧´+´>≠⋈⌈´

Is the sum of the sublist greater than both the length of the sublist and the max of the sublist?

This function will always return 1 for any sublist that:

  • Starts and ends with a nonzero mushroom width, and
  • Has all zeros between the two nonzero values, if
  • The two mushrooms overlap

It will also return 1 for certain other sublists, but only if they contain a sublist that matches the above criteria. Thus, if there are any 1's in the results, that indicates the existence of some overlapping pair of mushrooms.

∨˝⍟2

We have a 2D array of 0's and 1's; fold its leading axis on logical OR twice, giving a 0D array containing 1 if there were any 1's and 0 otherwise.

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

Vyxal, 19 bytes

¨2$:NrḢ+⁰ntiv";ÞfÞu

Try it online or verify all test cases.

Port of 05AB1E. Too bad we don't have a loop index variable. Then it could be 16 bytes.

¨2$:NrḢ+⁰ntiv";ÞfÞu
¨2                  # Open a dyadic map lambda: Map over the implicit first input, pushing both item and index
  $                 #  Swap so the item is at the top
   :Nr              #  Range [n, -n)
      Ḣ             #  Remove the first item to make this (n, -n)
       +            #  Add the index
        ⁰nti        #  Index the loop-index into the second input
            v"      #  Pair each in the list with this
              ;     # Close map
               Þf   # Flatten one level
                 Þu # Is this unique?
\$\endgroup\$
1
\$\begingroup\$

Python 3 with NumPy, 83 bytes

def f(h,w):
 for j in h:x,=(w*(h==j)>0).nonzero();1**((x-w[x])[1:]+1-(w[x]+x)[:-1])

Try it online!

Takes two array arguments and signals by error/no error.

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

C (clang), 128 bytes

i;j;k;*c;r;f(*h,*w,n){for(r=i=0;i<n;++i)for(c=calloc(n,8)+n,j=i;j<n;++j)for(k=-~j-w[j];h[i]==h[j]&k<j+w[j];)r|=++c[k++]>1;*h=r;}

Try it online!

Inputs a pointer to an array of mushroom heights \$h\$, a pointer to an array of mushroom widths \$w\$, and the length of the arrays (since pointers in C carry no length info).
Returns, through the input pointer \$h\$, \$0\$ if there aren't any collisions between mushroom caps and \$1\$ otherwise.

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

Jelly, 15 bytes

Ḥ’R_"ƲĖS€;€"ẎQƑ

A dyadic Link that accepts the widths on the left and the heights on the right and yields 0 if there are collisions or 1 if not.

Try it online! Or see the test-suite.

How?

Ḥ’R_"ƲĖS€;€"ẎQƑ - Link: widths, heights
     Ʋ          - last four links as a monad - f(widths):
                      e.g. widths = [3,2,0,1]
Ḥ               -   double          [6,4,0,2]
 ’              -   decrement       [5,3,-1,1]
  R             -   range           [[1,2,3,4,5],[1,2,3],[],[1]]
    "           -   zip with:
   _            -     subtract      [[-2,-1,0,1,2],[-1,0,1],[],[0]]
      Ė         - enumerate         [[1,[-2,-1,0,1,2],],[2,[-1,0,1]],[3,[]],[4,[0]]]
       S€       - sum each          [[-1,0,1,2,3],[1,2,3],[],[4]]
           "    - zip with heights applying:
         ;€     -   concatenate (the current height) to each
            Ẏ   - tighten
              Ƒ - is invariant under?
             Q  -   deduplicate
\$\endgroup\$
1
\$\begingroup\$

Desmos, 156 bytes

l=W.length
k=max(0,i-W[i])
L=[1...n]
g(n)=L[L0+n>0]0
f(H,W)=0^{0^{[max(∑_{i=1}^ljoin(g(k),g(W[i]+i-1-k)+1,g(l))[1...l]0^{(h-H[i])^2})forh=H[1...]].max-1}}

My attempt at solving this challenge without looking at the other answers lolol. You can see how terribly that came out just by how long the answer is.

The function f takes in the height list first and the width list second, and returns 0 for no collisions, 1 if there is a collision.

Also the H[1...] can't be golfed to H (I checked), because apparently H is recognized as a number, not a list, so the list comprehension errors out. H[1...] circumvents this error by forcing Desmos to recognize H as a list.

Try It On Desmos!

Try It On Desmos! - Prettified

I have added an explanation of my code below because I'm bored :P.

Explanation

The general rundown of my strategy is for each height, construct lists of 1's and 0's which correspond to the spaces that each mushroom takes up for that particular height. Then, all these lists are summed together. If there is a collision at that height, then there will be a number \$>1\$ in the list.

Now, to explain each part of the code.

L=[1...n]
g(n)=L[L0+n>0]0

g is a function that will return a list of n zeroes.

f(H,W)=0^{[max(∑_{i=1}^ljoin(g(k),g(W[i]+i-1-k)+1,g(l))[1...l]0^{(h-H[i])^2})forh=H[1...]].max-1}

f is the function that returns the answer. Let's break it down:

... [ ... forh=H[1...]]

For h in list H (looping over all heights)...

... ∑_{i=1}^l ...

Take the summation from i=1 to the length of list W of (looping over indices of the width list)...

join(g(k),g(W[i]+i-1-k)+1,g(l))[1...l]

A list of 1's and 0's, representing the spaces that the mushroom at index i in the width list takes up, with 1 representing the space taken up by the mushroom. This list is constructed by joining three individual lists into one list: g(k), g(W[i]+i-1-k)+1, and g(l).

The first list, g(k), consists of the 0's before the range of 1's which represent the mushroom. The number of 0's needed can be calculated by subtracting the width of the mushroom W[i] from its index i (The mushroom extends W[i]-1 spaces to the left from the center space, so i-W[i] is essentially calculating the index of the last 0 right before the mushroom.). The issue with this is that some mushrooms extend past the front of the list, which will make i-W[i] negative. While this is no problem for g (it returns an empty list for negative inputs), it may cause issues for length calculations later on (i.e. the list of 1's right after), so instead we store the length of the list as k=max(0,i-W[i]), and call g(k) to construct the list of 0's.

The second list, g(W[i]+i-1-k)+1, constructs a list of 1's which represent the space that the mushroom takes up. g returns a list of 0's, so we convert that to a list of 1's by adding 1 to the list. At first, it might be obvious to do g(2W[i]-1)+1 as each mushroom takes up \$2w-1\$ spaces. But this runs into the problem of width 0, as g(-1)+1 is just an empty list, but what we actually wanted was the list [0]. Also, the bigger problem is that it doesn't account for mushrooms extending past the front of the list, and will have too many 1's for those mushrooms. To counteract this problem, note that the length of the list up to the end of the mushroom has to be i+W[i]-1 (the mushroom extends W[i]-1 spaces to the right of its center, i, so the index of the last 1 in the mushroom is i+W[i]-1). The first list already accounted for k of the elements, so the second list will have a length of i+W[i]-1-k to account for the rest of the elements.

The last list, g(l), is simply to pad the end of the list with enough 0's to make the list have a length of at least l=W.length for the slice (explained below).

[1...l] is a slice that takes the first l elements of the list. This is to ensure that all the lists being summed have the same length, as Desmos gives an error if they aren't all the same length.

0^{(h-H[i])^2}

This checks if the height of the mushroom at index i is the same as the current height h (if we don't have this code, then the function would detect for collisions as if they were all on the same height). (h-H[i])^2 returns 0 if the current height h is the same as the mushroom's height H[i]. Otherwise, it returns a positive integer. Then, 0^{(h-H[i])^2} returns 1 if (h-H[i])^2 is 0, and 0 if (h-H[i])^2 is a positive integer.

Putting that all together, 0^{(h-H[i])^2} returns 1 if h equals H[i], and returns 0 otherwise. When multiplying this value with the list, if it is 1, then nothing happens to the list, but if it is 0, then all the entries in the list become 0, which essentially means that the list won't contribute to the summation at all. This causes any mushroom that isn't at the current height of the loop to be nullified, leaving only the mushrooms which are at the current height to contribute to the summation.

0^{0^{[max( ... ) ... ].max-1}}

Recall that if the summed list contains any number \$>1\$, then that means there is a collision. If there are any numbers \$>1\$, then the max of the summed list will be \$>1\$. The list comprehension will create a list of maximums for each height in H. By taking the maximum of the list comprehension, we can then detect if there were any collisions in any of the heights if the maximum is \$>1\$. We can do this by first subtracting one from the maximum, and then wrapping 0^{0^{ ... }} around it. 0^{0^n} for any integer n returns 1 if n is positive, and 0 if n is 0 or negative. This means if the maximum is 0 or 1, the function will return 0, because both 0^{0^{-1}} and 0^{0^0} return 0. If the maximum is 2 or above, then the function will return 1.

\$\endgroup\$

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.