Skip to content

Instantly share code, notes, and snippets.

@am-kantox
Last active April 19, 2023 19:50
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save am-kantox/d559895d7297d1a3f0d96eba4cdda5b3 to your computer and use it in GitHub Desktop.
Save am-kantox/d559895d7297d1a3f0d96eba4cdda5b3 to your computer and use it in GitHub Desktop.
Wolf + Goat + Cabbage
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment