Es gibt einen Fluss und es gibt Wölfe und Hühner auf einer Seite des Flusses. Sie haben ein Floß und müssen alle auf die andere Seite. Das Floß kann jedoch nicht alleine fahren. Das Floß sinkt, wenn mehr als zwei Tiere darauf sind. Keines der Tiere möchte nass werden, weil der Fluss kalt und schmutzig ist. Keines der Tiere kann über den Fluss springen oder fliegen. Wenn sich auf einer Seite Hühner befinden, können sich auf dieser Seite nicht mehr Wölfe befinden als auf dieser Seite - die Wölfe entscheiden sich dann, die Hühner zu fressen. Dies bedeutet, dass Sie nicht zwei Wölfe auf dem Floß mit einem Huhn zur Seite stellen können.

Ihre Aufgabe ist es, ein Programm / eine Funktion zu erstellen, das / die eine Anzahl von Wölfen und eine Anzahl von Hühnern (größer oder gleich der Anzahl von Wölfen) als Eingabe verwendet und ermittelt, wie oft sich das Floß am wenigsten über den Fluss bewegen muss. Wenn die Aufgabe nicht möglich ist, sollte das Programm / die Funktion einen leeren String ausgeben / zurückgeben. Es wird dann eine Methode ausgegeben / zurückgegeben, wie dies auf folgende Weise erfolgt:

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

Wie Sie ableiten können, bewegt sich das Floß automatisch in wechselnde Richtungen (links und rechts, beginnend von links nach rechts, wenn die ersten ein oder zwei Tiere den Fluss überqueren). Dies muss nicht ausgegeben / zurückgegeben werden. 'W', 'C', 'CW', 'CC' oder 'WW' in der Ausgabe können durch mindestens eine der folgenden Angaben getrennt sein:

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

Alternativ können Sie die Anweisungen als Elemente in einer Liste speichern (eine leere Liste bedeutet keine Lösung).

