29 votes

Programming Mini-Challenge: TicTacToeBot

I've seen the programming challenges on ~comp as well as quite a few users who are interested in getting started with programming. I thought it would be interesting to post some 'mini-challenges' that all could have a go at. I'm certain that many of you might find these pretty straight forward, but I still think there's merit in sharing different approaches to simple problems, including weird-and-wonderful ones.

This is my first post and I'm a maths-guy who dabbles in programming, so I'm not promising anything mind-blowing. If these gain any sort of traction I'll post some more.

Starting of with...


TicTacToeBot


Info

You will be writing code for a programme that will check to see if a player has won a game of tic-tac-toe.


Input

The input will be 9 characters that denote the situation of each square on the grid.

  • 'X' represents the X-player has moved on that square.
  • 'O' represents the O-player has moved on that square.
  • '#' represents that this square is empty.

Example:

|O| |X|
|X|X|O|    The input for this grid will be O#XXXOO##
|O| | |

Output

The expected output is the character representing the winning player, or "#" if the game is not won.

(e.g. The expected output for the example above is '#' since no player has won)


51 comments

  1. [7]
    Zekka
    Link
    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....

    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.

    11 votes
    1. eelnave
      Link Parent
      One line programs like this always make me feel like I need to change majors haha. Nice work!

      One line programs like this always make me feel like I need to change majors haha. Nice work!

      4 votes
    2. Zekka
      Link Parent
      While I'm at it, a gruesome C implementation! #define a(K,Y)c(Y)*c(Y+K)*c(Y+K+K) #define b(K,G)a(K,0)+a(K,G)+a(K,G+G) #define c(X)(h==z[1][X]) #define g(I)(h=I,b(1,3)+b(3,1)+a(4,0)+a(2,2))?I:...

      While I'm at it, a gruesome C implementation!

      #define a(K,Y)c(Y)*c(Y+K)*c(Y+K+K)
      #define b(K,G)a(K,0)+a(K,G)+a(K,G+G)
      #define c(X)(h==z[1][X])
      #define g(I)(h=I,b(1,3)+b(3,1)+a(4,0)+a(2,2))?I:
      main(h,z)char**z;{return g(88)g(79)35;}
      

      Invoke as ./a.out "X##X##X##". Tested on GCC, no optimizations.

      2 votes
    3. [2]
      NubWizard
      Link Parent
      If you don't mind me asking, could you break this code down for me? It's kind of blowing my mind haha

      If you don't mind me asking, could you break this code down for me?

      It's kind of blowing my mind haha

      2 votes
      1. Zekka
        Link Parent
        oh yeah sure. here are a series of simplifications and then i'll explain it: print "#OX"[sum((v=="XXX")*2+(v=="OOO")for v in[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")])] res =...

        oh yeah sure. here are a series of simplifications and then i'll explain it:

        print "#OX"[sum((v=="XXX")*2+(v=="OOO")for v in[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")])]
        
        res = sum((v=="XXX")*2+(v=="OOO")for v in[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")])
        print "#OX"[res]
        
        res = 0
        for v in[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")]:
          res += (v=="XXX")*2+(v=="OOO")
        print "#OX"[res]
        
        res = 0
        for v in[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")]:
          if v == "XXX":
            res += 2
          elif v == "OOO":
            res += 1
        print "#OX"[res]
        
        # This simplification on res only holds if there's only one winning row
        res = "#"
        for i,n in zip("00012236","34132311"): 
          v = b[int(i)::int(n)][:3] # slice from start index i, stepping by n -- take at most 3
          if v == "XXX":
            res = "X"
          elif v == "OOO":
            res = "O"
        print res
        

        As for the slice positions, just try screwing with a python string that contains "123456789" and you'll see what they target:

        "123456789"[0::3][:3] == "147"
        "123456789"[0::4][:3] == "159"
        "123456789"[0::1][:3] == "123"
        "123456789"[1::3][:3] == "258"
        "123456789"[2::2][:3] == "357"
        "123456789"[2::3][:3] == "369"
        "123456789"[3::1][:3] == "456"
        "123456789"[6::1][:3] == "789"
        
        1 vote
    4. [2]
      cge
      (edited )
      Link Parent
      A slight difficulty with this is that there are valid game states that have multiple winning rows, eg, "XXXOOXOOX", but which will fail in this code. Modifying it to use or and in, rather than...

      A slight difficulty with this is that there are valid game states that have multiple winning rows, eg, "XXXOOXOOX", but which will fail in this code. Modifying it to use or and in, rather than comparison and addition, one can save a few characters while covering, I think, every valid game state (behavior for invalid states is still undefined in general, though both players having winning lines will throw an error):

      y=[b[int(i)::int(n)][:3]for i,n in zip("00012236","34132311")];print"#OX"[("XXX"in y)*2|("OOO"in y)]
      

      (This is, obviously, only valid code in Python 2. The Python 3 version would cost two more characters because of the print. I also just use int, rather than replacing it, as replacing it actually uses a few more characters in total.)

      1 vote
      1. Zekka
        Link Parent
        oh yeah, this is a really good way to do it, thanks!

        oh yeah, this is a really good way to do it, thanks!

  2. [6]
    Celeo
    Link
    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...

    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.

    7 votes
    1. Mallard
      Link Parent
      Defining your win positions as strings and casting to int is very clean. I like it. My first solution used slices too and I agree that your second solution is nicer.

      Defining your win positions as strings and casting to int is very clean. I like it.

      My first solution used slices too and I agree that your second solution is nicer.

      3 votes
    2. [2]
      balooga
      Link Parent
      Nice, I just took a look at yours after posting mine and you had a very similar approach.

      Nice, I just took a look at yours after posting mine and you had a very similar approach.

  3. [3]
    what
    Link
    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...

    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

    5 votes
    1. Emerald_Knight
      Link Parent
      I've been pretty bad about not posting challenges lately, but my personal rule was to wait a week for someone else to come along in case they wanted to post a challenge, to avoid challenge...

      I've been pretty bad about not posting challenges lately, but my personal rule was to wait a week for someone else to come along in case they wanted to post a challenge, to avoid challenge fatigue. That's probably a bit excessive, however, and again was for my own purposes. A few days seems appropriate and anyone should feel free to post a challenge rather than believing that there's an authoritative voice here :)

      6 votes
    2. Soptik
      Link Parent
      Maybe, if it becomes an issue, then I or Emerald Knight (or you, if you want) will definitelly do something. But I don't think it's that bad now, however, maybe It'd be useful for people booking...

      Maybe, if it becomes an issue, then I or Emerald Knight (or you, if you want) will definitelly do something.

      But I don't think it's that bad now, however, maybe It'd be useful for people booking weeks to do challenge. I honestly didn't - and still don't - expect high participation in challenge creation, but @what sent me PM after my two wizards challenge that he would like to make challenge. I told him to wait few days and now someone was faster and already made a challenge.

      But as Emerald Knight said, few days (week at best) apart is enough, nobody "owns" the challenges and I don't expect that high participation to make some booking thread.

      2 votes
  4. min
    Link
    This took way longer than it should, but that's probably expected when learning a new language. I decided to do this challenge in Scala and made use of the grouped and sliding methods in the Scala...

    This took way longer than it should, but that's probably expected when learning a new language.

    I decided to do this challenge in Scala and made use of the grouped and sliding methods in the Scala standard library in order to split up a string that represented the board and check whether there were three 'X's or 'O's in a row. I couldn't think of anything better for diagonals, so I had to resort just manually checking the indices. I didn't feel that this challenge was large enough in size to need to setup a whole SBT project with ScalaTest, so I ran some simple checks within the same file. I used @Celeo 's test cases (Thanks!) and they all appear pass.

    Here's the source code in a gist: https://gist.github.com/mnxn/a84c2fdd2c7f99e40882f2efac1a8694

    And here it is in Scastie, so you can run it: https://scastie.scala-lang.org/rLeWuw13QGqfVaQZRNdz8g

    Thank you for the challenge, I needed something to do and I could certainly use more practice with Scala.

    4 votes
  5. [3]
    clone1
    (edited )
    Link
    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...

    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

    3 votes
    1. [2]
      Mallard
      Link Parent
      Line 9: if board[0][0] == board[1][1] == board[1][1] == board[2][2] Is the middle check needed?

      Line 9:

      if board[0][0] == board[1][1] == board[1][1] == board[2][2]
      

      Is the middle check needed?

      1 vote
      1. clone1
        Link Parent
        obviously not.... I think that when I made it i originally had if (board[0][0] == board[1][1] and board[1][1] == board[2][2]) but then I realized that an expression could have more than one =='s,...

        obviously not.... I think that when I made it i originally had if (board[0][0] == board[1][1] and board[1][1] == board[2][2]) but then I realized that an expression could have more than one =='s, and quickly swapped the and with =='s without thinking. Good catch

        1 vote
  6. [5]
    Yeet
    (edited )
    Link
    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...

    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!

    3 votes
    1. [2]
      Celeo
      Link Parent
      Nice work! I've been starting to pick up some Kotlin after using Java for many years; I'm really liking most of it.

      Nice work! I've been starting to pick up some Kotlin after using Java for many years; I'm really liking most of it.

      1 vote
      1. Yeet
        Link Parent
        Thanks! I'm digging Kotlin's extensive extension functions (no pun intended), it feels like piping with more flexibility. Their lambda system, data classes and short function syntax (fun () = ...)...

        Thanks! I'm digging Kotlin's extensive extension functions (no pun intended), it feels like piping with more flexibility. Their lambda system, data classes and short function syntax (fun () = ...) are pleasure to work with. Almost feels too good haha

        1 vote
    2. [2]
      Mallard
      Link Parent
      This was super interesting. Never seen Kotlin before, as far as I remember. I've been thinking about how the solutions in this thread would extend to n x n boards. This solution seems to have the...

      This was super interesting. Never seen Kotlin before, as far as I remember.

      I've been thinking about how the solutions in this thread would extend to n x n boards. This solution seems to have the least hard-coded parts. Cool.

      1 vote
      1. Yeet
        (edited )
        Link Parent
        Thank you. n×n boards sound like a cool challenge and I wanna try it now 😅 also my solution scales horribly on bigger boards because of combinationsOfThree(), so I'll try to think about something...

        Thank you. n×n boards sound like a cool challenge and I wanna try it now 😅 also my solution scales horribly on bigger boards because of combinationsOfThree(), so I'll try to think about something else. Maybe we can concurrently run a coroutine for each square on the board that crawls over its 8 surrounding squares and looks for a straight sequence of x symbol? Anyway, I already know what I'm doing tomorrow instead of working.

        1 vote
  7. [10]
    mount2010
    Link
    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...

    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?

    3 votes
    1. [4]
      Comment deleted by author
      Link Parent
      1. Emerald_Knight
        Link Parent
        This is really the way to go when learning. Get comfortable with the fundamentals, then build on top of them by trying new things.

        Start out with your program that does it with 1000 if statements, then go back and see if you can do it in a different way.

        This is really the way to go when learning. Get comfortable with the fundamentals, then build on top of them by trying new things.

        5 votes
      2. [2]
        mount2010
        Link Parent
        Thank you! I'm not good at Mathematics, I feel it's because of the way it's taught (again, the "what not why" method) :P

        Thank you! I'm not good at Mathematics, I feel it's because of the way it's taught (again, the "what not why" method) :P

        1. Emerald_Knight
          Link Parent
          Experimentation is definitely going to be your best friend. If you really want to get good at programming, become a scientist--modify the parameters of the experiment, hypothesize the expected...

          Experimentation is definitely going to be your best friend. If you really want to get good at programming, become a scientist--modify the parameters of the experiment, hypothesize the expected results, execute the experiment, compare the expected results to the actual results, analyze where you went wrong in your hypothesis (or in your implementation), rinse and repeat.

          Or, to simplify things, just be mindful of what you're doing, why you're doing it, and what you expect to happen as a result.

          If you're struggling to understand some code, consider commenting out different pieces, or isolating them in some other way, and observing what happens at that particular spot. The lazy way would be to just use a bunch of print statements. Alternatively, consider using some kind visualizing program that can step you through the execution of your code. For example, there's this website.

          What matters more than code, though, is learning how to solve problems in general. If you can describe how to solve a problem in intricate detail, then you can code a solution, even if it takes you a while to find the bits of code that you actually need.

    2. [3]
      Celeo
      Link Parent
      If you know how to chain together a bunch of if-elseif-else statements, then chain them together. It's better to get something working, even if you don't think it's as good as it could be, than to...

      If you know how to chain together a bunch of if-elseif-else statements, then chain them together. It's better to get something working, even if you don't think it's as good as it could be, than to get something fancy the first time. In the software development field, iterative development is just as important professionally as it is for learning: better to prove that something can be done first than to get everything done all at once.

      Getting "clever" with solutions stems from a couple of things:

      1. Knowing your language. This can come from tutorials and/or reading documentation. Know what your language can do, and then think about ways to apply it.

      2. Read other peoples' code. See how someone else writes a solution. If you don't understand some of it, ask. If you don't understand some of the syntax, look it up. Then, go back and see if it all makes sense.

      Learning to program is a difficult journey, and I think some sites/guides/recruiters/etc. try to make it sound like it's something that people can just pick up in a week and be good to go. It's challenging, but very much worth it (in my opinion). Keep at it!

      1 vote
      1. [2]
        mount2010
        Link Parent
        Haha, thank you! I feel like I am annoying other devs when I ask them about their code, especially since I'm autistic (I require much more questions to form a mental image of it, then I'm golden)....

        Haha, thank you! I feel like I am annoying other devs when I ask them about their code, especially since I'm autistic (I require much more questions to form a mental image of it, then I'm golden). There's the problem of finding such good code in the first place as well, and there's the problem of the formalities to do (I mean, the actual asking of questions - it is hard for an autistic!).
        And don't worry, I feel like I can accomplish what I want to do, just not cleverly. I've been programming for 4 years now :)

        2 votes
        1. Celeo
          Link Parent
          Yup, I get it. People should be able to explain their code, but it can be rough to ask a random person on the internet to do so. Fantastic!

          Yup, I get it. People should be able to explain their code, but it can be rough to ask a random person on the internet to do so.

          Fantastic!

    3. [3]
      super_james
      Link Parent
      Might be time to read a data structures & algorithms textbook or find a lecture series?

      Might be time to read a data structures & algorithms textbook or find a lecture series?

      1. [2]
        mount2010
        Link Parent
        Mind recommending some? It sounds like you have read some - what did you read?

        Mind recommending some? It sounds like you have read some - what did you read?

        2 votes
        1. Soptik
          Link Parent
          I'm not the one you're replying to and this is not textbook or lecture, but if you want to learn how to think like programmer and how to get better in creating your own algorithms, try it. Project...

          I'm not the one you're replying to and this is not textbook or lecture, but if you want to learn how to think like programmer and how to get better in creating your own algorithms, try it.

          Project Euler. It has a very long list of problems, from basic foobar to complex ones where I don't even get what they are asking me to do. It is solvable in any language and if you ever get stuck, it's easy to find tutorials and solutions to these problems.

          Project Euler

          1 vote
  8. s4b3r6
    Link
    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...

    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.

    3 votes
  9. cge
    Link
    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...

    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()))]
    
    3 votes
  10. Brayzure
    Link
    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...

    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.

    3 votes
  11. [2]
    what
    (edited )
    Link
    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.

    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.

    2 votes
    1. Celeo
      Link Parent
      Ooh I definitely want to see the Rust solution.

      Ooh I definitely want to see the Rust solution.

      2 votes
  12. Emerald_Knight
    Link
    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...

    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

    2 votes
  13. [3]
    balooga
    Link
    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...

    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?

    2 votes
    1. [2]
      Mallard
      Link Parent
      It wasn't a golfing challenge but by all means "golf" away!

      It wasn't a golfing challenge but by all means "golf" away!

      1. balooga
        (edited )
        Link Parent
        Okay, I took your challenge! Here's my golfed version: f=a=>{for(j of'012345678036147258048246'.match(/.{3}/g)){for(r=k=1,i=a[j[0]];3>k;k++)i!=a[j[k]]&&(r=0);if(r)return i}return'#'}; You can...

        Okay, I took your challenge! Here's my golfed version:

        f=a=>{for(j of'012345678036147258048246'.match(/.{3}/g)){for(r=k=1,i=a[j[0]];3>k;k++)i!=a[j[k]]&&(r=0);if(r)return i}return'#'};
        

        You can invoke it like this: f('O#XXXOX##')

        I'm using a number of tricks here, including splitting a string into an array of 3-char substrings, traversing those substrings by index as if they were arrays, evaluating integers as boolean, and declaring multiple vars with the same value. Using an arrow function means I don't have to write out the full keyword function. I was able to condense my three-way comparison into a tiny loop. Anyone feel free to let me know if you can make it even smaller!

        Edit: Removed some unnecessary semicolons for further reduction.

        Edit 2: Ran it through this minifier tool to find a couple more character savings!

        Edit 3: Realized I could trim it more if I pre-sliced the array but loaded it with integers, then cast them to strings later by prepending an empty string. Some of the values had leading zeroes so I just reordered them (since the order doesn't matter) so those would be preserved after conversion from the numeric type.

        f=b=>{for(j of[120,345,678,360,147,258,480,246]){for(j=''+j,r=k=1,i=b[j[0]];3>k;k++)i!=b[j[k]]&&(r=0);if(r)return i}return'#'}
        

        Edit 4: I had a niggling feeling I hadn't tested this thoroughly enough. Ran it against @Celeo's tester and found some bugs! Here's a slightly longer but working version:

        f=b=>{p=z='#';for(j of[120,345,678,360,147,258,480,246]){for(j+='',r=k=1,i=b[j[0]];3>k;k++)p!=i&&i==b[j[k]]&&r--;0>r&&(z=i)}return z}
        
  14. [3]
    mironimous
    (edited )
    Link
    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;...

    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⍴⍺=⍵}¨⊂⍞
    
    2 votes
    1. [2]
      Mallard
      Link Parent
      How do you set your IDE to work with pure dark magic?

      How do you set your IDE to work with pure dark magic?

      1. mironimous
        Link Parent
        If you want to see the dark magic, you'll obviously have to turn on the light theme.

        If you want to see the dark magic, you'll obviously have to turn on the light theme.

  15. [3]
    Gyrfalcon
    Link
    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.

    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.

    1 vote
    1. [2]
      Mallard
      Link Parent
      We only care which player, if any, has won - yes.

      We only care which player, if any, has won - yes.

      2 votes
      1. Gyrfalcon
        Link Parent
        Awesome, I'll get started on a solution.

        Awesome, I'll get started on a solution.

        2 votes
  16. Gyrfalcon
    Link
    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>...

    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.

    1 vote