Mengangkut serigala, kambing, dan kubis melintasi sungai tanpa efek pada Elixir

Ini sudah menjadi tradisi yang baik - semua hal menarik yang muncul di Haskell - diulangi di Elixir.

Tanda pertama adalah " Sekitar 20 baris untuk jumlah kata ", yang muncul sebagai alaverds pada " Mengalahkan C dengan dua puluh baris Haskell: menulis wc Anda " dari0xd34df00d - hari ini saya menemukan " Mengangkut serigala, kambing, dan kubis menyeberangi sungai dengan efek Haskell " dariiokasimov dan juga tidak bisa menahan.

Jadi, penuhi: enumerasi paralel asinkron penuh malas versus efek aljabar.

---

Pernyataan masalah (disalin dengan penuh syukur dari catatan asli):

Suatu ketika seorang petani perlu mengangkut serigala, kambing, dan kubis menyeberangi sungai. Petani memiliki perahu di mana, selain petani itu sendiri, hanya satu objek yang dapat ditampung - serigala, atau kambing, atau kubis. Jika petani meninggalkan serigala tanpa pengawasan, serigala akan memakan kambing; jika seorang petani meninggalkan kambing dengan kubis tanpa pengawasan, kambing akan memakan kubis tersebut.

: « », -, (+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 .

Ada satu peringatan: beberapa solusi akan dikembalikan sebagai daftar tetap karena Stream.flat_map/2. Tapi tidak apa-apa: setiap solusi diakhiri dengan satu set kosong, jadi kita dapat dengan mudah memecah lembaran datar ini menjadi beberapa bagian. Semua kode keluaran yang indah (yang hampir sama dengan logika) tidak akan saya berikan di sini, berikut adalah intisari bagi para penggemar.

---

Selamat transportasi pertanian!