Русский
Русский
English
Статистика
Реклама

Recovery mode Перевозим волка, козу и капусту через реку с эффектами на Elixir

Становится уже доброй традицией воспроизведение всего любопытного, что появилось на Хаскелеповторять на Эликсире.


Первой ласточкой были Примерно 20 строк для подсчета слов, появившиеся как алаверды на Побеждая C двадцатью строками Haskell: пишем свой wc от 0xd34df00dсегодня же я наткнулся на Перевозим волка, козу и капусту через реку с эффектами на Haskell от iokasimov и тоже не устоял.


Итак, встречайте: ленивый полный асинхронный параллельный перебор против алгебраических эффектов.




Постановка задачи (благодарно скопипащщено из оригинальной заметки):


Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.

Волк Коза Капуста


Мы будем действовать следующим образом: начнем с состояния все на левом берегу, и на каждом шаге будем запускать максимум столько эрланг-процессов, сколько на этом берегу живности (+1 для ходки порожняком). При этом мы всегда будем проверять, что остающаяся на берегу живность друг друга не перегрызет, и эти ветки будем отсекать сразу. Также мы будем хранить историю, и отсекать циклические ветки, возвращающие нас в уже виденное состояние. Это, кстати, не избыточные данныеисторию поездок мы будем возвращать в качестве результата.


Итак, начнем с объявлений.


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

Поскольку парсер хабра все еще живет в XIX веке, вот вам картинка с начальными значениями.


Начальные значения


Что ж, можно и перейти к собственно написанию кода.


Проверка целостности


@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

Построили множество тех, кто остается, множество тех, с кем они несовместимы, и удостоверились, что пересечений нет. Пока все тривиально.


Ход (лодкой)


Условия для порожней ходки, и ходки с живностью довольно сильно различаются, поэтому удобно их обработку разбить на две функции (nil отлично подходит в качестве никого).


@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]    }  endend

Собственно партия (многоходовочка)


Осталось, собственно, написать основную часть: рекурсивный запуск процессов. Нет ничего проще.


@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)   # лениво и рекурсивно  endend

Спасибо Stream, весь этот код ленив, сиречь выполняться не будет, пока не пнут. Мы же тут хаскель пародируем, помните?


Проверяем


Тесты я недолюбливаю и считаю пустой тратой времени: гораздо проще сразу писать рабочий код. Поэтому я просто создам функцию main/0 и выведу результаты на экран.


Тут есть один нюанс: несколько решений вернутся плоским списком из-за Stream.flat_map/2. Но это не страшно: каждое решение заканчивается пустым множеством, поэтому мы легко разобьем этот плоский лист на чанки. Весь код красивого вывода (которого чуть ли не столько же, сколько логики) я тут приводить не буду, вот gist для энтузиастов.




Удачной сельскохозяйственной перевозки!

Источник: habr.com
К списку статей
Опубликовано: 03.08.2020 22:10:54
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Алгоритмы

Функциональное программирование

Elixir/phoenix

Otp

Parallel computing

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2023, personeltest.ru