# Tents and Trees feasibility

Sequel to 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 trees, determine whether it is possible to place tents next to each of the trees so that they don't touch each other in 8 directions. Ignore the number clues in this challenge.

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

You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

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

### Truthy

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

T .

. T .
. . T

. .
T T
. .

. T .
T . T
. T .

. . .
T T .
. T T
. . .

. T . .
. . . T
T T . .
. . . .

. T . . . .
. . . . . .
. . T . . T
. T . T . .
T . T . . .
. T . . T .


### Falsy

(No space to place a tent)
T

T . T

T . T
. T .

. . . .
. T T T
T . . .

. T .
T T .
. T .

T . T
. . .
. T .

T . . . .
. . T . .
. T . T .
T . T . .
. T . . .

. . . . .
. T . . .
. T T . .
. . T T .
. . . . .

• Can someone explain to me why T . T is Falsy? (I.e. why TAT is not a valid answer) Is there a rule missing from the background, such as "There must be an equal number of Tents and Trees"? Commented Jul 15, 2020 at 14:25
• @Chronocidal "Place tents horizontally or vertically adjacent to each of the trees," but that isn't fully clear. The linked prequel states "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." Commented Jul 15, 2020 at 16:04

# Python 3.8 (pre-release), 253 244 bytes

from itertools import*
f=lambda b,h,w:all(set(t:=[i%w+i//w*1jfor i,e in enumerate(b)if e])&set(s:=[*map(sum,zip(t,T))])or~any(abs(a-b)<2for a,b in combinations(s,2))+all(h>a.imag>-1<a.real<w for a in s)for T in product(*[[1,1j,-1,-1j]]*sum(b)))


Try it online!

-6 bytes thanks to @user202729 (chain comparisons)

-3 bytes thanks to @ovs (1jfor; …or a+1^b…or~a+b for "implies" boolean operator)

# Itertools for combinations and product
from itertools import*
f=lambda b,h,w: all(
# Test if a given set of tent position deltas works:
# Positions are complex numbers: real part increasing to the right, imaginary part increasing down
# (De Morgan shortened, so many expressions negated)
# No tree is on a tent:
# t:=Tree positions (1s)
set(t:=[i%w+i//w*1j for i,e in enumerate(b)if e])
# s:=Tent positions as sum of tree positions and deltas
& set(s:=[*map(sum,zip(t,T))])
# and difference between all distinct pairs oftrees is at least 2:
or any(abs(a-b)<2for a,b in combinations(s,2))
# and all trees are within rectangular boundary
# (Using Python 2's quirky complex floordiv doesn't work since those return complex nums,
# which don't have a total order.
# Plus Python 38 has saves so much here; using 2 would be a waste anyway)
>= all(h > a.imag > -1 < a.real < w for a in s)
# For each possible delta (four directions, distance 1)
# sum(b) is the number of tents since each tent contributes 1
for T in product(*[[1,1j,-1,-1j]]*sum(b))
)

• w>a.real>-1<a.imag<h? Commented Jul 15, 2020 at 5:25
• @user202729 Ah, yes Commented Jul 15, 2020 at 5:38
• Two tiny improvements: The space in 1j for is unnecessary, and +1^ can be replaced with >=.
– ovs
Commented Jul 15, 2020 at 9:31
• @ovs That 1j for is wholly unintuitive, but I guess it makes a bit of sense from a parsing standpoint. Commented Jul 15, 2020 at 16:08
• One more: or a>=b can be or~a+b.
– ovs
Commented Jul 15, 2020 at 21:27

# Charcoal, 82 bytes

ＷＳ⊞υι≔⟦⟦⟧⟧θＦＬυＦ⌕Ａ§υιT«≔⟦⟧ηＦθ«υＦλ«Ｊ§μ⁰§μ¹A»Ｆ⁴«ＪκιＭ✳⊗μ¿›⁼.ＫＫ№ＫＭA⊞η⁺λ⟦⟦ⅈⅉ⟧⟧»⎚»≔ηθ»ＩＬθ


Try it online! Link is to verbose version of code. Takes input as newline-terminated strings and outputs the number of solutions. Explanation:

ＷＳ⊞υι


≔⟦⟦⟧⟧θ


ＦＬυＦ⌕Ａ§υιT«


Loop over the positions of the trees.

≔⟦⟧η


No tent positions for this tree found so far.

Ｆθ«


Loop over the tent positions for the previous trees.

υ


Print the grid.

Ｆλ«Ｊ§μ⁰§μ¹A»


Print the tents for this partial solution.

Ｆ⁴«


Check the four orthogonal directions.

ＪκιＭ✳⊗μ


Move to the relevant adjacent square.

¿›⁼.ＫＫ№ＫＭA


If this square is empty and is not bordered by a tent, ...

⊞η⁺λ⟦⟦ⅈⅉ⟧⟧


... then append its position to the previous partial solution and add it to the list of new partial solution.

»⎚


Clear the canvas after testing this tree.

»≔ηθ


Save the new solutions as the current solutions.

»ＩＬθ


Print the final number of solutions.