A TicTacToe solution

An anonymous reader offers this solution:

class TicTacToe {
    constructor() {
        this.turns = []
        this.board = new Array(9).fill(0)
        this.winner
        this.wins = {
            0: { 1: { 2: true }, 3: { 6: true }, 4: { 8: true } },
            1: { 4: { 7: true } },
            2: { 5: { 8: true }, 4: { 6: true } },
            3: { 4: { 5: true } },
            6: { 7: { 8: true } },
        }
        this.cellMap = {
            0: '_',
            1: 'X',
            2: 'O',
        }
    }

    print() {
        console.log('v'.repeat(7), 'turn', this.turns.length)

        this.board
            .map(c => this.cellMap[c])
            .join('')
            .match(/.{3}/g)
            .forEach(r => console.log(r))
    }

    takeTurn(t) {
        if (this.winner) {
            throw new Error('game is over')
        } else if (![1, 2].includes(t.state)) {
            throw new Error('invalid state')
        } else if (t.state === this.turns.slice(-1)[0]?.state) {
            throw new Error('not your turn')
        } else if (t.x < 0 || t.x > 2 || t.y < 0 || t.y > 2) {
            throw new Error('out of bounds')
        } else if (this.turns.find(turn => turn.x === t.x && turn.y === t.y)) {
            throw new Error('cell occupied')
        }

        this.board[t.x * 3 + t.y] = t.state
        const marks = this.board.reduce(
            (a, v, i) => (v === t.state ? [...a, i] : a),
            [],
        )
        const combos = combine(marks, 3)
        for (let i = 0; i < combos.length; i++) {
            const [a, b, c] = combos[i]
            if (this.wins[a] && this.wins[a][b] && this.wins[a][b][c]) {
                this.winner = this.cellMap[t.state]
                break
            }
        }

        this.turns.push(t)
        this.print()
        if (this.winner) return console.log('WINNER', this.winner)
    }
}

function combine(n, k) {
    let set
    if (typeof n == 'object') {
        set = n
        n = n.length
    }
    const result = []
    const combos = []
    const recurse = start => {
        if (combos.length + (n - start + 1) < k) {
            return
        }
        recurse(start + 1)
        combos.push(start)
        if (combos.length === k) {
            result.push(
                set
                    ? combos
                        .slice()
                        .map(c => set[c - 1])
                        .sort()
                    : combos.slice(),
            )
        } else if (combos.length + (n - start + 2) >= k) {
            recurse(start + 1)
        }
        combos.pop()
    }
    recurse(1, combos)
    return result
}

const t = new TicTacToe()
t.takeTurn({ state: 1, x: 0, y: 0 })
t.takeTurn({ state: 2, x: 1, y: 0 })
t.takeTurn({ state: 1, x: 2, y: 2 })
t.takeTurn({ state: 2, x: 1, y: 2 })
t.takeTurn({ state: 1, x: 0, y: 2 })
t.takeTurn({ state: 2, x: 1, y: 1 })

I've reproduced it here because Google strips the leading whitespace out of the comments section. I didn't have the original indentation, so I just asked Emacs to indent it.

---

It being an unsolicited submission, I'll have the gall to make an unsolicited critique.

From the standpoint of the original point of the question, the code demonstrates that the author can write coherent, runnable programs. Many of the candidates I interviewed could not get this far. That said, there is room for improvement.

My biggest concern is with the complexity of the code. Let me focus on the combine procedure for the moment. It took me some time to figure out what on earth it was trying to accomplish. It is given a list of the positions for a particular player during the game. So if the game looked like this:

 X | O | X
---+---+---
   | X | X
---+---+---
 O | O |   

the list of positions for X would be 0, 2, 4, 5. combine is also given a number k. It is to return a list of all the k-tuples that can be made from the list of positions. If k were 3 in this example, it would return (0, 2, 4), (0, 2, 5), (0, 4, 5), (2, 4, 5).

Take a moment to test your recursion skills by coding this up.

---

We can observe this recursion: the solution consists of the first element paired with all (k-1)-tuples of the remaining elements

(map 'list (lambda (s) (cons (car elements) s)) (combine (cdr elements) (- k 1)))

plus all the solutions that don't involve the first element

(combine (cdr elements) k)

There are two base cases: if k is zero, there is a single solution: the zero-tuple '(). If there are no elements, we cannot choose k of them and there are no solutions. Putting this together we get this:

(defun combine (elements k)
   (cond ((zerop k) (list '()))    ; a list of one solution, the zero-tuple
         ((null elements) (list))  ; a list of no solutions
         (t (append (map 'list (lambda (s)
                                 (cons (car elements) s))
                         (combine (cdr elements) (- k 1)))
                    (combine (cdr elements) k)))))

I'll leave it to the reader to translate this back into Javascript.

The author of the original code seems to have gotten lost in the mechanics of constructing solutions. The variable combos is pushed and popped as the recursive calls are made. This means we are keeping track of the recursion both through the recursive flow control and through mutation and backtracking. I find mutation and backtracking harder to understand than recursion because you have to keep track of when exactly things are being mutated.

As I mentioned in the previous post, I was less concerned with the details of how the program worked than I was with whether the candidate could take a “word problem” and turn it into something that works. This approach — generating triplets of positions and seeing if they are winning — works. However, I find overall that it is a bit too complex and the procedure combine is confusing.