| Bytes | Lang | Time | Link |
|---|---|---|---|
| 397 | Python3 | 241018T190844Z | Ajax1234 |
| 227 | JavaScript ES6 | 170121T220957Z | edc65 |
| 133 | CJam | 170121T084448Z | aditsu q |
| 268 | Perl 6 | 170121T174419Z | smls |
| 240 | JavaScript ES6 | 161021T073755Z | Arnauld |
| 156 | Perl | 161021T155037Z | Ton Hosp |
Python3, 397 bytes
def f(w,c):
q,s=[(M:=[[w,c],[0,0]],0,[])],[(M,0)]
for m,d,p in q:
if[0,0]==m[0]:return p
j,k=d,(d+1)%2
Q,S=[(0,0)],[]
for w,c in Q:
if w+c:S+=[(w,c)]
if w+c<2:Q+=[(w+1,c),(w,c+1)]
for w,c in S:
M=eval(str(m))
if m[j][0]-w>=0 and m[j][1]-c>=0 and M[k][0]+w<=M[k][1]+c:
M[j][0]-=w;M[j][1]-=c;M[k][0]+=w;M[k][1]+=c
if(M,k)not in s:q+=[(M,k,p+['W'*w+'C'*c])];s+=[(M,k)]
JavaScript (ES6), 227 237
Basically it does a BFS and remembers every state it reached in order to avoid infinite cycles. Unlike @aditsu's, I don't think there's any room for golfing
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")
Less golfed
(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>
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*
Explanation:
Basically the program does a BFS and remembers every state it reached in order to avoid infinite cycles. The working states are represented like [[Wl Cl] [Wr Cr] M1 M2 … Mn] where W = wolves, C = chickens, l = left side, r = right side, M = moves made so far (initially none), and the moves are like "C", "WC" or "WW" etc (practically more like ["" "C"], ["W" "C"], ["WW" ""], but it's the same when printing). The remembered states are represented like [[Wl Cl] [Wr Cr] S] where S is the side with the boat (0=left, 1=right).
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)})
.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]//()}
Generates increasingly longer chains of (wolf count, chicken count) states for the left bank, and returns the first one that matches all the rules.
Turns out this approach is neither efficient nor very concise, but at least it was fun to write.
I don't think I've never stacked the Z (zip) and X (cross) meta-operators before, like the ZZ- and ZX* here - kinda surprised that actually worked.
(The newlines are just added for display purposes, and aren't part of the byte count.)
JavaScript (ES6), 251 264 ... 244 240 bytes
Takes the number of wolves and chickens (w, c) and returns one of the optimal solutions, or undefined if there's no 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
Formatted and commented
Wrapper function:
( // 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
Main recursive function:
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
Test cases
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));
Perl, 179 165 164 163 157 156 bytes
Includes +4 for -p
Give wolves followed by chickens on STDIN
river.pl <<< "2 3"
Outputs the boat contents per line. For this example it gives:
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}{
Works as shown, but replace \xhh and \n by their literal versions to get the claimed score.
This will probably be beaten by a program that solves the general case (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`
Add to that the trivial solutions for only wolves and only chickens and a hardcoded special case for 2 2 and 3 3 (4 4 and higher have no solution). But that would be a boring program.
Explanation
The current state of the field is stored as a single string consisting of:
wfor a wolf on the bank with the boatcfor a chicken on the bank with the boat\x88(bit reversedw) for a wolf on the other bank\x9c(bit reversedc) for a chicken on the other bank- A character indicating the side the boat is on
Pfor the right bank,\xaf(bit reversedP) for the left bank (starting side) - a newline
\n - all the moves that have been done upto now terminated with newlines, e.g. something like
WC\nW\nWC\nC\n(notice theWs andCare in uppercase here)
The array @F will contain all reachable states. It is initialised by the starting string wolves times "w", chickens times "c", \xaf \n
The program then loops over @F which will get extended during the looping so new states get processed too. For every element it then does:
- Look at the string part left of the first
\nwhich represents the current position of the animals and the boat. If that has been seen before skip$a{$`x/\n/}++ - Check if there are chickens together with more wolves on any side. Skip if so
grep(y/c//<y/w//&/c/,$_,~$_) - Check if the boat is the far side together with all animals. If so we have a solution. Store that in
$\and keep that since the first solution found is the shortest$\||=$' x/^\w*\n/ - Otherwise try all ways of selecting 1 or 2 animals on the side with the boat. These are the
candwcharacters. (The animals at the other side won't match\w)/(\w?)(.*)(c|w)(.+)\n(?{code})^/. Then bit reverse the whole string before the\nexcept the animals that were selected for the boatpush@F,$1.$3.~"$`$2$4\xf5". Add the selected animals to the moves by uppercasing them:uc"$'$1$3\n"
The animal selection process effectively shuffles the string part representing them in many ways. So e.g. wcwc and wwcc can both get to represent 2 wolves and 2 chickens. The state check $a{$`x/\n/}++ will unnessarily distinguish these two so many more states than necessary will be generated and checked. Therefore the program will run out of memory and time as soon as the number of different animals gets larger. This is mitigated only a bit by the fact that the current version will stop adding new states once a solution is found