CareerCup

/**
 * `Snake` has three (3) possible commands: forward (F), right (R),
 * and left (L).
 * - F moves the head of the snake forward one (1) cell in the direction
 *   the head is currently facing
 * - R moves the snake head to the right.  The head can only move a
 *   maximum of 90 degrees from the base of the neck.  
 * - L rotates the snake head to the left.  Again, the head can only
 *   rotate a maximum of -90 degrees from the base of the neck.
 * 
 * The snake has a `head` which is located on a particular cell.
 * Model this as an array of length 2 which contains [i, j] the 
 * coordinates that the head is currently located.
 * 
 * The snake has a tail which is an arbitrary length array of
 * 2-tuples that functions as a queue where the top of the queue
 * is the [i,j] pair that represents the last segment of the tail.
 * 
 * When the snake moves forward the last 2-tuple is popped from
 * the tail and the previous head is enqueued, the new head is set
 * explicitly.
 * 
 * When the snake enters a space occupied by an apple the snake
 * is considered to have "grown" therefore enqueue the previous
 * head coordinates in the tail, set the new coordinates for the
 * head and do not pop the last element for the tail.
 * 
 * If the snake's next forward move would take it either into a
 * "wall" or "edge" of the map or into a space already occupied
 * by some segment of it's tail the snake is considered to be
 * killed and the game is over.
 * 
 * The grid itself may be represented by an MxN array of characters.
 */

The following is my implementation of the SnakeGame
I am just using a int[][] grid and a doubly linkedlist to keep track of the snake body
When the snake eats the food, i add a cell to the head
When the snake moves, i add the new cell to the head and remove its tail
The game is over when snake eats itself, move out of bounds, or when its size == grid.length*grid.length
Because I am not using fancy Java GUI for this, I purposefully did not make the snake to automatically move forward to the direction it is facing. Instead, I have the user to move the snake one cell at a time using prompt.

time complexity: O(n)
space complexity: O(2n)

The following is the code:

import java.util.*;
public class SnakeGame {

  int[][] grid;
  DoublyLinkedList dll;

  public static void main(String[] args) {
    SnakeGame sg = new SnakeGame(Integer.parseInt(args[0]));
  }

  public SnakeGame(int bounds) {
    grid = new int[bounds][bounds];
    dll = new DoublyLinkedList();
    play();
  }

  public void play() {
    startingPoint();
    placeFood();
    printGrid();
    while(true) {
      try {
        getMove();
        printGrid();
      } catch(GameOverException e) {
        System.out.println(e.getMessage());
        return;
      }
    }
  }

  public void getMove() throws GameOverException {
    Scanner sc = new Scanner(System.in);
    String input = sc.next();
    int currentRow = dll.head.position[0];
    int currentCol = dll.head.position[1];
    if(input.equals("w")) {
      currentRow--;
    } else if(input.equals("a")) {
      currentCol--;
    } else if(input.equals("s")) {
      currentRow++;
    } else if(input.equals("d")) {
      currentCol++;
    } else {
      getMove();
      return;
    }
    if(currentCol < 0 || currentCol == grid.length || currentRow < 0 || currentRow == grid.length)
      throw new GameOverException("You hit a wall");
    else if(grid[currentRow][currentCol] == 1) throw new GameOverException("You ate yourself");
    else if(grid[currentRow][currentCol] == 7) {
      dll.addFront(currentRow, currentCol);
      if(dll.size == grid.length*grid.length) throw new GameOverException("You won!");
      placeFood();
    } else {
      dll.addFront(currentRow, currentCol);
      dll.removeTail();
    }
  }

  public int[] getRandomPosition() {
    Random r = new Random();
    int row, col;
    do {
      row = r.nextInt(grid.length);
      col = r.nextInt(grid.length);
    } while(grid[row][col] != 0);
    int[] result = {row, col};
    return result;
  }

  public void startingPoint() {
    int[] position = getRandomPosition();
    dll.addFront(position[0], position[1]);
    grid[position[0]][position[1]] = 1;
  }

  public void placeFood() {
    int[] position = getRandomPosition();
    grid[position[0]][position[1]] = 7;
  }

  public void printGrid() {
    for(int i = 0; i < grid.length; i++) {
      System.out.println(Arrays.toString(grid[i]));
    }
  }

  public class DoublyLinkedList {
    Node head, tail;
    int size = 0;
    public DoublyLinkedList() {
      head = null; tail = null;
    }
    public void addFront(int row, int col) {
      if(head == null && tail == null) {
        head = tail = new Node(null, row, col, null);
      } else if(head == tail) {
        head = new Node(null, row, col, tail);
        tail.prev = head;
      } else {
        head = new Node(null, row, col, head);
        head.next.prev = head;
      }
      grid[row][col] = 1;
      size++;
    }
    public void removeTail() {
      if(tail == null) {
        return;
      } else if(head == tail) {
        grid[tail.position[0]][tail.position[1]] = 0;
        head = tail = null;
      } else {
        grid[tail.position[0]][tail.position[1]] = 0;
        tail = tail.prev;
        tail.next = null;
      }
      size--;
    }
  }

  public class Node {
    int[] position;
    Node next;
    Node prev;
    public Node(Node prev, int row, int col, Node next) {
      int[] pos = {row, col};
      position = pos;
      this.next = next;
      this.prev = prev;
    }
  }

  public class GameOverException extends Exception {
    public GameOverException(String message) {
      super(message);
    }
  }
}

Another approach you can use for space efficiency is to just use grid and implement the snake inside the grid. You can do this by doing the following:
(1) set empty spaces as 0
(2) set food as -1
(3) set snake body as positive integers more than 0

The way this works is that whenever you move the snake, you set the grid to 1 and increment every integer in the grid more than 0 while keeping track of the highest number (the tail). And at the end of this loop, you just make the tail 0. This follows that when the snake eats the food, you just don't delete the highest number.

Time complexity: O(n^2)
Space complexity: O(n)