Skip to content

Latest commit

 

History

History
289 lines (208 loc) · 11.5 KB

README.md

File metadata and controls

289 lines (208 loc) · 11.5 KB
Raw

IT duel 2016 at Anadea inc.

Epic win! :)

The challenge format - single creative problem, seven 4-max teams, 4 hours for solving.

The winner team:

The problem

The problem is about the Tetris game. Need to compile the square N*N (4 <= N <= 50) from the given set of tetromino figures. The figures can be rotated.

In general, you are given:

{
  size: N,
  signature: "#{FIGURE_1_ID}#{FIGURE_1_QUANTITY},...,#{FIGURE_M_ID}#{FIGURE_M_QUANTITY}"
}

The solution should look like:

[
  [FIGURE_ID, ANGLE_ID, X_1, Y_1],
  ...,
  [FIGURE_ID, ANGLE_ID, X_I, Y_I]
]

X and Y are top-left corner coordinates of placed figure, both starting from 0.

Figure IDs and angle IDs should correspond to the definition:

API

Take the task:

  URL: "http://tetro.andy128k.net/api/puzzle"
  HTTP method: `GET`

Required parameters:

  • token - unique team identifier;
  • size - foursquare(task) size;

Example:

  $ curl --request GET "http://tetro.andy128k.net/api/puzzle?token=57492ce2-e312-4c80-b131-37be4031f30e&size=4"

  >> {"id":123116,"size":4,"signature":"I1,J1,L1,Z1"}

Send the solution:

  URL: "http://tetro.andy128k.net/api/puzzle"
  HTTP method: `POST`

Required parameters:

  • token - unique token of your command;
  • id - task id;
  • solution - task solution;

Example:

  $ curl --request POST --data "token=57492ce2-e312-4c80-b131-37be4031f30e&id=123116&solution=[[\"L\",1,0,0],[\"S\",0,0,1],[\"L\",1,3,0],[\"S\",0,1,2]]" http://tetro.andy128k.net/api/puzzle

  >> {"id":123116,"solved":true,"submitted_at":"2015-12-12 12:12:12Z"}

Winner ideas

There are just three ones:

  1. Avoid the ado around Where to place the figure?. Instead, our target is to fill each cell of the board, one by one.

  2. Avoid the ado around the figure structure and rotations via bit masks. Board is not the N*N array as well, but an Integer compiled from N*N bits. In additional, start not from empty N*N board, but from (N+2)*(N+2) one, with a border - that helps us to avoid the ado around Is the figure inside the board still? and Is the figure's bit mask applied without infliction with the board edges?

  3. Imagine the tree, where vertex is concrete board filling (starting from empty board), and edges represent the Figure & Angle pairs which can fill the next board's empty cell. Then, try to find the path from root empty board tree node to fully filled board node via Depth-first search

That's all - neither kind of connectivity checks nor programming ado =) So simple to implement within 4 hours, so effective to get a victory :) The sources of that solution are marked by v0.0.1 tag.

Ultimate ideas

The Ultimate solution lives in master branch. It is natural evolution of winner one, but extended by several key ideas. Such as...

Balanced Figures Container !

Check it out

When we thinking what to do with the next empty board cell - try to place the figure types ordered by their remaining quantity, descending.

That helps us to reach the bottom of DFS stack with a one-two figure by each type, almost always.

Diagonal Cells Strategy !!

Check it out

In winner solution we iterated the board cells one after one, linearly:

That causes the long 2*N pathologic cell lines at the bottom of DFS stack, and turns DFS to infinity loop mode on large board sizes.

Lets walk through the board by diagonals:

Diagonal Cells Strategy & Balanced Figures Container synergy gives us the small empty-cells triangle at the bottom of DFS stack, with balanced remaining figures quantity:

This is a brilliant behavior, since any task on any board size aims to become the same small problem.

Now the remaining goal is to reach the bottom of stack as fast as possible. How to do that?..

Connectivity !!!

The target is simple - don't allow to apply the figure, which isolates the empty cells. How to do that?

Searching through the board for isolated empty cells each time when the figure has been applied? So boring... Can we do better?

Easy to see that the total count of empty cells is equals to N*N - 4 * APPLIED_FIGURES_COUNT. So we can take the right next empty cell, and calculate the count of empty cells connected to the first one, via Breadth-first search. If the result doesn't correspond to the formula - some empty cells are isolated.

Now it's time to remember about Diagonal Cells Strategy. One more step - check that connected empty cells count is just divisible by 4. That give us almost (or even exactly) zero chance to get the pathological case.

