TransWikia.com

Tents and Trees feasibility

Code Golf Asked on October 27, 2021

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

2 Answers

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.

Answered by Neil on October 27, 2021

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

Answered by fireflame241 on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP