27
\$\begingroup\$

Given a Minecraft terrain as a 2-dimensional array of integers or similar datastructure, determine the maximum number of cacti that can be planted on it.

The integers represent the height (y) of the terrain at each location (x and z). A cactus cannot be planted next to higher terrain or next to another cactus at the same height (next to = either x or z deviates by 1 and the other coordinates are the same).

visualisation

You can optionally make any of the following assumptions:

  • at least some terrain exists
  • all heights are between 1 and 100

Test cases

[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]] -> 8

[[7, 6, 5, 4], [6, 5, 4, 3], [5, 4, 3, 2], [4, 3, 2, 1]] -> 1

[[4, 3, 4, 1, 1, 3, 2, 4], [2, 4, 4, 2, 1, 2, 2, 3], [1, 1, 3, 2, 1, 2, 3, 2], [4, 4, 3, 1, 2, 2, 3, 3], [3, 2, 2, 2, 1, 1, 4, 4], [3, 2, 3, 1, 1, 1, 4, 1], [1, 3, 2, 2, 1, 3, 4, 3], [4, 4, 1, 1, 1, 1, 3, 2]] -> 17

[[5, 5, 5, 4, 5, 4, 4, 3, 1, 1, 4, 4, 4, 4, 3, 4], [5, 4, 4, 4, 4, 4, 3, 1, 1, 2, 4, 4, 3, 4, 4, 4], [5, 5, 4, 4, 5, 4, 4, 2, 1, 4, 4, 4, 4, 4, 2, 4], [4, 4, 4, 4, 4, 4, 3, 3, 3, 4, 3, 2, 4, 3, 2, 4], [4, 4, 4, 5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 3, 2], [4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 4, 3, 3], [4, 4, 1, 2, 3, 4, 5, 5, 4, 4, 4, 3, 3, 4, 5, 4], [4, 4, 4, 3, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4], [4, 4, 2, 4, 4, 4, 3, 4, 5, 4, 4, 4, 5, 5, 5, 4], [4, 4, 3, 4, 3, 2, 3, 4, 4, 4, 4, 4, 5, 4, 4, 4], [4, 4, 4, 3, 1, 2, 2, 3, 4, 4, 4, 4, 5, 4, 4, 4], [4, 4, 3, 1, 2, 3, 2, 4, 4, 3, 3, 3, 4, 4, 4, 4], [4, 4, 4, 1, 1, 1, 1, 1, 3, 3, 2, 3, 4, 3, 3, 4], [4, 4, 4, 4, 3, 1, 2, 3, 2, 3, 2, 2, 4, 4, 3, 4], [4, 4, 5, 4, 4, 4, 4, 4, 4, 3, 1, 4, 4, 4, 4, 4], [5, 4, 5, 4, 4, 4, 4, 3, 2, 3, 3, 4, 4, 3, 4, 4]] -> 80

Scoring

This is code-golf, the shortest submission (in bytes) for each language wins!

Lower bounds (approximations)

  1. Eliminate all locations next to higher terrain and fill in the remaining areas with the checkerboard pattern. (thanks to Bubbler)

  2. Eliminate all locations next to higher terrain, and repeatedly remove locations with minimal remaining neighbours along with their neighbours while counting them. (thanks to Jonathan Allan)

\$\endgroup\$
4
  • 8
    \$\begingroup\$ After erasing all spots that cannot have a cactus by an adjacent higher ground, the problem is essentially maximum independent set on a grid graph. Checkerboard pattern is not always optimal (example). \$\endgroup\$
    – Bubbler
    Commented Apr 1 at 23:38
  • 1
    \$\begingroup\$ @Bubbler You're absolutely right, I've corrected the visualisation and the test cases. \$\endgroup\$
    – Cactusroot
    Commented Apr 2 at 12:01
  • \$\begingroup\$ next to = either x or z deviates by 1 this reads like it is not allowed to have two cacti in adjacent rows or columns, independently of whether they are close to each other. It also allows planting an infinite number of cacti at the same location. \$\endgroup\$
    – Didier L
    Commented Apr 3 at 15:48
  • \$\begingroup\$ @DidierL changed it. \$\endgroup\$
    – Cactusroot
    Commented Apr 3 at 17:06

6 Answers 6

7
\$\begingroup\$

Picat, 216 bytes

