Оглавление

В прошлый раз мы работали с деревом валют, чтобы построить цепочку обмена. Мы нашли решение задачи, но упомянули, что в особых случаях дерево может получиться бесконечным. Объясним, как это возможно. Для этого вспомним, как zip/next обходит дерево.

Алгоритм называется depth first search или обход в глубину. При таком обходе код стремится в первую очередь вниз, а уже потом — в сторону (в нашем случае вправо). В этом легко убедиться, если разложить данные на части с помощью зиппера:

(->> [1 [2 [3] 4] 5]
     zip/vector-zip
     iter-zip
     (map zip/node)
     (map println))

;; 1
;; [2 [3] 4]
;; 2
;; [3]
;; 3
;; 4
;; 5

Цифра 3, идущая перед 4, говорит о том, что зиппер следует вглубь (внутрь вектора [3]) и только потом право.

Ещё более интересен случай с деревом, где у каждого узла потомки [1 2 3]. При обходе такого дерева зиппер будет стремиться вниз, каждый раз спускаясь в очередной вектор [1 2 3] и становясь на единицу. Покажем это на схеме:

(def zip-123
  (zip/zipper any?
              (constantly (seq [1 2 3]))
              nil
              1))
                       ┌───────┐
                       │[1 2 3]│
                       └───────┘
                           │
               ┌───────┐   │
               │[1 2 3]│◀──┘
               └───────┘
                   │
        ┌───────┐  │
        │[1 2 3]│◀─┘
        └───────┘
            │
            │
    ...   ◀─┘

Поскольку в зиппере нет условия, по которому производство потомков останавливается, их вложенность неограничена. Функция iter-zip вернёт бесконечную цепочку локаций, в каждой из которых единица. Неважно, сколько единиц мы возьмём от неё – сто или тысячу – получим столько же единиц.

(->> zip-123
     iter-zip
     (take 10)
     (map zip/node))

;; (1 1 1 1 1 1 1 1 1 1)

Вернёмся к обмену валют. Предположим, банк меняет рубли на доллары, доллары на евро и евро на рубли. Выразим это в коде:

(def rules
  [[:rub :usd]
   [:usd :eur]
   [:eur :rub]])

Читатель заметит, что получился замкнутый круг:

             ┌───────┐
        ┌───▶│  rub  │────┐
        │    └───────┘    │
        │                 ▼
    ┌───────┐         ┌───────┐
    │  eur  │◀────────│  usd  │
    └───────┘         └───────┘

Недостаток прошлого решения в том, что оно не учитывает цикличность правил. Предположим, клиент хочет обменять рубли на лиры. Начнём строить дерево от рубля. Начало цепочки:

                       ┌───────┐
                       │  rub  │
                       └───────┘
                           │
               ┌───────┐   │
               │  usd  │◀──┘
               └───────┘
                   │
        ┌───────┐  │
        │  eur  │◀─┘
        └───────┘
            │
 ┌───────┐  │
 │  rub  │◀─┘
 └───────┘

Мы снова пришли к рублю. Для него мы получим доллар, для доллара евро, затем рубль. Если продолжить итерацию, будем бесконечно погружаться в эту цепочку.

Логика подсказывает, что нужно пресечь обход вглубь, если очередная валюта равна исходной. Проще говоря, у элемента :rub, который стоит не на вершине, не может быть потомков. Но функции branch? и make-children не знают, какое место в дереве занимает элемент. Они принимают значения, а не локации, и не могут ответить на вопрос, вершина это или нет.

Проблему можно исправить с помощью состояния, например атома, который хранил бы список валют, которые мы обошли. Другой вариант – проверять, в какой раз мы обращаемся к валюте from для поиска потомков. Если в первый раз, мы на вершине дерева. Найдём потомков и изменим атом, на котором замкнута функция children. Если это последующий раз (атом изменён), мы наткнулись на цикл, и для него потомков нет.

Оба способа имеют право на жизнь, но хотелось бы решить задачу без состояния и изменяемых средств.

