Avoid overriding of equals and hashCode methods
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66// import java.util.*;
public class SnakeGame {
//2D position info is encoded to 1D and stored as two copies
Set<Integer> set; // this copy is good for fast loop-up for eating body case
Deque<Integer> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
this.score=0;
set = new HashSet<>();
set.add(0); //intially at [0][0]
body = new LinkedList<>();
body.addLast(0);
}
public int move(String direction) {
//case 0: game already over: do nothing
if (score == -1) {
return -1;
}
// compute new head
int rowHead = body.peekLast() / width;
int colHead = body.peekLast() % width;
switch (direction) {
case "U" : rowHead--;
break;
case "D" : rowHead++;
break;
case "L" : colHead--;
break;
default : colHead++;
}
int head = rowHead * width + colHead; // hashcode, 2D -> 1D
//case 1: out of boundary or eating body
set.remove(body.peekFirst()); // new head is legal to be in old tail's position, remove from set temporarily
if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
return score = -1;
}
// add head for case2 and case3
set.add(head);
body.addLast(head);
//case2: eating food, keep tail, add head
if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]) {
set.add(body.peekFirst()); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
//case3: normal move, remove tail after adding head
body.removeFirst();
return score;
}
}
Overriding of equals and hashCode methods with Point class1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93class SnakeGame {
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
Point clonePoint() {
return new Point(this.x, this.y);
}
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof Point)) return false;
Point p = (Point) o;
if (p.x == this.x && p.y == this.y) return true;
return false;
}
public int hashCode(){
return x*width+y;
}
}
// 2D position info is encoded to 1D and stored as two copies
Set<Point> set; // this copy is good for fast loop-up for eating body case
LinkedList<Point> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
set = new HashSet<>();
set.add(new Point(0, 0)); // intially at [0][0]
body = new LinkedList<>();
body.addLast(new Point(0, 0));
}
public int move(String direction) {
// case 0: game already over: do nothing
if (score == -1) {
return -1;
}
// compute new head
Point oldHead = body.getLast();
Point newHead = oldHead.clonePoint();
switch (direction) {
case "U":
newHead.x--;
break;
case "D":
newHead.x++;
break;
case "L":
newHead.y--;
break;
default:
newHead.y++;
}
Point tail = body.getFirst();
// case 1: out of boundary or eating body
set.remove(tail);
if (newHead.x < 0 || newHead.x == height || newHead.y < 0 || newHead.y == width || set.contains(newHead)) {
return -1;
}
// add head
set.add(newHead);
body.addLast(newHead);
// case 2: eating food, keep tail
if (foodIndex < food.length && newHead.x == food[foodIndex][0] && newHead.y == food[foodIndex][1]) {
set.add(tail); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
body.removeFirst();
return score;
}
}
java.awt.Point1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64import java.awt.Point;
class SnakeGame {
// 2D position info is encoded to 1D and stored as two copies
Set<Point> set; // this copy is good for fast loop-up for eating body case
LinkedList<Point> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
set = new HashSet<>();
set.add(new Point(0, 0)); // intially at [0][0]
body = new LinkedList<>();
body.addLast(new Point(0, 0));
}
public int move(String direction) {
// case 0: game already over: do nothing
if (score == -1) {
return -1;
}
// compute new head
Point oldHead = body.getLast();
Point newHead = new Point(oldHead);
switch (direction) {
case "U":
newHead.x--;
break;
case "D":
newHead.x++;
break;
case "L":
newHead.y--;
break;
default:
newHead.y++;
}
Point tail = body.getFirst();
// case 1: out of boundary or eating body
set.remove(tail);
if (newHead.x < 0 || newHead.x == height || newHead.y < 0 || newHead.y == width || set.contains(newHead)) {
return -1;
}
// add head
set.add(newHead);
body.addLast(newHead);
// case 2: eating food, keep tail
if (foodIndex < food.length && newHead.x == food[foodIndex][0] && newHead.y == food[foodIndex][1]) {
set.add(tail); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
body.removeFirst();
return score;
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/* use list to avoid implementation of overriding equals and hashcode methods, but too complex.
class SnakeGame {
// 2D position info is encoded to 1D and stored as two copies
Set<List<Integer>> set; // this copy is good for fast loop-up for eating body case
LinkedList<List<Integer>> body; // this copy is good for updating tail
int score;
int[][] food;
int foodIndex;
int width;
int height;
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
set = new HashSet<>();
set.add(new ArrayList<>(Arrays.asList(0,0))); // intially at [0][0]
body = new LinkedList<>();
body.addLast(new ArrayList<>(Arrays.asList(0,0)));
}
public int move(String direction) {
// case 0: game already over: do nothing
if (score == -1) {
return -1;
}
// compute new head
List<Integer> oldHead = body.getLast();
List<Integer> newHead = new ArrayList<>(oldHead);
switch (direction) {
case "U":
newHead.set(0,newHead.get(0)-1);
break;
case "D":
newHead.set(0,newHead.get(0)+1);
break;
case "L":
newHead.set(1,newHead.get(1)-1);
break;
default:
newHead.set(1,newHead.get(1)+1);
}
List<Integer> tail = body.getFirst();
// case 1: out of boundary or eating body
set.remove(tail);
if (newHead.get(0) < 0 || newHead.get(0) == height || newHead.get(1) < 0 || newHead.get(1) == width || set.contains(newHead)) {
return -1;
}
// add head
set.add(newHead);
body.addLast(newHead);
// case 2: eating food, keep tail
if (foodIndex < food.length && newHead.get(0) == food[foodIndex][0] && newHead.get(1) == food[foodIndex][1]) {
set.add(tail); // old tail does not change, so add it back to set
foodIndex++;
return ++score;
}
body.removeFirst();
return score;
}
}*/
1 | /* <- Can't use this code because can't override the equals method in array -> |