fork(44) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <random>
  4. #include <map>
  5. using namespace std;
  6.  
  7. random_device rd;
  8. mt19937 rng(rd());
  9. uniform_int_distribution<int> d4(0,3), d10(0,9);
  10.  
  11. int state[4][4];
  12.  
  13. void reset() { for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) state[r][c]=0; }
  14.  
  15. bool is_game_over() {
  16.     for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) if (state[r][c]==0) return false;
  17.     for (int r=0; r<4; ++r) for (int c=0; c<3; ++c) if (state[r][c]==state[r][c+1]) return false;
  18.     for (int r=0; r<3; ++r) for (int c=0; c<4; ++c) if (state[r][c]==state[r+1][c]) return false;
  19.     return true;
  20. }
  21.  
  22. void get_random_empty_cell(int &r, int &c) {
  23.     r=-1; c=-1;
  24.     int seen = 0;
  25.     for (int rr=0; rr<4; ++rr) for (int cc=0; cc<4; ++cc) if (state[rr][cc]==0) ++seen;
  26.     if (!seen) return;
  27.     while (true) { r=d4(rng); c=d4(rng); if (state[r][c]==0) return; }
  28. }
  29.  
  30. bool add_random_cell() {
  31.     int r, c; get_random_empty_cell(r,c);
  32.     if (r==-1) return false;
  33.     state[r][c] = ( d10(rng)==0 ? 4 : 2 );
  34.     return true;
  35. }
  36.  
  37. bool compress(int *row) {
  38.     int tmp[4], dal=0, hlp[4], bol=0;
  39.     bool change = false;
  40.     for (int i=0; i<4; ++i) if (row[i]) tmp[dal++]=row[i];
  41.     for (int i=0; i<4; ++i) hlp[i]=0;
  42.     for (int i=0; i<dal; ) { if (i+1<dal && tmp[i]==tmp[i+1]) { hlp[bol++]=2*tmp[i]; i+=2; } else { hlp[bol++]=tmp[i]; i+=1; } }
  43.     for (int i=0; i<4; ++i) if (row[i]!=hlp[i]) change = true;
  44.     for (int i=0; i<4; ++i) row[i]=hlp[i];
  45.     return change;
  46. }
  47.  
  48. bool move1(int r0, int c0, int dr, int dc) {
  49.     int tmp[4];
  50.     for (int i=0; i<4; ++i) tmp[i]=state[r0+i*dr][c0+i*dc];
  51.     bool change = compress(tmp);
  52.     for (int i=0; i<4; ++i) state[r0+i*dr][c0+i*dc]=tmp[i];
  53.     return change;
  54. }
  55.  
  56. void move(int d) {
  57.     bool change = false;
  58.     if (d==0) for (int c=0; c<4; ++c) change |= move1(0,c, 1,0);
  59.     if (d==1) for (int c=0; c<4; ++c) change |= move1(3,c,-1,0);
  60.     if (d==2) for (int r=0; r<4; ++r) change |= move1(r,0,0, 1);
  61.     if (d==3) for (int r=0; r<4; ++r) change |= move1(r,3,0,-1);
  62.     if (change) add_random_cell();
  63. }
  64.  
  65. int game() {
  66.     reset();
  67.     add_random_cell();
  68.     add_random_cell();
  69.     while (!is_game_over()) move( d4(rng) );
  70.     int answer = 0;
  71.     for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) answer = max( answer, state[r][c] );
  72.     return answer;
  73. }
  74.  
  75. int main() {
  76.     map<int,int> stats;
  77.     long long games; cin >> games;
  78.     while (--games) ++stats[ game() ];
  79.     for (auto tmp:stats) cout << tmp.first << ": " << tmp.second << endl;
  80. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
50
stdout
copy 
32: 2
64: 20
128: 23
256: 4
https://ideone.com/W3J9fO
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!