7
\$\begingroup\$

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 .
. . . . .
\$\endgroup\$
  • \$\begingroup\$ 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"? \$\endgroup\$ – Chronocidal Jul 15 at 14:25
  • 2
    \$\begingroup\$ @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." \$\endgroup\$ – fireflame241 Jul 15 at 16:04
5
\$\begingroup\$

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))
)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ w>a.real>-1<a.imag<h? \$\endgroup\$ – user202729 Jul 15 at 5:25
  • \$\begingroup\$ @user202729 Ah, yes \$\endgroup\$ – fireflame241 Jul 15 at 5:38
  • 3
    \$\begingroup\$ Two tiny improvements: The space in 1j for is unnecessary, and +1^ can be replaced with >=. \$\endgroup\$ – ovs Jul 15 at 9:31
  • 1
    \$\begingroup\$ @ovs That 1j for is wholly unintuitive, but I guess it makes a bit of sense from a parsing standpoint. \$\endgroup\$ – fireflame241 Jul 15 at 16:08
  • \$\begingroup\$ One more: or a>=b can be or~a+b. \$\endgroup\$ – ovs Jul 15 at 21:27
4
\$\begingroup\$

Charcoal, 82 bytes

WS⊞υι≔⟦⟦⟧⟧θFLυF⌕A§υιT«≔⟦⟧ηFθ«υFλ«J§μ⁰§μ¹A»F⁴«JκιM✳⊗μ¿›⁼.KK№KMA⊞η⁺λ⟦⟦ⅈⅉ⟧⟧»⎚»≔ηθ»ILθ

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

WS⊞υι

Read in the grid.

≔⟦⟦⟧⟧θ

Start with 1 solution for 0 tents.

FLυF⌕A§υιT«

Loop over the positions of the trees.

≔⟦⟧η

No tent positions for this tree found so far.

Fθ«

Loop over the tent positions for the previous trees.

υ

Print the grid.

Fλ«J§μ⁰§μ¹A»

Print the tents for this partial solution.

F⁴«

Check the four orthogonal directions.

JκιM✳⊗μ

Move to the relevant adjacent square.

¿›⁼.KK№KMA

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.

»ILθ

Print the final number of solutions.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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