Если посмотреть на дерево, станет ясно: проблема в порядке обхода. Поскольку мы стремимся вглубь, велика вероятность попасть в кротовую нору, из которой нельзя выбраться. Нам может повезти, когда мы удачно шагнули в ветку с решением (слева), а бесконечная ветка (справа) осталась нетронутой:

                 ┌───────┐
                 │  rub  │
                 └───────┘
                     │
         ┌───────┐   │   ┌───────┐
         │  yen  │◀──┴──▶│  usd  │
         └───────┘       └───────┘
             │               │
 ┏━━━━━━━┓   │               │   ┌───────┐
 ┃  lir  ┃◀──┘               └──▶│  eur  │
 ┗━━━━━━━┛                       └───────┘
                                     │
                                     │   ┌───────┐
                                     └──▶│  rub  │
                                         └───────┘
                                             │
                                             │
                                             └──▶  ...

Однако это везение, и на него нельзя полагаться в решении задач.

Предположим теперь, зиппер обходит локации не вглубь, а вширь и вправо. С таким порядком нам не страшны бесконечные ветки. Если таковая закралась в дерево, она не оттянет на себя обход. Вместо этого мы спускаемся по этажам и читаем все элементы этого уровня. Даже если один из них относится к бесконечной ветви, это не помешает исследовать остальные. Рисунок ниже показывает, как горизонтальный обход поможет добраться до цели. Вертикальный обход ушёл бы вы бесконечность, потому что обе ветви цикличны.


                           ┌───────┐
                         ┌─│  rub  │
                         │ └───────┘
                         ▼
                     ┌───────┐   ┌───────┐
                     │  yen  │──▶│  usd  │
                     └───────┘   └───────┘
                                     │
                   ┌─────────────────┘
                   ▼
               ┏━━━━━━━┓                ┌───────┐
               ┃  lir  ┃───────────────▶│  eur  │
               ┗━━━━━━━┛                └───────┘
                                            │
          ┌─────────────────────────────────┘
          ▼
      ┌───────┐   ┌───────┐         ┌───────┐   ┌───────┐
      │  rub  │──▶│  tug  │────────▶│  yen  │──▶│  rub  │
      └───────┘   └───────┘         └───────┘   └───────┘
          │                                         │
          │                                         │
   ...  ◀─┘                                         └─▶  ...

Проблема в том, что модуль clojure.zip предлагает только один способ обхода — в глубину с помощью zip/next. Другого алгоритма не предусмотрено. Мы напишем свою функцию, чтобы обойти зиппер “послойно”. Говоря иначе, для дерева как на рисунке:

                            ┌───────┐
  1                         │   1   │
                            └───────┘
                                │
              ┌───────┐         │         ┌───────┐
  2           │   2   │◀────────┴────────▶│   3   │
              └───────┘                   └───────┘
                  │                           │
      ┌───────┐   │   ┌───────┐   ┌───────┐   │   ┌───────┐
  3   │   4   │◀──┴──▶│   5   │   │   6   │◀──┴──▶│   7   │
      └───────┘       └───────┘   └───────┘       └───────┘

мы получим слои:

[1]
[2 3]
[4 5 6 7]

, при этом каждый элемент будет не примитивом, а локацией. Это значит, элемент помнит свое положение в дереве, от него можно переходить к другим элементам, получить его путь и так далее.

Для начала нужна функция, которая вернёт дочерние локации исходной. Её логика проста: погружаемся вниз, и если результат не пуст, двигаемся вправо.

(defn loc-children [loc]
  (when-let [loc-child (zip/down loc)]
    (->> loc-child
         (iterate zip/right)
         (take-while some?))))

Обратите внимание, что это не то же самое, что zip/children. Последняя вернёт значения, а не локации, а нам нужны именно локации. Сравните выражения:

(-> [1 2 3]
    zip/vector-zip
    zip/children)

(1 2 3)

и

(-> [1 2 3]
    zip/vector-zip
    loc-children)

([1 {:l [] :pnodes [[1 2 3]] :ppath nil :r (2 3)}]
 [2 {:l [1] :pnodes [[1 2 3]] :ppath nil :r (3)}]
 [3 {:l [1 2] :pnodes [[1 2 3]] :ppath nil :r nil}])

Во втором случае получили локации, в то время как zip/children просто обращается к функции для нахождения потомков, которую передали в зиппер.

Предположим, что для некоторой локации loc-children вернула список её потомков. Чтобы спуститься на уровень ниже, нужно найти потомков для них и объединить результат. Проще всего это это сделать выражением:

(mapcat loc-children locs)

, где locs — локации текущего уровня. Если передать в locs результат mapcat, продвинемся ещё дальше, и так до тех пор, пока не получим пустую последовательность. Всё вместе даёт нам функцию loc-layers:

