نقل الذئب والماعز والملفوف عبر النهر دون أي تأثير على الإكسير

لقد أصبح بالفعل تقليدًا جيدًا - كل شيء مثير للاهتمام ظهر على Haskell - يتكرر على الإكسير.

العلامة الأولى كانت " حوالي 20 سطراً لعد الكلمات " ، والتي ظهرت على شكل حرف " هزيمة C بعشرين سطراً من هاسكل: كتابة مرحاضك الخاص " من0xd34df00d - صادفت اليوم عبارة " نقل الذئب والماعز والملفوف عبر النهر مع التأثيرات في هاسكل " منيوكاسيموف وأيضا لا يمكن أن تقاوم.

لذا ، قابل: القوة الغاشمة المتوازية غير المتزامنة الكاملة البطيئة مقابل التأثيرات الجبرية.

---

بيان المشكلة (تم نسخه بامتنان من الملاحظة الأصلية):

كان الفلاح في يوم من الأيام بحاجة إلى نقل ذئب وماعز وملفوف عبر النهر. يمتلك الفلاح قاربًا ، إلى جانب الفلاح نفسه ، يمكن أن يصلح فيه شيء واحد فقط - إما ذئب أو ماعز أو ملفوف. إذا ترك الفلاح الذئب والماعز دون رقابة ، يأكل الذئب الماعز ؛ إذا ترك الفلاح عنزة مع ملفوف دون رقابة ، فإن الماعز تأكل الملفوف.

: « », -, (+1 ). ,  — , . , , . , ,  —  .

, .

defmodule WolfGoatCabbage.State do
  @moduledoc """
     .

   (`true` → , ), `ltr` —  ,  .
  """
  defstruct banks: %{true => [], false => []}, ltr: true, history: []
end

defmodule WolfGoatCabbage.Subj do
  @moduledoc """
   ,   .
  """
  defstruct [:me, :incompatible]
end

XIX , .

, .

@spec safe?(bank :: [%Subj{}]) :: boolean()
defp safe?(bank) do
  subjs =
    bank
    |> Enum.map(& &1.me)
    |> MapSet.new()
  incompatibles =
    bank
    |> Enum.flat_map(& &1.incompatible)
    |> MapSet.new()

  MapSet.disjoint?(subjs, incompatibles)
end

, , , , , . .

()

, , (nil «»).

@spec move(%State{}, nil | %Subj{}) :: %State{} | false
@doc """
   ,  ,      
   ,     .
"""
defp move(%State{ltr: ltr, banks: banks, history: history} = state, nil) do
  with true <- not ltr, true <- safe?(banks[ltr]) do
    %State{state | ltr: not ltr, history: [length(history) | history]}
  end
end

@doc """
   , ,     — 
  .

       , , 
  (      )  —
      .     —
  ,   —  `false`.
"""
defp move(%State{banks: banks, ltr: ltr, history: history}, who) do
  with true <- who in banks[ltr],
        banks = %{ltr => banks[ltr] -- [who], not ltr => [who | banks[not ltr]]},
        bank_state = MapSet.new(banks[true]),
        true <- safe?(banks[ltr]),
        true <- not Enum.member?(history, bank_state) do
    %State{
      banks: banks,
      ltr: not ltr,
      history: [bank_state | history]
    }
  end
end

()

, , : . .

@initial %State{
            banks: %{true => @subjs, false => []},
            history: [MapSet.new(@subjs)]
         }

@spec go(%State{}) :: [MapSet.t()]
def go(state \\ @initial) do
  case state.banks[true] do
    [] -> # !
      Enum.reverse(state.history)

    _some ->
      [nil | @subjs]
      |> Task.async_stream(&move(state, &1))
      |> Stream.map(&elem(&1, 1)) # 
      |> Stream.filter(& &1)      # 
      |> Stream.flat_map(&go/1)   #   
  end
end

Stream, , , . , ?

: . main/0 .

هناك فارق بسيط واحد هنا: ستعود العديد من الحلول كقائمة ثابتة بسبب Stream.flat_map/2. لكن هذا جيد: ينتهي كل حل بمجموعة فارغة ، لذلك يمكننا بسهولة تقسيم هذه الورقة المسطحة إلى قطع. كل كود الإخراج الجميل (والذي هو تقريبًا مثل المنطق) لن أعطيها هنا ، هنا جوهر للمتحمسين .

---

نقل زراعي سعيد!