Code Golf Asked on October 27, 2021
Sequel to Verify Tents and Trees solution.
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.
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 . . . . . .
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 code-golf rules apply. The shortest code in bytes wins.
This uses the same notation as the above example; T
for trees and .
for empty spaces.
. . .
. . .
. . . (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 .
(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 .
. . . . .
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
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)))
-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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP