19
\$\begingroup\$

Background

One kind of river-crossing problems involves two kinds of animals. One such problem reads like this: (all wordings, including animal species, are arbitrary)

A farmer has to cross a river with three chickens and three dogs. There's a boat which can only fit the farmer and at most two animals. On either side of the river, if both kinds of animals are present and the dogs outnumber the chickens at any moment, the dogs will kill the chickens. Also, for some reason, the farmer can't cross the river alone. Can the farmer safely cross the river with all his animals? (For the sake of the puzzle, assume that all animals land on the destination side before the next turn.)

Bonus: What if the farmer had four of each kind of animals?

whose answer is

Yes:

πŸ”πŸ”πŸ”πŸ•πŸ•πŸ• |          |
                πŸ•πŸ•->
πŸ”πŸ”πŸ”πŸ•     |          | πŸ•πŸ•
                <-πŸ•
πŸ”πŸ”πŸ”πŸ•πŸ•   |          | πŸ•
                πŸ•πŸ•->
πŸ”πŸ”πŸ”       |          | πŸ•πŸ•πŸ•
                <-πŸ•
πŸ”πŸ”πŸ”πŸ•     |          | πŸ•πŸ•
                πŸ”πŸ”->
πŸ”πŸ•         |          | πŸ”πŸ”πŸ•πŸ•
                <-πŸ”πŸ•
πŸ”πŸ”πŸ•πŸ•     |          | πŸ”πŸ•
                πŸ”πŸ”->
πŸ•πŸ•         |          | πŸ”πŸ”πŸ”πŸ•
                <-πŸ•
πŸ•πŸ•πŸ•       |          | πŸ”πŸ”πŸ”
                πŸ•πŸ•->
πŸ•           |          | πŸ”πŸ”πŸ” πŸ•πŸ•
                <-πŸ•
πŸ•πŸ•         |          | πŸ”πŸ”πŸ” πŸ•
                πŸ•πŸ•->
             |          | πŸ”πŸ”πŸ” πŸ•πŸ•πŸ•

Bonus: No.

One way to solve this puzzle is to construct a grid like this: O indicates that the dog-chicken combination is allowed on the initial side (and the rest on the opposite side); X means not allowed.

πŸ•\πŸ”| 0 1 2 3
-----+---------
  0  | O X X O
  1  | O O X O
  2  | O X O O
  3  | O X X O

Then the problem is about going from (3,3) to (0,0) with alternating forward-backward moves (using NSEW for one step in each cardinal direction):

  • Forward: one of N, W, NN, WW, or NW
  • Backward: one of S, E, SS, EE, or SE

The solution in the spoiler box follows the path below:

(3,3) NN -> (1,3)
      S  -> (2,3)
      NN -> (0,3)
      S  -> (1,3)
      WW -> (1,1)
      SE -> (2,2)
      WW -> (2,0)
      S  -> (3,0)
      NN -> (1,0)
      S  -> (2,0)
      NN -> (0,0)

Challenge

Given a rectangular grid of valid states as shown above, determine whether the river-crossing puzzle has a solution or not, i.e. a forward-backward alternating path exists between the top left corner and the bottom right corner.

The input has at least two rows and columns, but it may or may not be a square. The O's and X's in the input may be represented using any two distinct constant values (e.g. booleans, numbers, strings). You may assume the start and end corners are both O's.

For output, you can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

The test cases use 1 and 0 for O and X respectively.

Truthy

[[1, 0],
 [0, 1]]

[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

[[1, 1, 0],
 [0, 1, 1]]

[[1, 0, 1, 1, 1, 0, 1],
 [1, 1, 1, 0, 1, 1, 1]]

[[1, 1, 1],
 [0, 0, 1],
 [0, 0, 1]]

[[1, 0, 1, 1, 1],
 [1, 0, 0, 0, 1],
 [1, 1, 1, 0, 1]]

[[1, 0, 0, 1],
 [1, 1, 0, 1],
 [1, 0, 1, 1],
 [1, 0, 0, 1]]

Falsy

[[1, 0, 0],
 [0, 0, 1]]

[[1, 0, 1],
 [1, 0, 1]]

[[1, 1, 0],
 [1, 0, 1]]

[[1, 0, 0, 0, 1],
 [1, 1, 0, 0, 1],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 1, 1],
 [1, 0, 0, 0, 1]]

Related: Wolves and Chickens (bonus: can you exploit the strategy to golf the linked challenge further?)

