Оглавление

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

До сих пор вторая функция, которую мы передавали в зиппер, возвращала потомков из ветки. Для вектора это была просто seq, для XML — более сложная комбинация (comp seq :content). Оба варианта отталкиваются от родительского узла, и если потомков нет, функция вернет nil.

Но что если функция потомков вернет постоянный набор, например:

(fn [_]
  (seq [1 2 3]))

Как поведет себя такой зиппер? Напишем его:

(def zip-123
  (zip/zipper any?
              (constantly (seq [1 2 3]))
              nil
              1))

Из-за того, что у любого элемента три потомка, зиппер станет бесконечным. Обойти его с помощью iter-zip не получится — zip/next будет все глубже погружаться в зиппер, и достигнет не его конца, а лимитов на память.

Ради интереса сделаем несколько шагов по новому зипперу. Спустимся вниз и вправо. Мы окажемся в двойке на середине вектора [1 2 3]:

(def loc-2
  (-> zip-123
      zip/down
      zip/right))

(zip/node loc-2)
;; 2

Покажем наше положение не схеме. Шаги влево и право сдвинут нас на единицу и тройку:

              ┌───────────┐
              │     1     │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃     2     ┃───▶│   3   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │[1 2 3]│
                └───────┘

С шагом вниз мы провалимся в очередной вектор [1 2 3] и так далее. Ради интереса спустимся вниз и вправо пять раз, и все равно окажемся в двойке:

(def down-right (comp zip/right zip/down))

(-> loc-2
    down-right
    down-right
    down-right
    down-right
    down-right
    zip/node)
;; 2

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

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

Однако заданный явно вектор [1 2 3] не раскрывает их. Если потомки известны заранее, нужда в зиппере отпадает — коллекцию можно обойти более простым способом. Интересен случай, когда потомки зависят от каких-то внешних факторов. Например, обе функции branch? и children могут быть замкнуты на других коллекциях и данных. Это тоже обход, но по другим правилам.

Знакомый принес с собеседования задачу. Представим, что банк разменивает валюты, например доллары на евро, рубли на лиры и так далее. Для краткости обозначим пары (usd, eur), (rub, lir). Размен действует в одном направлении: чтобы поменять евро на доллары или лиры на рубли, у банка должны быть отдельные правила (eur, usd) и (lir, rub).

В банк обращается клиент, чтобы разменять валюту X на Y. Если в правилах обмена есть пара (X, Y), проблем не возникнет. Но если пары нет, банк должен построить цепочку обменов. Например, клиент хочет поменять доллары на лиры, но в банке нет прямой пары (usd, lir). Однако есть пары (usd, eur) и (eur, lir). В этом случае клиенту предложат обмен usd -> eur -> lir.

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

Опишем входные данные в терминах Clojure. Каждое правило будет вектором двух кейвордов — с какой валюты на какую происходит обмен. Вектор правил назовем rules. Кроме правил, мы принимаем параметры from и to — валюты, с чего на что менять, тоже кейворды.

;; rules
[[:usd :rub] [:rub :eur] [:eur :lir]]

:usd ;; from
:rub ;; to

На выходе ожидаем последовательность цепочек от from к to или nil. Для случая выше цепочка от доллара к евро выглядит так:

[:usd :rub :eur]

Все вместе дает функцию exchanges, тело которой нам предстоит заполнить:

(defn exchanges [rules from to]
  ...)

Для начала напишем несколько тестов. Они помогут размяться, и заодно мы лучше поймем задачу. Первый тест — простой обмен, который есть среди правил:

(deftest test-simple
  (is (= [[:usd :rub]]
         (exchanges [[:usd :rub]] :usd :rub))))

Обмен в обратную сторону невозможен, если нет обратного правила:

(deftest test-reverse-err
  (is (nil? (exchanges [[:rub :usd]] :usd :rub))))

Случай, когда обмен невозможен:

(deftest test-no-solution
  (is (nil? (exchanges [[:rub :usd] [:lir :eur]] :usd :eur))))

Наиболее важный сценарий: транзитивный обмен. От долларов к рублям можно дойти двумя путями:

(deftest test-two-ways
  (is (= [[:usd :eur :rub]
          [:usd :lir :rub]]
         (exchanges [[:usd :eur]
                     [:eur :rub]
                     [:usd :lir]
                     [:lir :rub]] :usd :rub))))

Еще один тест проверяет, что вы вернем только самые короткие цепочки. Обмен с четырьмя валютами (в данном случае [:usd :yen :eur :rub]) не попадет в результат:

(deftest test-short-ways-only
  (is (= [[:usd :eur :rub]
          [:usd :lir :rub]]
         (exchanges [[:usd :eur]
                     [:eur :rub]
                     [:usd :lir]
                     [:lir :rub]
                     [:usd :yen]
                     [:yen :eur]] :usd :rub))))

