Slide and Merge

In a popular sliding puzzle, numbered tiles sit on an n by n board. board is a list of n rows, each a list of n numbers, where 0 is an empty square. moves is a string of 'L', 'R', 'U' and 'D' (left, right, up, down). Each move tilts the board in that direction:

• Every tile slides as far as it can in that direction.
• When a tile slides into a tile of the same value, the two merge into one tile with double the value, and the move scores the value of the new tile. A tile made by a merge cannot merge again in the same move.
• In each row (or column), the tiles nearest the side they slide toward are handled first. So moving left turns the row [2, 2, 2, 2] into [4, 4, 0, 0] (scoring 8), [2, 2, 2, 0] into [4, 2, 0, 0], and [4, 4, 8, 0] into [8, 8, 0, 0]: the new 8 does not merge with the old one.

After a move that changes the board, a new tile 2 appears on the first empty square in reading order (row 0 from left to right, then row 1, and so on). A move that changes nothing has no effect at all: no new tile and no score.

Write slide_game(board, moves) that plays all the moves and returns a tuple (board, score): the final board as a list of lists, and the total score.

Examples

slide_game([[2, 2, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 'L')
# returns ([[4, 2, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], 4)

slide_game([[0, 2], [0, 2]], 'U')
# returns ([[2, 4], [0, 0]], 4)

slide_game([[2, 4], [8, 16]], 'LURD')
# returns ([[2, 4], [8, 16]], 0)

In the first example the two 2s merge into a 4 (scoring 4), and a new 2 appears on the first empty square, right next to it. In the last example nothing can slide or merge, so no move changes anything.

Constraints

• 1 <= n <= 8; moves has up to 5,000 letters.
• Every tile is 0 or a power of 2.