Connect Four Programming Challenge Pt. 1

I recently had a programming challenge for an interview that required me to code a "functional" version of Connect 4 - namely that it could simulate the game via the following:

Simulate the board, and placement of pieces
Can display / represent the board in ASCIII format
Simulate the game state and alternation of turns between players
Check for victory condition

Simple enough. I was given ~2 hrs to design and implement this barebones version, and was asked not to necessarily design a UI for it. Here I discuss some of the thoughts and rationales behind some of my design decisions.

The Board

To start with, a default game of Connect Four has two players, on a 7x5 board that has a victory condition of 4 connected pieces.

However - the idea of hard coding values into this game, even for a programming challenge seemed short sighted. Though this probably wasn't the best decision for a time limited challenge, I decided to design my version with extendability and generalizability in mind. Thus the board is initialized by arguments (X,Y,N) with default values (7,5,4).

Since the main mode of operation on this board would be insertion of pieces by column (top down), I opted for simplest representation of a two dimensional array, column major.

Pieces

The most extensible form of this would be to allow for an arbitrary number of pieces, up to the same amount of players. This is where there is room for improvement - I hardcoded the state as constants (0, 1, 2) in the Board class to represent (Empty, P1, P2) respectively.

In the future, this should be its own generic enums class that can be extended to an arbitrary number of players, and should be its own variable owned by the board and passed in by the game.

Insertion of Pieces

Pieces must be inserted from the top down, and cannot be inserted arbitrarily to replace other pieces. The most analogous structure for this would naturally be a stack to represent the columns, but the tradeoff made for insertion simplicity would make the algorithm for verifying a win condition somewhat difficult (unless you modified the stack to allow for indexing and error checking, but at the point why bother?)

I made the choice to use a naive algorithm of checking from the bottom up each time for the first "empty" slot. This is fairly straightforward but may be cost prohibitive in a large board (O(y) accesses). Presumably if the board has followed consistent rules, there should be pieces at the bottom, and after the first empty slot all empty pieces above it. In the array, this is analogous to finding the first index of an "empty" piece followed by a bunch of empty repeats.

I did not do it here but the first free insertion point can be cached and incremented and at the cost of O(x) space but makes insertion an O(1) operation.

Board Representation

For a 2-hour programming challenge it wouldn't be prudent/feasible to design a full GUI (and in fact explicitly I was asked not to). A simple terminal representation (yes, technically a GUI, I know) would suffice.

Pieces are just the number that they are in the enum. (0 is empty, P1 is 1, and P2 is 2, vs Red and Black in the actual game). An empty board then, starts out as a grid of 0's

The first thought that I had was that you would want to know which column you wanted to insert into by inspection - it would be frustrating to insert blindly into a board and have to count vs. being able to see which columns corresponded to what number. There are line breaks to demarcate the difference between the column number and the piece representation (just numbers currently).

My naive implementation was written as follows:

A list of the number of columns joined by a single space (0...x-1)
A "-" character of the same length as the (0...x-1) row
Each piece represented by its enum value joined by a single space

However, while sufficient for small boards, this begins to break when either pieces are not represented by single digit characters (possible when > 9 players, different pieces, or when width > 11 as the columns become misaligned.

In the interest of extendability, this is not sufficient and needs to solved by having a more flexible form of alignment vs. assuming single digit characters separated by single spaces.

Format Strings to the Rescue

Format strings are great for generating strings procedurally! I needed a way to create a buffered space and center these strings within them so they'd align correctly! First, I needed to calculate the necessary width of this buffered space.

Minimizing imports

The decision for the maximum width of this space was pretty straightforward. This was breaking on large column sizes because the digits of these column headers were wider than expected. So the number of digits of the largest column size was the limit, so to speak. Note: This ignores the fact that pieces should also be allowed to grow with the number of plays and might be larger than column size. However, since player growth and piece size was ignored earlier in the design, they are also ignored here.

The answer is simple - it is the ceiling of logarithm base 10 of the column size - this gives you the number of digits. However, because the math library is not included by default in python, I wanted to minimize the number of imports and do it entirely in string processing. The same number can be achieved by simply taking the length of the string representation of the column size!

Format Strings All the Way Down

Format strings are themselves just strings, you can manipulate them and create them just like any other string! Using the width calculated above, I created a generic format string for one entry, and then joined them all with a single space. I then populated this wide format string with each row of the grid along with the column headers. This gives us a correct and flexible implementation string representation of the grid!

To be continued in Pt 2...