As in problem 73, a tic-tac-toe board is represented by a two dimensional vector. X is represented by :x, O is represented by :o, and empty is represented by :e.

Create a function that accepts a game piece and board as arguments, and returns a set (possibly empty) of all valid board placements of the game piece which would result in an immediate win.

Board coordinates should be as in calls to get-in. For example, [0 1] is the topmost row, center position.

problem: 119

I reused the algorithm from the previous exercise 73 which, given a board, compute the winner of the board. And first, I developed a version to prove the correctness of the algorithm.

## Correctness

My main idea to solve this is to generate all possible boards by replacing for each :e the player we want to see win. Then computing the coordinates for which it indeed worked.

(defn win? [b] (letfn [(w [[[a b c] [d e f] [g h i]] p] (or (= p a b c) (= p d e f) (= p g h i) (= p a d g) (= p b e h) (= p c f i) (= p a e i) (= p c e g)))] (cond (w b :x) :x (w b :o) :o :else nil))) (defn win [p b] (let [n (-> b first count)] (->> (for [x (range n) y (range n)] [(get-in b [x y]) [x y]]) (filter (fn [[e _]] (= :e e))) (map (fn [[_ v]] [(win? (assoc-in b v p)) v])) (filter (fn [[w _]] (= p w))) (map second) (into #{}))))

Simply, I pipe these different computation steps:

- I compute all the values for all possible coordinates
- filter on the value :e for each coordinates
- replace the empty entries by the current player to play and compute the winner of the result board
- filter on the winner which must be the current player
- retrieve only the coordinates
- reduce them in a set

and voila, tests ok.

## Improvments

From this on, I realised that most of those steps could be done directly with the initial list comprehension for. So here it goes:

(defn w? [b] (letfn [(w [[[a b c] [d e f] [g h i]] p] (or (= p a b c) (= p d e f) (= p g h i) (= p a d g) (= p b e h) (= p c f i) (= p a e i) (= p c e g)))] (cond (w b :x) :x (w b :o) :o :else nil))) (defn win [p b] (let [n (-> b first count) r (range n)] (set (for [x r y r :let [v [x y] e (get-in b v)] :when (and (= :e e) (= p (-> b (assoc-in v p) w?)))] v)))) (fact (win :x [[:o :e :e] [:o :x :o] [:x :x :e]]) => #{[2 2] [0 1] [0 2]}) (fact (win :x [[:x :o :o] [:x :x :e] [:e :o :e]]) => #{[2 2] [1 2] [2 0]}) (fact (win :x [[:x :e :x] [:o :x :o] [:e :o :e]]) => #{[2 2] [0 1] [2 0]}) (fact (win :x [[:x :x :o] [:e :e :e] [:e :e :e]]) => #{}) (fact (win :o [[:x :x :o] [:o :e :o] [:x :e :e]]) => #{[2 2] [1 1]})

source: 119

Nice !

How about some core.logic and bench for improvements over huge grids ? cf. https://gist.github.com/4686830

Hi,

As soon as I can, I’ll go and check on how to make that happen!