Il y a une rivière et il y a des loups et des poulets d'un côté de la rivière. Ils ont un radeau et ils ont tous besoin de se rendre de l'autre côté. Cependant, le radeau ne peut pas voyager seul. Le radeau coulera si plus de deux animaux s'y trouvent. Aucun animal ne veut se mouiller à cause du froid et de la saleté de la rivière. Aucun des animaux ne peut sauter ou survoler la rivière. De plus, s'il y a des poulets d'un côté, il ne peut pas y avoir plus de loups de ce côté qu'il n'y a de poulets de ce côté - les loups décideront alors de manger les poulets. Cela signifie que vous ne pouvez pas prendre deux loups sur le radeau avec un poulet.

Votre tâche consiste à créer un programme / une fonction qui prend un certain nombre de loups et un certain nombre de poulets (supérieur ou égal au nombre de loups) en entrée et trouve le plus petit nombre de fois que le radeau doit se déplacer à travers la rivière. Si la tâche n'est pas possible, le programme / la fonction doit générer / renvoyer une chaîne vide. Il imprimera / retournera ensuite une méthode pour savoir comment procéder de la manière suivante:

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

Comme vous pouvez le déduire, le radeau se déplacera automatiquement dans des directions alternées (gauche et droite, en commençant de gauche à droite lorsque le premier ou les deux premiers animaux traversent la rivière). Cela n'a pas besoin d'être sorti / retourné. «W», «C», «CW», «CC» ou «WW» dans la sortie peuvent être séparés par au moins l'un des éléments suivants:

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

Alternativement, vous pouvez stocker les instructions en tant qu'éléments dans une liste (une liste vide signifie aucune solution).

Cas de test (sortie séparée par des virgules - l'entrée prend la forme 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

Essayez de rendre votre code aussi court en octets que possible.

Perl, 179 165 164 163 163 157 156 octets

Comprend +4 pour -p

Donner des loups suivis de poulets sur STDIN

river.pl <<< "2 3"

Sort le contenu du bateau par ligne. Pour cet exemple, il donne:

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}{

Fonctionne comme indiqué, mais remplacez \xhhet \npar leurs versions littérales pour obtenir le score revendiqué.

Cela sera probablement battu par un programme qui résout le cas général (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`

Ajoutez à cela les solutions triviales pour les loups et les poulets uniquement et un cas spécial codé en dur pour 2 2et 3 3( 4 4et plus n'ont pas de solution). Mais ce serait un programme ennuyeux.

Explication

L'état actuel du champ est stocké sous la forme d'une chaîne unique composée de:

• w pour un loup sur la berge avec le bateau
• c pour un poulet sur la berge avec le bateau
• \x88(peu inversé w) pour un loup sur l'autre rive
• \x9c(peu inversé c) pour un poulet sur l'autre rive
• Un personnage indiquant le côté du bateau Ppour la rive droite,\xaf (bit inversé P) pour la rive gauche (côté de départ)
• une nouvelle ligne \n
• tous les mouvements qui ont été effectués jusqu'à maintenant se terminent par des sauts de ligne, par exemple quelque chose comme WC\nW\nWC\nC\n(notez les Ws etC sont en majuscules ici)

Le tableau @F contiendra tous les états accessibles. Il est initialisé par la chaîne de départwolves times "w", chickens times "c", \xaf \n

Le programme boucle ensuite sur @F ce qui sera étendu pendant la boucle afin que de nouveaux états soient également traités. Pour chaque élément, il fait alors:

• Regardez la partie chaîne à gauche du premier \n qui représente la position actuelle des animaux et du bateau. Si cela a été vu avant de sauter$a{$`x/\n/}++
• Vérifiez s'il y a des poulets avec plus de loups de chaque côté. Sautez si c'est le casgrep(y/c//<y/w//&/c/,$_,~$_)
• Vérifiez si le bateau est de l'autre côté avec tous les animaux. Si oui, nous avons une solution. Conservez-le dans $\et conservez-le puisque la première solution trouvée est la plus courte$\||=$' x/^\w*\n/
• Sinon, essayez toutes les façons de sélectionner 1 ou 2 animaux sur le côté avec le bateau. Ce sont les caractères cet w. (Les animaux de l'autre côté ne correspondront pas \w) /(\w?)(.*)(c|w)(.+)\n(?{code})^/. Ensuite, inversez un peu toute la chaîne avant le \nsauf les animaux qui ont été sélectionnés pour le bateau push@F,$1.$3.~"$`$2$4\xf5". Ajoutez les animaux sélectionnés aux mouvements en les mettant en majuscule:uc"$'$1$3\n"

Le processus de sélection des animaux mélange efficacement la partie chaîne qui les représente de plusieurs façons. Donc, par exemple, wcwcet wwccpeuvent tous deux représenter 2 loups et 2 poulets. La vérification d'état $a{$`x/\n/}++distinguera inutilement ces deux états, de sorte que plus d'états que nécessaire seront générés et vérifiés. Par conséquent, le programme manquera de mémoire et de temps dès que le nombre d'animaux différents augmentera. Ceci n'est que légèrement atténué par le fait que la version actuelle cessera d'ajouter de nouveaux états une fois qu'une solution sera trouvée

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

Prend le nombre de loups et de poulets (w, c)et retourne l'une des solutions optimales, ou undefineds'il n'y a pas de solution.

(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

Formaté et commenté

Fonction wrapper:

(                                    // 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

Fonction récursive principale:

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

Cas de test

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*

Essayez-le en ligne

Explication:

Fondamentalement, le programme fait un BFS et se souvient de chaque état atteint afin d'éviter les cycles infinis. Les états de travail sont représentés comme [[Wl Cl] [Wr Cr] M1 M2… Mn] où W = loups, C = poulets, l = côté gauche, r = côté droit, M = mouvements effectués jusqu'à présent (initialement aucun), et les mouvements sont comme "C", "WC" ou "WW" etc (pratiquement plus comme ["" "C"], ["W" "C"], ["WW" ""], mais c'est la même chose lors de l'impression). Les états mémorisés sont représentés comme [[Wl Cl] [Wr Cr] S] où S est le côté avec le bateau (0 = gauche, 1 = droite).

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 octets

->*@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]//()}

Génère des chaînes de plus en plus longues (wolf count, chicken count) états pour la rive gauche et renvoie le premier qui correspond à toutes les règles.

Il s'avère que cette approche n'est ni efficace ni très concise, mais au moins c'était amusant d'écrire.
Je ne pense pas avoir jamais empilé les méta-opérateurs Z(zip) et X(croisés) auparavant, comme les ZZ-etZX* ici - un peu surpris que cela ait réellement fonctionné.

(Les sauts de ligne sont juste ajoutés à des fins d'affichage et ne font pas partie du nombre d'octets.)

JavaScript (ES6), 227 237

Fondamentalement, il fait un BFS et se souvient de chaque état atteint afin d'éviter les cycles infinis. Contrairement à @ aditsu, je ne pense pas qu'il y ait de place pour le 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")

Moins 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
}

Tester

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>