11
\$\begingroup\$

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 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 . .
\$\endgroup\$
  • \$\begingroup\$ Can we assume the input will always contain at least one tent and/or tree? So an input with only empty spots / dots is undefined and it doesn't matter whether it outputs truthy or falsey? And what about an empty input? \$\endgroup\$ – Kevin Cruijssen Jul 6 at 17:31
  • \$\begingroup\$ @Kevin Input may have zero tents and zero trees, which is truthy. You can assume the input will have at least one row and one column. Will add a test case shortly. \$\endgroup\$ – Bubbler Jul 6 at 21:49
4
\$\begingroup\$

J, 88 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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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