Transporte de lobo, cabra e repolho através do rio sem efeitos no Elixir

Já está se tornando uma boa tradição - tudo de interessante que apareceu em Haskell é repetido em Elixir.

O primeiro sinal foi " Cerca de 20 linhas para contagem de palavras ", que apareceu como alaverds em " Derrotando C com vinte linhas de Haskell: escrevendo seu wc " de0xd34df00d - hoje me deparei com " Transportando lobo, cabra e repolho pelo rio com efeitos em Haskell " deiokasimov e também não pude resistir.

Então, conheça: preguiçoso completo assíncrono paralelo força bruta versus efeitos algébricos.

---

Declaração do problema (copiada com gratidão da nota original):

Certa vez, um camponês precisava transportar um lobo, uma cabra e um repolho para o outro lado do rio. O camponês tem um barco no qual, além do próprio camponês, cabe apenas um objeto - um lobo, ou uma cabra, ou um repolho. Se o camponês deixar o lobo com a cabra sem vigilância, o lobo comerá a cabra; se um camponês deixa uma cabra com repolho sem vigilância, a cabra comerá o repolho.

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

Há uma nuance aqui: várias soluções retornarão como uma lista plana devido a Stream.flat_map/2. Mas tudo bem: toda solução termina com um conjunto vazio, então podemos facilmente quebrar essa folha plana em pedaços. Todo o código da bela saída (que é quase tanto quanto a lógica) não vou dar aqui, aqui está um resumo para os entusiastas.

---

Feliz transporte agrícola!