Tic-tac-toe: reflections on a classic programming challenge

Coding up a game such as Tic-tac-toe is a classic programming challenge, but one which I never took much more than passing interest.

I mean: I can see it is a good quick-start tutorial to a language/tool (e.g. React quick start). I also really enjoyed it when I did it for the first time. But after the first time, why do it again and again and again?

But recently I changed my mind. I had attended my 2nd London Clojure Dojo: one of the projects that was attempted was coding a programme to solve the New York Times Strands puzzle.

The rules of the game are simple. Given a grid of alphabets, find a “snake” through the grid that spells a word that correspond to a certain theme, e.g. the word “PUZZLE” below.

Two people attempted the project and the Dojo, and each gave a presentation afterwards. They used completely differently approaches: one starts with a dictionary, and for each entry, try to see if it is possible to make a word out of the grid. The other starts with a letter in the grid, and see if a word can be made out of it by snaking around.

It later struck me that the point for these challenges is not just finding any old way to solve the puzzle in as little time as can be done. Instead, it is seeing the many, many different ways of approaching the same issue, and comparing them with each other.

For example, even if we limit ourselves to plain HTML and JS, there must be so many ways to code up a 2-person tic-tac-toe game.

In the past, I would probably have started out trying to create a playable UI and then see how it goes. But another plan of attack, which ignores the UI altogether, is this.

Encode the grid by a 1 to 9 array (we start from 1 as opposed to 0, due the resemblance of the grid to a phone number dial).

In terms of the JS data structures, there are 3 arrays:

• an array representing the empty spaces. The starting point is [1, 2, 3, 4, 5, 6 , 7, 8, 9 ].
• an array representing Player 1’s circles. The starting point is []; each time player 1 chooses a space, the empty spaces array is spliced and the spliced element is pushed into the Player 1 array.
• ibid. for a Player 2 crosses.

On the HTML side:

• there is a paragraph displaying empty spaces array.
• there is a form for Player 1 to select his move. The available moves are the elements of the empty array. The submit button is enabled or disabled, depending on whether the length of the empty spaces array is even or odd.
• Ibid. for Player 2.

And finally in terms of the JS logic:-

• After each form submission, there should be a check on whether either the Player 1 array or the Player 2 array contains one of these winning combinations with every() and includes() (e.g. here)

[
  [1, 2, 3],
  [1, 5, 9],
  ...
]

But the above implementation (if correct) should be very scalable. There should be no fundamental difficulty expanding this to (say) have 3 different players (circles, crosses, and stars), or to have 4 x 4 spaces as opposed to 3 x 3. Of course, the winning condition needs to be modified: but the rest of the code doesn’t need to change.

This scalability consideration is the point of interest that I had missed and which probably motivates people to have a crack at these challenges again and again.