import cp.
f(M)=S=>R=M.len,C=M[1].len,X=new_array(R,C),X::0..1,foreach(A in 1..R,B in 1..C,D in 1..R,E in 1..C,abs(A-D)+abs(B-E)=1)X[D,E]#<=min(1-X[A,B],M[D,E]/M[A,B])end,S#=sum([Z:Y in X,Z in Y]),solve([$max(S)],X).

Try it on Picat Web IDE!

This language is cool but damn verbose lol. Models the problem as a constraint problem and passes the instance to the CP solver. The link uses import sat instead which is 1 byte longer but much much faster for this problem.

Ungolfed with comments:

import cp. % constraint solver

% define a function that returns the value of S in the end
f(M) = S =>
    R = M.len, C = M[1].len, % dimensions of the matrix
    X = new_array(R,C), % create boolean variables, 1=cactus, 0=no cactus
    X :: 0..1,
    % for each adjacent pair of (A,B) and (D,E)
    foreach(A in 1..R, B in 1..C, D in 1..R, E in 1..C,
        abs(A-D)+abs(B-E) = 1)
        % obfuscated version of:
        % X[A,B] + X[D,E] #<= 1, % no two cacti are adjacent
        % if M[D,E] < M[A,B] then X[D,E] #= 0 end % no cactus with adjacent higher ground
        X[D,E] #<= min(1-X[A,B], M[D,E]/M[A,B])
    end,
    S #= sum([Z:Y in X,Z in Y]), % optimization variable: # of cacti
    solve([$max(S)], X). % maximize it and return the resulting S
\$\endgroup\$
5
\$\begingroup\$

Python3, 566 bytes

Long, but not naive brute-force.

