Оглавление

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

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

(->> [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 вернет бесконечную цепочку локаций, каждая из которых несет единицу. Даже если ограничить итерацию с помощью (take n), это ничего не даст — просто получим N единиц:

(->> 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 мы не знаем, какое место в дереве занимает элемент. В них приходят чистые значения, а не локации. Это можно исправить с помощью состояния, например атома, который хранил бы список валют, которые мы обошли. Но сейчас мы ставим задачу обойтись без состояния и изменяемых объектов.

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

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

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

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

                 ┌───────┐
             ┌───│  rub  │
             │   └───────┘
             ▼
         ┌───────┐       ┌───────┐
         │  yen  │──────▶│  usd  │
         └───────┘       └───────┘
                             │
     ┌───────────────────────┘
     ▼
 ┏━━━━━━━┓                       ┌───────┐
 ┃  lir  ┃──────────────────────▶│  eur  │
 ┗━━━━━━━┛                       └───────┘
                                     │
                                     │   ┌───────┐
                                     └──▶│  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 новый уровень, продвинемся еще дальше, и так до тех пор, пока не получим пустую последовательность. Все вместе дает нам функцию loc-layers:

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

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

(let [layers (-> [[[[1]]] 2 [[[3]]] 3]
                 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)

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

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

Вернемся к обмену валют. Подберем правила обмена так, чтобы в них были циклические зависимости. Зиппер останется прежним: он точно так же строит дерево обмена при помощи локальной функции get-children, которая замкнута на правилах.

(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)))))

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

Примеры обмена:

(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 пригодится вам в других случаях, связанных с графами и вершинами.

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

Оглавление