353. Design Snake Game

Posted on | Edited on | Views: 1

LeetCode

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 class

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
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
93
class 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);
        }

        @Override
        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;
        }
        
        @Override
        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.Point

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
import 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
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
/* <- Can't use this code because can't override the equals method in array ->
class SnakeGame {
    // 2D position info is encoded to 1D and stored as two copies
    Set<int[]> set; // this copy is good for fast loop-up for eating body case
    LinkedList<int[]> 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 int[] { 0, 0 }); // intially at [0][0]
        body = new LinkedList<>();
        body.addLast(new int[] { 0, 0 });
    }

    public int move(String direction) {
        // case 0: game already over: do nothing
        if (score == -1) {
            return -1;
        }

        // compute new head
        int[] oldHead = body.getLast();
        int[] newHead = new int[] { oldHead[0], oldHead[1] };
        switch (direction) {
        case "U":
            newHead[0]--;
            break;
        case "D":
            newHead[0]++;
            break;
        case "L":
            newHead[1]--;
            break;
        default:
            newHead[1]++;
        }

        int[] tail = body.getFirst();
        // case 1: out of boundary or eating body
        set.remove(tail);
        if (newHead[0] < 0 || newHead[0] == height || newHead[1] < 0 || newHead[1] == width || 
            set.contains(newHead)) {
            return score = -1;
        }

        // add head
        set.add(newHead);
        body.addLast(newHead);
        // case 2: eating food, keep tail
        if (foodIndex < food.length && newHead[0] == food[foodIndex][0] && newHead[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;
    }
}*/
0%