🛸 🍈 🐅 エリクサーに影響を与えずに、オオカミ、ヤギ、キャベツを川を渡って輸送する 🍚 👩🏽‍🔧 🔏

それはすでに良い伝統になりつつあります-ハスケルに現れたすべての興味深いものはエリクサーで繰り返されます。

最初の兆候は、「だっワードカウントのため20行についてのalaverdsとして登場し、」「ハスケルの20行で破っC：自分のWCを書く」から0xd34df00d -今日は、「出会ったHaskellでは効果で川を渡っオオカミ、ヤギとキャベツの輸送から」イオカシモフまた、抵抗できませんでした。

だから、満たしてください：怠惰な完全非同期並列列挙対代数的効果。

問題の説明（元のメモからありがたいことにコピー）：

かつて農民はオオカミ、ヤギ、キャベツを川を渡って運ぶ必要がありました。農民は、農民自身のほかに、オオカミ、ヤギ、またはキャベツのいずれか1つのオブジェクトのみが収まるボートを持っています。農民がヤギと一緒にオオカミを離れると、オオカミはヤギを食べます。農民がキャベツを持ってヤギを放置すると、ヤギはキャベツを食べます。

オオカミ→ヤギ→キャベツ

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

ここには1つのニュアンスがあります。いくつかのソリューションは、のためにフラットリストとして返されStream.flat_map/2ます。しかし、それは問題ありません。すべてのソリューションは空のセットで終わるため、このフラットシートを簡単にチャンクに分割できます。ここでは説明しませんが、すべての美しい出力コード（ロジックとほぼ同じです）は、愛好家のための要点です。

オオカミ→ヤギ→キャベツ

幸せな農業輸送！

エリクサーに影響を与えずに、オオカミ、ヤギ、キャベツを川を渡って輸送する

()

()

More articles: