Unity Continuous Integration

And finally Unity Continuous Integration (CI) plugin is on Unity Asset Store! Check it out: https://www.assetstore.unity3d.com/#/content/12695.

I spent a day setting up Jenkins build machine on Road Smash project and spent one more day to unify builder script and writing documentation, so I can use it on any unity project with any CI framework and any CVS systems, including asset server, git, svn. It works out-of-box, the only thing you need is to call the right method(like BuildAndroid, BuildIOS) from command line(OSX, Windows).

For now Unity CI supports:

• iOS build
• Android builds (including different builds for different textures format, including ATC, ETC, DXT & PVRTC). You can call a method to build 5 different apks, which will support different textures from AndroidManifest.xml and may be uploaded to Google Play as multiple apks.

I didn't include changing version code to plugin, because every project may have its own policy and I may break it, but it is really easy to add there. I'll write another post about all android building stuff later.

I'm planning to include unit-testing plugin to CI and make it portable. I'll finish it up as soon as I'll have a free time for it.

P.S. Unity Technologies rejected my Flurry plugin(full iOS & Android, Windows Phone beta support) for its own internal business reasons. Is anybody interested in it?

Codility prefix problem

I got a problem from codility site and was asked to solve it. Here's a link on stackoverflow. In two words: assume we have a string S and we need to choose such a prefix P of S, that product of its length and occurrence in S will be maximum.

For example, S = "abababa" has the following prefixes:

"a", whose product equals 1 * 4 = 4,
"ab", whose product equals 2 * 3 = 6,
"aba", whose product equals 3 * 3 = 9,
"abab", whose product equals 4 * 2 = 8,
"ababa", whose product equals 5 * 2 = 10,
"ababab", whose product equals 6 * 1 = 6,
"abababa", whose product equals 7 * 1 = 7.

I like problems like that. It has obvious solution in O(N ** 3) time, elegant and easy to guess if you know z-algorithm O(N ** 2) solution and tricky O(N) solution.

Ok, first solution is naive brute-force. You choose length from 1 to N, get a prefix of its length and count occurences by brute-force searching. So, choosing length takes O(N) time and brute force takes O(N ** 2) time, totally O(N ** 3).

Ok, it doesn't really what we want to achieve. Let's think how we can reduce complexity. Anyone who ever learned strings knows that string occurence can be searched in O(N) time, so with a little code we can achieve O(N ** 2) time compexity solution. I used Z-algorithm. Here's the code:

vector<int> z_function(string &S); //z-function, z[0] = S.length()

int calculate(string &S) {
 vector<int> z = z_function(S);

 int ans = 0;
 for (int i = 1; i <= S.length(); ++i) { //iterate on length
  int k = 0; //counter of occurrences
  for (int j = 0; j < S.length(); ++j) 
   if (z[j] >= i) ++k;  

  //update answer
  ans = max(ans, i * k);
 }
        return ans;
}

But it is still not enough though. How we can get rid of nested loop? We can precalc prefix occurences with Z-algo and finding them in constant time. Initially Z-algo returns an array, where z[i] is the length of longest substring starting from S[i], which is also prefix of S. For "abacaba" it will return {7, 0, 1, 0, 3, 0, 1}. And we know that if prefix of S with length i has N occurrences, then all smaller prefixes of S will have at least N occurrences. So, we create an array of occurrences, iterate over z-array, updating new created array and finally iterate over it backwards, updating as explained above.

vector<int> z_function(string &S); //z-function, z[0] = S.length()

int calculate(string &S) {
 vector<int> z = z_function(S);

 int n = S.length(); 
 vector<int> cnt(n + 1);


 //cnt[i] - count of i-length prefix occurrences of S 
 for (int i = 0; i < n; ++i) 
  ++cnt[z[i]];

 //if cnt[i] is in S, cnt[i - 1] will be in S
 int previous = 0;
 for (int i = n; i > 0; --i) {
  cnt[i] += previous;
  previous = cnt[i];
 }

 int ans = 0;
 for (int i = 1; i <= S.length(); ++i) { //iterate on length
  int test = cnt[i] * i;
  //update answer
  ans = max(ans, test);
 }

 return ans;
}

We separately count occurrences in O(N) time and find the answer in O(N) time as wanted.

For me it is the most easiest way to solve this problem. If anyone knows better solution, please kindly share.