Transport von Wolf, Ziege und Kohl über den Fluss ohne Auswirkungen auf Elixier

Es wird bereits zu einer guten Tradition - alles Interessante, was auf Haskell erschienen ist -, auf Elixir wiederholt zu werden.

Das erste Zeichen war " Ungefähr 20 Zeilen für das Zählen von Wörtern ", das als Alaverds auf " Besiege C mit zwanzig Zeilen von Haskell: Schreiben Sie Ihr eigenes WC " von erschien0xd34df00d - Heute bin ich auf " Transport eines Wolfes, einer Ziege und eines Kohls über den Fluss mit Auswirkungen in Haskell " von gestoßeniokasimov und konnte auch nicht widerstehen.

Treffen Sie sich also: faul voll asynchrone parallele Brute Force versus algebraische Effekte.

---

Problemstellung (dankbar aus der Originalnotiz kopiert):

Einmal musste ein Bauer einen Wolf, eine Ziege und einen Kohl über den Fluss transportieren. Der Bauer hat ein Boot, in das neben dem Bauern selbst nur ein Gegenstand passen kann - entweder ein Wolf, eine Ziege oder ein Kohl. Wenn der Bauer den Wolf mit der Ziege unbeaufsichtigt lässt, frisst der Wolf die Ziege; Wenn ein Bauer eine Ziege mit Kohl unbeaufsichtigt lässt, frisst die Ziege den Kohl.

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

Hier gibt es eine Nuance: Mehrere Lösungen werden aufgrund von als flache Liste zurückgegeben Stream.flat_map/2. Aber das ist in Ordnung: Jede Lösung endet mit einem leeren Satz, sodass wir dieses flache Blatt leicht in Stücke zerbrechen können. All den schönen Ausgabecode (der fast so viel wie Logik ist) werde ich hier nicht geben, hier ist ein Kern für Enthusiasten.

---

Glücklicher landwirtschaftlicher Transport!