Problem 187884 · hard · Phase 01 Prerequisites & Setup

The Pocket Arcade Snake

lists · strings · loops · conditionals · simulation

You are writing the engine for a handheld snake game on a board of rows by cols cells (row 0 is the top, column 0 the left). The snake starts as a single cell at [0, 0], and it has eaten nothing. moves is a string of U, D, L, R; each letter moves the head one cell.

food is a list of [row, col] cells. The first one lies on the board from the start. When the snake eats a piece, the next piece in the list appears; if that piece would appear on a cell the snake occupies, it is thrown away and the one after it is tried. When the list runs out, no food is left.

One move happens in this order:

  1. The head's new cell is computed. If it is off the board, the game ends.
  2. If the new cell holds the food, the snake grows: its tail stays where it is and the score goes up by 1. Otherwise the tail cell is vacated first.
  3. If the new cell is part of the (remaining) body, the game ends. Because the tail leaves first, moving into the cell the tail is just leaving is allowed, even for a snake of length 2 turning straight back.
  4. Otherwise the head enters the new cell, and after eating the next food appears.

Write snake_game(rows, cols, moves, food) that returns [score, completed], where completed is how many moves were finished before the game ended (the move that ends the game does not count). If no move ends the game, completed is len(moves).

Examples

Input:  rows = 3, cols = 3, moves = "RRDLL", food = [[0, 2], [1, 1], [2, 2]]
Output: [2, 5]

Input:  rows = 1, cols = 4, moves = "RRLR", food = [[0, 1], [0, 2]]
Output: [2, 2]
Explanation: after eating twice the body is (0,2),(0,1),(0,0); moving L hits (0,1).

Input:  rows = 1, cols = 3, moves = "RL", food = [[0, 1]]
Output: [1, 2]
Explanation: the head moves onto (0,0) just as the tail leaves it.

Constraints

  • 1 <= rows, cols <= 30, 0 <= len(moves) <= 3000, 0 <= len(food) <= 900
  • Every food cell is on the board, and food[0] is not [0, 0].

Goals

  • Store a moving body as a list of cells, head first
  • Order the steps of one game tick so the tail rule comes out right
  • Stop a simulation at the exact move that ends the game
Starting Python…