狼和鸡

Question

河的一边有一条河，还有狼和鸡。他们有一个木筏，他们都需要到另一边去。然而，木筏不能独自航行。如果船上有两只以上的动物，木筏就会沉下去。没有一只动物想弄湿，因为河水又冷又脏。没有一种动物能跳过或飞过这条河。另外，如果一边有鸡，那一边的狼不可能比那边的鸡多--然后狼就会决定吃鸡。这意味着你不能用一只鸡把两只狼放在木筏上。

您的任务是制作一个程序/函数，以若干狼和若干只鸡(大于或等于狼的数量)作为输入，并找到木筏在河上移动的最小次数。如果任务不可能，程序/函数应该输出/返回一个空字符串。然后，它将以下列方式打印/返回一个关于如何完成此操作的方法：

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

正如你可以推断的，木筏将自动向交替的方向移动(从左到右，从左到右，当第一、两只动物过河时，从左到右)。这不需要输出/返回。输出中的“w”、“C”、“CW”、“CC”或“WW”可以至少用下列一种分隔：

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

或者，您可以将说明存储为列表中的项(空列表意味着没有解决方案)。

测试用例(以逗号分隔的输出--输入形式为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

尽量使您的代码尽可能短于字节。

Answer 1

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*

S*&input=[3 3]">在网上试试

解释：

基本上，为了避免无限循环，程序会执行BFS并记住它所达到的每一个状态。工作状态表示为[Wl Cl M1 M2…]。W=狼，C=鸡，L=左边，r=右边，M=目前为止所做的动作(最初没有)，这些动作类似于"C"，"WC“或"WW”等等(实际上更像“C”，“W”“C”，“WW”，但印刷时是一样的)。记忆中的状态就像[Wl Cl S]，S和船在一起(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