Clojure Tic Tac Toe solver

Question

I am going through the 4clojure problems and I currently just solved the Tic Tac Toe analyzer:

(fn [board]
    (let [vr (for [x (range 3)]
              (get-in board[(+ x 0) (+ x 0)]))
          vl (for [x (range 3)]
               (get-in board [(+ x) (- 2 x)]))
          columns (apply map vector board)
          checks (concat board [vl] [vr] columns)]
      (letfn [(check-board [[row & res]]
                (if row
                  (let [dist (distinct row)]
                      (if (or (= dist [:o]) (= dist [:x]))
                        (first dist)
                        (check-board res)))
                  nil))]
        (check-board checks))))

I'm looking for any feedback about how I could make the code more terse.

Could I have created the diagonal vectors in one expression?

I don't like that I had to use recursion but I could not think of a way of using something like reduce because I don't think there is a way to short circuit reduce if you find the result midway through processing all the values.

Is there a way that I could avoid recursion with this problem?

Answer 1

Some Minor Points

(+ x 0) and (+x) can be replaced by just x, in (get-in board[(+ x 0) (+ x 0)])) and (get-in board [(+ x) (- 2 x)])) respectively.

You can omit the nil in else position in if : (if row ... nil) \$\rightarrow\$ (if row ...)

Idiomatic way of checking if something is one of a number of things is using a set of those values as a predicate: (or (= dist [:o]) (= dist [:x])) \$\rightarrow\$ (#{[:o] [:x]} dist)

Rename row to something not misleading. Since you named the collection checks you could name the iteration variable check.

Your Questions

Could I have created the diagonal vectors in one expression?

Yes. If you factor out the differing portions, namely [x x] and [x (- 2 x)], you get:

(let [diagonals (for [f [#(list % %) #(list % (- 2 %))]]
                  (for [x (range 3)]
                    (get-in board (f x))))

Since diagonals is already a sequence, you replace checks (concat board [vl] [vr] columns)] with checks (concat board diagonals columns)

Is there a way that I could avoid recursion with this problem?

Recursive processing of collections/sequences can be straightforwardly transformed to for expressions. Your :

(letfn [(check-board [[row & res]]
                (if row
                  (let [dist (distinct row)]
                      (if (or (= dist [:o]) (= dist [:x]))
                        (first dist)
                        (check-board res)))
                  nil))]
        (check-board checks))))

becomes this:

(first 
  (for [row checks 
        :let [dist (distinct row)] 
        :when (or (= dist [:o]) (= dist [:x]))]
    (first dist)))

Note for is lazy, therefore (first (for ... is equivalent to your short-circuit return.

These Changes Applied Altogether

(fn [board]
  (let [diagonals (for [f [#(list % %) #(list % (- 2 %))]]
                    (for [x (range 3)]
                      (get-in board (f x))))
        columns (apply map vector board)
        checks (concat board diagonals columns)]
    (first 
      (for [check checks 
            :let [dist (distinct check)] 
            :when (#{[:o] [:x]} dist)]
        (first dist)))))

Final Point

Also check out some, every?, keep, etc. which process collections with a predicate; and which this exercise probably wants you to learn. For example some is probably what you mean by short-cut evaluation reduce.

Answer 2

Stimulated by your question, I've had another go at solving this.

Could you have created the diagonal vectors in one expression?

Yes. See below.

Is there a way that you could avoid recursion with this problem?

Yes. The problem is not properly recursive. You can use the sequence functions to

• generate the lines,
• scan through them, and
• to scan each line if need be (avoided below).

And, by the way, there is now the reduced function which allows you to exit a reduce.

---

The idea is to do it in two stages:

1. From the given rows, generate the columns and the diagonals, hence all the lines.
2. Test each line in turn to see if it is purely :xs or purely :os. If so, that's the answer.

Hopefully, whatever we use to run through the lines will return nil if it doesn't find a solving one.

(defn ttt [rows]
  (let [cols (apply map vector rows)
        diags (map #(map % (range 3)) [#((rows %) %) #((rows %) (- 2 %))])
        lines (concat rows cols diags)]
    (first (some (comp #{#{:x} #{:o}} set) lines))))

---

I now see that @abuzittingillifirca's solution exploits all the techniques employed here, though preferring for to some and map.