some algorithmic puzzles, tutorials, interview questions... and stuff...

Tuesday, December 22, 2009

How to hack daily puzzles on www.gameknot.com

What better way of wasting two hours of your life then hacking a website? :) Actually what I'm going to show here is just a simple example of javascript function overriding, it doesn't even deserve the name "hack". The site is not very secured, but the basic stuff (moves, canceling games etc.) is checked server side, so there's not much anybody could do.

You need Firefox with the extension "Firebug" installed. Now, assuming you like chess and you have an account at http://www.gamespot.com, notice that if you open a daily puzzle, then open the right-click menu and click "View source", the whole solution is encrypted. However the javascript files, which handle moving and verifying your moves, are not encrypted in any way. Pay attention to this line:
<script type="text/javascript" src="/js/chess-puzzle.js?122109"></script>
You can use the javascript formatter to make the file chess-puzzle.js a little more readable.
There are some interesting functions you can pay attention to. For example:

   1:  function show_move_hint() //this displays a hint if not in "contest mode"
   2:  function display_move_hint(countdown) //this one ensures the hint is displayed only once
   3:  function report_wrong_move() //this one tells the server you made a wrong move
   4:  function callback_record_move_solve() //this one records the puzzle as "unsolved" if you made more than 2 mistakes
What would happen if I would chose to override one of them? :) Or all, for that matter. Well, I could not try it myself since I would probably get my account deleted, but you could: just open Firebug, as in the screen-shot below, and edit the last <script> tag in the "head" section, to fit the following:

   1:  <script type="text/javascript"><!--
   2:  if (top.location!=location) { top.location.href = location.href; }
   3:   
   4:  function show_move_hint() {
   5:  //////if(contest_mode())return;
   6:  //////if(show_move_hint_count > 0)count_hints2++;
   7:  //////else count_hints1++;
   8:  //////if(!node_hints[cur_solution_node])node_hints[cur_solution_node] = 1;
   9:  //////else node_hints[cur_solution_node]++;
  10:  //////if(count_hints1 == 1 && count_hints2 == 0)report_solved(0);
  11:  //////show_move_hint_count++;
  12:     display_move_hint(5);
  13:  //////disable_hint_button();
  14:     }
  15:   
  16:  function display_move_hint(countdown) {
  17:  //////if(cur_mode != modes.SOLVE)return true;
  18:  //////if(cur_solution_node < 0 || cur_solution_node >= solution.length)return;
  19:     var sn = solution[cur_solution_node];
  20:     if(!sn.moves.length)return;
  21:     var cc = sn.moves[0].coords;
  22:     var mv = bob.chess_decode_move(cc);
  23:     var b_on = countdown % 2 ? 1 : 0;
  24:     bob.update_cell_image(mv[0], mv[1], b_on);
  25:     if(show_move_hint_count > 1)bob.update_cell_image(mv[2], mv[3], b_on);
  26:     countdown--;
  27:     if(countdown >= 0) {
  28:        display_hint_timer = window.setTimeout('display_move_hint(' + countdown + ')', 300);
  29:        }
  30:     }
  31:   
  32:  function report_wrong_move() {
  33:  //////   count_wrong_moves++;
  34:  //////   if(contest_mode(1)) {
  35:  //////      bob.b_allow_new_moves = 0;
  36:  //////      if(count_wrong_moves >= 4) {
  37:  //////         report_contest_wrong_move();
  38:  //////         alert('Sorry, you have failed to solve this puzzle.\nPlease check back tomorrow for the correct solution and\na new puzzle and another chance to win the Grand Prize!');
  39:  //////         top.location.href = location.href;
  40:  //////         return;
  41:  //////         }
  42:  //////      pop_msg('Processing, please wait...', 10000, 10000);
  43:  //////      setTimeout(function() {
  44:  //////         report_contest_wrong_move(); }
  45:  //////      , 1);
  46:  //////      return;
  47:  //////    }
  48:  //////    if(count_wrong_moves == 1 || count_wrong_moves == 6)report_solved(0);
  49:     var m = ['Wrong move', 'Not quite', 'Sorry', 'Incorrect'];
  50:     pop_msg(m[Math.floor(Math.random() * m.length)] + '. Try again!', 1000);
  51:     }
  52:   
  53:  function callback_record_move_solve() {
  54:     var sn = solution[cur_solution_node];
  55:     if(bob.b_checkmate) {
  56:        if(!report_solved(1))return;
  57:        var last_mv = split_move(bob.chess_get_last_move());
  58:        for(var i = 0; i < sn.moves.length; i++) {
  59:           var mv = sn.moves[i];
  60:           if(!same_move(mv, last_mv))continue;
  61:           cur_solution_node = mv.goto_node;
  62:           break;
  63:           }
  64:        start_solved_mode();
  65:        return;
  66:        }
  67:     if(bob.cur_to_move != puzzle_to_move) {
  68:        var last_mv = split_move(bob.chess_get_last_move());
  69:        var b_found = 0;
  70:        var best_mtc =- 1;
  71:        for(var i = 0; i < sn.moves.length; i++) {
  72:           var mv = sn.moves[i];
  73:           var mtc = solution[mv.goto_node].moves_to_checkmate;
  74:           if(best_mtc < 0)best_mtc = mtc;
  75:           if(best_mtc < mtc)break;
  76:           if(!same_move(mv, last_mv))continue;
  77:           b_found = 1;
  78:           break;
  79:           }
  80:        if(b_found) {
  81:           cur_solution_node = mv.goto_node;
  82:           sn = solution[cur_solution_node];
  83:           var best_move = decide_best_move(cur_solution_node);
  84:           mv = sn.moves[best_move];
  85:           cur_solution_node = mv.goto_node;
  86:           node_solution_moves[cur_solution_node] = 1;
  87:           make_move(mv.coords, mv.promo);
  88:           return;
  89:           }
  90:  /////////report_wrong_move();
  91:        bob.undo_last_move();
  92:  /////////if(!node_wrong_moves[cur_solution_node])node_wrong_moves[cur_solution_node] = 1;
  93:  /////////else node_wrong_moves[cur_solution_node]++;
  94:        }
  95:     bob.b_allow_new_moves = 1;
  96:     update_last_move_cell_cursor();
  97:     }
  98:  // --></script>

