Java代写：ITI1121 Symmetries and Iterators

发表于   |   分类于

练习Iterators的用法，对Tic-Tac-Toe进行翻转变换。

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 ormedBoard1], 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