Wolf + Goat + Cabbage

wgc.ex

defmodule WolfGoatCabbage.State do
  defstruct banks: %{true => [], false => []}, ltr: true, history: []
end

defmodule WolfGoatCabbage.Subj do
  defstruct me: nil, incompatible: []
end

defmodule WolfGoatCabbage do
  alias WolfGoatCabbage.{State, Subj}
  require Integer

  @goat %Subj{me: "🐐", incompatible: ["🥦", "🐺"]}
  @wolf %Subj{me: "🐺", incompatible: ["🐐"]}
  @cabb %Subj{me: "🥦", incompatible: ["🐐"]}

  @subjs [@goat, @wolf, @cabb]

  def main do
    direction = &if Integer.is_odd(&1), do: "➡️", else: "⬅️"

    results =
      go()
      |> Stream.chunk_by(&(MapSet.new() == &1))
      |> Stream.chunk_every(2)
      |> Stream.map(&List.flatten/1)
      |> Stream.map(fn list ->
        list
        |> Stream.with_index()
        |> Enum.reduce(%{prev: [], moves: []}, fn
          {whos, idx}, acc when is_integer(whos) ->
            %{acc | moves: [direction.(idx) <> " ⛵" | acc.moves]}

          {whos, idx}, acc ->
            curr = Enum.map(whos, & &1.me)

            case {acc.prev -- curr, curr -- acc.prev} do
              {[who], _} ->
                %{acc | prev: curr, moves: [direction.(idx) <> " " <> who | acc.moves]}

              {_, [who]} ->
                %{acc | prev: curr, moves: [direction.(idx) <> " " <> who | acc.moves]}

              {_, _} = foo ->
                %{acc | prev: curr}
            end
        end)
        |> Map.get(:moves)
        |> Enum.reverse()
        |> Enum.join(" :: ")
      end)
      |> Enum.to_list()
  end

  @initial %State{
    banks: %{true => @subjs, false => []},
    history: [MapSet.new(@subjs)]
  }

  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

  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

  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

  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
end