2048 Game Solver: Optimal Next Move

You are given the current state of a 2048 game board represented as a 4×4 grid. Your task is to write a program that computes the optimal next move among the four possible directions: up, down, left, or right.

The game rules are similar to the classic 2048 game: when a move is performed, the tiles slide as far as possible in the chosen direction, merging identical numbers (only once per move). The score after a move is computed as the sum of the values in the grid after sliding and merging. The optimal move is defined as the one that maximizes this evaluation sum. If there are multiple moves with the same evaluation, choose the first one in the order: up, down, left, right.

The merging rule is expressed by the formula: \(a + a \longrightarrow 2a\). For each row (or column) in the direction of motion, sliding and merging operations should be performed according to the standard 2048 rule.

inputFormat

The input is read from standard input (stdin) and consists of exactly 4 lines. Each line contains 4 space separated integers representing one row of the game grid.

Example:

2 4 2 0
2 0 4 2
8 16 32 0
1024 1024 64 0

outputFormat

Print to standard output (stdout) a single line containing the optimal move, which is one of: up, down, left, right.

2 4 2 0
2 0 4 2
8 16 32 0
1024 1024 64 0

up