Transporter le loup, la chèvre et le chou à travers la rivière sans effet sur l'élixir

Cela devient déjà une bonne tradition - tout ce qui est intéressant qui est apparu sur Haskell - se répète sur Elixir.

Le premier signe était " Environ 20 lignes pour compter les mots ", qui apparaissait comme des alaverds sur " Vaincre C avec vingt lignes de Haskell: écrire votre wc " de0xd34df00d - aujourd'hui, je suis tombé sur " Transporter le loup, la chèvre et le chou à travers la rivière avec des effets à Haskell " deIokasimov et ne pouvait pas non plus résister.

Alors, rencontrez: force brute parallèle asynchrone complète paresseuse contre effets algébriques.

---

Énoncé du problème (copié avec gratitude de la note originale):

Autrefois, un paysan avait besoin de transporter un loup, une chèvre et un chou à travers la rivière. Le paysan a un bateau dans lequel, à part le paysan lui-même, un seul objet peut tenir - soit un loup, ou une chèvre, ou un chou. Si le paysan laisse le loup avec la chèvre sans surveillance, le loup mangera la chèvre; si un paysan laisse une chèvre avec du chou sans surveillance, la chèvre mangera le chou.

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

Il y a une nuance ici: plusieurs solutions reviendront sous forme de liste plate en raison de Stream.flat_map/2. Mais ce n'est pas grave: chaque solution se termine par un ensemble vide, nous pouvons donc facilement diviser cette feuille plate en morceaux. Tout le beau code de sortie (qui est presque autant que logique) que je ne donnerai pas ici, voici un résumé pour les passionnés.

---

Bon transport agricole!