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

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ßsZðת€ü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
    ª      # 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 `Zðת` 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=₀|¬{s₂\s₂c⊇Ċ=₂}&{iiʰgᵗcṗʰ}ᶠhᵍpᵗz₂{\b-ᵐȧᵐ+1}ᵐ

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

How it works

c=₀|

Either the flatten matrix contains only 0's or …

¬{s₂\s₂c

No 2x2 submatrix flattened …

⊇Ċ=₂}

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

&{iiʰgᵗc

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

ṗʰ}

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

ᶠp

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

hᵍ

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

z₂

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

{\b-ᵐȧᵐ+1}ᵐ

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.