练习Iterators的用法，对 [ Tic-Tac-Toe
](https://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Tic_tac_toe.svg/200px-
Tic_tac_toe.svg.png “Tic-tac-toe”) 进行翻转变换。
Learning objectives
- Iterating through different states
- Using indirection
Introduction
In the previous assignment, we had an optional question, Q3, to remove
symmetries in our list of games, when dealing with 3x3 games. In this
assignment, we will solve that problem in the general case, and use iteration
to do so.
Symmetries and iterators
When we created our list of games in Q2 of assignment 2, we added a lot of
solutions that were essentially identical, simply a symmetry of other games
already listed. For example, as we discussed in Q3 of assignment 2, there are
only 3 different ways to play the first move on a 3x3 Tic-Tac-Toe game. The
other 6 opening moves are equivalents by symmetry.
Let’s looks at symmetries in a nxm grid. Let’s first assume that n m, that is,
the grid is not square. In the case of a non-square grid, we have essentially
two symmetries: vertical flip, and horizontal flip (Figure 1).
For each such non-square nxm grid, there are up to 3 different but symmetrical
grids: the one obtain with a vertical symmetry, the one obtained with a
horizontal symmetry, and the one obtain with a combination of both symmetries
(Figure 2).
Something that will come handy is that it is possible to iterate through all
of these symmetries by repeatedly applying transformations, for example the
series horizontal, then vertical, then horizontal symmetry will give you all
four boards, as shown Figure 3.
Things are a little bit more complicated when the grid is square. In addition
to horizontal and vertical symme- tries, we have both diagonals, and well as
rotation (Figure 4). Each grid now gives us up to 7 other different but
symmetrical grids, shown Figure 5.
Here again, it is possible to iterate through all 8 different but symmetrical
equivalent (square) grids, for ex- ample with the sequence rotation-rotation-
rotation-horizontal symmetry-rotation-rotation-rotation, as illustrated Figure
6.
Step 1: Modifying Utils.java
From the discussion above, we can deduce that implementing the horizontal
symmetry, the vertical symmetry and the 90 degree (clockwise) rotation is
enough to get every possibly symmetrical grid, for both square and non square
grids. So we are going to add three methods in Utils.java to do this. In
keeping with our previous approach, the grids are going to be stored using a
one dimensional array. For reasons that will become clear very soon, we will
use an array of integers for our grid. Each of the three methods will have
three parameters: the number of lines and the number of columns of the grid,
and a reference to the array of integers representing the grid. You need to
implement the three class methods in the class Utils.java, that is:
- public static void horizontalFlip(int lines, int columns, int[] transformedBoard): performs a horizontal symmetry on the elements in the columnsxlines grid stored in the array reference by transformedBoard. The elements in the array referenced by transformedBoard are modified accordingly (see example below).
- public static void verticalFlip(int lines, int columns, int[] transformedBoard): performs a vertical symme- try on the elements in the columnsxlines grid stored in the array reference by transformedBoard. The elements in the array referenced by transformedBoard are modified accordingly (see example below).
- public static void rotate(int lines, int columns, int[] transformedBoard): rotates clockwise by 90 degrees the elements in the columnslines grid stored in the array reference by transformedBoard. The elements in the array referenced by transformedBoard are modified accordingly (see example below).
All three methods must check the provided inputs and handle all possible cases
as required. The class Utils.java comes with the following tests.
Running the test above should produce the following output:
% javac Utils.java
% java Utils
testing 2 lines and 2 columns.
[0, 1, 2, 3]
HF => [2, 3, 0, 1]
HF => [0, 1, 2, 3]
VF => [1, 0, 3, 2]
VF => [0, 1, 2, 3]
ROT => [2, 0, 3, 1]
ROT => [3, 2, 1, 0]
ROT => [1, 3, 0, 2]
ROT => [0, 1, 2, 3]
testing 2 lines and 3 columns.
[0, 1, 2, 3, 4, 5]
HF => [3, 4, 5, 0, 1, 2]
HF => [0, 1, 2, 3, 4, 5]
VF => [2, 1, 0, 5, 4, 3]
VF => [0, 1, 2, 3, 4, 5]
testing 3 lines and 3 columns.
[0, 1, 2, 3, 4, 5, 6, 7, 8]
HF => [6, 7, 8, 3, 4, 5, 0, 1, 2]
HF => [0, 1, 2, 3, 4, 5, 6, 7, 8]
VF => [2, 1, 0, 5, 4, 3, 8, 7, 6]
VF => [0, 1, 2, 3, 4, 5, 6, 7, 8]
ROT => [6, 3, 0, 7, 4, 1, 8, 5, 2]
ROT => [8, 7, 6, 5, 4, 3, 2, 1, 0]
ROT => [2, 5, 8, 1, 4, 7, 0, 3, 6]
ROT => [0, 1, 2, 3, 4, 5, 6, 7, 8]
testing 4 lines and 3 columns.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
HF => [9, 10, 11, 6, 7, 8, 3, 4, 5, 0, 1, 2]
HF => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
VF => [2, 1, 0, 5, 4, 3, 8, 7, 6, 11, 10, 9]
VF => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
testing 4 lines and 4 columns.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
HF => [12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3]
HF => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
VF => [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]
VF => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
ROT => [12, 8, 4, 0, 13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3]
ROT => [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
ROT => [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12]
ROT => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
%
Step 2: Generating every non-symmetrical nxm games
In assignment 2, we have already created a method that generates all the
possible games for a given grid size. That method would only add a game to the
list if the game was not equal to a game that was already there. Therefore,
from that viewpoint, all we need to do is slightly update that method to only
add a game if it is not equal or symmetrical to a game that is already there.
The new instance method equalsWithSymmetry of TicTacToeGame provides that
information. We just need to implement it, and the method
generateAllUniqueGames which is provided in the class ListOfGamesGenerator
will generate the list of lists we are looking for.
Indirection
In order to implement equalsWithSymmetry in TicTacToeGame, we will have to
loop through all the possible symmetrical games to see if we have a match. Of
course, we could simply apply the symmetries on the board itself. We would
thus apply transformations to the board until it either matches the board of
the game we are comparing it with (in which case it is symmetrical) or we run
out of symmetrical games (in which case it is not symmetrical).
However, changing the board itself might have unwanted side effects. For
example, imagine that we are printing the game to the user. What would happen
is that since the board is flipped through symmetrical equivalent games, the
game presented to the user might be a different but symmetrical game every
time, which would clearly not be good.
Therefore, we are going to introduce a level of indirection to compute our
symmetries. The board itself will remain unchanged, but we will use another
array that will map the indices of the board to their current symmet- rical
locations. We will use an instance variable, the array of integer
transformedBoard to store the indirection. Initially, since there is no
transformation, we always have board[i]==board[transformedBoard[i]]. But after
some symmetries have been applied to the game, transformedBoard[i] records
where the index i of the board is mapped to in the symmetry.
For example, imagine a 2x2 board. Before any symmetry, we have
transformedBoard[i]==i for 0 <= i < 4 , and thus
board[i]==board[transformedBoard[i]]. If we apply a vertical symmetry for
example, the index 0 is mapped to 1, 1 is mapped to 0, 2 is mapped to 3 and 3
is mapped to 2. board remains unchanged, and transformedBoard = {1,0,3,2}. So
if one want to know what is at index 1 of the board after symmetry, they have
to access board[transf ormedBoard [ 1
](https://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Tic_tac_toe.svg/200px-
Tic_tac_toe.svg.png “Tic-tac-toe”) ], which is thus board[0] before symmetry.
Iterating though symmetrical board
The second thing to do is to decide how we are going to systematically go
through all the symmetries of a given
- hasNext() returns true if and only if a call to the method next would succeed, and false otherwise.
- Each call to the method next finds the next symmetrical equivalent board in transformedBoard. It throws an exception IllegalStateException if it is called next more times than there are symmetries between two calls to the method reset.
- The method reset puts transformedBoard back in its original value, correponding the the unchanged board.
The following Java program illustrates the intended use for hasNext, next, and
reset (the method toStringTransformed of TicTacToeGame returns a String
representation of the tranformed game).
As pointed out ealier, we only need three transformations to iterate through
every symmetrical games: vertical symmetry (VSYM), horizontal symmetry (HSYM)
and rotation (ROT). We also need the ability to reset the game to its original
state, the identity transformation (ID).
Following a call to the method reset, each call to the method next changes the
orientation of the game according to the following list of operations: - for a non-square board: ID, HSYM,VSYM, HSYM
- for a square board: ID, ROT, ROT, ROT, HSYM ,ROT, ROT, ROT
You must add all the necessary instance variables to implement the methods:
hasNext, next and reset.
Finally, you need to implement the instance method boolean
equalsWithSymmetry(TicTacToeGame other), which returns true if and only if
this instance of TicTacToeGame and other are identical up to symmetry.
The class ListOfGamesGenerator has a method generateAllUniqueGames (already
implemented) which relies on equalsWithSymmetry to generate the list of games.
Here are a few sample runs:
% java TicTacToe
****
======= level 0 =======: 1 element(s) (1 still playing)
======= level 1 =======: 3 element(s) (3 still playing)
======= level 2 =======: 12 element(s) (12 still playing)
======= level 3 =======: 38 element(s) (38 still playing)
======= level 4 =======: 108 element(s) (108 still playing)
======= level 5 =======: 174 element(s) (153 still playing)
======= level 6 =======: 204 element(s) (183 still playing)
======= level 7 =======: 153 element(s) (95 still playing)
======= level 8 =======: 57 element(s) (34 still playing)
======= level 9 =======: 15 element(s) (0 still playing)
that’s 765 games
91 won by X
44 won by O
3 draw
It took 116ms.
% java TicTacToe 2 2 2
****
======= level 0 =======: 1 element(s) (1 still playing)
======= level 1 =======: 1 element(s) (1 still playing)
======= level 2 =======: 2 element(s) (2 still playing)
======= level 3 =======: 2 element(s) (0 still playing)
that’s 6 games
2 wonbyX
0 wonbyO
0 draw
It took 38ms.
% java TicTacToe 2 2 3
****
======= level 0 =======: 1 element(s) (1 still playing)
======= level 1 =======: 1 element(s) (1 still playing)
======= level 2 =======: 2 element(s) (2 still playing)
======= level 3 =======: 2 element(s) (2 still playing)
======= level 4 =======: 2 element(s) (0 still playing)
that’s 8 games
0 wonbyX
0 wonbyO
2 draw
It took 40ms.
Files
You must hand in a zip file (no other file format will be accepted). The name
of the top directory has to have the following form: a3_3000000_3000001, where
3000000 and 3000001 are the student numbers of the team members submitting the
assignment (simply repeat the same number if your team has one member). The
name of the folder starts with the letter “a” (lowercase), followed by the
number of the assignment, here 3. The parts are separated by the underscore
(not the hyphen). There are no spaces in the name of the directory. The
archive a3_3000000_3000001.zip contains the files that you can use as a
starting point. Your submission must contain the following files.
- README.txt
- A text file that contains the names of the two partners for the assignments, their student ids, section, and a short description of the assignment (one or two lines).
- CellValue.java
- GameState.java
- ListOfGamesGenerator.java - StudentInfo.java
- Test.java
- TicTacToe.java
- TicTacToeGame.java
- Transformation.java
- Utils.java
