Deserialize breadth-first trees

Question

I need to work with quad-trees as follows:

           p
         /| |\ 
        / | | \    
       /  | |  \
      p   w b   p
    /| |\     /| |\   
   / | | \   / | | \
  b  w w  b w  b w  b

But they have been serialized to a string using breadth-first order, so the previous tree would have the following representation:

ppwbpbwwbwbwb

I'm trying to transform such a string to a nested vector structure:

[ [ b w w b ] w b [ w b w b] ]

But sometimes the following code doesn't work correctly:

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (reverse r)) pending)
          (= p \p)        (recur (conj r s) rs rp)
          :else           (recur (conj r p) stack rp))))

Edited for adding a complex example:

Another (failed) example. The next tree:

                    |
         +------+-------+------+
         |      |       |      |
         |      w       w      |
         |                     |
   +---+---+---+         +---+---+---+
   |   |   |   |         |   |   |   | 
   |   w   w   |         |   w   w   |
   |           |         |           |
+-+-+-+     +-+-+-+   +-+-+-+     +-+-+-+
| | | |     | | | |   | | | |     | | | |
b b b b     w w w w   b b w w     b w b w

will be serialized as:

ppwwppwwppwwpbbbbwwwwbbwwbwbw

and the goal is to get the following structure:

[ [ [ b b b b ] w w [ w w w w ] ] w w [ [ b b w w ] w w [ b w b w ] ] ]

But my code gives a different (wrong) structure.

Answer 1

Your code suffers from some names representing lists instead of (intended) vectors.

This can already been seen from the function's return value, which is a list.

Look at these parts of the code:

(loop   ...
        [s & rs :as stack]
        ...
        (recur (conj r s) rs rp)

The highlighted [s & rs :as stack] will get the stack vector, name the first element s and the remaining elements as list(!) rs. As rs is a list, it will at some point pass on like that to stack (via the last recur), which then also is a list, and not a vector. Then, the next time r has 4 elements, (conj stack ... will not append r, but prefix it, as that is the behaviour of conj when applied to lists. Quoted from the docs:

;; notice that conjoining to a vector is done at the end

;; notice conjoining to a list is done at the beginning

This, of course, destroys the intended algorithm, and explains the wrong results you get.

A similar problem occurs with (reverse r) which returns a seq, even though r is a vector.

You can fix it, for instance, by applying (into [] ...) where you want lists to be passed on as vectors. I see two spots where you need to do this:

(defn read-quad-tree [pattern]
  (loop [r                    []
         [s & rs :as stack]   []
         [p & rp :as pending] (reverse pattern)]
    (cond (nil? pending)  (first r)
          (= (count r) 4) (recur [] (conj stack (into [] (reverse r))) pending)
          (= p \p)        (recur (conj r s) (into [] rs) rp)
          :else           (recur (conj r p) stack rp))))

The fix is not needed for pending, as it never "infects" the other names with the list type.

When the corrected code is called like this:

(println (read-quad-tree "ppwwppwwppwwpbbbbwwwwbbwwbwbw"))

it will output:

[[[b b b b] w w [w w w w]] w w [[b b w w] w w [b w b w]]]

While looking for the problem, I also added some checks on (in)valid patterns, which might interest you. The extended code is as follows:

(defn read-quad-tree [pattern]
    (loop   [r                   []
            [s & rs :as stack]   []
            [p & rp :as pending] (reverse pattern)]
        (cond
            (nil? pending)
                (if (or (seq stack) (not= (count r) 1))
                    {:error "Too few 'p'"}
                    {:tree (first r)})
            (= (count r) 4)
                (recur [] (conj stack (into [] (reverse r))) pending)
            (= p \p) 
                (if (empty? s)
                    {:error (format "'p' at %s lacks %d children" (count pending) (- 4 (count r)))}
                    (recur (conj r s) (into [] rs) rp))
            :else
                (recur (conj r p) stack rp))))

It will return a map with a tree key if all goes well, or with an error key if the pattern is incomplete.