(defn loc-layers [loc]
  (->> [loc]
       (iterate (fn [locs]
                  (mapcat loc-children locs)))
       (take-while seq)))

Она принимает корневую локацию, от которой начинается итерация по слоям. Первый слой мы задали явно как вектор одной локации. Затем идут его потомки, затем потомки потомков и так далее. Мы остановимся лишь когда получим пустой слой. Быстрая проверка:

(def data [[[[1]]] 2 [[[3]]] 3])

(let [layers (-> data
                 zip/vector-zip
                 loc-layers)]
  (for [layer layers]
    (->> layer
         (map zip/node)
         println)))

;; ([[[[1]]] 2 [[[3]]] 3])
;; ([[[1]]] 2 [[[3]]] 3)
;; ([[1]] [[3]])
;; ([1] [3])
;; (1 3)

Чтобы соединить слои в цепь, воспользуемся apply и concat. Эта функция не понадобится в решении задачи, но может оказаться полезной:

(defn loc-seq-layers [loc]
  (apply concat (loc-layers loc)))

Вернёмся к обмену валют. Подберём правила обмена так, чтобы в них были циклические зависимости:

(def rules2
  [[:rub :usd]
   [:usd :eur]
   [:eur :rub]

   [:rub :lir]
   [:lir :eur]
   [:eur :din]
   [:din :tug]])

Зиппер не изменится, но теперь мы обходим его по-другому: не с помощью zip/next, а функцией loc-layers. На каждом шаге получим слои обмена. Наша задача — найти в очередном слое локации, чей узел равен конечной валюте. Если нашли хотя бы одну, задача решена. Останется вычислить до них путь.

(defn exchange2 [rules from to]

  (letfn [(get-children [value]
            (seq (for [[v1 v2] rules
                       :when (= v1 value)]
                   v2)))

          (loc-to? [loc]
            (-> loc zip/node (= to)))

          (find-locs-to [layer]
            (seq (filter loc-to? layer)))

          (->exchange [loc]
            (conj (zip/path loc) (zip/node loc)))]

    (let [zipper (zip/zipper keyword?
                             get-children
                             nil
                             from)]

      (->> zipper
           loc-layers
           (some find-locs-to)
           (map ->exchange)))))

Заметим, что теперь не нужно сравнивать длины цепочек: если локации относятся к одному уровню, число шагов до них одинаково. По условию задачи мы заинтересованы в самых коротких вариантах обмена. Если на третьем уровне нашлась одна цепочка, а на четвертом их три, последние нам не интересны — обход завершится на третьем слое.

Примеры обмена с правилами, заданными в rules2:

(exchange2 rules2 :rub :eur)
([:rub :usd :eur] [:rub :lir :eur])

(exchange2 rules2 :rub :tug)
([:rub :usd :eur :din :tug] [:rub :lir :eur :din :tug])

(exchange2 rules2 :lir :din)
([:lir :eur :din])

Решение все ещё не идеально. Если указать пару валют, для которых нет цепочки, получим бесконечный цикл. Чтобы пресечь его, ограничьте число слоев каким-то разумным числом, например пятью. С точки зрения финансов обмен с таким числом операций будет невыгодным, а потому лишен смысла. Технически это значит добавить форму (take N) сразу после loc-layers:

(->> zipper
     loc-layers
     (take 5)
     (some find-locs-to)
     (map ->exchange))

Теперь для неверной пары получим пустой результат:

(exchange2 rules2 :tug :yen)
()

Задачу можно развить еще дальше. Скажем, для каждой цепочки считать издержки и комиссию за операцию. Для этого в вектор [:from :to] добавим обменный курс и вознаграждение. В зависимости от того, на чьей мы стороне — клиента или банка — будем искать самые затратные или оптимальные обмены. Предлагаем читателю придумать свои вариации к этой задаче.

На этом мы закончим с валютами и двинемся дальше. Мы рассмотрели, как порядок обхода влияет на решение задачи. В разных случаях применяют методы в глубину и в ширину. Это важно для бесконечных деревьев, когда алгоритм может зациклиться при обходе. В поставке clojure.zip нет обхода вширь, но легко написать функцию деления зиппера на слои. Возможно, loc-layers пригодится вам в других случаях, связанных с графами и вершинами.

(Продолжение следует)

Оглавление