\$\endgroup\$
0

3 Answers 3

6
\$\begingroup\$

Wolfram Language (Mathematica), 97 bytes

Saved 6 bytes thanks to @att.

FindPath[Pick[e@@#<->#2,0<=Min[d=#2-#]<Tr@d<3]&@@@#~Tuples~2,1~e~1,Last@#]~FreeQ~{}&@*Position[1]

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 97 bytes \$\endgroup\$
    – att
    Oct 19, 2021 at 22:32
3
\$\begingroup\$

Charcoal, 88 bytes

βŠžΟ…βŠ–βŸ¦β°οΌ¬ΞΈοΌ¬Β§ΞΈβ°βŸ§οΌ¦ΞΈοΌ¦Β²βŠžΞΉβ°οΌ¦Β²βŠžΞΈοΌ₯§θ⁰¦⁰FυF³F³«≔οΌ₯ΞΉβŽ‡Ξ½βΊΞΌΓ—Β§ΞΉβ°βŽ‡βŠ–Ξ½Ξ»ΞΊΒ±ΞΌΞ·ΒΏβˆ§βˆ¨ΞΊΞ»βˆ§β€ΊΒ³βΊΞΊΞ»β€ΊΒ§Β§ΞΈΒ§Ξ·ΒΉΒ§Ξ·Β²β„–Ο…Ξ·Β«βŠžΟ…Ξ·Β¬βŒˆΞ¦Ξ·Ξ½

Try it online! Link is to verbose version of code. Outputs - if a solution exists, nothing if not. Explanation:

βŠžΟ…βŠ–βŸ¦β°οΌ¬ΞΈοΌ¬Β§ΞΈβ°βŸ§

Start a breadth-first search with the initial position of the next move from the bottom right corner being a "forward" move.

FθF²⊞ι⁰F²⊞θοΌ₯§θ⁰¦⁰

Pad the input with two rows and columns of zeros.

οΌ¦Ο…οΌ¦Β³οΌ¦Β³Β«

Consider all moves from all positions plus some illegal moves at this point.

≔οΌ₯ΞΉβŽ‡Ξ½βΊΞΌΓ—Β§ΞΉβ°βŽ‡βŠ–Ξ½Ξ»ΞΊΒ±ΞΌΞ·

Calculate the resulting position from this move, adjusted for "forward" and "reverse".

ΒΏβˆ§βˆ¨ΞΊΞ»βˆ§β€ΊΒ³βΊΞΊΞ»β€ΊΒ§Β§ΞΈΒ§Ξ·ΒΉΒ§Ξ·Β²β„–Ο…Ξ·Β«

If the move is legal (i.e. one of NN, NW, N, WW or W for "forward" and equivalently for "reverse"), and the resulting position is legal and as yet unknown, then:

βŠžΟ…Ξ·

Add the position to the list of known positions.

¬⌈Φην

Output a - if this position is in fact the top left.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 112 bytes

Expects a matrix of 0's and 2's, for 'X' and 'O' respectively. Returns 0 or 2.

f=(m,x=0,y=0,i=1,r=m[y]||0)=>(r[x]--&&[1,2,4,5,8].some(d=>r[x+1]+1||m[y+1]?f(m,x+i*d%4,y+i*(d>>2),-i):1))*++r[x]

Try it online!

Commented

f = (                     // f is a recursive function taking:
  m,                      //   m[]    = input matrix
  x = 0, y = 0,           //   (x, y) = current position
  i = 1,                  //   i      = direction (1 for S/E, -1 for N/W)
  r = m[y] || 0           //   r[]    = current row
) => (                    //
  r[x]--                  // decrement r[x]
  &&                      // abort if it was 0 or undefined
  [1, 2, 4, 5, 8]         // otherwise, for each value d
  .some(d =>              // in [1, 2, 4, 5, 8]:
    r[x + 1] + 1 ||       //   if there's either a cell on our right
    m[y + 1] ?            //   or below us:
      f(                  //     do a recursive call:
        m,                //       pass m[]
        x + i * d % 4,    //       update x to x + i * (d mod 4)
        y + i * (d >> 2), //       update y to y + i * (d >> 2)
        -i                //       invert the direction
      )                   //     end of recursive call
    :                     //   else (we've reached the bottom-right corner):
      1                   //     success
  )                       // end of some()
) * ++r[x]                // restore r[x]
\$\endgroup\$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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