How many cacti can I plant here?

Question

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).

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)

Answer 1

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

Answer 2

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!

Answer 3

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

Answer 4

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

Answer 5

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!

Answer 6

Charcoal, 72 bytes

≔⊕Ｌ⌊θηＦθＦ⊞Ｏι⁰⊞υκＦη⊞υ⁰≔⟦υ⟧υＦυＦ⊖∨⊕⌕ιφＬιＦ⬤⟦¹±¹η±η⟧¬›§ι⁺κλ§ικ⊞υＥι⎇⁼νκφμＩ№⊟υφ

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

≔⊕Ｌ⌊θη

Get 1 more than the width of the input matrix.

ＦθＦ⊞Ｏι⁰⊞υκＦη⊞υ⁰

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

≔⟦υ⟧υＦυ

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

Ｆ⊖∨⊕⌕ιφＬι

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.)

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

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

⊞υＥι⎇⁼νκφμ

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.

Ｉ№⊟υφ

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