Free Image Hosting at www.ImageShack.us

The lines prefixed with ////// need to be deleted. I just left them there so a comparison can be made: before and after. I wonder if the requests which go the server are as easily hacked as this.... Have fun!

Saturday, December 12, 2009

How to generate random numbers in [1...7] from random numbers in [1...5]

Well known as a Google/Microsoft interview question, the following problem is actually really complicated to solve correctly, although it looks easy:

Given a function which produces a random integer in the range 1 to 5, write another function which uses it and produces a random integer in the range 1 to 7.

I'm going to modify this a little and make it generic:
Given a function which produces a random integer in the range 1 to 5(M), write another function which uses it and produces a random integer in the range 0 to 7(N).

Of course it's easy to do it without generating a uniform distribution so I'm not going to spend time on that.
What needs to be done is generate a uniform distribution. But consider this example:
If we add random(5) + random(5), assuming random(5) generates numbers from 0 to 4, we have:

   1:  0+0
   2:  0+1, 1+0
   3:  0+2, 2+0, 1+1
   4:  0+3, 3+0, 1+2, 2+1
   5:  0+4, 4+0, 1+3, 3+1, 2+2
   6:  1+4, 4+1, 2+3, 3+2
   7:  2+3, 3+2, 3+3
   8:  3+4, 4+3
   9:  4+4

This obviously is not a uniform distribution because we have more chances of generating the number 4 than the number 8. So whatever algorithm is needed, it cannot simply use operations involving random(5). Or, actually it can, with some complicated math behind. Read about Box–Muller transformations and Rejection sampling.

What I think is a simpler algorithm is the following: since every number can be represented in X bits, generate X numbers from 1 to 5, and depending on the generated number, set bit X to 1 or 0. Number from 0 to 7 can be represented with 3 bits. Let me know what you think.

   1:  int genRandom1to5() {
   2:      return (rand() % 5) + 1;
   3:  }
   4:   
   5:  int genRandom1to7() {
   6:      int rand17 = 0;
   7:      for (int i = 0; i < 3; i++) {
   8:          int rand15 = 3;
   9:          while (rand15 == 3) {
  10:              rand15 = genRandom1to5();
  11:          }
  12:          if (rand15 < 3)
  13:              rand17 |= (1 << i);
  14:      }
  15:      return rand17;
  16:  }