Ada sungai dan ada serigala dan ayam di satu sisi sungai. Mereka memiliki rakit dan mereka semua harus ke sisi lain. Namun, rakit tidak dapat melakukan perjalanan sendiri. Rakit akan tenggelam jika ada lebih dari dua binatang di dalamnya. Tidak ada hewan yang mau basah karena sungai itu dingin dan kotor. Tidak ada hewan yang bisa melompat atau terbang di atas sungai. Juga, jika ada ayam di satu sisi, tidak mungkin ada lebih banyak serigala di sisi itu daripada ada ayam di sisi itu - serigala kemudian akan memutuskan untuk memakan ayam. Ini berarti bahwa Anda tidak dapat membawa dua serigala di rakit ke sisi dengan satu ayam.

Tugas Anda adalah membuat program / fungsi yang mengambil sejumlah serigala dan sejumlah ayam (lebih besar atau sama dengan jumlah serigala) sebagai input dan menemukan berapa kali rakit harus bergerak menyeberangi sungai. Jika tugas tidak memungkinkan, program / fungsi harus menampilkan / mengembalikan string kosong. Kemudian akan mencetak / mengembalikan satu metode tentang bagaimana hal ini dilakukan dengan cara berikut:

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

Seperti yang dapat Anda simpulkan, rakit akan secara otomatis bergerak ke arah yang bergantian (kiri dan kanan, mulai dari kiri ke kanan ketika satu atau dua hewan pertama menyeberangi sungai). Ini tidak perlu di-output / dikembalikan. 'W', 'C', 'CW', 'CC' atau 'WW' dalam output dapat dipisahkan oleh setidaknya satu dari yang berikut:

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

Atau, Anda dapat menyimpan arah sebagai item dalam daftar (daftar kosong berarti tidak ada solusi).

Test case (keluaran dipisahkan dengan koma - input berbentuk 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

Cobalah untuk membuat kode Anda sesingkat mungkin.

Perl, 179 165 164 163 157 156 byte

Termasuk +4 untuk -p

Berikan serigala diikuti oleh ayam di STDIN

river.pl <<< "2 3"

Output isi perahu per baris. Untuk contoh ini memberi:

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

Bekerja seperti yang ditunjukkan, tetapi ganti \xhhdan\n dengan versi literalnya untuk mendapatkan skor yang diklaim.

Ini mungkin akan dikalahkan oleh program yang memecahkan kasus umum (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`

Tambahkan ke bahwa solusi sepele hanya untuk serigala dan hanya ayam dan kasus khusus hardcod untuk 2 2dan 3 3(4 4 dan lebih tinggi tidak punya solusi). Tapi itu akan menjadi program yang membosankan.

Penjelasan

Keadaan saat bidang disimpan sebagai string tunggal yang terdiri dari:

• w untuk seekor serigala di tepi sungai dengan perahu
• c untuk ayam di bank dengan perahu
• \x88(sedikit terbalik w) untuk serigala di bank lain
• \x9c(agak terbalik c) untuk ayam di bank lain
• Karakter yang menunjukkan sisi perahu Puntuk sisi kanan, \xaf(sedikit terbalik P) untuk sisi kiri (sisi awal)
• baris baru \n
• semua gerakan yang telah dilakukan hingga sekarang diakhiri dengan baris baru, misalnya sesuatu seperti WC\nW\nWC\nC\n(perhatikan huruf Ws dan Cada dalam huruf besar di sini)

Array @Fakan berisi semua status yang dapat dijangkau. Ini diinisialisasi oleh string awalwolves times "w", chickens times "c", \xaf \n

Program kemudian @Fmengulang yang akan diperpanjang selama perulangan sehingga negara-negara baru juga diproses. Untuk setiap elemen yang dilakukannya:

• Lihatlah bagian senar kiri yang pertama \nyang mewakili posisi hewan dan perahu saat ini. Jika itu sudah terlihat sebelum lewati$a{$`x/\n/}++
• Periksa apakah ada ayam bersama dengan lebih banyak serigala di sisi mana pun. Lewati jika demikiangrep(y/c//<y/w//&/c/,$_,~$_)
• Periksa apakah perahunya jauh bersama dengan semua binatang. Jika demikian kita punya solusinya. Simpan itu $\dan simpan itu sejak solusi pertama ditemukan adalah yang terpendek$\||=$' x/^\w*\n/
• Kalau tidak, cobalah semua cara memilih 1 atau 2 hewan di samping dengan perahu. Ini adalah cdan wkarakter. (Hewan-hewan di sisi lain tidak akan cocok \w) /(\w?)(.*)(c|w)(.+)\n(?{code})^/. Kemudian sedikit membalikkan seluruh tali sebelum \nkecuali binatang yang dipilih untuk kapal push@F,$1.$3.~"$`$2$4\xf5". Tambahkan hewan-hewan yang dipilih ke gerakan dengan menambahkan mereka:uc"$'$1$3\n"

Proses pemilihan hewan secara efektif mengocok bagian tali yang mewakili mereka dalam banyak cara. Jadi mis wcwcdan wwcckeduanya bisa mewakili 2 serigala dan 2 ekor ayam. Pemeriksaan status $a{$`x/\n/}++akan membedakan dua keadaan ini secara tidak wajar, sehingga lebih banyak keadaan dari yang diperlukan akan dihasilkan dan diperiksa. Oleh karena itu program ini akan kehabisan memori dan waktu segera setelah jumlah hewan yang berbeda semakin besar. Ini diredakan hanya sedikit oleh fakta bahwa versi saat ini akan berhenti menambahkan status baru setelah solusi ditemukan

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

Mengambil jumlah serigala dan ayam (w, c)dan mengembalikan salah satu solusi optimal, atau undefinedjika tidak ada solusi.

(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

Diformat dan dikomentari

Fungsi pembungkus:

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

Fungsi rekursif utama:

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

Uji kasus

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*

Cobalah online

Penjelasan:

Pada dasarnya program ini melakukan BFS dan mengingat setiap keadaan yang dicapai untuk menghindari siklus tak terbatas. Status kerja diwakili seperti [[Wl Cl] [Wr Cr] M1 M2… Mn] di mana W = serigala, C = ayam, l = sisi kiri, r = sisi kanan, M = bergerak sejauh ini (awalnya tidak ada), dan gerakannya seperti "C", "WC" atau "WW" dll (praktis lebih seperti ["" "C"], ["W" "C"], ["WW" ""]], tetapi itu sama saja saat mencetak). Status yang diingat diwakili seperti [[Wl Cl] [Wr Cr] S] di mana S adalah sisi dengan perahu (0 = kiri, 1 = kanan).

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 byte

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

Menghasilkan rantai yang semakin panjang (wolf count, chicken count) negara yang untuk bank kiri, dan mengembalikan yang pertama yang cocok dengan semua aturan.

Ternyata pendekatan ini tidak efisien atau terlalu ringkas, tetapi setidaknya itu menyenangkan untuk ditulis.
Saya tidak berpikir saya pernah menumpuk meta-operator Z(zip) dan X(cross) sebelumnya, sepertiZZ- dan di ZX*sini - agak terkejut bahwa ini benar-benar berhasil.

(Baris baru ditambahkan untuk tujuan tampilan, dan bukan bagian dari jumlah byte.)

JavaScript (ES6), 227 237

Pada dasarnya ia melakukan BFS dan mengingat setiap negara yang dicapai untuk menghindari siklus tak terbatas. Tidak seperti @ aditsu, saya tidak berpikir ada ruang untuk bermain 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")

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

Uji

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>