12
\$\begingroup\$

The Cabbage, Wolf, Goat riddle with a twist!

Backstory:

There’s an intergalactic river than needs to be crossed! Being a space-ferryman you’ve offered some aliens on your small space ferry that can only carry two entities: you and a passenger. However, you know that because politics, some of these aliens will instantly zap some other aliens if they are left at on a planet unsupervised. Supervision means you are watching them. (Once they go to the other side, they are no longer affiliated with you and you can just let them sort it out amongst themselves). Being an uneducated earthling, you have no way of knowing who will zap who until you meet them, and therefore you can’t plan who will ride your ship when. So, you decide to write a program that will instantly plan your route.

Input:

Input can be taken in any way that makes sense. It will be a list of strings. The first character of the string will be a length 1 name of the alien. The second character of the string will be who the alien will zap. If there is no second character, the alien is at peace with everybody (unless it has been previously declared that somebody hates that alien).

Examples:

  • ["WG", "GC"] - the original riddle.
  • ["YB", "BU", "UJ", "YJ"] - the Yipiyuks zap the Bobles, the Bobles zap the Umpalumps, the Umpalumps zap the Jogos, and the Yipiyuks zap the Jogos.
  • ["YB", "U"] - the Yipiyuks zap the Bobles, and the Umpalumps are just sitting there chilling.
  • ["YB", "B"] - the Yipiyuks zap the Bobles, and even though the Bobles want to chill, they can’t.

Output:

Output the solution to the puzzle. The first element of the list will be who goes on the first trip to the destination. The second element of the list (if necessary) is who will come back from the the destination. The third will be who goes to the destination on the second round, and so on. Redundant trips must be avoided (ie. the Yipiyuks go and then come back again.) If there is no solution, output something that is distinguishable from a solution. If there is more than one solution, output any solution as long as it is correct.

Examples:

  • ["G", "", "W", "G", "C", "", "G"] - Solution to the original Cabbage Wolf Goat riddle. The Goat goes, and nobody goes back. The Wolf goes, and the Goat goes back. The Cabbage goes, and nobody goes back. And finally, the Goat is brought to the other side.
  • ["Y"] The Yipiyuks go to the other side, and nothing else happens.

Test Cases

["WG", "GC"]       ->  ["G", "", "W", "G", "C", "", "G"]
["YB", "U"]        ->  ["Y", "", "U", "", "B"]
["YB", "B"]        ->  ["Y", "", "B"] 
["YB", "BU", "YU"] ->  No Solution

This is , so shortest answer in bytes wins!

\$\endgroup\$
17
  • 3
    \$\begingroup\$ Related \$\endgroup\$
    – Arnauld
    Commented Nov 21, 2022 at 10:47
  • 4
    \$\begingroup\$ When it says "Once they go to the other side, they are no longer affiliated with you and you can just let them sort it out amongst themselves" is that after only after we have completed the transfer of all aliens? \$\endgroup\$ Commented Nov 21, 2022 at 13:44
  • 2
    \$\begingroup\$ Am I correct in asserting that ["YB", "BU", "UJ", "YJ"] has no solution due to the fact that whichever alien we decided to transfer first we'd be leaving a pair behind where one would zap the other? \$\endgroup\$ Commented Nov 21, 2022 at 13:49
  • 2
    \$\begingroup\$ @Arnauld - Ah, that definitely needs clarifying, then. Although I'd personally be surprised if supervision by a cabbage would reliably deter a wolf from eating a goat... \$\endgroup\$ Commented Nov 21, 2022 at 15:31
  • 3
    \$\begingroup\$ The poor Jogos, everybody hates them :( \$\endgroup\$
    – Seggan
    Commented Nov 21, 2022 at 16:44

2 Answers 2

4
\$\begingroup\$

Python 3, 180 bytes

def f(l):
 X={''}.union(*l);B=X-X;n=1;q=S=L=[]
 while n or B:
  while~-len(B)and B in map(set,l)or(n,B)in S:n,B,L,*q=q
  for i in X-B:q=*q,1-n,X-B-{'',i},L+[i];S=*S,(n,B)
 return L

Try it online!

Raises an exception to indicate no solution.

\$\endgroup\$
4
+50
\$\begingroup\$

JavaScript (ES7), 187 bytes

Returns a string, where , means that there's no alien in the ship. Throws an error if there's no solution.

f=(a,N=0,s=new Set(','+a),M=2**s.size-1,g=(o,m)=>m^M?[...s].some((v,i,b)=>!o[N]&a.every(s=>~(m^m%2*M)&(h=n=>1<<b.indexOf(s[n]))(0)+h(1))&(m>>i^~m)&&g(o+v,m^1<<i^!!i)):O=o)=>g``?O:f(a,N+2)

Try it online!

Commented

Wrapper

f = (                   // f is a recursive function taking:
  a,                    //   a[] = input array
  N = 0,                //   N   = maximum number of rides - 1
  s = new Set(',' + a), //   s   = set of alien characters
                        //         + a leading comma for the pilot
  M = 2 ** s.size - 1,  //   M   = bit mask of passengers (pilot + aliens)
  g = ...               //   g   = main search function (detailed below)
) => g`` ? O            // if g() does not succeed,
         : f(a, N + 2)  // increase N until it does

Search function

g = (                   // g is the main recursive search function taking:
  o,                    //   o = output string
  m                     //   m = bit mask of transferred passengers
) =>                    //       bit #0 is the pilot
m ^ M ?                 // if m is not equal to M:
  [...s]                //   turn s into an array
  .some((v, i, b) =>    //   for each character v at position i in b[]:
    !o[N] &             //     abort if we've reached the max. number of rides
    a.every(s =>        //     for each string s in a[]:
      ~(m ^ m % 2 * M)  //       take the 1's complement of either m or m XOR M
      &                 //       depending on the side of arrival
      ( h = n =>        //       h is a helper function that turns the 1st or
        1 <<            //       2nd character of s into a bit mask according
        b.indexOf(s[n]) //       to its position in b[] (2**31 if not found)
      )(0) + h(1)       //       if both antagonists are there, we have a *ZAP*
                        //       situation
    ) &                 //     end of every()
    (m >> i ^ ~m)       //     make sure the passenger is on the departure side
    &&                  //     if successful:
      g(                //       do a recursive call to g:
        o + v,          //         append v to the output string
        m ^ 1 << i      //         mark the passenger as transferred
        ^ !!i           //         unless the passenger is the pilot himself,
                        //         mark the pilot as transferred as well
      )                 //     end of recursive call
  )                     //   end of some
:                       // else:
  O = o                 //   success: save the solution in O
\$\endgroup\$
2
  • \$\begingroup\$ You the ferryman has to be there in order for no zapping to occur. Will fix the wording. \$\endgroup\$ Commented Nov 21, 2022 at 17:19
  • \$\begingroup\$ @joyoforigami Thanks for the clarification. Fixed accordingly. \$\endgroup\$
    – Arnauld
    Commented Nov 21, 2022 at 17:37

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.