Java ArrayList solution - All test cases passed (except four body collision test cases)


  • 0
    V

    Four test cases failed where the snake is colliding with itself. There are two ways around this, either I iterate over the ArrayList and make sure that the new head is not colliding with any of the exisiting snake body units. But that's an O(N) time solution. Or, I can use a hashmap but that's O(SCORE) space solution.

    Can anybody help me pick which would be appropriate or perhaps, even give a better solution to the problem?

    Thanks.

     public class SnakeGame {
            
            public class Pair{
                int w;
                int h;
                
                Pair(int width, int height)
                {
                    w = width;
                    h = height;
                }
                
                Pair(Pair obj)
                {
                    w = obj.w;
                    h = obj.h;
                }
            }
        
            /** Initialize your data structure here.
                @param width - screen width
                @param height - screen height 
                @param food - A list of food positions
                E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
                int width;
                int height;
                int food[][];
                int score = 0;
                List<Pair> snakeList;
                Pair foodLocation;
                int level = 0;
                
            public SnakeGame(int width, int height, int[][] food) {
                this.width = width;
                this.height = height;
                this.food = food;
                snakeList = new ArrayList<Pair>();
                Pair startPoint = new Pair(0, 0);
                snakeList.add(startPoint);
                getFoodLocation();
            }
            
            public void getFoodLocation()
            {
                if(level > food.length-1)
                {
                    foodLocation = null;
                    return;
                }
                foodLocation = new Pair(food[level][1], food[level][0]);
                level++;
            }
            
            /** Moves the snake.
                @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
                @return The game's score after the move. Return -1 if game over. 
                Game over when snake crosses the screen boundary or bites its body. */
            public int move(String direction) {
                Pair head = snakeList.get(0);
                Pair nextPosition = null;
            
                if(direction.equals("U"))
                {
                      nextPosition = new Pair(head.w, head.h-1);
                }
                
                
                if(direction.equals("L"))
                {
                      nextPosition = new Pair(head.w-1, head.h);
                }
                
                
                if(direction.equals("R"))
                {
                      nextPosition = new Pair(head.w+1, head.h);
                }
                
                
                if(direction.equals("D"))
                {
                      nextPosition = new Pair(head.w, head.h+1);
                }
                
                if(nextPosition == null || nextPosition.w < 0 || nextPosition.h > height-1 || nextPosition.h < 0 || nextPosition.w > width-1)
                {
                    return -1;
                }
                
                if(foodLocation != null && nextPosition.w == foodLocation.w && nextPosition.h == foodLocation.h)
                {
                    snakeList.add(0, new Pair(foodLocation));
                    getFoodLocation();
                    score++;
                }
                else
                {
                    snakeList.add(0, new Pair(nextPosition));
                    snakeList.remove(snakeList.size()-1);
                }
                return score;
                
            }
            
        }
        
        /**
         * Your SnakeGame object will be instantiated and called as such:
         * SnakeGame obj = new SnakeGame(width, height, food);
         * int param_1 = obj.move(direction);
         */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.