# Verify Tents and Trees solution

## Background

Tents and Trees (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically adjacent to each of the trees, so that no two tents touch each other in 8 directions (horizontally, vertically, and diagonally) and the number of tents on each row/column matches the given clues.

### Example puzzle and solution

In these examples, trees are T and tents are A.

Puzzle
2 0 2 0 2 1
2 . T . T . .
1 . . . . T .
1 T . T . . .
2 . . . . . T
1 T . . . . .
0 . . . . . .

Solution
2 0 2 0 2 1
2 . T A T A .
1 A . . . T .
1 T . T . A .
2 A . A . . T
1 T . . . . A
0 . . . . . .


## Challenge

Given a grid with some tents and trees, determine whether the tents are placed correctly. Ignore the number clues in this challenge. In particular, your program should check the following:

• The number of tents equals the number of trees,
• The tents do not touch each other in 8 directions, and
• There is at least one way to associate every tent with an adjacent tree in 4 directions, so that every tree is used exactly once.

If all of the above are satisfied, output a truthy value; otherwise, output a falsy value. You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.

You may take the input in any reasonable way to represent a matrix containing three distinct values to represent a tree, a tent, and an empty space respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

This uses the same notation as the above example; T for trees, A for tents, and . for empty spaces.

### Truthy

. . .
. . .
. . . (empty board)

T A

A T A
. . T

A T A
T . T
A T A
(note that there are two ways to associate tents with trees)

A . .
T T A
A T T
. . A

. T A .
A . . T
T T . A
. A . .


### Falsy

(The number of Ts and As don't match)
T

A

T A T

(Two A's touch each other)
T A T
A . .

A . . A
T T T T
. A A .

(Some T's are not associated with an A)
A T A
T T .
A T A

A . T
T T A
A . .

• Can we assume the input will always contain at least one tent and/or tree? So an input with only empty spots / dots is undefined and it doesn't matter whether it outputs truthy or falsey? And what about an empty input? Jul 6, 2020 at 17:31
• @Kevin Input may have zero tents and zero trees, which is truthy. You can assume the input will have at least one row and one column. Will add a test case shortly. Jul 6, 2020 at 21:49

# J, 88 86 bytes

Expects a matrix with 0 for ., 1 for A and 2 for T.

(2>1#.1=,);.3~&2 2*/@,&,1&=((1 e.[:*/"{2>[:+/"1|@-"2)i.@!@#A.]) ::0&($#:i.@$#~&,])2&=


Try it online!

### How it works

1&= (…) 2&=


Tents on the left side, trees on the right side.

(…)&($#:i.@$#~&,])


Convert both arguments to 2D coordinates.

(…) ::0


If the following function throws an error, return 0. This happens only in the single A case. :-(

i.@!@#A.]


List all permutations of the trees.

|@-"2


Get the difference between the tents from every permutation.

[:*/2>[:+/"1


Check that each difference's sum is 1.

1 e.


Does any permutation fulfill this?

(2>1#.1=,);.3~&2 2


Get all 2x2 matrices of the original, and check if there is at most one tent in there.

*/@,@,


Combine both results, flatten the lists, and check if there are only 1's.

# JavaScript (ES7),  159 156  153 bytes

Expects a matrix of integers, with 0 for empty, -1 for a tree and 1 for a tent. Returns 0 or 1.

m=>(g=(X,Y,R)=>!/1/.test(m)|m.some((r,y)=>r.some((v,x)=>1/Y?(q=(x-X)**2+(y-Y)**2)?R?v+q?0:g(R[X]=r[x]=0)|R[X]++|r[x]--:q<3*v:0:v>0&&!g(x,y)&g(x,y,r))))


Try it online!

### How?

The main recursive function is used to perform 3 distinct tasks. The corresponding calls are marked as A-type, B-type and C-type respectively in the commented source. Below is a summary:

 type   | Y defined | R defined | task
--------+-----------+-----------+----------------------------------------------------
A-type |    no     |     no    | Look for tents. Process B-type and C-type calls
|           |           | for each of them.
--------+-----------+-----------+----------------------------------------------------
B-type |   yes     |     no    | Look for another tent touching the reference tent.
--------+-----------+-----------+----------------------------------------------------
C-type |   yes     |    yes    | Look for adjacent trees. Attempt to remove each of
|           |           | them with the reference tent. Chain with an A-type
|           |           | call.


### Commented

m => (                       // m[] = input matrix
g = (                      // g is the main recursive function taking:
X, Y,                    //   (X, Y) = reference tent coordinates
R                        //   R[] = reference tent row
) =>                       //
!/1/.test(m) |           // success if all the tents and trees have been removed
m.some((r, y) =>         // for each row r[] at position y in m[]:
r.some((v, x) =>       //   for each value v at position x in r[]:
1 / Y ?              //     if Y is defined:
( q = (x - X) ** 2 //       q = squared distance (quadrance)
+ (y - Y) ** 2 //           between (x, y) and (X, Y)
) ?                //       if it's not equal to 0:
R ?              //         if R[] is defined (C-type call):
v + q ? 0 :    //           if v = -1 and q = 1, meaning that we have
g(           //             do an A-type recursive call:
R[X] =     //               with both the reference tent
r[x] = 0   //               and this tree removed
)            //             end of recursive call
| R[X]++     //             restore the tent
| r[x]--     //             and the tree
:                //           else (B-type call):
q < 3 * v      //             test whether this is a tent with q < 3
:                  //       else (q = 0):
0                //         do nothing
:                    //     else (A-type call):
v > 0 &&           //       if this is a tent:
!g(x, y)         //         do a B-type recursive call to make sure it's
&                //         not touching another tent
g(x, y, r)       //         do a C-type recursive call to make sure that
//         it can be associated to a tree
)                      //   end of inner some()
)                        // end of outer some()
)$$$$                          // initial A-type call to g with both Y and R undefined


# 05AB1E, 534942 60 bytes

1«ÐεNUεXN)]€{.¡н}¦UœεX‚®ζεαO<]PßsZð×ª€ü2ø€ü2J˜2δ¢à*ISPΘ‚à


+11 bytes as bug-fix (thanks for noticing @xash) and +7 bytes to account for inputs only containing empty cells.. Not too happy with the current program full of ugly edge-case workarounds tbh, but it works..

Input as a list of string-lines, where $$\2\$$ is a tent; $$\3\$$ is a tree; and $$\1\$$ is an empty spot.
Outputs $$\1\$$ for truthy; and anything else for falsey (only $$\1\$$ is truthy in 05AB1E, so this is allowed by the challenge rule "You can choose to follow your language's convention of truthy/falsy").

Explanation:

I do three main steps:

Step 1: Get all coordinates of the trees and tents, and check whether there is a permutation of tree permutations that has a horizontal or vertical distance of 1 with the tent coordinates.

1«         # Add a trailing empty spot to each row
# (to account for matrices with only tents/trees and single-cell inputs)
Ð        # Triplicate this matrix with added trailing 2s
ε       # Map each row to:
NU     #  Store the index of this outer map in X
ε      #  Inner map over each cell of this row:
XN)   #   Create a triplet of the cell-value, X, and the inner map-index N
]       # Close the nested maps
€     # Flatten the list of lists of cell-coordinates one level down
{          # Sort the list of coordinates, so the empty spots are before tents, and tents
# before trees
.¡ }      # Then group them by:
н       #  Their first item (the type of cell)
¦     # And remove the first group of empty spots
          # Pop and push the list of tree and tent coordinates separated to the stack
U         # Pop and store the tent coordinates in variable X
# (or the input with trailing empty spots if there were only empty spots in
#  the input)
œ        # Get all permutations of the tree coordinates
# (or the input with trailing empty spots if there are none, hence the
ε          # Map each permutation of tree coordinates to:
X‚        #  Pair it with the tent coordinates X
ζ      #  Zip/transpose; swapping rows/columns,
®       #  with -1 as filler value if the amount of tents/trees isn't equal
ε     #  Map each pair of triplets to:
#  Pop and push them separated to the stack
α   #  Get the absolute different between the values at the same positions
O  #  Take the sum of those differences for each triplet
< #  Subtract each by 1 to account for the [2,3] of the tree/tent types
]          # Close the nested maps
P         # Take the product of each difference of coordinates
ß        # And pop and push the smallest difference


Step 2: Get all 2x2 blocks of the matrix, and check that each block contains either none or a single tent (by counting the amount of tents per 2x2 block, and then getting the maximum).

s          # Swap to get the input-matrix with trailing empty spots we triplicated
Z         # Get its maximum (without popping)
ð×       # Create a string with that many spaces
ª      # And append it to the list
# (it's usually way too large, but that doesn't matter since it's shortened
#  automatically by the ø below)
€         # For each row:
ü2       #  Create overlapping pairs
#  (the ü2 doesn't work for single characters, hence the need for the
#   1« and Zð×ª prior)
ø      # Zip/transpose; swapping rows/columns
# (which also shortens the very long final row of space-pairs)
€     # For each column of width 2:
ü2   #  Create overlapping pairs
# (we now have a list of 2x2 blocks)
J         # Join all 2x2 blocks together to a single 4-sized string
˜        # And flatten the list
δ      # Then for each 4-sized string:
2 ¢     #  Count the amount of tents it contains
à    # Pop and get the maximum count
# (if this maximum is 1, it means there aren't any adjacent nor diagonally
#  adjacent tents in any 2x2 block)


Step 3: Add the checks together, and account for inputs consisting only of empty spots as edge-case:

*          # Multiply the two values together
I         # Push the input-matrix again
S        # Convert it to a flattened list of digits
P       # Take the product
Θ      # Check that this is exactly 1 (1 if 1; 0 if not)
‚     # Pair it with the multiplied earlier two checks
à    # And pop and push the maximum of this pair
# (for which 1 is truthy; and anything else is falsey)
# (after which it is output implicitly as result)


# Brachylog, 59 47 54 45 bytes

Trying to get into Brachylog lately, so here is a (now very) rough port of my J approach. Takes in a matrix with 0 for ., 2 for A and 3 for T. Either fails to unify (prints false) or doesn't.

c=₀|¬{s₂\s₂c⊇Ċ=₂}&{iiʰgᵗcṗʰ}ᶠhᵍpᵗz₂{\b-ᵐȧᵐ+1}ᵐ


Try it online! or verify all test cases (returns truthy cases).

### How it works

c=₀|


Either the flatten matrix contains only 0's or …

¬{s₂\s₂c


No 2x2 submatrix flattened …

⊇Ċ=₂}


contains an ordered subset of length 2 that is just 2's (tents).

&{iiʰgᵗc


And the input must be converted to [type, y, x], where …

ṗʰ}


type is a prime (there seems no shorter way to filter out 0).

ᶠp


Find all [type, y, x] put them into a list, and permute this list.

hᵍ


Group them by their type; [[[3,0,2], …], [[4,1,2], …]].

z₂


Zip both groups together and make sure they have the same length. We now have [[[3,0,2], [4,1,2]], …]

{\b-ᵐȧᵐ+1}ᵐ


For every element [[3,0,2], [4,1,2]] transpose [[3,4],[0,1],[2,2]] behead [[0,1],[2,2]] subtract [_1,0] absolute value [1,0] sum 1 and that must unify with 1. So this unifies if any permutation of the one group is exactly 1 tile away from the other one.

# Wolfram Language (Mathematica), 146 bytes

<<Combinatorica
f=2*Length@MaximalMatching@MakeGraph[v=Position[#,A|T],Norm[#-#2]==1&]==Length@v&&
And@@Join@@BlockMap[Count[#,A,2]<2&,#,{2,2},1]&


Try it online!

Note:

• The second line break is only added in the post for ease of reading.
• importing Combinatorica later will make the symbols refer to the Global ones and will not have the correct result.
• Although CombinatoricaMakeGraph is rather long, MaximalMatching is 7 characters shorter than FindIndependentEdgeSet.
• I suppose this solution is the fastest...? There exists algorithms to find maximal matching in polynomial time, while testing all permutations take exponential time.