3
\$\begingroup\$

I've been playing around with Clojure for a while now, and one of the tasks I occasionally find awkward is parsing input. For example, I took part in the facebook hacker cup recently, where part of the challenge was to read input like this:

5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####

Where the first line is the number of "cases" to follow and the first line of each case is the number of lines in that case. It seems fairly obvious to me that the output of parsing this should be a list of "cases", but there's no obvious way to know when to split the data without reading part of the data first. (In this particular case I know I could look for lines with numbers vs. lines with #s, but I'm more interested in a general solution)

I ended up implementing this like:

(defn read-stdin   
  []
  (line-seq (java.io.BufferedReader. *in*)))

(defn my-iterate   
  [f n input]
  "Calls iterate on input and returns the final result"   
  (nth (iterate f input) n))

(defn parse-grid   
  "Parses a text grid of .s and #s and returns a set of coord
   pairs for each # element"
  [lines]
  (set (filter identity
      (for [[row line] (map-indexed vector lines)
            [col c] (map-indexed vector line)]
        (if (= c \#) [row col] nil)))))

(defn parse-case   
  "Takes a case-array and some lines, parses out a single case,
   adds it to the case-array and returns along with the remainder of the lines.
   Meant to be used with iterate"
  [[cases [first-line & lines]]]
  (let [problem-size (read-string first-line)]
    [(conj cases {:size problem-size
                   :blacks (parse-grid (take problem-size lines))}),
     (drop problem-size lines)]))

(defn parse-cases   
  [[first-line & rest-lines]]   
  (let [num-cases (read-string first-line)]
    (first (my-iterate parse-case num-cases [[] rest-lines]))))

(def read-cases-stdin (comp parse-cases read-stdin))

The parse-case function is my main worry here - it feels really awkward to have to return a vector of the current case list and the rest of the input, and have to deal with unpacking it again on the next iteration of the function. Is there a more idiomatic way of going about doing this?

Any other general feedback on my code would also be welcome.

\$\endgroup\$
3
\$\begingroup\$

I think your main problem is that you're using iterate where partitioning and mapping would work just fine.

I would create a simple helper function that splits the input line-seq into cases. Normally you could use partition for this, but since the number of lines can vary from case to case, you would have to use loop/recur. (See my split-cases function below. Also, note that we don't really care about the number of cases on the first line; we completely ignore it via destructuring.)

Now, believe it or not, all you have to do is map your parse-grid function over the result of (split-cases ...) and you'll end up with a list of sets of coordinates, one for each case.

I think your parse-grid function is very nice. It's concise and it makes good use of map-indexed and destructuring. The only thing I would tweak is that I would leverage the built-in :when syntax of Clojure's for macro to filter out the coordinates of the non-# characters. Then you can take out the filter identity part because there are no longer any nil values to remove.

So, here is how I would revise your code:

(defn split-cases [[_ & lines]]
  "Returns a seq of cases, each of which is a seq of #/. lines."
  (loop [result []
         [number-of-lines & lines] lines]
    (if (seq lines)
      (recur (conj result (take number-of-lines lines))
             (drop number-of-lines lines))
      result)))

(defn parse-grid [grid]
  "Parses a text grid of .s and #s and returns a set of coord
   pairs for each # element"
  (set (for [[row line] (map-indexed vector grid)
             [col c]    (map-indexed vector line)]
             :when (= c \#)]
         [row col])))

(defn read-stdin [] 
  (line-seq (java.io.BufferedReader. *in*)))

(defn parse-cases-stdin []
  (map parse-grid (split-cases (read-stdin))))
\$\endgroup\$
  • \$\begingroup\$ I'd almost given up on this question, but that's a great answer. Thanks. \$\endgroup\$ – obmarg Mar 26 '14 at 18:19
  • \$\begingroup\$ As CR's top clojure answerer, you should join us in our chatroom sometime so you can get to know the site better. ;) \$\endgroup\$ – syb0rg Mar 26 '14 at 21:03
  • \$\begingroup\$ @syb0rg Think I will sometime! \$\endgroup\$ – Dave Yarwood Mar 28 '14 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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