Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

The following text is an in-order traversal of a binary tree with 1023 nodes. What is the sum of the digits appearing in the leaves?

How can I improve this Clojure code? It looks strange to me to have two recurs in the if.

(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
share|improve this question

migrated from stackoverflow.com Jul 16 '11 at 1:33

This question came from our site for professional and enthusiast programmers.

1  
Are we assuming this is a complete binary tree? Otherwise I don't think a single inorder traversal is enough to reliably figure out what the leaves are. –  overthink Jul 16 '11 at 2:11
    
depends on whats important to you, readability, speed, memory etc. the readability there can definitely use some improvement. –  Hermann Ingjaldsson Jul 16 '11 at 8:43

3 Answers 3

Here's a version of the function that I find nicer:

(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

I imagine it can be further reduced to be more idiomatic Clojure, but I find this pretty readable.

Important assumption: this algorithm only works if the input is an inorder traversal of a complete binary tree. If the original tree was not complete, a single inorder traversal is not sufficient to reconstruct it and find the leaves.

share|improve this answer

I find it useful to think in seqs and built-in functions.

Assuming that the the numbers are leaves. You can extract all the leaves using re-seq, then map them to numbers and then use apply + to all the numbers to get the sum:

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

This code is doing several distinct things and one of the really great things about clojure is that it lets you make things simple by decomposing things that do more than one task into a series of individual tasks.

if is:

  • taking every other letter in a string (perhaps you meant to take every letter)
  • picking out the digits
  • convert them into numbers.
  • adding them all up.

take every other character:

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

pick out the digits:

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

turn them into integers:

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

add them all up, keeping the intermediates:

(reductions + ...

so if i compose these i end up with:

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

producing:

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


In your example the lines

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

combined with:

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

work out the same as taking every other letter. I'm only looking at the code and not the problem you are trying to solve so I can't say if this is what you want or not. If by chance this is a bug then your could change the 2 to a 1 and get all the letters:

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

producing an answer of 679.

the reduced clojure-map-reduce-style form of this code would become a bit simpler:

(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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.