defmodule WolfGoatCabbage.State do
  @moduledoc """
  Текущее состояние нашей микровселенной.
  Берега (`true` → исходный, левый), `ltr` — маркер направления, история поездок.
  """
  defstruct banks: %{true => [], false => []}, ltr: true, history: []
end
defmodule WolfGoatCabbage.Subj do
  @moduledoc """
  Единица живности, с кем конфликтует.
  """
  defstruct [:me, :incompatible]
end

@spec safe?(
  banks :: %{true => [%Subj{}], false => [%Subj{}]},
  ltr :: boolean()
) :: boolean()
defp safe?(banks, ltr) do
  subjs =
    banks[ltr]
    |> Enum.map(& &1.me)
    |> MapSet.new()
  incompatibles =
    banks[ltr]
    |> Enum.flat_map(& &1.incompatible)
    |> MapSet.new()
  MapSet.disjoint?(subjs, incompatibles)
end

@spec move(%State{}, nil | %Subj{}) :: %State{} | false
@doc """
Если в лодке никого, достаточно проверить, что мы не оставляем берег
в уже виденном состоянии, и напрямую вернуть новое состояние.
"""
defp move(%State{ltr: ltr, banks: banks, history: history} = state, nil) do
  !(ltr || Enum.member?(history, MapSet.new(banks[ltr]))) &&
    %State{state | ltr: not ltr, history: [length(history) | history]}
end
@doc """
Когда в лодке блеют, тявкают, или выразительно хлопают листьями —
все немного сложнее.
Мы переносим живность с одного берега на другой, удостоверяемся, что
ходка безопасна (на покидаемом берегу не возникнет внеплановый ужин) и —
что мы еще не видели такого состояния. Если все критерии выполнены —
возвращаем новое состояние, если нет — терминирующий `false`.
"""
defp move(%State{banks: banks, ltr: ltr, history: history}, who) do
  with banks <- %{ltr => banks[ltr] -- [who], not ltr => [who | banks[not ltr]]},
        true <- safe?(banks, ltr),
        true <- not Enum.member?(history, MapSet.new(banks[true])) do
    %State{
      banks: banks,
      ltr: not ltr,
      history: [MapSet.new(banks[true]) | 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 | some]
      |> Task.async_stream(&move(state, &1))
      |> Stream.map(&elem(&1, 1)) # лениво
      |> Stream.filter(& &1)      # лениво
      |> Stream.flat_map(&go/1)   # лениво и рекурсивно
  end
end