Created
March 31, 2016 18:23
-
-
Save freckletonj/52fac60ea752dd5ae2a5f571ee897786 to your computer and use it in GitHub Desktop.
Convert a sequence into spiral matrix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn rotate | |
"rotate a 2D matrix 90 degrees, it's ok if it's not a perfect square" | |
[mat] | |
(loop [remaining (map reverse mat) | |
result []] | |
(if (every? empty? remaining) | |
result | |
(recur (map rest remaining) | |
(conj result (remove nil? (mapv first remaining))))))) | |
(defn spiralize | |
"take a sequence, and wrap it around a central cell until you have a 2D matrix that | |
represents the entire sequence, spiralized. | |
Note: This is really slow, to keep rotating the matrix over and over" | |
[start-coll] | |
(let [edge (int (Math/ceil (Math/sqrt (count start-coll)))) | |
start-legs (concat (mapcat (fn [x] [x x]) (range 1 edge)) [edge])] | |
(loop [mat '() | |
coll start-coll | |
legs start-legs] | |
(if (empty? legs) | |
mat | |
(recur (->> mat | |
(cons (take (first legs) coll)) | |
rotate) | |
(drop (first legs) coll) | |
(rest legs)))))) | |
(time (do | |
(spiralize (range (* 300 300))) | |
"done")) ;; "Elapsed time: 3681.074952 msecs" | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
As seen at the bottom, this is reallly slow, and the time increase fast as the length of
start-coll
increases.I think the slow part is that at each iteration, I rotate the entire matrix. But this feels very "functional" as I'm not side-effecting to update the matrix. Maybe I could maintain some notion of