В терминах олимпиадного программирования можно сказать, что задача предлагает отдельные ребра графа. Требуется проверить, можно ли составить из ребер непрерывный маршрут от вершины А к B. Но в этом уроке мы решим задачу на зипперах, поэтому не будем использовать термины “граф”, “ребра” и другие. Мы не гарантируем, что решение будет оптимальным, и возможно, алгоритм на графах справится лучше. Однако надеемся, что пример еще больше раскроет мощь зипперов.

Как вы помните, зипперы нужны для обхода деревьев, и данные задачи подходят на эту роль. Представим, что на вершине дерева стоит валюта from, которую мы хотим разменять. Пусть это будет доллар. Очевидно, что потомки этой валюты — все те, на которую ее можно разменять. Для этого выберем второй элемент из каждой пары, где первый элемент равен from:

(def rules
  [[:usd :rub]
   [:usd :lir]
   [:rub :eur]
   [:rub :yen]
   [:eur :lir]
   [:lir :tug]])

(def from :usd)

(def usd-children
  (for [[v1 v2] rules
        :when (= v1 from)]
    v2))
;; (:rub :lir)

Изобразим мнимое дерево и обозначим уровни:

                  ┌───────┐
     1            │  usd  │
                  └───────┘
                      │
          ┌───────┐   │   ┌───────┐
     2    │  rub  │◀──┴──▶│  lir  │
          └───────┘       └───────┘

Для каждой валюты второго уровня найдем потомков по такому же правилу. Для удобства напишем функцию get-children:

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

(get-children :rub)
;; (:eur :yen)

Новое дерево:

                      ┌───────┐
    1                 │  usd  │
                      └───────┘
                          │
              ┌───────┐   │   ┌───────┐
    2         │  rub  │◀──┴──▶│  lir  │
              └───────┘       └───────┘
                  │               │
       ┌───────┐  │  ┌───────┐    │  ┌───────┐
    3  │  eur  │◀─┴─▶│  yen  │    └─▶│  tug  │
       └───────┘     └───────┘       └───────┘

Заметим, что это именно виртуальное дерево, о котором мы говорили недавно. У нас нет этого дерева на руках – оно получается в процессе. Функция make-children замкнута на исходных парах обмена. Это пример того, как обходить структуры данных, которые получаем в полете из других данных.

Структура дерева валют известна, и его можно обойти. Вопрос, до каких пор его обходить? Очевидно, мы должны остановиться, как только встретим локацию, чей узел равен валюте to. Пусть это будут йены. Это значит, мы соединили from и to с помощью других валют. На схеме ниже обозначено решение:

                      ┌───────┐
    1                 │  usd  │
                      └───────┘
                          │
              ┌───────┐   │   ┌ ─ ─ ─ ┐
    2         │  rub  │◀──┘
              └───────┘       └ ─ ─ ─ ┘
                  │
       ┌ ─ ─ ─ ┐  │  ┌───────┐       ┌ ─ ─ ─ ┐
    3             └─▶│  yen  │
       └ ─ ─ ─ ┘     └───────┘       └ ─ ─ ─ ┘

Чтобы получить цепочку обмена, локацию передают в функцию zip/path. Она вернет вектор всех родителей локации, не включая ее саму. Таким образом, путь к локации и ее узел образуют цепочку обмена.

На базе этих рассуждений напишем код. Двигаемся сверху вниз. Подготовим зиппер:

(def zip-val
  (zip/zipper keyword?
              get-children
              nil
              from))

Ищем в зиппере локацию с целевой валютой:

(def loc-to
  (->> zip-val
       iter-zip
       (some (fn [loc]
               (when (-> loc zip/node (= to))
                 loc)))))

Если нашли, то получим из нее цепочку обмена:

(conj (zip/path loc-to) (zip/node loc-to))
;; [:usd :rub :yen]

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

Расширим исходные данные:

(def rules
  [[:usd :rub]
   [:usd :lir]
   [:rub :eur]
   [:lir :yen]
   [:rub :yen]
   [:eur :lir]
   [:lir :tug]])

(def from :usd)
(def to :yen)

и найдем цепочки. Для этого заменим some на filter:

(def locs-to
  (->> zip-val
       iter-zip
       (filter (fn [loc]
                 (-> loc zip/node (= to))))))

(for [loc locs-to]
  (conj (zip/path loc) (zip/node loc)))

([:usd :rub :eur :lir :yen]
 [:usd :rub :yen]
 [:usd :lir :yen])

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

(defn get-shortest-chains
  [chains]
  (when (seq chains)
    (let [count->chains (group-by count chains)
          min-count (apply min (keys count->chains))]
      (get count->chains min-count))))

Для последнего результата получим два вектора по три валюты в каждом. Этот случай покрывает последний тест test-short-ways-only, где длинные цепочки отбрасываются:

[[:usd :rub :yen] [:usd :lir :yen]]

Из фрагментов кода соберите функцию exchanges. Добейтесь, чтобы проходили тесты. Добавьте в них больше случаев.

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

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

Оглавление