# A good data structure for representing a tic-tac-toe board?

7 messages
Open this post in threaded view
|

## A good data structure for representing a tic-tac-toe board?

 Hi Folks, Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board:      'X' |   -----------------------   |   'O' with this string: "X  O" The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'. The problem with the representation is that it is difficult to determine when a player has won. Can you recommend a representation that makes it easy to: 1. determine when a player has won 2. identify cells that are filled or empty 3. mark an empty cell /Roger
Open this post in threaded view
|

## A good data structure for representing a tic-tac-toe board?

 Start with a data type for the cell values, instead of Char. Then use an Array of Arrays, containing those values. data Cell = Empty | O | X type Board = Array Int Cell Finding winning "rows" and "columns" is easy. Diagonals are slightly more complicated. Peter On 18 March 2013 15:54, Costello, Roger L. wrote: > Hi Folks, > > Currently I am representing a tic-tac-toe board as a string, with 'X' > denoting player 1 and 'O' denoting player 2. For example, I represent this > 2x2 game board: > >      'X'        | > ----------------------- >         |   'O' > > with this string: "X  O" > > The nice thing about that representation is that it is each to identify > which cells are filled or empty, and it is easy to mark a cell with an 'X' > or 'O'. > > The problem with the representation is that it is difficult to determine > when a player has won. > > Can you recommend a representation that makes it easy to: > > 1. determine when a player has won > 2. identify cells that are filled or empty > 3. mark an empty cell > > /Roger > > _______________________________________________ > Beginners mailing list > Beginners at haskell.org > http://www.haskell.org/mailman/listinfo/beginners> -------------- next part -------------- An HTML attachment was scrubbed... URL:
Open this post in threaded view
|

## A good data structure for representing a tic-tac-toe board?

 In reply to this post by Costello, Roger L. Consider the following game: Two players take turns choosing a number from 1-9 (inclusive).  Once a number has been chosen it cannot be chosen again.  The winner is the first player to have three of their selected numbers which sum to 15. Surprisingly, this game turns out to be isomorphic to tic-tac-toe, which can be seen by arranging the numbers from 1-9 in a magic square, such as 8 3 4 1 5 9 6 7 2 It is not hard to check that three distinct numbers from 1-9 sum to 15 if and only if they correspond to a tic-tac-toe win on the board above.  This means you can represent the state of the board as a pair of sets.  To check the state of a cell you look up the corresponding number from the board above in both sets.  To mark an empty cell you add the corresponding number to one of the sets.  To check whether a player has won, you list all size-3 subsets of their set and check whether any of them sum to 15. You may or may not agree that this fulfills your criteria, but at least it is cute. -Brent On Mon, Mar 18, 2013 at 03:54:58PM +0000, Costello, Roger L. wrote: > Hi Folks, > > Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board: > >      'X' |   > ----------------------- >   |   'O' > > with this string: "X  O" > > The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'. > > The problem with the representation is that it is difficult to determine when a player has won. > > Can you recommend a representation that makes it easy to: > > 1. determine when a player has won > 2. identify cells that are filled or empty > 3. mark an empty cell > > /Roger > > _______________________________________________ > Beginners mailing list > Beginners at haskell.org > http://www.haskell.org/mailman/listinfo/beginners
Open this post in threaded view
|

## A good data structure for representing a tic-tac-toe board?

 In reply to this post by Peter Hall If taking the array approach, I'd recommend using a single array indexed by the (x,y) position of the cell, this way neither direction has a greater implied significance. Diagonals should also be easier. Aside: Tony Morris wrote a very interesting exercise based on tic-tac-toe and it is available on Hackage: http://hackage.haskell.org/package/TicTacToeOn Tue, Mar 19, 2013 at 3:49 AM, Peter Hall wrote: > Start with a data type for the cell values, instead of Char. Then use an > Array of Arrays, containing those values. > > data Cell = Empty | O | X > type Board = Array Int Cell > > Finding winning "rows" and "columns" is easy. Diagonals are slightly more > complicated. > > Peter > > > > On 18 March 2013 15:54, Costello, Roger L. wrote: > >> Hi Folks, >> >> Currently I am representing a tic-tac-toe board as a string, with 'X' >> denoting player 1 and 'O' denoting player 2. For example, I represent this >> 2x2 game board: >> >>      'X'        | >> ----------------------- >>         |   'O' >> >> with this string: "X  O" >> >> The nice thing about that representation is that it is each to identify >> which cells are filled or empty, and it is easy to mark a cell with an 'X' >> or 'O'. >> >> The problem with the representation is that it is difficult to determine >> when a player has won. >> >> Can you recommend a representation that makes it easy to: >> >> 1. determine when a player has won >> 2. identify cells that are filled or empty >> 3. mark an empty cell >> >> /Roger >> >> _______________________________________________ >> Beginners mailing list >> Beginners at haskell.org >> http://www.haskell.org/mailman/listinfo/beginners>> > > > _______________________________________________ > Beginners mailing list > Beginners at haskell.org > http://www.haskell.org/mailman/listinfo/beginners> > -------------- next part -------------- An HTML attachment was scrubbed... URL:
Open this post in threaded view
|

## A good data structure for representing a tic-tac-toe board?

 In reply to this post by Costello, Roger L. Roger, Without writing any code, and still learning Haskell I personally don't see anything intrinsically wrong with using a String, it's simple, it works and what more can you ask from code than that! I would go so far as to add "\n" after each line so that you can print the status of the game to the console in one go, then checking for a winning line would be as simple as writing a function that takes as its input the String and a list of string offsets which make up a line, with the assumption that [0] is the first board position, [2] is the end of the first line and [3] contains the first "\n" character I would (pseudo-code / made up from keyboard, pebcak may apply) go for this approach: topLineWin     = checkLine myBoard  "O" [0,1,2]   -- did O win ? topleftDiagWin = checkLine myBoard  "X" [0,5,10]  -- did X win ? botLineWin     = checkLine my Board "X" [8,9,10]  -- did X win ? and so on. The implementation of checkLine is left as an exercise for the reader as they say but by using partial application you can make the code very readbable. I might even try this myself and post it back for a laugh. It's surprising sometime the difference between what you think you know and what you actually know! Some coding hints and thinking as I go... topLine = [0,1,2] topleftDiagWin = [0,5,10] etc. winnerO = checkLine myString "O" winnerX = checkLine myString "X" checkLine topLine playerCode -- did the top line win? ... By making the checkLine return a Bool then you can have a list of functions that you could then pass through the Data.List.all and make it something like this:   all [ winnerO topLine, winnerO botLine, ... etc] Just to make the array number clear, here is the complete board:          "\n" 0  1   2  3 4  5   6  7 8  9  10 10 All the best, that's no coding and pure thought for that so YMMV! Sean Charles. On 18 March 2013 15:54, Costello, Roger L. wrote: > Hi Folks, > > Currently I am representing a tic-tac-toe board as a string, with 'X' > denoting player 1 and 'O' denoting player 2. For example, I represent this > 2x2 game board: > >      'X'        | > ----------------------- >         |   'O' > > with this string: "X  O" > > The nice thing about that representation is that it is each to identify > which cells are filled or empty, and it is easy to mark a cell with an 'X' > or 'O'. > > The problem with the representation is that it is difficult to determine > when a player has won. > > Can you recommend a representation that makes it easy to: > > 1. determine when a player has won > 2. identify cells that are filled or empty > 3. mark an empty cell > > /Roger > > _______________________________________________ > Beginners mailing list > Beginners at haskell.org > http://www.haskell.org/mailman/listinfo/beginners> -------------- next part -------------- An HTML attachment was scrubbed... URL: