## Sunday, November 2, 2014

### Technetium OR Reverse Interleave in Clojure

"Yet ‘ banished ’? Hang up philosophy!
Unless philosophy can make a Juliet,
Displant a town, reverse a prince's doom,
It helps not, it prevails not. Talk no more.
"
-- Shakespeare, Romeo and Juliet
Act III, Scene III, Lines 58-61

4clojure problem number 43 states:

"Write a function which reverses the interleave process into x number of subsequences."
For now let's look at the interleave process before we move on to reversing it.

ClojureDocs gives us the following:

"Returns a lazy seq of the first item in each coll, then the second etc."
In other words, give interleave a bunch of collections and it will place an item from each one into a result collection in a lazy way.  Something like this (based on the wikipedia entry):

Given sequences x and y with members i = 0, 1, 2, ... the interleave sequence of x and y is:
x0, y0, x1, y1, x2, y2, ...

Let's look at using interleave with the results of the test cases given by the 4clojure problem in a Clojure REPL.

(interleave '(1 3 5) '(2 4 6))
;; (1 2 3 4 5 6)

(interleave '(0 3 6) '(1 4 7) '(2 5 8))
;; (0 1 2 3 4 5 6 7 8)

(interleave '(0 5) '(1 6) '(2 7) '(3 8) '(4 9))
;; (0 1 2 3 4 5 6 7 8 9)

If we look at one of these in more detail we can see that it is following the definition given above.

(interleave '(0 3 6) '(1 4 7) '(2 5 8))
;; (0 1 2 3 4 5 6 7 8)

Or more mathematically

(interleave '(:x0 :x1 :x2) '(:y0 :y1 :y2) '(:z0 :z1 :z2))
;; (:x0 :y0 :z0 :x1 :y1 :z1 :x2 :y2 :z2)

Interleaving does not do a sort or anything like that, so if we move around the input we get different output:

(interleave '(1 4 7) '(0 3 6) '(2 5 8))
;; (1 0 2 4 3 5 7 6 8)

Now let's look at the problem at hand.

"Write a function which reverses the interleave process into x number of subsequences."

(= (__ [1 2 3 4 5 6] 2) '((1 3 5) (2 4 6)))

(= (__ (range 9) 3) '((0 3 6) (1 4 7) (2 5 8)))

(= (__ (range 10) 5) '((0 5) (1 6) (2 7) (3 8) (4 9)))

We need to come up with a function which will reverse the interleave function.  In other words, given a collection and the number of partitions we want returned, we get a collection of collections which can be interleave to return back the original collection given.

First thing we can do is set up our partitions using the partition function.

(fn [xs n]
(->> (partition n xs) ))

This would give us the following using the test cases from 4clojure:

((fn [xs n]
(->> (partition n xs) ))
[1 2 3 4 5 6] 2)
;; ((1 2) (3 4) (5 6))

((fn [xs n]
(->> (partition n xs) ))
(range 9) 3)
;; ((0 1 2) (3 4 5) (6 7 8))

((fn [xs n]
(->> (partition n xs) ))
(range 10) 5)
;; ((0 1 2 3 4) (5 6 7 8 9))

We now have each collection containing the number of partitions we want in the final result but everything is all mixed up!

If we look at the output for the first test case right now we have:
( (1 2) (3 4) (5 6) ) but what we want is:
( (1 3 5) (2 4 6) )

Looking at this closer we have the following:
( (1 2) (3 4) (5 6) ) but we want this:
( (1 3 5) (2 4 6) )

Looks like if we just need to map out the members in order and we'll get the result we want.  Following this will give us the following function:

(fn [xs n]
(->> (partition n xs) (apply map list)))

Running this against our test cases gives us the following:

((fn [xs n]
(->> (partition n xs) (apply map list)))
[1 2 3 4 5 6] 2)
;; ((1 3 5) (2 4 6))

((fn [xs n]
(->> (partition n xs) (apply map list)))
(range 9) 3)
;; ((0 3 6) (1 4 7) (2 5 8))

((fn [xs n]
(->> (partition n xs) (apply map list)))
(range 10) 5)
;; ((0 5) (1 6) (2 7) (3 8) (4 9))

This is exactly what we want.

Now I did not see this solution at first, this is what I submitted first to 4clojure:

(fn [xs n]
(->> (map-indexed #(hash-map (mod %1 n) %2) xs) (group-by keys) (map second) (map #(mapcat vals %))))

Yep, very complex but it does work :(

As soon as I look at ramo and amcnamara's solutions I saw what I really wanted to do in my head but was unsure of how to with my Clojure knowledge, resulting in the final function I submitted:

(fn [xs n]
(->> (partition n xs) (apply map list)))