Design Snake game

https://discuss.leetcode.com/topic/110/design-snake-game

Design a Snake game on a device that has screen of width x height.

Initially the snake is at position (0,0) with length = 1 unit.

You are given a list of food's positions. When a snake eats the food, its length and the game's score both increase by 1.

Each food appears one after another. For example, the second food will not appear until the first food was eaten by the snake. Same with others.

class Snake {
    public Snake(int width, int height, List<int[2]> food) {

    }

    /**
     * @param direction U = Up, L = Left, R = Right, D = Down
     * @return The game's score after the move. Return -1 if game over.
     */
    public int move(char direction) {

    }
}

The list contains all food's positions. Initially the food appears at position food.get(0), only one food may appear at the screen at once. After the snake eats the first food, the second food will appear at position food.get(1), and the same for the third food and so on...

Each move controls the snake head's direction. So if moving the snake head in that direction causes the head to touch the snake's body, it results in game over.

It should be List<int[2]>. Each food is represent by an array of size 2, ary[0] = row, ary[1] = col.

Yes the food is given in the constructor. If the position of the food is occupied by the snake body then according to the rules, the snake's length and the game score immediately increase by one.

In real game you would generate randomly the next food's position, but I think you want a deterministic score after each move so it is easier to test.

valid move down
/###H
/###T
becomes
/####
/##TH
valid move up
/###T
/###H
becomes
/##TH
/####
valid move right
/ ####
/ ##HT
becomes
/ ###T
/ ###H
valid move left
/####
/TH##
becomes
/ T###
/ H###
invalid cross with screen borders

From my experience playing snake game, when the snake's head moves toward the food, the snake's tail does not move, which essentially grows the length by 1.

    public static class Node {
        int x;
        int y;
        Node pre;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int len, foodIdx;
    Node[][] screen;
    List<int[][]> food;
    Node head;
    Node tail;
    boolean over;

    public Snake(int width, int height, List<int[][]> food) {
        this.food = food;
        screen = new Node[width + 1][height + 1];
        head = new Node(0, 0);
        screen[0][0] = head;
        tail = head;
        len = 1;
        foodIdx = 0;
        over = false;
    }

    /**
     * @param direction
     *            U = Up, L = Left, R = Right, D = Down
     * @return The game's score after the move. Return -1 if game over.
     */
    public int move(char direction) {
        int x = head.x;
        int y = head.y;

        if ('U' == direction) {
            y++;
        } else if ('L' == direction) {
            x--;
        } else if ('R' == direction) {
            x++;
        } else if ('D' == direction) {
            y--;
        }

        if (!check(x, y)) {
            over = true;
            return -1;
        }

        move(x, y);
        len += eat(x, y);
        return len - 1;
    }

    private int eat(int x, int y) {
        if (food != null && food.size() > foodIdx) {
            int[][] f = food.get(foodIdx);
            if (f[x][y] > 0) {
                foodIdx++;
                return 1;
            } else {
                // delete tail node
                Node tmp = tail;
                tail = tail.pre;
                screen[tmp.x][tmp.y] = null;
            }
        }
        return 0;
    }

    private boolean check(int x, int y) {
        return (!over && x >= 0 && y >= 0 && x < screen.length && y < screen[0].length && screen[x][y] == null);
    }

    private void move(int x, int y) {
        Node n = new Node(x, y);
        screen[x][y] = n;
        head.pre = n;
        head = n;
    }

    public void print() {
        int[][] f = null;
        if (food != null && food.size() > foodIdx) {
            f = food.get(foodIdx);
        }

        for (int i = 0; i < screen.length; i++) {
            for (int j = 0; j < screen[0].length; j++) {
                if (f!=null && f.length > i && f[0].length > j && f[i][j] > 0) {
                    System.out.print("2");
                } else {
                    if (screen[i][j] != null) {
                        System.out.print("1");
                    } else {
                        System.out.print("0");
                    }
                }
            }
            System.out.println();
        }

    }

I mean the matrix “screen”, it's like a Sparse Matrix . most of time the snake's size is far less than the matrix's size. I can use LinkedHashMap or LinkedHashSet store the snake.

X. Solution

public class Snake { 
 enum Direction {
  Up,
  Down,
  Right,
  Left
 } 
 
 private Queue<int[]> foodList;
 private LinkedList<int[]> body;
 private Set<Integer> bodyIndex;
 private int width;
 private int height; 
 private int score;
 
 public Snake(int w, int h , List<int[]> food) {
  foodList = new LinkedList<>(food);
  width = w;
  height = h;
  body = new LinkedList<>();
  bodyIndex = new HashSet<>();
  body.add(new int[] {0,0});
  bodyIndex.add(0);
 }
 
 private int[] moveToCell(Direction dir, int[] head) {  
  int res[]  = Arrays.copyOf(head, 2);
  switch (dir) {
   case Up : res[0]--; break; 
   case Down : res[0]++; break; 
   case Left : res[1]--; break; 
   case Right : res[1]++; break; 
  }
  return res;
 }
 
 int move(Direction dir) {
  if (foodList.isEmpty())
   return  score;
  else {
   int[] currFood = foodList.peek();
   int[] next = moveToCell(dir, body.getFirst()); 
   if ((next[0] == width) || (next[0] < 0) || (next[1] == height) || (next[1] < 0))
    return -1;
   int index = next[0] * width + next[1];
   if(bodyIndex.contains(index))
    return -1;
   if (next[0] != currFood[0] || next[1] != currFood[1]) {
    int[] tail = body.removeLast();
    bodyIndex.remove(tail[0] * width + tail[1]);    
   }
   else
   {
    foodList.remove(); 
    score++;  
   }
   body.addFirst(next);
   bodyIndex.add(index); 
      
   return score;
  }
 }
}

By the way I think the food should not appear in any block that is occupied by the Snake. To see why this is so, imagine the food appear at (0,0) right at where the Snake is initially positioned. Since the Snake eats the food by default, in which direction does the Snake's tail grow?

You are right, in this case there will be ambiguity in where the tail grows.

 When you eat the food, the tail does not move. Otherwise you check if it touches the body (not including the tail/head). Then update the snake by removing the tail and insert it into the head.

In my code forgot to check if my next step is tail

I can change function "move" to check if the snake moves in cell occupied by its body only when this cell is not occupied by food.
I also think that if the player avoid moving to snakes body cells, the game will return -1 only when the snake tail is so large as the whole grid