Does BFS take O(N*N) still? Then final step. Consider that all diagonals which are previous relatively to initial empty cell's one - are always filled. As well as all next diagonals starting from sixth one - are always empty.

Compile this knowledge, and reach the Holy Grail - the linear time.

Check it out.

And, the last key idea is...

Pathologies !!!!

Lets cure some pathologic situations.

The first of them look like:

There is no any figure which can be applied within. Let's prevent this situation.

Again, don't be so boring... Don't search this pattern through the whole board each time when some figure has been applied.

It's better to ask - when it appears?

Remember about Diagonal Cells Strategy. Easy to see, that it appears right after the J figure with 1 angle is going to be applied:

Are these all the cases?..

No :) Let's consider also I figure with 1 angle:

The same related to L : 2 and I : 0 figures, when we are close to the board's bottom:

The second pathologic situation looks like:

The problem is that algorithm doesn't see that L figure can be applied here. That's because it is trying to apply L like that:

Check out the both fixes.

Some cool programming tips & tricks

Third-party libraries:

Ruby programming in general:

  • Use $LOAD_PATH & autoload. Forget about require
  • Use throw & catch rather than raise & rescue if the stack surface is a normal behavior, but not exception
  • Aim to at least linear memory usage
  • Emulate the enumerable by yields (one, two, three), rather than to feed the garbage collector by extra arrays. If you need the true enumerable for chaining - just add return enum_for(:same_method_name, *args) unless block_given? to the beginning of method
  • while(true) is MUCH faster than loop do o_O
  • Use matrix.reverse.transpose to rotate the matrix by 90 clockwise, and matrix.transpose.reverse to rotate counterclockwise
  • Me - mo - ization!
  • BalancedFiguresContainer should be ordered by figure types, in additional to ordering by quantities. Otherwise the iteration through it will be corrupted.
  • BalancedFiguresContainer can be implemented much effectively by any kind of OrderedArray-like data structure, such as Heap. Hope that it's clear why we are idle here :)
  • As for Lazy calculations in Ruby, look at some frank benchmarks, think about..
  • Check out some other interesting benchmarks
  • Remember that Recursion is anti-pattern in general case. Especially for Ruby, especially for now
  • Remember that UnitTest is anti-pattern as well =)

Bit masks:

  • Bitwise operators are a bit SLOWER than arithmetic analogs o_O
  • In order to keep the board's lower coordinates at lower Integer bits, we need to reverse the figure mask
  • Figure bit masks should be compiled for each specific board size before the usage, since they are multiline
  • Bitwise AND helps us to check the infliction of positioned figure with partially filled board
  • Simple arithmetic addition helps us to apply the positioned figure. Consider that it works only if no inflictions there. In general case, bitwise OR does the same
  • The [] method returns the specific bit on Integers

The solution

Clone it. Bundle it.

Run it:

  $ ./tetris net_solve {SIZE} [TIMEOUT]

Output sample, for 50 size:

  [23.53s] {"id"=>407833, "size"=>50, "signature"=>"I49,J127,L49,O13,S127,T126,Z134"}
  [0.07s] Solved!
  [0.32s] {"puzzle_id"=>407833, "solved"=>true, "submitted_at"=>"2015-12-06T16:48:07.162Z"}
  ==========================================

  [78.88s] {"id"=>407835, "size"=>50, "signature"=>"I50,J114,L65,O17,S155,T94,Z130"}
  [0.06s] Solved!
  [0.16s] {"puzzle_id"=>407835, "solved"=>true, "submitted_at"=>"2015-12-06T16:49:26.296Z"}
  ==========================================

  [18.79s] {"id"=>407836, "size"=>50, "signature"=>"I41,J101,L61,O16,S154,T136,Z116"}
  [0.06s] Solved!
  [0.25s] {"puzzle_id"=>407836, "solved"=>true, "submitted_at"=>"2015-12-06T16:49:45.374Z"}
  ==========================================

  [69.96s] {"id"=>407837, "size"=>50, "signature"=>"I52,J106,L47,O12,S156,T110,Z142"}
  [0.06s] Solved!
  [7.68s] {"puzzle_id"=>407837, "solved"=>true, "submitted_at"=>"2015-12-06T16:51:03.098Z"}

Do you want to see how does it work internally? There is a verbose mode of solving. Choose the test case, run something like:

  $ ./tetris test 12 -v

TODO

  • Fix message on timeout, the problem is not solved in this case ))
  • Move API URL and token to config file
  • Cleanup connectivity
  • Pathology check with bit masks
  • Recursive to iterative (?)
  • Tests (?)

LICENSE

MIT License. Copyright (c) 2015 Sergey Tokarenko, Dmitriy Kiriyenko, Alexey Kudryashov.