Transporte de lobos, cabras y repollos a través del río sin efectos en Elixir

Ya se está convirtiendo en una buena tradición, todo lo interesante que ha aparecido en Haskell, que se repetirá en Elixir.

El primer letrero era " Aproximadamente 20 líneas para el recuento de palabras ", que aparecía como alaverds en " Derrotando a C con veinte líneas de Haskell: escribiendo tu wc " de0xd34df00d - hoy me encontré con " Transportando un lobo, una cabra y un repollo a través del río con efectos Haskell " deiokasimov y además no pude resistir.

Entonces, conozca: fuerza bruta paralela asincrónica completa perezosa versus efectos algebraicos.

---

Enunciado del problema (copiado con gratitud de la nota original):

Una vez, un campesino necesitaba transportar un lobo, una cabra y un repollo a través del río. El campesino tiene un bote en el que, además del campesino mismo, solo cabe un objeto: un lobo, una cabra o un repollo. Si el campesino deja desatendido al lobo con la cabra, el lobo se comerá la cabra; si un campesino deja desatendida una cabra con repollo, la cabra se comerá el repollo.

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

Aquí hay un matiz: varias soluciones regresarán como una lista plana debido a Stream.flat_map/2. Pero está bien: cada solución termina con un juego vacío, por lo que podemos romper fácilmente esta hoja plana en trozos. Todo el hermoso código de salida (que es casi tanto como lógica) no lo daré aquí, aquí hay una esencia para los entusiastas.

---

¡Feliz transporte agrícola!