Transporting wolf, goat and cabbage across the river with no effects on Elixir

It is already becoming a good tradition - everything interesting that has appeared on Haskell - to be repeated on Elixir.

The first sign was " About 20 lines for word count ", which appeared as alaverds on " Defeating C with twenty lines of Haskell: writing your wc " from0xd34df00d - today I came across " Transporting a wolf, goat and cabbage across the river with effects in Haskell " fromiokasimov and also could not resist.

So, meet: lazy full asynchronous parallel brute-force versus algebraic effects.

---

Problem statement (gratefully copied from the original note):

Once a peasant needed to transport a wolf, a goat and a cabbage across the river. The peasant has a boat in which, besides the peasant himself, only one object can fit - either a wolf, or a goat, or a cabbage. If the peasant leaves the wolf with the goat unattended, the wolf will eat the goat; if a peasant leaves a goat with cabbage unattended, the goat will eat the cabbage.

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

There is one caveat: several solutions will return as a flat list due to Stream.flat_map/2. But that's okay: every solution ends with an empty set, so we can easily break this flat sheet into chunks. All the beautiful output code (which is almost as much as logic) I will not give here, here is a gist for enthusiasts.

---

Happy agricultural transportation!