Verify Tents and Trees solution

Question

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 code-golf 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 . .

• Kevin Cruijssen: 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?
• Bubbler: @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.

Answer 1

J, ⁸⁸ 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.

Answer 2

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
 // found an adjacent tree:
 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

Answer 3

05AB1E, (削除) 53 (削除ここまで) (削除) 49 (削除ここまで) (削除) 42 (削除ここまで) 60 bytes

1«ÐεNUεXN)]€`{.¡н}¦`UœεX‚®ζε`αO<]Pßs×ばつa€ü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").

Try it online or verify all test cases.

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
 # triplicate instead of duplicate..)
ε # 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
 a # 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 ×ばつa` 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)

Answer 4

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=0|¬{s2\s2c⊇Ċ=2}&{iihgtcṗh}fhgptz2{\b-mȧm+1}m

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

How it works

c=0|

Either the flatten matrix contains only 0's or ...

¬{s2\s2c

No 2x2 submatrix flattened ...

⊇Ċ=2}

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

&{iihgtc

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

ṗh}

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

fp

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

hg

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

z2

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

{\b-mȧm+1}m

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.

Answer 5

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 Combinatorica`MakeGraph 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.