from itertools import*
E=enumerate
M=[(0,1),(0,-1),(1,0),(-1,0)]
def G(d,v):
 while v:
  a,*v=v;v={*v}
  q,s=[a],[a]
  for x,y in q:
   for X,Y in M:
    if d.get(T:=(x+X,y+Y))==d[(x,y)]and T in v:v-={T};q+=[T];s+=[T]
  yield s
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 q=[{*i}for i in[*G(d,{(x,y)for x,y in d if all(d[(x,y)]>=d.get((x+X,y+Y),0)for X,Y in M)})]]
 e=0
 for a in q:
  for i in range(len(a),0,-1):
   F=0
   for j in combinations(a,i):
    if all(all((x+X,y+Y)not in j for X,Y in M)for x,y in j):F=len(j);break
   if F:e+=F;break
 return e

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Is it strongly cut-away or proven polynomial time? \$\endgroup\$
    – l4m2
    Commented Apr 2 at 1:56
  • \$\begingroup\$ @l4m2 Only strongly cut-away. There is still room for improvements, but they would greatly increase the size of any already very large solution :) \$\endgroup\$
    – Ajax1234
    Commented Apr 2 at 2:06
  • \$\begingroup\$ You can replace if all(all((x+X,y+Y)not in j... with if 1-any(any((x+X,y+Y)in j... for -2. \$\endgroup\$
    – nedla2004
    Commented Apr 4 at 7:06
5
\$\begingroup\$

JavaScript (Node.js), 150 147 bytes

f=(x,j=0,i=0,e=x[i],J)=>e?Math.max(f(x,J=e[j+1]?j+1:0,i+!J),e[v=e[j]++,j-1]>v|e[j+1]>v|(x[i-1]||0)[j]>v|(x[i+1]||0)[j]>v?0:1+f(x,J,i+!J),!e[j]--):0

Try it online!

Brute-force

\$\endgroup\$
5
\$\begingroup\$

Jelly, 34 bytes

ạSỊɗƇⱮ`
ŒJÇðZÆṁWfœịÐṀð€ẎŒPṚÇẈPƊÞḢL

A monadic Link that accepts a list of lists of positive integers, the landscape, and yields a non-negative integer, the maximal cactus count.

Try it online! (too slow for any of the non-trivial test cases!)

How?

Find all possible cactus planting locations, \$L\$, given the landscape's heights then find the largest subset of \$L\$ for which all neighbourhoods are of size one.

ạSỊɗƇⱮ` - Link 1, getNeighbourhoods: list of pairs of integers, Locations
     Ɱ` - for Y in Locations:
    Ƈ   -   filter keep any Location, X, for which:
   ɗ    -     last three links as a dyad - f(X, Y):    
ạ       -       X absolute difference Y -> Delta = [abs(X1-Y1), abs(X2-Y2)]
 S      -       sum
  Ị     -       insignificant? -> Does X=Y or are X & Y neighbours?

ŒJÇðZÆṁWfœịÐṀð€ẎŒPṚÇẈPƊÞḢL - Main Link: list of lists of positive integers, Landscape
ŒJ                         - multidimensional indices -> all locations
  Ç                        - call Link 1 -> all neighbourhoods
   ð         ð€            - dyadic link for each - f(Neighbourhood, Landscape):
    Z                      -   transpose the Neighbourhood
     Æṁ                    -   median (vectorises) -> the planting location
       W                   -   wrap that in a list
         œịÐṀ              -   maximums of Neighbourhood by indexing into Landscape
        f                  -   {wrapped planting location} keep if in {maximums}
               Ẏ           - tighten -> all possible planting locations
                ŒP         - powerset
                  Ṛ        - reverse -> largest to smallest
                      ƊÞ   - sort by last three links as a monad:
                   Ç       -   call Link 1 -> neighbourhoods of the set
                    Ẉ      -   length of each
                     P     -   product (product of empty list is 1)
                        Ḣ  - head
                         L - length
\$\endgroup\$
3
  • \$\begingroup\$ Great approximation using a greedy algorithm! One counter example is [[2, 2, 1], [2, 2, 2], [1, 2, 2]]. The algorithm is indifferent between any of the corners and chooses the top-left, while choosing an "inner" one would be optimal. \$\endgroup\$
    – Cactusroot
    Commented Apr 2 at 16:36
  • \$\begingroup\$ Yep, looks wrong, will delete and bring this back when fixed... \$\endgroup\$ Commented Apr 2 at 16:48
  • \$\begingroup\$ OK changed it to asses all subsets of the set of possible planting locations, and as I suspected it is now too slow to complete any of the non-trivial test cases in under 60s on TIO :p \$\endgroup\$ Commented Apr 2 at 17:18
1
\$\begingroup\$

Python 3, 89 bytes

f=lambda a:max(all(0<a.get(i+b,1)<=a[i]for b in(1,-1,1j,-1j))and-~f({**a,i:0})for i in a)

Try it online!

A recursive function which brute-forces all combinations. It is very slow and only the most simple test cases finish on TIO.

It takes a complex-number indexed dictionary as input. If that is not allowed, it can be constructed from a 2D array at the cost of 66 additional bytes:

Python 3, 155 bytes

lambda a,E=enumerate:f({i+1j*j:h for i,r in E(a)for j,h in E(r)})
f=lambda a:max(all(0<a.get(i+b,1)<=a[i]for b in(1,-1,1j,-1j))and-~f({**a,i:0})for i in a)

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Setting terrain height to 0 for planted cacti and interpreting terrain with y=0 as infinitely high is a great way to check for neighbouring cacti and higher terrain at the same time! \$\endgroup\$
    – Cactusroot
    Commented Apr 4 at 12:16
1
\$\begingroup\$

Charcoal, 72 bytes

≔⊕L⌊θηFθF⊞Oι⁰⊞υκFη⊞υ⁰≔⟦υ⟧υFυF⊖∨⊕⌕ιφLιF⬤⟦¹±¹η±η⟧¬›§ι⁺κλ§ικ⊞υEι⎇⁼νκφμI№⊟υφ

Try it online! Link is to verbose version of code. Assumes input values will be positive but less than 1000. Explanation: Brute force again.

≔⊕L⌊θη

Get 1 more than the width of the input matrix.

FθF⊞Oι⁰⊞υκFη⊞υ⁰

Generate the result of flattening the input matrix bordered with 0s below and to the right.

≔⟦υ⟧υFυ

Start a breadth-first search with the flattened input matrix and no cacti.

F⊖∨⊕⌕ιφLι

Loop up until the previously planted cactus for this flattened matrix. (This is mainly to avoid planting cacti twice in the same spot and costs the same number of bytes as as looping over all non-planted squares but has much better time complexity.)

F⬤⟦¹±¹η±η⟧¬›§ι⁺κλ§ικ

Check all "neighbours" to ensure none of them are higher or were previously planted.

⊞υEι⎇⁼νκφμ

If so then add the result of planting the cactus to the list of new flattened matrices. Cacti are marked as having a height of 1000 which prevents subsequent cacti from being placed adjacent to them.

I№⊟υφ

Output the count of cacti planted in the last flattened matrix (which will always have the maximum possible count).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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