algorithm - 2048 game: how many moves did I do? -


2048 used quite popular little while ago. played , lot of people posted nice screenshots accomplishments(myself among them). @ point began wonder if possible tell how long did play score. benchmarked , turns out that(at least on android application have) no more 1 move can made in 1 second. if play long enough(and fast enough) number of moves you've made quite approximation number of seconds you've played. question is: possible having screenshot of 2048 game compute how many moves made.

here example screenshot(actually best effort on game far):

from screenshot can see field layout @ current moment , number of points player has earned. so: information enough compute how many moves i've made , if so, algorithm that?

note: remind points scored when 2 tiles "combine" , number of points scored value of new tile(i.e. sum of values of tiles being combined).

the short answer is possible compute number of moves using information. explain algorithm , try post answer in steps. each step observation targeted @ helping solve problem. encourage reader try , solve problem alone after each tip.

  1. observation number one: after each move 1 tile appears. tile either 4 or 2. need count number of tiles appeared. @ least on version of game played game started 2 tiles 2 on them placed @ random.

  2. we don't care actual layout of field. care numbers present on it. become more obvious when explain algorithm.

  3. seeing values in cells on field can compute score if 2 had appeared after each move. call value twos_score.

  4. the number of fours have appeared equal difference of twos_score , actual_score divided 4. true because forming 4 2 2-s have scored 4 points, while if 4 appears straight away score 0. call number of fours fours.

  5. we can compute number of twos needed form numbers on field. after need subtract 2 * fours value single 4 replaces need of 2 2s. call twos.

using observations able solve problem. explain in more details how perform separate steps.

how compute score if 2 appeared?

i prove form number 2n, player score 2n*(n - 1) points(using induction).

  • the statements obvious 2 directly appears , therefor no points scored it.
  • let's assume fixed k number 2k user score 2k*(k - 1)
  • for k + 1: 2k + 1 can formed combining 2 numbers of value 2k. user score 2k*(k - 1) + 2k*(k - 1) + 2k+1(the score 2 numbers being combined plus score new number).
    equals: 2k + 1*(k - 1) + 2k+1= 2k+1 * (k - 1 + 1) = 2k+1 * k. completes induction.

therefor compute score if twos appeared need iterate on numbers on board , accumulate score them using formula above.

how compute number of twos needed form numbers on field?

it easier notice number of twos needed form 2n 2n - 1. strict proof can again done using induction, leave reader.

the code

i provide code solving problem in c++. not use language specific(appart vector dynamically expanding array) should easy port many other languages.

/**  * @param - vector containing values in field.   *   value of 0 means "empty cell".  * @param score - score player has.  * @return pair first number number of twos appeared  *    , second number number of fours appeared.  */ pair<int,int> solve(const vector<vector<int> >& a, int score) {   vector<int> counts(20, 0);   (int = 0; < (int)a.size(); ++i) {     (int j = 0; j < (int)a[0].size(); ++j) {       if (a[i][j] == 0) {         continue;       }       int num;       (int l = 1; l < 20; ++l) {         if (a[i][j] == 1 << l) {           num = l;           break;         }       }       counts[num]++;     }   }   // score if twos appeared every time   int twos_score = 0;   (int = 1; < 20; ++i) {     twos_score += counts[i] * (1 << i) * (i - 1);   }    // each 4 appears instead of 2 overall score decreases 4   int fours = (twos_score - score) / 4;    // how many twos needed numbers on field(ignoring score)   int twos = 0;   (int = 1; < 20; ++i) {     twos += counts[i] * (1 << (i - 1));   }   // each 4 replaces 2 2-s   twos -= fours * 2;    return make_pair(twos, fours); }

now answer how many moves we've made should add 2 values of pair returned function , subtract 2 because 2 tiles 2 appear straight away.


Comments

Post a Comment

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

consider, toml node module can use: // toml.d.ts declare module toml { export function parse(value:string):any; } declare module "toml" { export = toml; } then: /// <reference path="../../../../../defs/toml/toml.d.ts"/> import toml = require('toml'); toml.parse(...); however, node module export single function, such 'glob' ( https://github.com/isaacs/node-glob ). the node usage of module be: var glob = require("glob") glob("*.js", {}, callback(err, files) { ... }); you'd naively expect this: // glob.d.ts declare function globs(paths:string, options:any, callback:{(err:any, files:string[]):void; ...but because typescripts 'import' semantics bit strange, seems can use 'import .. = require()' statement alias modules . trying call: /// <reference path="../../../../../defs/glob/glob.d.ts"/> import blog = require('glob'); results in: error ts2072: mod
Read more

openid - Okta: Failed to get authorization code through API call -

i'm integrating okta own idp server using okta's api. i'm implementing authorization code flow following steps below: in own server, use /api/v1/authn endpoint sessiontoken. use sessiontoken obtain authorization calling endpoint: /oauth2/v1/authorize?client_id=" + clientid + "&sessiontoken=" + sessiontoken + "&response_type=code&response_mode=query&scope=openid&redirect_uri=" + redirecturl + "&state=evanyang&nonce=" it's supposed return response status code 302 , location header containing redirect url code value. however, keep getting response status code 200 , without location header, html body saying "you using unsupported browser." , "javascript disabled on browser." according api documentation: http://developer.okta.com/docs/api/resources/oidc.html#authentication-request , sessiontoken parameter sufficient this: an okta one-time sessiontoken. allows api-based
Read more

thorough guide for profiling racket code -

did googling ("racket profiling", "racket measure performance"), didn't find , there no examples in docs. did google "profile" search on htdp - no luck. (profile (f ...)) output isn't obvious other small snippets. ideally want python's python -m cprofile usage examples. when search "python profiling", both duckduckgo , google give top result: 26.4. python profilers . (although scanned quickly, seems more of reference "thorough usage guide" examples. if had else in mind, perhaps please link that?) the equivalent racket documentation be: profile: statistical profiler . a usage example: #lang racket (require profile) (profile-thunk (thunk (function-to-profile arg0 arg1) )) here (thunk e) convenience (lambda () e) . bigger example: #lang racket (module mod racket (provide f) (define (f) (for/list ([i 10000]) i))) (require (prefix-in mod: 'mod)) (define (f) (for ([i 10000
Read more