IT Duel 2016 at Anadea Inc.
Epic win! :)
IT Duel was held on November 28, 2015 at Anadea Inc. The challenge format  single creative problem, seven 4max teams, 4 hours for solving.
The winner team:
 Sergey Tokarenko  LinkedIn, GitHub
 Dmitriy Kiriyenko  LinkedIn, GitHub
 Alexey Kudryashov  LinkedIn, GitHub
Hereby, the winners share their insights.
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 topleft corner coordinates of placed figure, both starting from 0
.
Figure IDs and angle IDs should correspond to the definition:
API
Take the task:
URL: "https://tetromino.anadea.info/api/puzzle"
HTTP method: `GET`
Required parameters:
 token  unique team identifier;
 size  foursquare(task) size;
Example:
$ curl request GET "https://tetromino.anadea.info/api/puzzle?token=57492ce2e3124c80b13137be4031f30e&size=4"
>> {"id":123116,"size":4,"signature":"I1,J1,L1,Z1"}
Send the solution:
URL: "https://tetromino.anadea.info/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=57492ce2e3124c80b13137be4031f30e&id=123116&solution=[[\"L\",1,0,0],[\"S\",0,0,1],[\"L\",1,3,0],[\"S\",0,1,2]]" https://tetromino.anadea.info/api/puzzle
>> {"id":123116,"solved":true,"submitted_at":"20151212 12:12:12Z"}
Winner ideas
There are just three ones:
 Avoid the ado around Where to place the figure? Instead, our target is to fill each cell of the board, one by one.
 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 fromN*N
bits. In addition, start not from emptyN*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?  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 way from root empty board tree node to fully filled board node via Depthfirst 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!
When we think 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 onetwo figure by each type, almost always.
Diagonal Cells Strategy!!
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.
Let's walk through the board by diagonals:
Diagonal Cells Strategy & Balanced Figures Container synergy gives us the small emptycells 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 applying 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 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 Breadthfirst search. Unless the result corresponds 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.
And, the last key idea is...
Pathologies!!!!
Let's cure some pathologic situations.
The first of them looks 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 is 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
Thirdparty libraries:
 Use Thor to build the commandline interfaces
 Use httparty to build the HTTP clients
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 addition to ordering by quantities. Otherwise, the iteration through it will be corrupted.

BalancedFiguresContainer can be implemented much more 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 antipattern in general case. Especially for Ruby, especially for now
 Remember that UnitTest is antipattern 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 have 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"=>"20151206T16: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"=>"20151206T16: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"=>"20151206T16: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"=>"20151206T16:51:03.098Z"}
Wold you like to see how it works 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
 Recursive to iterative (?)
 Tests (?)
LICENSE
MIT License. Copyright (c) 2015 Sergey Tokarenko, Dmitriy Kiriyenko, Alexey Kudryashov.