Michael Whatcott - Working with Grids in Clojure

I'm working on a fun new project: building a tic-tac-toe game that features an unbeatable AI in Clojure! I'm also working on Project Euler problem #11. Both of these projects deal with grids.

Generally, when I approach a problem I (try to) go for the simplist solution. For instance, when building a tic-tac-toe program you can simply hard-code all possible winning combinations because there are so few. That would probably be the fastest way to build an MVP. But, I'm also wanting to solve that Euler problem which deals with much larger grid, and you have to traverse the grid in rows, columns, and diagonals to find the winning combination of digits to produce the correct answer.

So, I thought I'd try my hand at implementing a more general solution to the tic-tac-toe game in hopes that I'd learn something about working with grids and better position myself to solve the Euler problem. I might learning something along the way and I can always fall back on the original, simpler, hard-coded approach if things don't work out.

To begin with, the number of diagonals in a grid is equal to:

length + width - 1

The following diagram illustrates the five right-leaning diagonals of a 3x3 grid.

1 / /
2 / /
3 4 5

The following diagram illustrates the seven right-leaning diagonals of a 4x4 grid.

1 / / /
2 / / /
3 / / /
4 5 6 7

In my first stab I treated left-leaning diagonals separately from right-leaning diagonals:

(defn rows->right-diagonals [rows]
  (let [length         (count rows)
        height         (count (first rows))
        diagonal-count (dec (+ length height))]
    (->> (range diagonal-count)
         (map #(extract-right-diagonal rows %)))))

(defn rows->left-diagonals [rows]
  (let [length         (count rows)
        height         (count (first rows))
        diagonal-count (dec (+ length height))]
    (->> (range diagonal-count)
         (map #(extract-left-diagonal rows %)))))

Wow, those almost exactly alike! The only difference is the function they call to traverse each diagonal, which look like this:

(defn extract-right-diagonal [rows row]
  (loop [row row, col 0, out []]
    (if (< row 0)
      (filter #(not (false? %)) out)
      (let [value (nth (nth rows row []) col false)]
        (recur (dec row) (inc col) (conj out value))))))

(defn extract-left-diagonal [rows row]
  (loop [row row, col (dec (count (first rows))), out []]
    (if (< col 0)
      (filter #(not (false? %)) out)
      (let [value (nth (nth rows row []) col false)]
        (recur (dec row) (dec col) (conj out value))))))

Again, very simliar in structure, but there are subtle differences. I really didn't like all of this duplication. Then it hit me: you only need to know how to extract diagonals in one direction if you can properly rotate the grid!

Get the right-leaning diagonals from the rows.
Get the left-leaning diagonals by getting the right-leaning diagonals from the columns (rotated rows).

Here's a function that will turn rows into columns:

(defn rows->columns [rows]
  (for [column (range (count rows))]
    (map #(nth % column) rows)))

Except it doesn't work. Why not????? Well, try it out. Then draw it out. That's what I had to do to realize that this code doesn't really rotate the grid, it just flips it along a line of symmetry and this doesn't really change the direction of the diagonals as hoped.

Here's an example. We start with a 3X3 grid encoded in a single vector:

[0 1 2 3 4 5 6 7 8]

I'll render it as a grid (for convenience):

0 1 2
3 4 5
6 7 8

The right-leaning diagonals of that grid are as follows (when sorted):

If we run the grid through (rows->columns (partition 3 grid)) to get the columns we get this new grid:

0 3 6
1 4 7
2 5 8

The right-leaning diagonals (when each are sorted in place) have not changed at all, proving that we didn't really rotate the grid, we just fipped it along a line of symmetry!

The solution is simple: reverse the columns!

(defn rows->columns [rows]
  (reverse
    (for [column (range (count rows))]
      (map #(nth % column) rows))))

Now we get the following grid from (rows->columns (partition 3 grid)):

2 5 8
1 4 7
0 3 6

...which produces the following right-leaning diagonals:

And that does it! Here's how the above functions are used to determine the winner of a tic-tac-toe game:

(def X "X")
(def O "O")

(defn threesome [mark row] (= row (repeat 3 mark)))

(defn winner [grid]
  (let [rows   (partition 3 grid)
        cols   (rows->columns rows)
        left   (rows->diagonals cols)
        right  (rows->diagonals rows)
        all    (concat rows cols left right)
        x-wins (some (partial threesome X) all)
        o-wins (some (partial threesome O) all)]
    (cond x-wins X o-wins O :else nil)))

(winner [X O O
         O X X
         X O X]) ; -> X

With all tests passing, I'm now ready to implement the AI...