Hay un río y hay lobos y gallinas a un lado del río. Tienen una balsa y todos necesitan llegar al otro lado. Sin embargo, la balsa no puede viajar sola. La balsa se hundirá si hay más de dos animales en ella. Ninguno de los animales quiere mojarse porque el río está frío y sucio. Ninguno de los animales puede saltar o volar sobre el río. Además, si hay pollos en un lado, no puede haber más lobos en ese lado que pollos en ese lado: los lobos decidirán comerlos. Esto significa que no puedes llevar a dos lobos en la balsa a un lado con un pollo.

Su tarea es hacer un programa / función que tome una cantidad de lobos y una cantidad de pollos (mayor o igual que la cantidad de lobos) como entrada y encuentre la menor cantidad de veces que la balsa tiene que moverse a través del río. Si la tarea no es posible, el programa / función debería generar / devolver una cadena vacía. Luego imprimirá / devolverá un método sobre cómo se hace de la siguiente manera:

W if a wolf crosses the river on its own
C if a chicken crosses the river on its own
CW if a chicken and a wolf cross the river -- WC is also fine
CC if two chickens cross the river
WW if two wolves cross the river

Como puede deducir, la balsa se moverá automáticamente en direcciones alternas (izquierda y derecha, comenzando de izquierda a derecha cuando el primero o dos animales crucen el río). Esto no necesita ser enviado / devuelto. 'W', 'C', 'CW', 'CC' o 'WW' en la salida pueden estar separados por al menos uno de los siguientes:

spaces (' ')
commas (',')
newlines

Alternativamente, puede almacenar las instrucciones como elementos en una lista (una lista vacía significa que no hay solución).

Casos de prueba (salida separada por comas - la entrada toma la forma wolves,chickens):

1,1 -> CW

2,2 -> CW,C,CC,C,CW

1,2 -> CW,W,CW

0,10 -> CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC

3,2 -> no solution

Intenta hacer que tu código sea lo más corto posible en bytes.

Perl, 179 165 164 163 157 156 bytes

Incluye +4 para -p

Dar lobos seguidos de pollos en STDIN

river.pl <<< "2 3"

Emite el contenido del barco por línea. Para este ejemplo da:

WC
C
CC
C
CC
W
WW

river.pl:

