One 2048 Move
National Olympiad — National round (2015 season)
Submission name: power2.cpp
Problem summary
Perform one left or right move on a row of tiles. Zero means empty. Tiles slide as far as possible; equal neighboring values merge into their sum. A resulting tile may not merge again during the same move. Process tiles from the movement side first.
Source clarification. The story calls all values powers of two, but the input list also includes 6. The same algorithm correctly handles 6 by merging equal values; it does not assume a powers-of-two property.
Input
n and l or r, followed by n tile values.
Output
The n resulting tile values in their original left-to-right positions.
Constraints
2 ≤ n ≤ 100,000; initial nonzero tiles are at most 64 (the PDF lists 2, 4, 6, 8, 16, 32, 64).
Worked example
An independently prepared example for this explanation.
Input
10 l 2 0 2 0 4 4 0 8 0 8
Output
4 8 16 0 0 0 0 0 0 0
Solution analysis
- Handle both directions using the same left-move algorithm: reverse the row before and after processing when the requested direction is right. Remove zeros to obtain the sequence of tiles in movement order.
- Scan this compact sequence. If the next two values match, emit their sum and skip both. Otherwise emit the current value alone. Because each original tile is consumed once, an emitted sum cannot merge again in this move.
- The first sample compacts to [2, 2, 4, 4, 8, 8]. Pairwise merging produces [4, 8, 16], which is padded with seven zeros. In particular, the new 4 does not immediately merge with an original 4.
Why it works
Compaction preserves the order of all tiles while implementing movement through empty cells. In movement order, the next two original tiles merge exactly when equal; once merged, neither can participate again. The scan makes precisely those decisions. Zero padding and the final reversal restore the correct positions and direction.
Watch out. Do not merge a newly formed tile again. Merge pairs from the movement side, especially for three equal tiles. Reverse the entire row for right moves.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
char direction;
cin >> n >> direction;
vector<int> row(n);
for (int &value : row) {
cin >> value;
}
if (direction == 'r') {
reverse(row.begin(), row.end());
}
vector<int> tiles;
for (int value : row) {
if (value != 0) {
tiles.push_back(value);
}
}
vector<int> result;
// Consuming both original tiles prevents a second merge of the new tile.
for (size_t i = 0; i < tiles.size();) {
if (i + 1 < tiles.size() && tiles[i] == tiles[i + 1]) {
result.push_back(tiles[i] * 2);
i += 2;
} else {
result.push_back(tiles[i]);
++i;
}
}
result.resize(n, 0);
if (direction == 'r') {
reverse(result.begin(), result.end());
}
for (int i = 0; i < n; ++i) {
cout << (i == 0 ? "" : " ") << result[i];
}
cout << '\n';
return 0;
}