Найти сумму цифр, появляющихся в листья, в обход в обратном порядке


Следующий текст в порядке обхода двоичного дерева с 1023 узлы. Какова сумма цифр, появляющихся в листьях?

Как я могу улучшить этот код в Clojure? Это выглядит странно для меня два рецидивирует в если.

(ns fun2)

(defn parse [in sum]
 (println "sum" sum)
 (if (> (.length in) 1)
   (let [next-char (subs in 0 1)]
     (if (.matches next-char "[0-9]")
       (recur (subs in 2) (+ sum (Integer/parseInt next-char)))
       (recur (subs in 2) sum)))))

(parse (slurp "/Users/clojure/challange2.txt") 0)

;; ans 331


Комментарии
3 ответа

Вот версия функции, которые я нахожу приятнее:

(defn parse [s]
(apply + (->> s
(partition-all 2) ; iterate pairs of chars in s
(map (comp str first)) ; leaf node is the first in the pair
(filter (partial re-find #"\d")) ; keep only digits
(map #(Integer/parseInt %))))) ; turn 'em into ints

Я представляю, как он может быть сокращен, чтобы быть более идиоматические в Clojure, но я нахожу это довольно читаемым.

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

5
ответ дан 16 июля 2011 в 02:07 Источник Поделиться

Я нахожу полезным думать в seqs и встроенные функции.

Предполагая, что числа являются листья. Вы можете извлечь все листья, используя ре-сл, тогда карте их в числа, а затем применить + к все числа, чтобы получить сумму:

  (defn sum-leaves [s]
(apply + (map #(- (int (first %)) (int \0)) (re-seq #"[0-9]" s))))

2
ответ дан 17 июля 2011 в 05:07 Источник Поделиться

Этот код делает несколько разные вещи, и одна из действительно больших вещей о Clojure-это то, что он позволяет упростить путем разложения вещи, которые делают больше, чем одну задачу на ряд отдельных задач.

если:


  • принимая все остальные буквы в строке (может быть, хотел взять каждую букву)

  • выбирая цифр

  • преобразовать их в числа.

  • добавив их всех.

взять любой другой персонаж:

(apply str (flatten (partition-all 1 2 in)))

выбрать цифры:

(re-seq #"[0-9]" ...

превратить их в целые числа:

(map #(Integer/parseInt (str %)) ...

добавить их всех, сохраняя интермедиатов:

(reductions + ...

так что если я сочиняю эти я в конечном итоге с:

(reductions + 
(map #(Integer/parseInt (str %))
(re-seq #"[0-9]"
(apply str (flatten (partition-all 1 2 in))))))

производить:

(2 11 15 15 19 20 24 33 34 35 44 46 48 48 55 63 67 
76 77 79 83 90 95 102 106 109 114 121
121 127 136 144 151 160 168 174 174 176
180 182 191 199 204 211 214 216 222 226
235 242 246 247 250 252 260 263 270 275
276 277 278 282 288 295 299 299 304 308
310 315 323 326 326 331)



В вашем примере линии

      (recur (subs in 2) (+ sum (Integer/parseInt next-char)))
(recur (subs in 2) sum)))))

в сочетании с:

(let [next-char (subs in 0 1)]

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

(defn parse [in sum]
(println "sum" sum)
(if (> (.length in) 1)
(let [next-char (subs in 0 1)]
(if (.matches next-char "[0-9]")
(recur (subs in 1) (+ sum (Integer/parseInt next-char)))
(recur (subs in 1) sum)))))

получения ответа из 679.

снижение в Clojure-карту-уменьшить-стиль форма этого код станет немного проще:

(reductions + (map #(Integer/parseInt (str %)) (re-seq #"[0-9]" in)))

(4 7 9 18 26 28 32 41 50 53 53 57 64 72 79 85 88 89
90 99 103 112 113 114 120 124 130 131 137 142 143
152 159 159 159 161 168 170 170 177 180 188 189 193
198 198 207 208 209 217 219 223 230 235 242 249 251
255 257 261 264 269 276 276 285 291 297 306 314 320
327 329 338 339 347 356 362 362 370 377 379 383 385
394 402 407 415 419 426 427 430 434 436 442 446 447
449 456 465 472 475 479 484 485 488 492 493 498 500
508 517 520 527 532 533 534 535 539 541 549 555 563
570 574 574 579 585 589 589 591 591 596 604 613 618
622 631 634 640 647 650 654 654 661 666 675 679)

1
ответ дан 16 июля 2011 в 01:07 Источник Поделиться