Snake game
Simulate the Snake game on a width x height grid. The snake starts length 1 at cell (row 0, col 0) and you process a list of moves, each 'U','D','L','R'. food is a list of [row, col] cells that appear in order; eating the current food grows the snake by one and advances to the next food. A move returns the current score (length-1), or -1 if the snake hits a wall or its own body, after which the game ends. Return the list of results per move. The snake's tail vacates its cell on a non-eating move (so moving into the old tail cell is allowed).
snake_game(width: int, height: int, food: list[list[int]], moves: list[str]) → list[int][3,2,[[1,2],[0,1]],["R","D","R","U","L","U"]]out[0,0,1,1,2,-1]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[3,2,[[1,2],[0,1]],["R","D","R","U","L","U"]][0,0,1,1,2,-1]not run yetsample