#!/usr/bin/perl -p
/ /;@F=w x$`.c x$'."\xaf\n";$a{$`x/\n/}++||grep(y/c//<y/w//&/c/,$_,~$_)or$\||=$' x/^\w*\n|(\w?)(.*)(c|w)(.+)\n(?{push@F,$1.$3.~"$`$2$4\xf5".uc"$'$1$3\n"})^/ for@F}{

Funciona como se muestra, pero reemplaza \xhhy \npor sus versiones literales para obtener la puntuación reclamada.

Esto probablemente será superado por un programa que resuelva el caso general (C> W> 0)

* output `WC W WC C` until there is only one wolf left on the left bank (--w, --c)
* output `CC C` until there is only one chicken left on the left bank (--c)
* output `WC`

Agregue a eso las soluciones triviales para solo lobos y solo pollos y un estuche especial codificado para 2 2y 3 3( 4 4y más alto no tienen solución). Pero ese sería un programa aburrido.

Explicación

El estado actual del campo se almacena como una sola cadena que consiste en:

• w para un lobo en la orilla con el bote
• c por un pollo en la orilla con el bote
• \x88(poco invertido w) para un lobo en el otro banco
• \x9c(poco invertido c) para un pollo en el otro banco
• Un carácter que indica el lado en el que se encuentra el barco Ppara la orilla derecha, \xaf(bit invertido P) para la orilla izquierda (lado inicial)
• una nueva línea \n
• todos los movimientos que se han hecho hasta ahora terminaron con nuevas líneas, por ejemplo, algo así WC\nW\nWC\nC\n(observe los Wsy Cestán en mayúsculas aquí)

La matriz @Fcontendrá todos los estados accesibles. Se inicializa con la cadena de iniciowolves times "w", chickens times "c", \xaf \n

Luego, el programa realiza un bucle @Fque se extenderá durante el bucle para que también se procesen nuevos estados. Para cada elemento, entonces hace:

• Mire la parte de la cuerda a la izquierda de la primera \nque representa la posición actual de los animales y el bote. Si eso se ha visto antes de saltar$a{$`x/\n/}++
• Compruebe si hay pollos junto con más lobos en cualquier lado. Omitir si es asígrep(y/c//<y/w//&/c/,$_,~$_)
• Verifique si el bote está al otro lado junto con todos los animales. Si es así, tenemos una solución. Guárdelo $\y guárdelo ya que la primera solución encontrada es la más corta$\||=$' x/^\w*\n/
• De lo contrario, intente todas las formas de seleccionar 1 o 2 animales en el costado del bote. Estos son los cy wpersonajes. (Los animales del otro lado no coincidirán \w) /(\w?)(.*)(c|w)(.+)\n(?{code})^/. Luego, invierta la cadena completa antes de la \nexcepción de los animales que fueron seleccionados para el bote push@F,$1.$3.~"$`$2$4\xf5". Agregue los animales seleccionados a los movimientos en mayúsculas:uc"$'$1$3\n"

El proceso de selección de animales baraja efectivamente la parte de la cuerda que los representa de muchas maneras. Entonces, por ejemplo, wcwcy wwccambos pueden llegar a representar 2 lobos y 2 pollos. La comprobación de estado $a{$`x/\n/}++distinguirá de manera poco práctica estos dos estados, por lo que se generarán y comprobarán muchos más estados de los necesarios. Por lo tanto, el programa se quedará sin memoria y tiempo tan pronto como el número de animales diferentes aumente. Esto se mitiga solo un poco por el hecho de que la versión actual dejará de agregar nuevos estados una vez que se encuentre una solución

JavaScript (ES6), 251 264 ... 244 240 bytes

Toma el número de lobos y gallinas (w, c)y devuelve una de las soluciones óptimas, o undefinedsi no hay solución.

(w,c,v={},B=1/0,S)=>(r=(s,w,c,W=0,C=0,d=1,N=0,k=w+'|'+c+d)=>v[k]|c*w>c*c|C*W>C*C|w<0|c<0|W<0|C<0?0:w|c?[v[k]=1,2,4,8,5].map(n=>r(s+'C'.repeat(b=n>>2)+'W'.repeat(a=n&3)+' ',w-d*a,c-d*b,W+d*a,C+d*b,-d,N+1))&(v[k]=0):N<B&&(B=N,S=s))('',w,c)||S

Formateado y comentado

Función de envoltura:

(                                    // given:
  w,                                 // - w : # of wolves
  c,                                 // - c : # of chickens
  v = {},                            // - v : object keeping track of visited nodes
  B = 1 / 0,                         // - B : length of best solution
  S                                  // - S : best solution
) => (                               //
r = (...) => ...                     // process recursive calls (see below)
)('', w, c) || S                     // return the best solution

Función recursiva principal:

r = (                                // given:
  s,                                 // - s : current solution (as text)
  w, c,                              // - w/c : # of chickens/wolves on the left side
  W = 0, C = 0,                      // - W/C : # of chickens/wolves on the right side
  d = 1,                             // - d : direction (1:left to right, -1:right to left)
  N = 0,                             // - N : length of current solution
  k = w + '|' + c + d                // - k : key identifying the current node
) =>                                 //
v[k] |                               // abort if this node was already visited
c * w > c * c | C * W > C * C |      // or there are more wolves than chickens somewhere
w < 0 | c < 0 | W < 0 | C < 0 ?      // or we have created antimatter animals 
  0                                  //
:                                    // else:
  w | c ?                            //   if there are still animals on the left side:
    [v[k] = 1, 2, 4, 8, 5].map(n =>  //     set node as visited and do a recursive call
      r(                             //     for each combination: W, WW, C, CC and CW
        s + 'C'.repeat(b = n >> 2) + //     append used combination to current solution
        'W'.repeat(a = n & 3) + ' ', //     wolves = bits 0-1 of n / chickens = bits 2-3
        w - d * a,                   //     update wolves on the left side
        c - d * b,                   //     update chickens on the left side
        W + d * a,                   //     update wolves on the right side
        C + d * b,                   //     update chickens on the right side
        -d,                          //     use opposite direction for the next turn
        N + 1                        //     increment length of current solution
      )                              //
    ) &                              //     once we're done,
    (v[k] = 0)                       //     set this node back to 'not visited'
  :                                  //   else:
    N < B &&                         //     save this solution if it's shorter than the
    (B = N, S = s)                   //     best solution encountered so far

Casos de prueba

let f =

(w,c,v={},B=1/0,S)=>(r=(s,w,c,W=0,C=0,d=1,N=0,k=w+'|'+c+d)=>v[k]|c*w>c*c|C*W>C*C|w<0|c<0|W<0|C<0?0:w|c?[v[k]=1,2,4,8,5].map(n=>r(s+'C'.repeat(b=n>>2)+'W'.repeat(a=n&3)+' ',w-d*a,c-d*b,W+d*a,C+d*b,-d,N+1))&(v[k]=0):N<B&&(B=N,S=s))('',w,c)||S

console.log(f(1, 1));
console.log(f(2, 2));
console.log(f(1, 2));
console.log(f(0, 10));
console.log(f(3, 2));

CJam, 133

q~[0_]]_0+a:A;a{{28e3Zb2/{[YT2*(f*_Wf*]X..+:Bs'-&B2<{~_@<*},+{B2<T!+a:CA&{AC+:A;BY"WC".*a+}|}|}fY}fX]T!:T;__!\{0=:+!},e|:R!}g;R0=2>S*

Pruébalo en línea

Explicación:

Básicamente, el programa realiza un BFS y recuerda cada estado alcanzado para evitar ciclos infinitos. Los estados de trabajo se representan como [[Wl Cl] [Wr Cr] M1 M2 ... Mn] donde W = lobos, C = pollos, l = lado izquierdo, r = lado derecho, M = movimientos realizados hasta ahora (inicialmente ninguno), y los movimientos son como "C", "WC" o "WW", etc. (prácticamente más como ["" "C"], ["W" "C"], ["WW" ""], pero es lo mismo al imprimir). Los estados recordados se representan como [[Wl Cl] [Wr Cr] S] donde S es el lado del barco (0 = izquierda, 1 = derecha).

q~                 read and evaluate the input ([Wl Cl] array)
[0_]               push [0 0] as the initial [Wr Cr] array
]_                 wrap both in an array (initial working state) and duplicate it
0+a                append 0 (representing left side) and wrap in an array
:A;                store in A and pop; this is the array of remembered states
a                  wrap the working state in an array
{…}g               do … while
  {…}fX            for each working state X
    28e3Zb2/       convert 28000 to base 3 and group the digits into pairs
                    this generates [[1 1] [0 2] [1 0] [2 0] [0 1]]
                    which are all possible moves represented as [Wb Cb] (b=boat)
    {…}fY          for each "numeric move" pair Y
      […]          make an array of…
        YT2*(f*    Y negated if T=0 (T is the current boat side, initially 0)
        _Wf*       and the (arithmetic) negation of the previous pair
      X..+         add the 2 pairs to X, element by element
                    this performs the move by adding & subtracting the numbers
                    from the appropriate sides, determined by T
      :Bs          store the updated state in B, then convert to string
      '-&          intersect with "-" to see if there was any negative number
      B2<          also get just the animal counts from B (first 2 pairs)
      {…},         filter the 2 sides by checking…
        ~_@<*      if W>C>0 (it calculates (C<W)*C)
      +            concatenate the results from the negative test and eating test
      {…}|         if it comes up empty (valid state)…
        B2<        get the animal counts from B (first 2 pairs)
        T!+        append !T (opposite side)
        a:C        wrap in an array and store in C
        A&         intersect with A to see if we already reached that state
        {…}|       if not, then…
          AC+:A;   append C to A
          BY       push B and Y (updated state and numeric move)
          "WC".*   repeat "W" and "C" the corresponding numbers of times from Y
                    to generate the alphabetic move
          a+       wrap in array and append to B (adding the current move)
  ]                collect all the derived states in an array
  T!:T;            reverse the side with the boat
  __!              make 2 copies of the state array, and check if it's empty
  \{…},            filter another copy of it, checking for each state…
    0=:+!          if the left side adds up to 0
  e|:R             logical "or" the two and store the result in R
  !                (logically) negate R, using it as a do-while condition
                    the loop ends when there are no more working states
                    or there are states with the left side empty
;                  after the loop, pop the last state array
R0=2>S*            if the problem is solved, R has solution states,
                    and this extracts the moves from the first state
                    and joins them with space
                   if there's no solution, R=1
                    and this repeats a space 0 times, resulting in empty string

Perl 6 , 268 bytes

->*@a {(
[X](0 X..@a)[1..*-2]
.grep({![>](|$_,0)&![>](|(@a Z-$_),0)})
.combinations(2)
.combinations
.map(|*.permutations)
.map({.map(|*)»[*]})
.map({((|$_,(0,0)ZZ-@a,|$_)ZX*|(-1,1)xx*)»[*]})
.grep({.all.&{.all>=0&&3>.sum>0}})
.map({.map:{[~](<W C>Zx$_)}})
if [<=] @a
)[0]//()}

Genera cadenas de (wolf count, chicken count)estados cada vez más largas para la orilla izquierda y devuelve la primera que coincide con todas las reglas.

Resulta que este enfoque no es eficiente ni muy conciso, pero al menos fue divertido escribirlo.
No creo que nunca haya apilado los meta-operadores Z(zip) y X(cross) antes, como el ZZ-y ZX*aquí, un poco sorprendido de que realmente haya funcionado.

(Las nuevas líneas solo se agregan para fines de visualización y no forman parte del recuento de bytes).

JavaScript (ES6), 227 237

Básicamente, hace un BFS y recuerda cada estado que alcanzó para evitar ciclos infinitos. A diferencia de @ aditsu, no creo que haya lugar para el golf

v=>g=>eval("o=[],s=[[v,g,0,k=[]]];for(i=0;y=s[i++];k[y]=k[y]||['WW','C','CC','W','CW'].map((u,j)=>(r=w-(j?j/3|0:2),q=c-j%3,d=g-q,e=v-r,r<0|q<0|!!q&r>q|!!d&e>d)||s.push([e,d,!z,[...p,u]])))o=([w,c,z,p]=y,y[3]=!z|c-g|w-v)?o:i=p")

Menos golf

(v,g) => {
  o = []; // output
  k = []; // hashtable to check states already seen
  s=[[v, g, 0, []]]; // states list: each element is wolves,chickens,side,path
  for(i = 0; 
      y = s[i++]; // exit loop when there are no more states to expand
     )
  {
    [w, c, z, p] = x; // wolves on this side, chickens on this side, side, path
    if (z && c==g && w==v) // if all chicken and wolves on the other side
      o = p, // the current path is the output
      i = p  // this will force the loop to terminate
    y[3] = 0; // forget the path, now I can use y as the key to check state and avoid cycles
    if (! k[y]) // it's a new state
    {
       k[y] = 1; // remember it
       ['WW','C','CC','W','CW'].map( (u,j)=> (
          a = j ? j/3|0 : 2, // wolves to move
          b = j % 3, // chicken to move  
          r = w - a, // new number of wolves on this side 
          q = c - b, // new number of chickens on this side
          e = v - r, // new number of wolves on other side
          d = g - q, // new number of chickens on other side
          // check condition about the number of animals together
          // if ok, push a new state
          r<0 |q<0 | !!q&r>q | !!d&e>d || 
            s.push([e, d, !z, [...p,u]) 
       )
    }
  }
  return o
}

Prueba

F=
v=>g=>eval("o=[],s=[[v,g,0,k=[]]];for(i=0;y=s[i++];k[y]=k[y]||['WW','C','CC','W','CW'].map((u,j)=>(r=w-(j?j/3|0:2),q=c-j%3,d=g-q,e=v-r,r<0|q<0|!!q&r>q|!!d&e>d)||s.push([e,d,!z,[...p,u]])))o=([w,c,z,p]=y,y[3]=!z|c-g|w-v)?o:i=p")

function update() {
  var c=+C.value, w=+W.value
  O.textContent=F(w)(c)
}

update()

input { width: 4em }

Chickens <input id=C value=2 type=number min=0 oninput='update()'>
Wolves <input id=W value=2 type=number min=0 oninput='update()'>
<pre id=O></pre>