Testfälle (Ausgabe durch Komma getrennt - Eingabe hat die Form 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

Versuchen Sie, Ihren Code so kurz wie möglich in Bytes zu halten.

Perl, 179 165 164 163 157 156 Bytes

Beinhaltet +4 für -p

Gib Wölfen gefolgt von Hühnern auf STDIN

river.pl <<< "2 3"

Gibt den Bootsinhalt pro Zeile aus. Für dieses Beispiel gibt es:

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

Funktioniert wie abgebildet, aber ersetzen \xhh und \ndurch ihre Literalversionen, um die beanspruchte Punktzahl zu erhalten.

Dies wird wahrscheinlich von einem Programm geschlagen, das den allgemeinen Fall löst (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`

Hinzu kommen die trivialen Lösungen für nur Wölfe und nur Hühner und ein fest codierter Spezialfall für 2 2 und3 3 ( 4 4und höher haben keine Lösung). Aber das wäre ein langweiliges Programm.

Erläuterung

Der aktuelle Status des Feldes wird als einzelne Zeichenfolge gespeichert, bestehend aus:

• w für einen Wolf am Ufer mit dem Boot
• c für ein Huhn am Ufer mit dem Boot
• \x88 (Bit vertauscht w ) für einen Wolf am anderen Ufer
• \x9c (Bit vertauscht c ) für ein Huhn am anderen Ufer
• Ein Zeichen, das angibt, auf welcher Seite sich das Boot am Prechten Ufer befindet \xaf(Bit umgekehrt)P ), für das linke Ufer (Startseite)
• eine newline \n
• Alle bisher durchgeführten Züge werden mit Zeilenumbrüchen abgeschlossen, z. B. so etwas wie WC\nW\nWC\nC\n(beachte das Ws und schreibe Chier groß).

Das Array @Fenthält alle erreichbaren Zustände. Es wird durch die Startzeichenfolge initialisiertwolves times "w", chickens times "c", \xaf \n

Das Programm durchläuft dann eine Schleife, @Fdie während des Schleifens verlängert wird, so dass auch neue Zustände verarbeitet werden. Für jedes Element gilt dann:

• Schauen Sie sich den Saitenteil links vom ersten an \n der die aktuelle Position der Tiere und des Bootes darstellt. Wenn das schon mal gesehen wurde überspringen$a{$`x/\n/}++
• Überprüfen Sie, ob sich auf jeder Seite Hühner mit mehr Wölfen befinden. Überspringen, wenn jagrep(y/c//<y/w//&/c/,$_,~$_)
• Überprüfen Sie, ob sich das Boot mit allen Tieren auf der anderen Seite befindet. Dann haben wir eine Lösung. $\Bewahren Sie das auf und bewahren Sie es auf, da die erste gefundene Lösung die kürzeste ist$\||=$' x/^\w*\n/
• Andernfalls versuchen Sie alle Möglichkeiten, 1 oder 2 Tiere an der Seite des Bootes auszuwählen. Dies sind die cund wZeichen. (Die Tiere auf der anderen Seite werden passen nicht zusammen \w) /(\w?)(.*)(c|w)(.+)\n(?{code})^/. Dann drehen Sie die gesamte Saite vor den \nTieren, die für das Boot ausgewählt wurden, um push@F,$1.$3.~"$`$2$4\xf5". Fügen Sie die ausgewählten Tiere zu den Zügen hinzu, indem Sie sie mit einem Großbuchstaben versehen:uc"$'$1$3\n"

Der Tierauswahlprozess mischt effektiv den String-Teil, der sie auf viele Arten repräsentiert. So können zB wcwcund wwccbeide 2 Wölfe und 2 Hühner darstellen. Die Zustandsüberprüfung $a{$`x/\n/}++unterscheidet diese zwei so viel mehr Zustände, als notwendig sind, und wird erzeugt und überprüft. Aus diesem Grund wird dem Programm der Speicher und die Zeit ausgehen, sobald die Anzahl der verschiedenen Tiere größer wird. Dies wird nur ein wenig dadurch gemildert, dass die aktuelle Version keine neuen Status mehr hinzufügt, sobald eine Lösung gefunden wurde

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

Nimmt die Anzahl der Wölfe und Hühner (w, c)und gibt eine der optimalen Lösungen zurück, oder undefinedwenn es keine Lösung gibt.

(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

Formatiert und kommentiert

Wrapper-Funktion:

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

Hauptrekursivfunktion:

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

Testfälle

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*

Probieren Sie es online aus

Erläuterung:

Grundsätzlich führt das Programm ein BFS durch und merkt sich jeden erreichten Zustand, um unendliche Zyklen zu vermeiden. Die Arbeitszustände sind wie [[Wl Cl] [Wr Cr] M1 M2… Mn] dargestellt, wobei W = Wölfe, C = Hühner, l = linke Seite, r = rechte Seite, M = bisher ausgeführte Züge (anfangs keine), und die Bewegungen sind wie "C", "WC" oder "WW" usw. (praktisch eher wie ["" C "], [" W "" C "], [" WW ""], aber es ist dasselbe beim Drucken). Die erinnerten Zustände werden wie [[Wl Cl] [Wr Cr] S] dargestellt, wobei S die Seite mit dem Boot ist (0 = links, 1 = rechts).

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

Erzeugt zunehmend längere Ketten von (wolf count, chicken count) für die linke Bank und gibt die erste zurück, die allen Regeln entspricht.

Es hat sich herausgestellt, dass dieser Ansatz weder effizient noch sehr prägnant ist, aber zumindest hat es Spaß gemacht, zu schreiben.
Ich glaube, ich habe die Z(zip) - und X(cross) -Meta-Operatoren noch nie so gestapelt wie die ZZ-undZX* hier - ein bisschen überrascht, dass das tatsächlich funktioniert hat.

(Die Zeilenumbrüche werden nur zu Anzeigezwecken hinzugefügt und sind nicht Teil der Byteanzahl.)

JavaScript (ES6), 227 237

Grundsätzlich führt es ein BFS durch und merkt sich jeden erreichten Zustand, um unendliche Zyklen zu vermeiden. Im Gegensatz zu @aditsu glaube ich, dass es keinen Platz zum Golfen gibt

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")

Weniger golfen

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

Prüfung

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>