4096 II

Computer Science Level 5

Chris decided to code a game called 4096 which he believes is the next big thing. The game is relatively simple. You have a 4 × 4 4\times 4 grid that contains integers that are all powers of 2. Tiles slide as far as possible in the chosen direction until they are stopped by either another tile or the edge of the grid. If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. The resulting tile cannot merge with another tile again in the same move.

The possible moves are L , R , U , D L,R,U,D which means swipe to the left, right, up and down respectively. Eventually, there will be some random number pops out and might replace the old tile.

Here is your starting configuration,

Wikipedia Wikipedia

This file contains 1000 lines. Each lines is an operation either :

  • L : swipe to the left
  • R : swipe to the right
  • U : swipe up
  • D : swipe down
  • P x y v : replace cell ( x , y ) (x,y) with number v v . It is guaranteed that v v is a power of 2.

What is the sum of all numbers in the grid after all operations are executed?

Details and Assumptions

The top row from left to right are cells ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) (1,1), (1,2), (1,3), (1,4) .


The answer is 626.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Christopher Boo
Jul 18, 2016

Relevant wiki: Graph implementation and representation

2048 is a game invented by Gabriele Cirulli. Playing the game itself is simple, but coding it up is not. I often hear non-programmers under appreciate the effort of game and software developers. This inspires me to create this example problem. Sure, it does not need advanced algorithm and data structure, but the patience to code a seemingly tedious program neatly and provide high readability is often what programmer deals with. If you think this is tough, note that this problem does not fully simulate the game as I can "replace" tiles but the tiles appear on the game must be on an empty one. We still have a long way to code to its perfect form. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
#include <bits/stdc++.h>
using namespace std;

int a[4][4];

int main() {

    // initial config
    a[0][0] = 0; a[0][1] = 0, a[0][2] = 2, a[0][3] = 4;
    a[1][0] = 0; a[1][1] = 0, a[1][2] = 4, a[1][3] = 8;
    a[2][0] = 0; a[2][1] = 2, a[2][2] = 16, a[2][3] = 32;
    a[3][0] = 0; a[3][1] = 2, a[3][2] = 2, a[3][3] = 16;

    for (int i = 0; i < 1000; i++) {
        char op;
        cin >> op;

        if (op == 'L') {
            for (int i = 0; i < 4; i++) {
                deque<int> d;
                for (int j = 0; j < 4; j++) {
                    if (a[i][j] != 0) {
                        d.push_back(a[i][j]);
                    }
                }

                int j = 0;
                while (d.size() > 0) {
                    if (d.size() > 1 && d[0] == d[1]) {
                        a[i][j++] = (d[0] << 1);                   
                        d.pop_front();
                        d.pop_front();
                    }
                    else {
                        a[i][j++] = d[0];
                        d.pop_front();
                    }
                }
                while (j < 4) {
                    a[i][j++] = 0;
                }
            }
        } if (op == 'U') {
            for (int i = 0; i < 4; i++) {
                deque<int> d;
                for (int j = 0; j < 4; j++) {
                    if (a[j][i] != 0) {
                        d.push_back(a[j][i]);
                    }
                }
                int j = 0;
                while (d.size() > 0) {
                    if (d.size() > 1 && d[0] == d[1]) {
                        a[j++][i] = d[0] << 1;                   
                        d.pop_front();
                        d.pop_front();
                    }
                    else {
                        a[j++][i] = d[0];
                        d.pop_front();
                    }
                }
                while (j < 4) {
                    a[j++][i] = 0;
                }
            }
        } if (op == 'R') {
            for (int i = 0; i < 4; i++) {
                deque<int> d;
                for (int j = 3; j >= 0; j--) {
                    if (a[i][j] != 0) {
                        d.push_back(a[i][j]);
                    }
                }
                int j = 3;
                while (d.size() > 0) {
                    if (d.size() > 1 && d[0] == d[1]) {
                        a[i][j--] = d[0] << 1;                   
                        d.pop_front();
                        d.pop_front();
                    }
                    else {
                        a[i][j--] = d[0];
                        d.pop_front();
                    }
                }
                while (j >= 0) {
                    a[i][j--] = 0;
                }
            }
        } if (op == 'D') {
            for (int i = 0; i < 4; i++) {
                deque<int> d;
                for (int j = 3; j >= 0; j--) {
                    if (a[j][i] != 0) {
                        d.push_back(a[j][i]);
                    }
                }
                int j = 3;
                while (d.size() > 0) {
                    if (d.size() > 1 && d[0] == d[1]) {
                        a[j--][i] = d[0] << 1;                   
                        d.pop_front();
                        d.pop_front();
                    }
                    else {
                        a[j--][i] = d[0];
                        d.pop_front();
                    }
                }
                while (j >= 0) {
                    a[j--][i] = 0;
                }
            }
        } if (op == 'P') {
            int x, y, v;
            scanf("%d%d%d",&x,&y,&v); x--; y--;
            a[x][y] = v;
        }
    }

    long long ans = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%d ", a[i][j]);
            ans += a[i][j];
        }
        printf("\n");
    }

    cout << ans << endl;

    return 0;
}

I admit this is not a neat code. It's just a lot of copy/paste and stress tested.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

I agree with you it's kind of tedious to test for a multitude of cases. The choice of C as programming language, make things even more tedious.

Abdelhamid Saadi - 4 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...