Some days ago I wrote a simple maze generator using depth-first search. It's really trivial, took much less space than my age-old Ruby implementation and - most importantly - made me play around with trees in Clojure.
Today, on a three-hour ride on the train I was bored. So my mind drifted off to my happy place (which, incidentally, is programming) and I started thinking about the aforementioned generator. I realized that all generated mazes could be represented as a tree (I... won't confess as to what data structure I used before.), so, upon further thought, I also concluded that path-finding between two points is trivial, assuming that one of the points is the root node... then I thought some more, and thought, "Hey! In the case of the maze it doesn't really matter WHICH node is the root node... so, I should be able to make a different node the root node without changing the structure of the maze at ALL."
Some mililitre of ink, some paper and quite some thoughts later...
It's definately possible. And, actually, not so hard.
1 -> 2
-> 3
-> 4 -> 5 -> 6
-> 7 -> 8
-> 9
Let's use this beautiful *cough* tree. Let's say we want to find the way from 4 to 3. The way is simple: 4 -> 1 -> 3. But it's not entirely clear from a data-structure point of view. So...
4 -> 5 -> 6
-> 7 -> 8
-> 9
-> 1 -> 2
-> 3
Upon closer inspection, what happened is very clear. All nodes UP from 4 were appended to the 4 instead. I don't feel like typing out another entire tree, but if there were more nodes above the 4, then all nodes above it would be in reversed order:
1 -> 2 -> 3 -> 4 -> 5
becomes
3 -> 4 -> 5
-> 2 -> 1
You see, 1 -> 2 became 2 -> 1.
So, that's about the entire theory - take all nodes up until the root, reverse the order, and append that to the node you want to be the new root.
Let's implement it.
I assume trees built from vectors in the form of:
node => [[object] & nodes]
Which means the first item of each vector is basically anything (in our example these would be numbers), followed by any number of similarly-structured vectors.
[1 [2] [3 [4]]]
is equal to:
1 -> 2
-> 3 -> 4
Because I was on a train at the time, and I couldn't recall any function to do it (nor use the clojure.repl tools very well) I wrote my own function to remove an indexed item from a vector, called "without". Basically...
(defn without [n v]
(vec (concat (take n v) (drop (inc n) v))))
Nothing too exciting. Also, probably redundant.
At this point I was kind of stuck. I wrote something along the lines of this...
(defn reroot [tree [n1 & nr]]
(if n1
(conj (reroot (tree n1) nr) (without n1 tree))
tree))
I used destructuring here (which I will go into in more detail in the next post), but here, it's enough to know that (reroot [tree] [1 2 3]) would have n1 = 1 and nr = [2 3].
Anyway, the first argument is the tree itself, obviously, whereas the second argument is the "path" to the new root node.
For example,
(reroot [1 [2] [3 [4]]] [2 1])
should result in
[4 [3 [1 [2]]]]
since item #1 in item #2 of the original tree is 4.
Anyways, the code snipped above is wrong. I didn't really know why, I only knew I was doing something wrong. I was totally shotgunning it, putting a without there, removing one somewhere else, replacing it with a simple access-by-index... Until I thought - SCREW THIS, let's do it properly.
I wrote another helper function, I called it swap. It would swap (HAH!) the places of the root node and it's child node of index n:
(defn swap [tree n]
(conj (tree n) (without n tree)))
Trivial enough.
I didn't explain yet why I use the without. Picture this tree:
1 -> 2 -> 3
-> 4 -> 5
Calling swap 1 on it (index 1 is the 2 -> 3 branch) would result in this without the "without":
2 -> 3
-> 1 -> 2 -> 3
-> 4 -> 5
while it should be
2 -> 3
-> 1 -> 4 -> 5
Now it's quite obvious; I use the "without" to achieve the effect of taking out the branch from the tree I'm appending to it.
Now return to our reroot...
(defn reroot [tree [n1 & nr]]
(if n1
(recur (step tree n1) nr)
tree))
This works as intended.
But, this being Clojure, such a simple function in four lines? No way this is done. We can do it better.
And of course, the pattern is pretty obvious: some value that is modified repeatedly, according to some list passed along. Sounds awfully like reduce.
Hence, the final version:
(defn without [n v]
(vec (concat (take n v) (drop (inc n) v))))
(defn swap [tree n]
(conj (tree n) (without n tree)))
(defn reroot [tree path]
(reduce swap tree path))
If this isn't elegant, I don't know what is*.
*If you ignore the part with that "without" for a moment.
No comments:
Post a Comment