Programming Mini-Challenge: TicTacToeBot

The smallest solution I could come up with in Python:

g=int
print "#OX"[sum((v=="XXX")*2+(v=="OOO")for v in[b[g(i)::g(n)][:3]for i,n in zip("00012236","34132311")])]

Tested pretty thoroughly. Produces wrong answers with multiple winning rows on the board, but should be correct with one winning row. Board goes in B.

I didn't expect to be the first one, but here's some Python, and running with the sample data.

There is a finite set of winning combinations. I loop over those, convert them to array indexes, and check if all those indexes are the same in the passed data (and not #). My first solution was using Python's great slice syntax, but switched to this approach when I was writing out the test cases; figured it was an easier visual representation of what was going on.

Slightly off topic, but maybe a thread for planning/scheduling these threads would be useful? I (and probably others) have some ideas, and it’s probably best we post the challenges a few days apart to give people time to work on them.

@Soptik

Wow, I actually did this about a week ago because I was making multiplayer tictactoe with python, in order to learn ncurses and how to communicate between scripts with sockets. My solution isn't very clean. My board was represented as a 2d array so I'll just convert the string to that and reuse my old solution. I used all() to check for vertical and horizontal wins but couldn't think of a good way for diagonals so I just checked them manually.

https://gist.github.com/clonex10100/dca06673ba90c9281f9989a7d179b143

Aight, here's a funky Kotlin solution, written functionally. I'm treating each group of three symbols as a mathematical function, and I'm trying to find whether its slope is linear. If it is, then we've got a winner. It took me a while and I had a nice time, looking forward to more of these!

One of my biggest problems with programming is that "I see all these programming challenges and don't know how to do them without using if()s!". And I don't know how to progress beyond - it seems there are only two types of programming tutorials online, those that don't allow you to do what you want to do by forcing you to do what the tutorial wants to do (which, sometimes, is wrong) - e.g. Codecademy, Udemy. These tutorials reek of "do this, and you might get a working program" (Especially Codecademy- I started with it, felt I was going nowhere, learnt from MDN instead, and found a great many errors Codecademy was making me write, that don't actually work correctly in a real environment) , instead of "why".
And the other type is too terse for beginners - frequently requiring a computer science background.
What I want is something like MDN's learning area (I greatly admire the "We aren't here to promote you to expert, we are here to promote you to comfortable" philosophy). Unfortunately, MDN only teaches webdev, not skills required for these programming challenges.
Does anyone have such a tutorial or guide that covers these skills, or has a rebuttal for my frustration with such "what and not why" tutorials?

Time for some fun!

WARNING: This is much longer than I expected, because the problem actually has more depth than I expected.

First, I needed to establish some tests. There's three ways of winning, that I can tell:

1. Have a whole row
2. Have a whole column
3. Have a diagonal

These rules apply even in a tie, as you can consider absences as a third player, and still get the correct results.

So... Tests!

Winning row:

000
X##
#X#

000X###X#

Unfortunately, this reveals a problem. Here, three zeroes also triggers three hashes later, because of the compression.

Which means # can't always be considered a player.

This sent me down a spiral - a brute force approach to solving winners and losers and ties in ticetactoe could take a considerable number of loops to solve, and I don't like that at all.

So how else have people solved it?

Turns out it's been solved using a bunch of algorithms that are familiar to me. Tree shaking, alpha reduction, and other heuristics. Basically, all the stuff we use to solve safety in programming languages.

This changed my tactic. Originally I was just going to write some shellscript, and then try to minimise it a bit, practice some codegolf.

Instead of finding a clever way to examine the problem, I decided to bruteforce it as quickly as possible. Afterall, there's only a few options for winning.

But, I needed a few more test cases than just the one given, so I could ensure it is accurate.

void test(const char* str, char res) {
  if(solve(str) == res) {
    printf("%s", "Pass");
  } else {
    printf("%s", "Fail");
  }
}

int main(int argc, char* argv[]) {
  test("O#XXXOO##", '#');
  test("X#OOOXX##", '#');
  test("XXX#OO##O", 'X');
  test("OOO#XX##X", 'O');
  test("X#O#XOO#X", 'X');
  test("O#X#OXX#O", 'O');
}

I can refactor that later, so we just deal with assurances, and can take user input, but for now, we need to create the elusive char solve(const char* str).

char solve(const char* str) {
  if(str[0] == 'X' && str[1] == 'X' && str[2] == 'X' ||
  str[0] == 'X' && str[3] == 'X' && str[6] == 'X' ||
  str[0] == 'X' && str[4] == 'X' && str[8] == 'X' ||
  str[1] == 'X' && str[4] == 'X' && str[7] == 'X' ||
  str[2] == 'X' && str[5] == 'X' && str[8] == 'X' ||
  str[2] == 'X' && str[4] == 'X' && str[6] == 'X' ||
  str[3] == 'X' && str[4] == 'X' && str[5] == 'X' ||
  str[6] == 'X' && str[7] == 'X' && str[8] == 'X') {
    return 'X';
  } else
  if(str[0] == 'O' && str[1] == 'O' && str[2] == 'O' ||
  str[0] == 'O' && str[3] == 'O' && str[6] == 'O' ||
  str[0] == 'O' && str[4] == 'O' && str[8] == 'O' ||
  str[1] == 'O' && str[4] == 'O' && str[7] == 'O' ||
  str[2] == 'O' && str[5] == 'O' && str[8] == 'O' ||
  str[2] == 'O' && str[4] == 'O' && str[6] == 'O' ||
  str[3] == 'O' && str[4] == 'O' && str[5] == 'O' ||
  str[6] == 'O' && str[7] == 'O' && str[8] == 'O') {
    return 'O';
  } else {
    return '#';
  }
}

Obviously there is some edge-case handling I haven't done here. For instance, solve prefers X to win. And a board without a valid input would result in strange behaviour. But, that's not something solve needs to deal with. Input validation could happen somewhere else.

However, our little test cases pass.

But... Time for a little optimisation, because there's a few obvious things we can do.

The first being, remove that repetition in solve.

Then we can remove our testcases and add a little user input.

Which leaves us with this as the final expression:

#include <stdio.h>

int solve_for(const char* str, char check) {
  return str[0] == check && str[1] == check && str[2] == check ||
  str[0] == check && str[3] == check && str[6] == check ||
  str[0] == check && str[4] == check && str[8] == check ||
  str[1] == check && str[4] == check && str[7] == check ||
  str[2] == check && str[5] == check && str[8] == check ||
  str[2] == check && str[4] == check && str[6] == check ||
  str[3] == check && str[4] == check && str[5] == check ||
  str[6] == check && str[7] == check && str[8] == check;
}

char solve(const char* str) {
  if(solve_for(str, 'X')) {
    return 'X';
  } else
  if(solve_for(str, 'O')) {
    return 'O';
  } else {
    return '#';
  }
}

int main(int argc, char* argv[]) {
  char data[9];
  if (fgets(data, sizeof data, stdin)) {
    printf("%c", solve(data));
  }
}

I'd find a pattern to remove the monstrous comparison in solve_for, but it's 2am.

So, there you have it. A little C solver, incredibly stupid, but rather fast as the whole thing is basically bitshifts.

In thinking about this, and solutions that have already been presented, I thought I would take a slightly different approach that extends (or at least clarifies) some parts of the problem.

The basic problem is to take an input, in a particular format, to be interpreted as a game state, and from that game state, determine whether a player has won, and if so, which.

However, a player has only won if the game has been played correctly: if they cheated so as to create an impossible game state, they should not be seen as having won. Similarly, it's also possible that the input is either an impossible game state, or simply not a valid format at all.

To cover all inputs, I add an additional output option, "!". Now, I want a function that, for a given input string, returns:

• '#' if neither player has won,
• 'X' or 'O', respectively, if that player has won.
• '!' if either the input is not a game state at all, or is not a valid game state.

Because of the mechanics of tic-tac-toe, a game state is only valid if (with the assumption that either player may start first)

1. there are either the same number of Xs and Os, or they differ in number by 1, and
2. there are winning lines (though potentially more than one) for at most one player.

Thus, I need to check:

1. Is the format correct at all? Is it the right length, and does it contain no characters other than the correct three characters?
2. Is there at least one winning line for a player?
3. Are the number of Xs and Os within valid limits?
4. Are there winning lines for both players, making the state invalid?

Note that the length must be checked before slicing up the string, to avoid errors for invalid input.

With this, trying to keep a short but not ultra-shortened program, and incorporating @Zekka's clever slicing, I get

def gameresult(s):
    if len(s)!=9: return '!'
    b = [s[int(i)::int(n)][:3] for i,n in zip("00012236","34132311")]
    return '#XO!'[('XXX' in b) | 2*('OOO' in b) | \
           3*((abs(s.count('X')-s.count('O')) > 1) | \
           (set(s)-set('#XO')!=set()))]

Figured I'd post a solution in Javascript, was fun to see how I would approach it. I wanted to improve on the "check all eight lines and see if any match" solution, so I decided to modify it slightly. I reasoned that, if a winning row exists, it must pass through one of three spots. The center, or either of two opposite corners. The script checks those three spots and, if they have a mark in them, checks if a row exists that passes throw it. If a valid row exists, it's immediately returned.

const valid = {
    // Each key represents a starting spot
    4: [ // Each item represents the remaining two spots in a row
        [0, 8],
        [1, 7],
        [2, 6],
        [3, 5]
    ],
    0: [
        [1, 2],
        [3, 6]
    ],
    8: [
        [2, 5],
        [6, 7]
    ]
}

function checkForWinner(board) {
    for(const testSpot of Object.keys(valid)) {
        // Continue check if test spot is not empty
        if(board[testSpot] !== "#") {
            const player = board[testSpot];
            // Check each row that passes through test spot
            for(const checkSpots of valid[testSpot]) {
                if(board[checkSpots[0]] === player && board[checkSpots[1]] === player) {
                    return player;
                }
            }
        }
    }
    // Alternatively, return "#" and forgo the check later on
    return false;
}

const boardString = process.argv[2];
const board = boardString.split("");
const winner = checkForWinner(board);
console.log(winner ? winner : "#")

The script can be run by calling
node check "O#XXXOO##"

It's not exactly short, but I'm happy with how I solved it.

Javascript solution

Go solution

Thanks @Celeo for the test data!

I'm also going to try this in Go and Rust at some point, I need to practice them more often.

Alright, I got a little bored and decided to go beyond the basic challenge and added some amount of playable functionality. The opponent strategy isn't fully implemented yet--it's just a simple winning move vs. blocking move vs. open square check right now--but I plan to change that later. In fact, it's still a bit of a work in progress in general, but it's after 1am and I need to quit being an idiot and actually get some sleep before work in the morning. It's in PHP and thus not really designed to be used in an interactive shell session of some kind, but whatever.

I have a few test cases to showcase importing and computing a winner, though, so it works as an over-engineered solution for this challenge.

GitLab Snippet

Online PHP Sandbox

My quick-and-dirty JavaScript solution. I suppose there are more elegant ways to detect horizontal/vertical/diagonal lines in the grid, but since there are only eight possible win conditions I just hard-coded them.

function findWinner(board){
	let state = board.split('');
	let lines = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];
	let winner = '#';
	for(const line of lines){
		if(state[line[0]] === state[line[1]] && state[line[1]] === state[line[2]])
			winner = state[line[0]];
	}
	return winner;
}

I could probably make this a lot smaller but this wasn't a golfing challenge, was it?

I guess I am a little late, but here is yet another C solution:

#define a(x) int x=0;for(;*n[1];n[1]++)x=4*x|*n[1]==*#x;x*=0x41040404440015;x&=x*2&0xa80080080020820;
main(z,n)char**n;{a(O)a(X)return O?79:X?88:35;}

This basically converts the field to a base 4 number and then does some magic with some constants, for O and then for X, and returns the solution as the return value of the program. The string is given as the first argument to the program.

Figuring out how these constants work is left as an exercise for the reader.

Edit: also, here is a naive implementation in gnu sed -r:

s/.*(O|X)..\1..\1.*|^(...)*(O|X)\3\3.*|(O|X)...\4...\4|..(O|X).\5.\5../\1\3\4\5/;s/..+/#/

Edit 2: Because this challenge is fun, here is another solution using GNU APL:

↑'OX#'/⍨1,⍨'OX'{∨/(16<2⊥⌽5⍴x∧⊖⌽x),∧/(⍉x)⍪x←3 3⍴⍺=⍵}¨⊂⍞

To clarify, we are only checking to see if a winning move has already been made, correct? We don't care if one player will win, only whether or not one player has won, if that makes sense.

My solution wasn't anything new or interesting compared to the other C solutions, so I decided to make it so it could take piped input and work with that. The code is below:

#include <stdio.h>

void boardCheck(char input[20]);

int main(int argc, char **argv)
{
    int gameNum = 1;
    printf("Player 1 is X, player 2 is O\n");
    while(!feof(stdin))
    {
        printf("Game %d: ", gameNum);
        char inputString[20];
        scanf("%20c", inputString);
        boardCheck(inputString);
        printf("\n");
        gameNum++;
    }   
}


void boardCheck(char input[20])
{
    int board[3][3];
    int count = 0;
    for(int i = 0 ; i < 3 ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            if(input[count] == '#')
                board[j][i] = 0;
            else if(input[count] == 'X')
                board[j][i] = 1;
            else
                board[j][i] = 2;
            count++;
        }
    }
    for(int i = 0 ; i < 3 ; i++)
    {
        if((board[0][i] == board[1][i]) && (board[1][i] == board[2][i]) && (board[0][i]))
        {
            printf("Player %d wins!", board[0][i]);
            return;
        }
    }

    for(int j = 0 ; j < 3 ; j++)
    {
        if((board[j][0] == board[j][1]) && (board[j][1] == board[j][2]) && (board[j][0]))
        {
            printf("Player %d wins!", board[j][0]);
            return;
        }
    }

    if((board[0][0] == board[1][1]) && (board[1][1] == board[2][2]) && (board[0][0]))
    {    
        printf("Player %d wins!", board[0][0]);
        return;
    }

    else if((board[2][0] == board[1][1]) && (board[1][1] == board[0][2]) && (board[2][0]))
    {
        printf("Player %d wins!", board[2][0]);
        return;
    }
    printf("There is no winner.");
}

Then with @Celeo's test data in a text file, I run the program by calling cat test.txt | ./TicTacCheck.out.