Jest rzeka i wilki i kury po jednej stronie rzeki. Mają tratwę i wszyscy muszą przejść na drugą stronę. Tratwa nie może jednak samodzielnie podróżować. Tratwa zatonie, jeśli będzie na niej więcej niż dwa zwierzęta. Żadne ze zwierząt nie chce się zmoczyć, ponieważ rzeka jest zimna i brudna. Żadne ze zwierząt nie może skakać ani latać nad rzeką. Ponadto, jeśli kurczaki są po jednej stronie, po tej stronie nie może być więcej wilków niż kurczaków po tej stronie - wówczas wilki zdecydują się je zjeść. Oznacza to, że nie możesz wziąć dwóch wilków na tratwie na bok z jednym kurczakiem.

Twoim zadaniem jest stworzenie programu / funkcji, która pobierze liczbę wilków i kurczaków (większą lub równą liczbie wilków) jako dane wejściowe i znajdzie najmniejszą liczbę ruchów tratwy przez rzekę. Jeśli zadanie nie jest możliwe, program / funkcja powinna wypisać / zwrócić pusty ciąg znaków. Następnie wydrukuje / zwróci jedną metodę, jak to zrobić:

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

Jak można wywnioskować, tratwa automatycznie przesunie się w naprzemiennych kierunkach (w lewo iw prawo, zaczynając od lewej do prawej, gdy pierwsze lub dwa zwierzęta przekroczą rzekę). To nie musi być wysyłane / zwracane. „W”, „C”, „CW”, „CC” lub „WW” na wyjściu można oddzielić co najmniej jednym z poniższych:

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

Alternatywnie możesz przechowywać wskazówki jako pozycje na liście (pusta lista oznacza brak rozwiązania).

Przypadki testowe (dane wyjściowe oddzielone przecinkami - dane wejściowe mają postać 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

Staraj się, aby Twój kod był jak najkrótszy.

Perl, 179 165 164 163 157 156 156 bajtów

Obejmuje +4 za -p

Daj wilkom, a następnie kurczętom STDIN

river.pl <<< "2 3"

Wysyła zawartość łodzi w wierszu. W tym przykładzie daje:

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

Działa jak pokazano, ale wymienić \xhhi \nich dosłowne wersji dostać twierdził wynik.

Prawdopodobnie zostanie pobity przez program, który rozwiązuje ogólny przypadek (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`

Dodaj do tego trywialne rozwiązania tylko dla wilków i tylko kurczaków oraz zakodowany specjalny przypadek dla 2 2i 3 3( 4 4i wyżej nie mają rozwiązania). Ale to byłby nudny program.

Wyjaśnienie

Bieżący stan pola jest przechowywany jako pojedynczy ciąg znaków składający się z:

• w dla wilka na brzegu z łodzią
• c dla kurczaka na brzegu z łodzią
• \x88(nieco odwrócony w) dla wilka na drugim brzegu
• \x9c(nieco odwrócony c) dla kurczaka na drugim brzegu
• Znak wskazujący bok łodzi na Pprawym brzegu \xaf(odwrócony bit P) na lewym brzegu (strona początkowa)
• nowa linia \n
• wszystkie ruchy, które zostały wykonane do tej pory, kończą się teraz znakiem nowej linii, np. coś podobnego WC\nW\nWC\nC\n(zwróć uwagę na Ws i Csą tu wielkie litery)

Tablica @Fbędzie zawierać wszystkie osiągalne stany. Jest inicjowany przez ciąg początkowywolves times "w", chickens times "c", \xaf \n

Następnie program zapętla @Fsię w pętli, dzięki czemu nowe stany również są przetwarzane. Następnie dla każdego elementu:

• Spójrz na część smyczkową po lewej stronie pierwszej, \nktóra reprezentuje bieżącą pozycję zwierząt i łodzi. Jeśli było to widoczne przed pominięciem$a{$`x/\n/}++
• Sprawdź, czy po każdej stronie są kurczaki i więcej wilków. Pomiń, jeśli takgrep(y/c//<y/w//&/c/,$_,~$_)
• Sprawdź, czy łódź jest na drugim końcu razem ze wszystkimi zwierzętami. Jeśli tak, mamy rozwiązanie. Przechowuj $\i przechowuj, ponieważ pierwsze znalezione rozwiązanie jest najkrótsze$\||=$' x/^\w*\n/
• W przeciwnym razie wypróbuj wszystkie sposoby wyboru 1 lub 2 zwierząt z boku łodzi. To są znaki ci w. (Zwierzęta po drugiej stronie nie będą pasować \w) /(\w?)(.*)(c|w)(.+)\n(?{code})^/. Następnie odwróć cały łańcuch przed \nwyjątkiem zwierząt, które zostały wybrane do łodzi push@F,$1.$3.~"$`$2$4\xf5". Dodaj wybrane zwierzęta do ruchów, przesuwając je górną częścią:uc"$'$1$3\n"

Proces selekcji zwierząt skutecznie tasuje reprezentującą je część strunową na wiele sposobów. Tak więc np. wcwcI wwccmogą zarówno reprezentować 2 wilki, jak i 2 kurczaki. Kontrola stanu $a{$`x/\n/}++bez rozróżnienia rozróżni te dwa o wiele więcej stanów, niż to konieczne, zostanie wygenerowanych i sprawdzonych. Dlatego programowi zabraknie pamięci i czasu, gdy tylko liczba różnych zwierząt będzie większa. Jest to nieco ograniczone przez fakt, że obecna wersja przestanie dodawać nowe stany po znalezieniu rozwiązania

JavaScript (ES6), 251 264 ... 244 240 bajtów

Pobiera liczbę wilków i kurczaków (w, c)i zwraca jedno z optymalnych rozwiązań lub undefinedjeśli nie ma rozwiązania.

(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

Sformatowane i skomentowane

Funkcja owijania:

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

Główna funkcja rekurencyjna:

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

Przypadki testowe

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*

Wypróbuj online

Wyjaśnienie:

Zasadniczo program wykonuje BFS i zapamiętuje każdy osiągnięty stan, aby uniknąć nieskończonych cykli. Stany robocze są reprezentowane jak [[Wl Cl] [Wr Cr] M1 M2… Mn] gdzie W = wilki, C = kurczaki, l = lewa strona, r = prawa strona, M = dotychczas wykonane ruchy (początkowo brak), a ruchy są jak „C”, „WC” lub „WW” itp. (praktycznie bardziej jak [„” „C”], [„W” „C”], [„WW” „”], ale jest taki sam podczas drukowania). Zapamiętane stany są reprezentowane jak [[Wl Cl] [Wr Cr] S], gdzie S jest bokiem łodzi (0 = lewy, 1 = prawy).

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 bajtów

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

Generuje coraz dłuższe łańcuchy (wolf count, chicken count)stanów dla lewego brzegu i zwraca pierwszy, który pasuje do wszystkich reguł.

Okazuje się, że takie podejście nie jest ani wydajne, ani bardzo zwięzłe, ale przynajmniej fajnie było pisać.
Nie sądzę, że nigdy wcześniej nie stosowałem meta-operatorów Z(zip) i X(cross), tak jak ZZ-i ZX*tutaj - trochę zaskoczony, że tak naprawdę działał.

(Nowe wiersze zostały właśnie dodane do celów wyświetlania i nie są częścią liczby bajtów).

JavaScript (ES6), 227 237

Zasadniczo wykonuje BFS i zapamiętuje każdy osiągnięty stan, aby uniknąć nieskończonych cykli. W przeciwieństwie do @ aditsu, nie sądzę, żeby było miejsce na golfa

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

Mniej golfa

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

Test

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>