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

Costello, Roger L.

18 Mar 2013 18 Mar '13

11:54 a.m.

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

Show replies by date

Peter Hall

18 Mar 18 Mar

3:49 p.m.

New subject: 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Lyndon Maydwell

11:16 p.m.

New subject: A good data structure for representing a tic-tac-toe board?

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/TicTacToe On 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Peter Hall

19 Mar 19 Mar

8:32 a.m.

New subject: A good data structure for representing a tic-tac-toe board?

Ah yes, that is nicer! I got too used to the limitations of the other languages I use :) Peter On 19 March 2013 03:16, Lyndon Maydwell wrote:

...

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/TicTacToe

On 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Brent Yorgey

18 Mar 18 Mar

4:59 p.m.

New subject: A good data structure for representing a tic-tac-toe board?

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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

emacstheviking

19 Mar 19 Mar

5:57 a.m.

New subject: A good data structure for representing a tic-tac-toe board?

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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

KC

11:36 p.m.

New subject: A good data structure for representing a tic-tac-toe board?

You may want more than one data structure. For example, one for machine use and another for display to the user. Since your data structure is "relatively" small, lists should be fast enough and strings are lists. On Mon, Mar 18, 2013 at 8:54 AM, 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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- -- Regards, KC

4444

Age (days ago)

4446

Last active (days ago)

List overview

Download

6 comments

6 participants

participants (6)

Brent Yorgey
Costello, Roger L.
emacstheviking
KC
Lyndon Maydwell
Peter Hall