Minimal

Stanford AI Class Finished

2011-12-22T12:57:00.001+02:00

Stanford AI class is over. I was very interesting and I learned a lot new things. Unfortunately I sucked at the first 2 questions of final exam and my score is not so high as I would like it to be. But there will be new interesting courses in spring - I will take my "revenge" there. So far I have signed up to Machine Learning, Game Theory and Design and Analysis of Algorithms courses and I hope I will have enough time for that. :)

Java: Save InputStream Into File

2011-11-14T12:15:00.001+02:00

Imagine we need to save an InputStream into file. That can happen when requesting some url, or when just copying the file from one place to another on hard disk. There are a lot of answers provided by google on request java save inputstream to file. I have checked the first result page and everywhere almost 1 and the same solution is provided, which includes the following loop:

int read = 0;
byte[] bytes = new byte[1024];
 
while ((read = inputStream.read(bytes)) != -1) {
 out.write(bytes, 0, read);
}

Seriously, guys, don't you think there is something wrong here? Even in C++ people do not copy streams by operating bytes anymore! There should be a lot better way :) (I am not considering now usage of any additional libraries that require some additional jar files).

import sun.misc.IOUtils;

new FileOutputStream("tmp.txt").write(IOUtils.readFully(inputStream, -1, false));

Top 10 Jenkins Must-Have Plugins

2011-08-24T13:03:00.000+03:00

We at ZeroTurnaround have been using Jenkins for a long time already, and at last decided to create a small review of plugins and features we use.

Ruby Pack/Unpack

2011-06-10T22:02:00.002+03:00

Having a party in ZeroTurnaround new office in Tartu. There is a mat on the floor near the entrance door that says:

01010111011001010110110001100011011011110110110101100101

Using ruby, we can quickly figure out, what that actually means:

["01010111011001010110110001100011011011110110110101100101"].pack('B*') #==> Welcome

Ruby string pack unpack detailed usage.

GeekOut: The First Java Conference In Estonia

2011-06-09T23:01:00.005+03:00

Today I have attended the first Java conference in Estonia: GeekOut. That is also my first conference at all, as I have never participated earlier in such an event. Nipping on ahead I could say, that the activity was a success. It was good organized, informative, interesting, with great food and beer (although I do not drink alcohol :) ).

The day started with small introduction from Jevgeni Kabanov, the founder and CTO of ZeroTurnaround, the organizers of the GeekOut. After that the main part began.

The first talk was about Java 7 by Martijn Verburg. It was about the new features that are coming in JDK 7. Project Coin announced:

Strings in switch
Automatic Resource Management (such as c# using construction)
Numeric literals with underscores. (Like in ruby: 3_456_789)
Improved Type Inference for Generic Instance Creation
We can skip generics on the right side:
```
Map<String, List<String>> anagrams = new HashMap<>();
```
New file handling mechanism, which "is finally done right, I hope" (M.V.)
Nonblocking I/O for sockets and files, new Files and Paths classes that provide some util functions to work with filelike objects, that are quicker than in JDK 6, multicatch and some others...

Next speech was about "Riding the data tsunami and coming out on top" by Alex Snaps. He introduced Terracotta - an open source solution for application scalability, availability and performance.

After a coffee break Joonas Lehtinen told us about Vaadin}> - the web framework for java, that allows creating rich internet applications fast and without a line in javascript. Interesting fact is that Vaadin is actually "10 years old, but 21 months young" - as the framework exists already for a long time, but only recently it became popular. You can write everything in java, no javascript debugging, no html, and if you are writing in some other jvm language, then you don't need java too! Scala, Groovy, Jruby ... are all good. Also a nice coding session, where Joonas wrote a nice web application in 15 minutes! I liked it, very impressive.

John Davies talked about integration of applications. Banking realities: FpML, 100-100000 messages/sec, latency critical - 10ms, xml is evil - no time for <>, network cards process the messages, not cpu - how the time is critical, 30PB of cache?! We also learned, why common message mapping is bad, when you have huge amount of data. That is converting to common message format and from it, when we can actually convert straight. What we need actually is to know how to convert each field of the message between POJO and particular format. XPath using in objects... and so on.

After the lunch noSql databases, particularly GraphDB called Neo4j was covered by Peter Neubauer. It was a kind of introductory presentation, showing the concepts of the database, with examples of searching and storing the data and also conditions in which GraphDBs can and should be used instead of Sql databases.

Jevgeni Kabanov showed problems that one may face doing the update of web application. For instance, the out of memory error problem arises because of previous version of application not being garbage collected, if there is a not matter how small leak, because it has the link to the classloader and it has the link to the previous version of application.

The last talk, presented once again by Martijn Verburg, was a relaxing one. Very funny, but at the same time serious. Have to figure out yourself, what qualities of a Diabolic Programmer are good, what not, and what good to some extent.

The closing of the GeekOut conference was in cafe in the same building. Free pizza and some drinks - nice ending of the good day. Next time I definitely will attend GeekOut again!

The Slides:

PS. I will list all the slides of the presentations here as soon as they appear.

Google Code Jam 2011 Qualification Round

2011-05-11T11:16:00.000+03:00

This Saturday Google Code Jam 2011 Qualification Round took place. I didn't have much time to spend on the problems, but still have solved a couple and proceeded to Round 1.

The ones that I solved are Magicka and Candy Splitting.

Magicka

First I tried to solve it with some cunning string substitution involving regular expressions. But in the end the simple simulation did the trick. I actually was a little bit disappointed after the official solutions were announced, because I thought that there should be some trick in here.

#!/usr/bin/ruby

lines = ARGF.readlines

t = lines.first.to_i
(1..t).each do |test_id|
  arr = lines[test_id].split " "
  c = arr[0].to_i
  combines = arr[1..c].inject({}){|memo, e| memo[e[0..1]]=e[2]; memo[e[1]+e[0]]=e[2]; memo }
  d = arr[c+1].to_i
  opposed = arr[c+2..c+1+d]
  n = arr[c+2+d].to_i
  elems = arr[c+3+d] #.split("").collect {|i| i.to_sym }

  result = []
  elems.split("").each do |elem|
    result << elem
    if result.length > 1
      last2 = result[-2..-1].join
      if combines.key?(last2)
        result.pop(2)
        result = result << combines[last2]
      end
      opposed.each do |o|
        if result.include?(o[0]) && result.include?(o[1])
          result = []
          break
        end
      end
    end
  end

  puts "Case ##{test_id}: [#{result.join(", ")}]"
end

Candy Splitting

This one was a little bit more tricky and the author's solution is much more simpler and clear than mine. I made it using old school brute force, just like Goro (strength is my strength :) )

#!/usr/bin/ruby

def s( candies, pile1, pile2 )
 #p "c:#{candies}, 1:#{pile1}, 2:#{pile2}"
 if candies.empty?
  if !pile1.empty? && !pile2.empty? && pile1.inject(0){|memo, i| memo ^ i} == pile2.inject(0){|memo, i| memo ^ i}
   return pile1
  else
   return false
  end
 end
 x = candies.shift
 p1 = pile1.clone
 return s( candies, p1 << x, pile2) || s( candies, pile1, pile2 << x)
end

lines = ARGF.readlines

t = lines.first.to_i
(1..t).each do |test_id|
 n_candies = lines[test_id*2-1]
 candies = lines[test_id*2].split(" ").collect{|i| i.to_i }

 r = s( candies.sort.reverse, [], [] )
 r = !r ? "NO" : r.inject(:+)

 puts "Case ##{test_id}: #{r}"
end

Mercurial In Ubuntu

2011-04-21T17:03:00.000+03:00

Since I have moved to ZeroTurnaround I had to learn a lot of new and interesting things. Most of them are very simple to write about, but as time passes I finally thought up the things, I could share with you.

We use Mercurial as SCM. So here is a small tip for ubuntu users how to configure hg.

Mercurial is available to install through repository

$ sudo aptitude install mercurial

So now as it is installed, we can configure it. Mercurial reads configuration data from several files, if they exist. To list them use:

$ hg help config

Now we will edit the $HOME/.hgrc file to add there some user information, authentication and enable plugins. A configuration file consists of sections, led by a [section] header and followed by name = value entries (sometimes called configuration keys)

[ui]
username = Firstname Lastname <firstname.lastname@example.net>

Here we introduced ourselves. The section is [ui] and ui.username is typically a person's name and email address. If this field is not declared in hgrc, you will have to enter it manually every time you commit.

[auth]
foo.prefix=*
foo.username=firstname.lastname@example.net
foo.password=SecretPassword123

The [auth] section allows you to store credentials for http authentication, I hate entering username and password every time I pull or push. You can store several different credentials for different servers here. They will be grouped by the part before the . (full stop, foo - in my example). And the auth.prefix will determine, which credentials should be used for what http address. It should be either * or a URI with or without the scheme part. In my example 1 and the same credentials are used for all addresses.

[extensions]
fetch = 
color =
#this extension will get loaded from the file specified
myfeature = ~/.hgext/myfeature.py

Mercurial has an extension mechanism for adding new features. To enable an extension, create an entry for it in [extensions] section. There is a list of extensions for Mercurial and you can write one yourself. Extensions bundled with Mercurial does not need anything after the equals sign, but you need to provide the full path to others.

Now that we have configured it a little bit, we can start using. Mercurial tutorial by Joel Spolsky will teach you, how.

Hello, ZeroTurnaround!

2011-01-14T16:38:00.001+02:00

A week ago I have left Axinom. Now I work in ZeroTurnaround - the famous home of JRebel. I don't want to write about the causes that made me to do it. (Those who interested may ask in private.) The only thing I can say, that I am definitely glad :) I did it.

This job switch also means change of technologies I will be working with. During this week I recalled a little bit of Java and got acquainted with Maven, Ant, Hudson and Selenium (not java specific, but still something new). So look for Java related posts in the near future.

Happy New Year!

2010-12-31T10:44:00.000+02:00

The image is not mine, but I really liked it. Happy New Year to All of you!

Automatic Update Of Moles References To Other Solution Projects

2010-12-20T15:50:00.000+02:00

The situation: I have a solution with several projects in it. One of them is UnitTest project, that uses Moles for mocking. And it has referenses to other projecs in solution as well as to their moled dlls. Every time I change code in my projects and rebuild them, the UnitTest project loses the references to moled dlls, as they allready have other versions. I see that Moles builds new versions of projects' dlls, but it does not update references. Why?

RTFM, Juri.

From the Microsoft Moles Reference Manual (page 12)

The Moles framework for Visual Studio monitors build events and automatically forces the regeneration of stub types for projects that have been updated. For efficiency reasons, this automatic update only works for .moles files that are in the top level folder of the project, to avoid walking large nested project structures. This automatic update creates a smooth experience when writing code in a test-driven development style.

So the automatic update of references works only for .moles files that are in the same folder with the project file. But I have moved all the .moles files into separate folder.

Now that I moved all the .moles files back, it is working.

Solution: Eee Pc Ubuntu 10.10 Wireless Connection Fail After Resume From Hibernate

2010-12-17T23:10:00.001+02:00

After upgrading your Ubuntu to Maverick, you may have experienced some problems using wireless networks. That is when your computer resumes from hibernate, it is no longer able to connect to any wireless network and only a restart will make it do it again. Also some random disconnects from wireless occur. That concerns not only Eee Pc (I have a 1000h), but I believe every computer that uses RaLink network controller. First, check if it is you :)

$ lspci -k|grep -i network --after-context 3
03:00.0 Network controller: RaLink RT2860
Subsystem: Foxconn International, Inc. Device e002
Kernel driver in use: rt2800pci
Kernel modules: rt2800pci, rt2860sta

With Ubuntu 10.10 some hardware that was previously driven by the rt2860sta driver is now driven by default by the rt2800pci driver. Sometimes the new rt2800pci does not work as well as the rt2860sta. In that case it is often possible to switch back by blacklisting. As we already saw, we have both drivers installed and the pci one in use. Now we will create a text file that will allow us to easily switch between the drivers.

sudo gedit /etc/modprobe.d/blacklist-wlan.conf

Copy these 2 lines into the newly created file.

blacklist rt2800pci
#install rt2860sta /bin/false

And save. After the reboot your computer will use the rt2860sta driver. If you want to switch back to the rt2800pci driver, just comment the first line, uncomment the second and reboot.

PS. Solution was found here

SICP: The 8 queens puzzle

2010-12-14T22:59:00.000+02:00

The Google AI Contest is over and now I continue to read the SICP book. Now we are solving the famous 8 queens puzzle. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the k^th queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle. We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n×n chessboard.

In the beginning we are given this procedure.

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

and we need to write all the sub-procedures that are used by the main one. Let's start from the simplest one.

(define empty-board '())

Next task is to write the safe? function. This should determine for a set of positions, whether the queen in the k^th column is safe with respect to the others. I decided to split it into three procedures. 1 checks the horizontal line, one diagonal up and the other diagonal down. We don't actually need the k argument, as we should always check the last queen only. I use reversed-positions as we are starting from the last queen and going to the first one.

(define (safe? k positions)
  (let ((reversed-positions (reverse positions))
        (last (car (reverse positions))))
  (and (horizontal-safe? last (cdr reversed-positions))
       (diagonal-up-safe? last (cdr reversed-positions))
       (diagonal-down-safe? last (cdr reversed-positions)))))

(define (horizontal-safe? q positions)
  (if (null? positions)
      true
      (and (not (= (car positions) q))
           (horizontal-safe? q (cdr positions)))))

(define (diagonal-up-safe? q reversed-positions)
  (if (null? reversed-positions)
      true
      (and (not(= (car reversed-positions) (+ q 1)))
           (diagonal-up-safe? (+ q 1) (cdr reversed-positions)))))

(define (diagonal-down-safe? q reversed-positions)
  (if (null? reversed-positions)
      true
      (and (not(= (car reversed-positions) (- q 1)))
           (diagonal-down-safe? (- q 1) (cdr reversed-positions)))))

The remaining procedures are much easier to write. flatmap should join all the lists, that represent queens on board, into one big list. enumerate-interval just returns a list with values between low and high. adjoin-position just adds new queen to the existing ones.

(define (flatmap proc lst)
  (foldr append '() (map proc lst)))

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (append (list low) (enumerate-interval (+ low 1) high))))

(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list new-row)))

As you can see, there are some parameters in procedures that are not used. They can be safely removed.

(queens 8)

Returns 92 solutions - which is right.

Understanding Pac-Man Ghost Behavior

2010-12-05T11:55:00.000+02:00

A very interesting article about the ghost AI in the world famous game.

Google AI Challenge. Final.

2010-12-04T12:08:00.002+02:00

So the Google AI Contest is over. I have finished in 150 place, which is good, but could be better :).

The winner - bocsimacko - has shared his algorithm and source code in his blog. The same was done by the runner up - _iouri_ - here. As the two best algorithms are revealed, I will not bother with revealing my :) and start with homework - now the task is to go through at least one of them and understand all the ideas discovered and implemented.

I am looking forward to the next Google AI Challenge and this time I will prepare thoroughly to get the high place in it.

Google AI Challenge. Continued.

2010-09-27T15:10:00.001+03:00

Yesterday's 6 hours of coding and implementing the new version of my bot, that killed the previous one on every of 100 testing maps, are not wasted - I am on the 14^th place with ELO 3335.

Google AI Challenge

2010-09-24T13:37:00.000+03:00

University of Waterloo Computer Science Club organized AI Contest, sponsored by Google. Contestants are asked to create a bot that plays PlanetWars game, which is based on GalCon. The game field consists of several planets, that are occupied by one of the players or neutral. Planets produce ships (bigger planets do it quicker) players use to conquer new planets. The goal is to beat the other player.

I am also taking part in the tournament and, francly speaking, doing well. Currently I am around 200th place (username: 2stupidogs) in total ranking and one of the best in Estonia. Here are some strategy thoughts I can share with you as the starting point. These were used by my first 2 bots. (Now I have implemented a more deeper algorithm.) The organisers provide everyone with default strategy bot, that can we further improved. And by making the following small improvements you can make top 500 easily.

Default bot finds his strongest planet and sends half of the fleet from it to the near planet, that it considers to be weak.

First change is to send as many ships as needed to conquer the planet, not just the half.
Then change the planet score formula (Determines how weak enemy planet is). It should depend on distanse, growth rate and current fleet on the planet. For example, count in how many days the new planet will regenerate the fleet you had to use to conquer it. The less it takes, the better the planet for you.
Don't send fleet to the planet where is was sent already. (Well, this is doubtable, but you can try.)
Make a list of weakest planets for your strongest planet (not just the one weakest planet), and send a fleet to all of them as soon as you have enough ships.
Make a list of your strongest planets and look for weakest planets for every of them.

Just implementing this strategy I managed to make into top 350 list, but it was less contestants then.

MongoDB With C++ In Ubuntu

2010-08-25T17:05:00.002+03:00

Install standard repository package.

$ sudo aptitude install mongodb

Create data directory. By default mongo uses /data/db.

$ sudo mkdir -p /data/db/
$ sudo chown `id -u` /data/db

Try to run the server. (If you decided to use another path for data run mongod with --dbpath option)

$ mongod

If it runs, the you are ok. But if it throws an error

mongo: error while loading shared libraries: libmozjs.so: cannot open shared object file: No such file or directory

Then we will have to find that missing library.

$ find /usr/lib/* -name libmozjs.so
/usr/lib/firefox-3.6.8/libmozjs.so
/usr/lib/xulrunner-1.9.2.8/libmozjs.so
/usr/lib/xulrunner-devel-1.9.2.8/sdk/lib/libmozjs.so

Now create a symbolic link

$ cd /usr/lib
$ sudo ln -s xulrunner-devel-1.9.2.8/sdk/lib/libmozjs.so libmozjs.so

Now try to start the server again. It should be working. Start the client and run some queries:

$ mongo
> db.foo.save( { a : 1 } )
> db.foo.find()

Installing Libraries For C++

So the database is up and running, now we need some C++ libs to be able to connect to it.

$ sudo aptitude install libboost-all-dev libpcre++-dev

Now we should be able to run this code, to test the connection.

//tutorial.cpp
#include <iostream>
#include <mongo/client/dbclient.h>

using namespace std;

void run() {
  mongo::DBClientConnection c;
  c.connect("localhost");
}

int main() {
  try {
    run();
    cout << "connected ok" << endl;
  } catch( mongo::DBException &e ) {
    cout << "caught " << e.what() << endl;
  }
  return 0;
}

Build and run this code using:

$ g++ tutorial.cpp -lmongoclient -lboost_thread-mt -lboost_filesystem-mt -lboost_program_options-mt tutorial
$ ./tutorial
connected ok

Determine If Number Is Prime

2010-08-18T22:27:00.007+03:00

The SICP book is still being read...

Now I am going to introduce some algorithms that allow us to say whether the number is prime or not. Again we will start from the simplest one.

Take numbers 1 by 1 starting from 2 to √n and check, if it divides n. The complexity of the algorithm is Θ(√n).

(define (prime? n)
  (define (divides? k)
    (= (remainder n k) 0))
  (define (find-divisor n test)
    (cond ((> (sqr test) n) n)
          ((divides? test) test)
          (else (find-divisor n (+ test 1)))))

  (= n (find-divisor n 2)))

Fermat Primality Test

There is a test for primality with Θ(log(n)) complexity. It is based on Fermat little theorem.

aⁿ ≡ a (mod n), where 1 ≤ a < n

Which means, that if n is prime, then for any integer a, aⁿ − a will be evenly divisible by n.

;this procedure calculates base^exp mod m without using big numbers
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp) (remainder (sqr (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

Unfortunately there are some issues with this test - it is probabilistic. If the test fails, n is certainly composite. But if it passes, it does not guarantee that n is prime, although it shows high probability for n to be. So we can run as many tests as we need to make the mistake probability as low as possible.

(define (fermat-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fermat-prime? n (- times 1)))
        (else false)))

Unfortunately that is not all. There are some numbers that pass the test (for every a!), without being prime. These are called Carmichael numbers. So to determine, if n is prime, we need to check if it passes the Fermat test and is not a Carmichael number, or use a similar Miller–Rabin primality test, that cannot be tricked.

Miller–Rabin Primality Test

It starts from an alternate form of Fermat's Little Theorem:

a^n-1 ≡ 1 (mod n), where 1 ≤ a < n

The difference is that whenever we perform the squaring step in expmod, we check to see if we have discovered a "nontrivial square root of 1 modulo p", that is, a number not equal to 1 or n - 1 whose square is equal to 1 mod n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a < n, computing a^n-1 in this way will reveal a nontrivial square root of 1 mod n.

(define (miller-rabin-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (miller-rabin-prime? n (- times 1)))
        (else false)))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

(define (expmod base exp m)
  (define (!= x y) (not (= x y)))

  (cond ((= exp 0) 1)
        ((and (!= base 1) 
              (!= base (- m 1)) 
              (= (remainder( sqr base) m) 1)) 0)
        ((even? exp) (remainder (sqr (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))

Fibonacci Numbers

2010-07-20T17:40:00.007+03:00

Continuing reading the SICP book...

In every book about algorithms I have read there is always a chapter about the Fibonacci numbers. Mainly on the different algorithms of calculating the n-th Fibonacci number and comparing their order of growth. First comes the algorithm, based on definition:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

This function is good at explaining tree recursion, but is awful for calculating Fibonacci numbers, as it makes too many unnecessary calculations. The order of growth is Θ(Fib(n)), which means exponential. The next comes iterative funcion, which solves the task much better, using less resources and time. Its order of growth is Θ(n) - linear.

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
     b
     (fib-iter (+ a b) a (- count 1))))

But there is also an algorithm that calculates Fibonacci number with Θ(log n) complexity. There, in the book they give you the function with gaps and some pointers ( no C here :) ), how to fill them.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   [??] calculate p'
                   [??] calculate q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

The authors remind us of the transformation of the state variables a and b in the previous (iterative) fib-iter procedure: a ← a + b and b ← a. Provided these state changes are labeled transformation T, applying T repeatedly for n iterations starting with a = 1 and b = 0 will produce the pair a = Fib(n + 1) and b = Fib(n). So the Fibonacci numbers are produced by the n^th power of the transformation T (Tⁿ), starting with the pair (1, 0).

Now consider the family of transformations T_pq which transforms the pair (a, b) according to the following rules:

a ← bq + aq + ap
b ← bp + aq

Where transformation T is just a special case of T_pq, where p = 0 and q = 1. Now it's up to you to find the transformation T_p'q' such so, if we apply T_pq twice, the effect is the same as using a single transformation T_p'q' of the same form. Compute p' and q' in terms of p and q and put into the function.

I will not provide the solution here, in case you want to handle it yourself. But if you are eager to see the result, visit some other blog that has the solution. :)

Structure and Interpretation of Computer Programs

2010-07-19T10:52:00.001+03:00

Recently we decided to read the "Structure and Interpretation of Computer Programs" book through. And not just read it, but also to complete the exercises, given after each chapter. On Friday we had a first meeting, concerning the first chapters we read.

As a working environment the Racket was chosen. It turned out to be a very powerful instrument: not just the language and it's interpretor, but almost a complete IDE with autocomplete, unit tests and even debugging.

That is how errors are shown in Racket. Yes, these arrows are cute.

The meeting was nice and quite productive. We shared some solutions to exercises, and also some were solved just in place. We learned that

(A 2 6)

is a very big number :), where

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

P.S. Thanks Anton for the picture :)

C# Function That Mimics SQL IN-operator

2010-07-14T17:32:00.001+03:00

A good question was asked on stackoverflow, and an even better answer received.

How can we rewrite the condition

if (a == x || a == y || a == z)

to make it more readable?

The answer is

public static bool IsIn<T>(this T obj, params T[] collection) {
   return collection.Contains(obj);
}

if (a.IsIn(x, y, z))

PS. Sorry for such a long period with no posting. You know, summer, Sun, beach, sea, +30 and vacation.

Google Code Jam 2010 - Round 1

2010-05-24T20:12:00.003+03:00

Sadly I didn't qualify into Round 2. But actually didn't have any chance, because at the time I posted my first solution to the A problem, the top scorers board was already full of 100s (That is maximum one could get for solving all 3 problems.) So as the qualifying round this one had 3 problems: A, B and C, with A being the simplest one and C the hardest one. As I participated in Round 1B, here are the thoughts on problems that I met there.

File Fix-It

(Problem Text)

This one is about creating the tree of folders and counting how many folders you have to create. The solution algorithm is simple.

We create a root node.
Read the next folder, we must create (with path).
Split the path.
Add folders one by one to the root node, counting how many of them we had to create.
Goto 2

Here is my c++ code.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Node{
public:
  string name;
  map<string, Node> children;

  Node(){}
  Node( string n ):name(n){}
};

vector<string> split( const string& s, const string& delimiter ){
  vector<string> result;
  string::size_type from = 0;
  string::size_type to = 0;

  while ( to != string::npos ){
    to = s.find( delimiter, from );
    if ( from < s.size() && from != to ){
      result.push_back( s.substr( from, to - from ) );
    }
    from = to + delimiter.size();
  }
  return result;
}

int add_to_node( Node* current, vector<string>& path ){
  int r = 0;
  for (int i=0; i<path.size(); i++){
    if (current->children.find(path[i]) == current->children.end()){
      r++;
      Node child(path[i]);
      current->children[path[i]] = child;
    }
    current = &( current->children[path[i]] );
  }
  return r;
}

int main(){
  int t;
  cin >> t;
  for (int i=1; i<=t; i++){
    int n, m;
    cin >> n >> m;
    Node root("");
    for (int j=0; j<n; j++){
      string s;
      cin >> s;
      vector<string> path = split( s, "/" );
      //cout << root.children.size();
      add_to_node( &root, path );
    }
    int total = 0;
    for (int j=0; j<m; j++){
      string s;
      cin >> s;
      vector<string> path = split( s, "/" );
      total += add_to_node( &root, path );
    }
    cout << "Case #" << i << ": " << total <<endl;
  }
}

Picking Up Chicks

(Problem Text)

This problem is about finding out how many (slow) chicks prevent one particular (fast) chick to get to the barn in time. (This solution is in ruby). My solution actually is not optimal, but it is still solving the problem.

#!/usr/bin/env ruby

c = ARGF.readline.to_i
(1..c).each do |i|
  n, k, b, t = ARGF.readline.split(" ").collect{|x| x.to_i }
  x = ARGF.readline.split(" ").collect{|y| y.to_i }
  v = ARGF.readline.split(" ").collect{|y| y.to_i }

  times = []
  x.each_index do |j|
    d = b-x[j]
    times << ( d % v[j] == 0 ? d / v[j] : d / v[j] + 1 )
  end

  chicks = 0
  max = 0
  swaps = 0

  times.reverse!
  times.each_index do |ti|
    max = times[ti] > max ? times[ti] : max
    if t >= max
      chicks += 1
    elsif t >= times[ti]
      chicks += 1
      #we need to swap only with those chicks that will arrive later and won't get in time
      swaps += times[0...ti].collect{|one| one > times[ti] && one > t ? one : nil }.compact.count
    end
    break if chicks >= k
  end

  print( "Case #", i,": ", (chicks >= k ? swaps : "IMPOSSIBLE"), "\n" )
end

Your Rank is Pure

(Problem Text)

I ran out of time before I even could understand what this problem was all about. So i cannot tell anything about it. I will try to solve it later though.

I have also checked out the official solutions for the first 2 problems, and they appear to be much cleaner and simpler than mine. My approach is too straightforward. Have to practice more...

Replacing Text In Html (Outside Html Tags)

2010-05-20T12:53:00.001+03:00

private const string OUTSIDE_TAG_LOOKAHEAD = "(?![^<]+>)";

public static string HighlightWordsInHtmlText( string htmlText, params string[] words ){
  if (words == null || string.IsNullOrEmpty(htmlText) ) return htmlText;
  Regex regex = new Regex(OUTSIDE_TAG_LOOKAHEAD + "("+ string.Join("|", words) +")", RegexOptions.IgnoreCase);
  return regex.Replace(htmlText, "<span class=\"highlight\">$&</span>" );
}

OUTSIDE_TAG_LOOKAHEAD - uses regular expression magic, that matches text inside tags, but as it is negated, the text matched is really outside of html tags.
$& - refers to the current match. We cannot put here any word as we don't precisely know what of them was found and in what case.
This example matches also tron in strong, if you need an exact match add word boundaries like that:

OUTSIDE_TAG_LOOKAHEAD + "\\b("+ string.Join("|", words) +")\\b"

Try Ruby Online

2010-05-17T11:37:00.000+03:00

Interactive ruby console is available at http://tryruby.org/. It is not very convenient to delete wrong entered character there (you should put a cursor on it, not after it, and press backspace), but it works! :)

[Almost] Universal Makefile

2010-05-16T15:25:00.006+03:00

#compiler
CC=g++
#compiler options
OPTS=-c -Wall
#source files
SOURCES=$(wildcard *.cc SomePath/*.cc )
#object files
OBJECTS=$(SOURCES:.cc=.o)
#sdl-config or any other library here. 
#``- ensures that the command between them is executed, and the result is put into LIBS
LIBS=`sdl-config --cflags --libs`
#executable filename
EXECUTABLE=Main.run
#Special symbols used:
#$^ - is all the dependencies (in this case =$(OBJECTS) )
#$@ - is the result name (in this case =$(EXECUTABLE) )

all: $(EXECUTABLE)

$(EXECUTABLE): $(OBJECTS)
 $(LINK.o) $^ -o $@ $(LIBS)

clean:
 rm $(EXECUTABLE) $(OBJECTS)

It is hard to say why it works, but it works. "Make" uses hidden rules to compile object files from sources.

See there for more (in Russian): http://abuse.edu.ioffe.ru/cluster/makeman or read the manual :)

Clean Code

2010-05-14T10:57:00.000+03:00

The "cleanest" code I have ever seen.

Google Code Jam 2010 - Qualification round

2010-05-09T10:22:00.004+03:00

Qualification round of Google Code Jam is over, I have managed to get only 53 points of 99 possible. Not a very good start, but nevertheless I proceeded to Round 1. Here is some of my code, that I solved the problems with.

Snapper Chain

It was the easiest problem to solve. (Problem Text) The key to the solution is that the chain shows number of snaps in binary (actually last n bits of it), and light is on when all snappers are in ON state (= the last n bits are all equal to 1).

#include <iostream>
#include <math.h>

using namespace std;

int main(){
  unsigned int t, n, k;
  cin >> t;
  for (unsigned int i=1; i<=t; i++){
    cin >> n >> k;
    unsigned int d = (1U << n ) - 1;

    cout << "Case #" << i << ": " <<
          (  (k & d) == d ? "ON" : "OFF" ) << endl;
  }
}

Provided code was successful with large input too.

Fair Warning

This one was a little bit harder. (Problem Text) The key is that the difference is time between any 2 events stays the same, no matter how big/small number of starboseconds we add to all of them. So we need a greatest common divisor of the differences.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint;

uint gcd( uint a, uint b ){
  if ( b == 0 ) return a;
  return gcd( b, a % b );
}

uint op_minus( uint a, uint b){
  return a > b ? a - b : b - a;
}

int main(){
  uint c, n, tmp;
  cin >> c;
  for (uint i=1; i<=c; i++){
    cin >> n;
    vector<uint> t;
    for (uint j=0; j<n; j++){
      cin >> tmp;
      t.push_back( tmp );
    }
    //after first transformation t[i] will have the difference 
    //between former t[i] and t[i+1]. 
    //The last member t[n-1] remains - it will be needed at the end 
    //to find the required amount of seconds to add 
    transform( t.begin(), t.end()-1, t.begin()+1, t.begin(), op_minus );
    //after second transformation t[i] will have the gcd of t[i-1] and t[i]
    //I use the following feature of gcd: gcd(a,b,c) == gcd(gcd(a,b), c)
    //every time we are at t[i] there is alreaady a gcd(t[i-2], t[i-1]) in t[i-1]
    transform( t.begin(), t.end()-2, t.begin()+1, t.begin()+1, gcd );
    
    uint remainder =  t.back() % *(t.end()-2);
    cout << "Case #" << i << ": " <<
            (remainder > 0 ?  *(t.end()-2) - remainder : 0 )<< endl;
  }
}

This code does not solve the large input as there are integers up to 10⁵⁰, and we need to use a bigint class, which I didn't find/write myself.

Theme Park

This is the hardest one to solve, because small input can be solved with straight approach, but the large one needs some different. And I couldn't figure it out. (Problem Text) The code that solves the small input is pretty straightforward. We take the group at the beginning of the queue as soon as it can fit in roller coaster. And don't forget that 1 and the same group cannot be taken twice in 1 run (that may happen if number of seats in roller coaster is more than all the number of people in queue)

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned int uint;

int main(){
  uint t, r, k, n, tmp, sum, total;
  cin >> t;
  for (uint i=1; i<=t; i++){
    cin >> r >> k >> n;
    vector<uint> g;
    total = 0;
    for (uint j=0; j<n; j++){
      cin >> tmp;
      g.push_back( tmp );
    }
    uint a=0;
    for (uint j=0; j<r; j++){
      uint sum = 0;
      for (uint b=0;  b<n && sum + g[a] <= k; a=(a+1)%n, b++ ){
        sum += g[a];
      }
      //cout << "sum: " << sum << " ";
      total += sum;
    }
    cout << "Case #" << i << ": " << total << endl;
  }
}

Pity, the same approach is too slow for large input.

The "official" solutions can be found here.

Escaping Curly Bracket in String.Format()

2010-05-04T16:43:00.006+03:00

If you need to print a curly bracket in string, when using string format, just put it twice in a row.

string.Format("{{ hello world }}")//{ hello world };
string.Format("{{0}}", 45);//{0}
string.Format("{{{0}}}", 45);//{45}
string.Format("{0:N}", 45);//45.00
string.Format("{{{0:N}}}", 45);//{N}

The last one is not `{45.00}`, because the parser when reading `}}}` first prints the escaped `}`, and only then closes the formatting section. And as `N}` number format does not mean anything to it, it just prints it out.

Pointers and Memory Handling In C++

2010-04-13T21:58:00.002+03:00

Handling memory resources doesn't need any special knowledge in C++, the memory is freed as soon as the variable is out of scope. Unless you are dealing with pointers. Memory that is addressed by pointer is not freed automatically, even if you are out the scope already. It should be done manually, using delete or some provided special function (If it's some library).

Let's take the following function as an example.

void use_file( const char* fn ){
  FILE* f = fopen( fn, "w" );
  //using f;
  fclose( f );
}

At first sight nothing seems to be wrong here. The memory allocated by fopen is freed at the end of the function with fclose. But what if some exception occurs between those two? Yes, the memory will not be freed. The first attempt to fix this is to add exception handling.

void use_file( const char* fn ){
  FILE* f = fopen( fn, "w" );
  try {
    //using f;
  }
  catch(...){
    fclose( f );
    throw;
  }
  fclose( f );
}

The problem of this solution is that it is too diffusive. Anybody wants to write everywhere try-catch blocks, just to make sure the memory is freed? I am too lazy to do that. There should be a more elegant solution. We can define a class File_ptr, that will behave just like FILE*, but will free resources automatically.

class File_ptr{
  FILE* fp;
public:

  //Constructor that creates File_ptr from FILE*
  File_ptr( FILE* pp ){ fp = pp; }
  
  //Destructor, that closes the file and frees memory
  ~File_ptr(){ if (fp) fclose( fp ) };
  
  //Type conversion operator. It is called every time an object 
  //of File_ptr type needs to be converted to FILE*;
  operator FILE* (){ return fp; }
}

This is a minimum amount of functions that needed for this wrapper class to work. The use_file function then will look like that.

void use_file( const char* fn ){
  File_ptr f = fopen( fn, "w" );
  //using f;
  //file will be closed automatically as soon as f is out of scope
}

But actually it is not all yet. You will also need to define a copy constructor and an assign operator in File_ptr. Here is the good explanation, why.

Joining a Vector And Splitting String In C++

2010-03-11T11:10:00.018+02:00

We need these two opposite operations more or less often. As C++ stl does not provide us these functions, we need to write them ourselves.

template <class T>
string vector_join( const vector<T>& v, const string& token ){
  ostringstream result;
  for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); i++){
    if (i != v.begin()) result << token;
    result << *i;
  }
  return result.str();
}

vector<string> string_split( const string& s, const string& delimiter ){
  vector<string> result;
  string::size_type from = 0;
  string::size_type to = 0;

  while ( to != string::npos ){
    to = s.find( delimiter, from );
    if ( from < s.size() && from != to ){
      result.push_back( s.substr( from, to - from ) );
    }
    from = to + delimiter.size();
  }
  return result;
}

The functions produce the following results:

string ss[] = { "qwerty", "hello", "world" };
vector<string> v( ss, ss+3 );
vector_join( v, ", ") );//"qwerty, hello, world"

int ii[] = { 111, 222, 333 };
vector<int> vi( ii, ii+3 );
vector_join( vi, "; ") );//"111; 222; 333"

string_split( "qwerty, hello, world", ", " );
//results in [ "qwerty", "hello", "world" ]
string_split( ", , wow, , qwerty, hello, world, ", ", " );
//results in [ "wow", "qwerty", "hello", "world" ]

If we have a space as delimiter, we can split string more efficient way and even make use of templates too

template <class T>
vector<T> string_split( const string& s ){
  vector<T> result;
  istringstream ss(s);
  copy( istream_iterator<T>(ss), istream_iterator<T>(), 
        back_inserter( result ) );
  return result;
}

And the tests:

string_split<float>( "11.1 22.2 33.3" );//[ 11.1, 22.2, 33.3 ]
string_split<int>( "111 222 333" );//[ 111, 222, 333 ]

Restoring the MSSQL Database

2010-03-02T10:28:00.003+02:00

Restoring of the database can be done through the database menu, or [I prefer] like that.

RESTORE DATABASE DatabaseName
FROM DISK = 'C:\Path\To\Backup\File\DatabaseName.bak'
WITH REPLACE

If you get the following error: "Exclusive access could not be obtained because the database is in use", try to get the list of connected users:

EXEC SP_WHO2

Find ones that are connected to DatabaseName and kill them

KILL [SPID]

How To Get Last Inserted Row ID In PostgreSQL

2010-02-06T21:26:00.003+02:00

Imagine we have a test table.

CREATE TABLE test (id SERIAL, name TEXT);

Use the RETURNING statement in the INSERT statement.

INSERT INTO test (name) VALUES ('My Name') RETURNING id;

 id 
----
  1 

INSERT INTO test (name) VALUES ('My Name 1') RETURNING id;

 id 
----
  2

Remove User List From Ubuntu Karmic Login

2010-01-23T18:09:00.005+02:00

As I use Ubuntu on my eeePC, I like better typing than using touchpad.

That would remove user list from login screen and will make you type your username instead of selecting it.

sudo -u gdm gconftool-2 --type bool --set /apps/gdm/simple-greeter/disable_user_list 'true'

Silverlight Cross-Domain Http Request Results Into Security Exception

2010-01-15T12:21:00.004+02:00

That is because cross-domain http requests are restricted in Silverlight. One has to add a crossdomain.xml into web service provider root folder with the following lines.

<?xml version="1.0"?>
<!DOCTYPE cross-domain-policy SYSTEM "http://www.macromedia.com/xml/dtds/cross-domain-policy.dtd">
<cross-domain-policy>
 <allow-access-from domain="*" />
</cross-domain-policy>

For more info see Network Security Access Restrictions in Silverlight.

Date (Without Time) In MsSql

2010-01-11T13:04:00.003+02:00

Should be something like that:

SELECT dateadd(day, datediff(day, 0, getdate()), 0)

C++ Header Files With Classes and Makefile

2010-01-07T21:52:00.003+02:00

2 good tutorials:

Class code and header files.

Makefile

Updated: And 1 more article about c++ unit test frameworks.

Date Parsing In C#

2009-12-20T11:08:00.004+02:00

DateTime.Parse("Dec 13 18:06");//Results in {06.12.2009 13:18:00}

Why?!

Virtual Desktop Manager For Windows

2009-12-03T12:21:00.003+02:00

I got too accustomed to multiple desktops on my home Ubuntu computer, that working under Windows with many open programs without ability to share them among several desktops made me too uncomfortable. VirtuaWin - The Virtual Desktop Manager was the solution :). Now I am happy again.

Add List To App.Config

2009-11-15T00:54:00.008+02:00

One can add list and not only a list to App.Config file of the .Net project. That can be done by declaring your own configuration element, say a ProductElement

class ProductElement : ConfigurationElement
{
  [ConfigurationProperty("name", IsKey=true, IsRequired=true)]
  public string Name
  {
    get { return this["name"]; }
  }

  [ConfigurationProperty("price")]
  public int Price
  {
    get { return Convert.ToInt32(this["price"]); }
  }
}

class ProductElementCollection : ConfigurationElementCollection
{
  protected override ConfigurationElement CreateNewElement()
  {
    return new ProductElement();
  }

  protected override object GetElementKey(ConfigurationElement element)
  {
    return ((ProductElement)element).Name;
  }
}

class ProductConfigurationSection : ConfigurationSection
{
   [ConfigurationProperty("products")]
   public ProductElementCollection Products
   {
      get { return (ProductElementCollection)this["products"]; }
   }
}

Use it in your app.config like that:

<configuration>
   <configSections>
      <section name="productConfigurationSection"
        type="MyNamespace.ProductConfigurationSection, MyAssembly" 
        requirePermission="false" />
   </configSections>
   <productConfigurationSection>
      <products>
         <add name="car" price="750000" />
         <add name="milk" price="13" />
      </products>
   </productConfigurationSection>
</configuration>

Note that Name is used as a key, so you cannot create 2 Products with the same name. But you can add more fields to the Product, just mark them accordingly. And from code you can access this section with:

ProductConfigurationSection section = (ProductConfigurationSection) ConfigurationManager.GetSection("productConfigurationSection");

The Most Intelligent Java IDE — Now Free and Open Source

2009-10-20T12:05:00.003+03:00

Hardly anyone will argue, that IntelliJ IDEA is one of the best IDE for Java and Ruby(Rails). And now it is going to be free! Yes, this title is taken from IntelliJ Site. Next version of the product will be free, and it can already be downloaded from the coerced link.

Convert Different Audio In Command Line in Ubuntu

2009-09-16T11:15:00.002+03:00

Converting different audio formats in Ubuntu is quite an easy task. Just start Soundconverter, or first install it, if you don't have.

sudo apt-get install soundconverter

But I needed to do it in command line. Soundconverter can do it either. (What a good boy!) But you just need to know the mime-type of the output file (simply adding the desired suffix doesn't work). For example, to convert "my_favourite mp3" to wav you can use:

soundconverter -b -m audio/x-wav -s .wav my_favourite.mp3

See the full list of mime types.

For the available options see

soundconverter -h

man soundconverter

Ruby Shoes

2009-08-02T13:15:00.000+03:00

I wanted to try ruby Shoes already long ago, but just didn't know what to start with. Until I found a quiteuseful article about making a game on ruby shoes. I tried it and it was unexpectedly easy. Here are some my subjective thoughts about it.

Good things:

It is very easy to study.

One can begin writing using shoes quite quickly and straightforward. No big manuals or hardly understandable api and howtos.

It is cute. :)

Yes, I really liked it. Different objects are created very easy, such as:

Shoes.app { button("Click me!") { alert("Good job.") } }

You also can draw with provided rect, oval or even arrow methods or import an image as a background. Motion ability is also provided:

Shoes.app do #A star that moves after the mouse pointer.
  @shape = star :points => 5
  motion do |left, top|
    @shape.move left, top
  end
end

Unfortunately there were also some disadvantages:

The whole Shoes application should be in Shoes.app block.

Seem to me to be a little bit uncomfortable.

You have to pass everywhere app variable that denotes the Shoes application.

Well, not just everywhere... But if you create your own class, which objects have to be drawn you also have to pass the application variable, or make it global, which is not really good pattern.

class RedRect

  def initialize( app )
    app.fill red
    app.rect :left => 10, :top => 10, :width => 40 
  end
end

Shoes.app do
  RedRect.new( self )
end

Pity, but it is slow.

The resulting snake in the game responds in about 2 seconds. It is a long period of time, especially on higher levels with higher speed.

In conclusion the authors' words about Shoes are right:"Shoes is a tiny graphics toolkit, designed for beginners". It can be used to create quickly a small application, where speed is not essential.

Access DOM Element Within IFrame

2009-07-31T10:42:00.006+03:00

Suppose we have a html page with frame or iframe in it and we need to get an element in it. Simple

document.getElementById("myElement");

will not find it, as it is searched only in the main page, where the frame is set. What we should do, is to find the frame first and then look for needed element in the right frame.

frame = document.getElementById("myFrame"); 
frame.contentWindow.getElementById("myElement");

Concatenate Strings On Group By In Sql

2009-07-09T14:41:00.000+03:00

Imagine we have the following table.

CREATE TABLE MyTable (id int, name varchar, value int);

INSERT INTO MyTable (id,name,value) VALUES (1, 'Hello', 4);
INSERT INTO MyTable (id,name,value) VALUES (1, 'World', 8);
INSERT INTO MyTable (id,name,value) VALUES (5, 'Great!', 9);

The result we would like to acquire is:

| id |   name_values    |
+----+------------------+
|  1 | Hello:4; World:8 |
|  5 | Great!:9         |

Names and values are concatenated into strings and grouped by id. We need an aggregate function, that concatenates strings for that. Here are some solutions for different sql databases.

MySql

This case is most easy one. Lucky users already have the GROUP_CONCAT(expr) function. This query should give the answer.

SELECT id, GROUP_CONCAT(name + ':' + value SEPARATOR '; ') AS name_values FROM MyTable GROUP BY id;

PostgreSql

The solution here is a bit more difficult, but nevertheless easy enough. We need to create our own aggregate function and use it in our query.

CREATE AGGREGATE aggr_textcat(
  basetype    = text,
  sfunc       = textcat,
  stype       = text,
  initcond    = ''
);

SELECT id, substring(aggr_textcat(', ' || name || ':' || value) from 2) AS name_values FROM MyTable GROUP BY id;

Here we used already existing function to concatenate text fields textcat, but we could write our own.

MsSql

Since version 2005 it became also possible to write your own aggregate function in MsSql, but here I provide another solution using inner select and xml path.

SELECT id, SUBSTRING(SELECT '; ' + name + ':' + CAST(value AS varchar(MAX)) 
FROM MyTable WHERE (id = Results.id) FOR XML PATH ('')),3,9999) AS name_values
FROM MyTable Results
GROUP BY id

Insert Large Amount Of Rows Into PostgreSQL

2009-06-24T20:48:00.004+03:00

Inserting large amount of data into postgres database may take a lot of time, if you use INSERT command. Consider better COPY command, though it is not so flexible.

COPY my_table_name(int_column, string_column, bytea_column) from stdin;
1    THISisSTRING    \\001\\017\\044
2    THISisSTRING2   \\001\\017\\062
3    THISisSTRING3   \\001\\017\\102

The default delimiter is tab (\t).

To acquire the right format in 1 particular case, you can fill database with some values using INSERT command and dump database with pg_dump. The resulting file will contain the right COPY syntax.

Ajax With InnerHTML()

2009-06-22T12:50:00.004+03:00

InnerHTML is not a standard, but it is more useful comparing to working with DOM with such functions as createElement and/or appendChild. But there is a problem with it: if you need further to handle the new added data (to refer new elements, to change/add their attributes), innerHTML is not good at all, as innerHTML simply visually adds new elements, but it does not really insert them in the DOM structure of the document. Attempting to do a document.getElementById() on a tag inside of code that was added using innerHTML just doesn't work. At least it didn't work for me in Firefox 3.

The folowing code can be accepted as the workaround.

var newDiv = document.createElement("div");//create new div
newDiv.innerHTML = xhr.responseText;//add response into new div
var container = document.getElementById("container");//find place where the response should be placed to
container.parentNode.insertBefore(newDiv, container);//add new div before the container
newDiv.parentNode.removeChild(container);//remove container

This way we get the same resulting document, but we can further work with DOM.

Master Degree Acquired

2009-06-12T17:25:00.000+03:00

Yes, at last. Now I am the Master of the Information Technology :) Sounds good!

Microsoft Excel 2007 Problems

2009-06-10T17:16:00.001+03:00

It is a must read, if you want to know what problems you may encounter, when exporting to excel 2007: "Microsoft Office XML formats ? Defective by design"

Array To String

2009-06-07T19:18:00.011+03:00

Oh, how I hate String.join(string, string[]) in mscorlib. And it is because of string[] argument. Why couldn't they make it accept array of objects and, before joining, cast every object with ToString() method?

Had to make it myself:

public string ListJoin<T>(string separator, T[] objs)//C# v3
{
  return string.Join(separator, Array.ConvertAll(objs, item => item.ToString()));
}

public string ListJoin<T>(string separator, T[] objs)//C# v2
{
  return string.Join(separator, Array.ConvertAll<T,string>(value, new Converter<T,string>(delegate(T i){return i.ToString();})));
}

Export String Values To Excel 2007

2009-05-14T10:56:00.016+03:00

If you encounter a following error, while exporting to Excel 2007 (.xlsx)

Errors were detected in file MyFileName.xlsx.
Repaired Records: Cell information from /xl/worksheets/sheet1.xml part

then, probably, you are exporting string values in wrong format. The right structure in this case is

<sheetData>
  <row>
   <c>
     <v>99999</v>
   </c>
   <c t="inlineStr">
     <is>
       <t>My Text</t>
     </is>
   </c>
  </row>
</sheetData>

Note, that there is no <v> tag in <c> as it should be with numbers. Instead you have to make an inline string (<is>) tag and put text (<t>) tag with needed text in it. Do not forget to add the t="inlineStr" attribute to <c> tag.

More info can be found developer:network.

Method with arbitrary number of parameters in C#

2009-04-27T16:51:00.006+03:00

One can also create a method with variable number of parameters in C#. It is needed, for example, when you have such logic, where you need to take value from one place, if it is not null, or from the other, or from the third place, if the first two are nulls, and so on. This can help:

public static T FirstNotNull<T>(params Nullable<T>[] objects) where T : struct
{
  foreach (Nullable<T> obj in objects)
    if (obj.HasValue) return obj.Value;
  return default(T);
}

Reserved word params shows, that we deal with an array of parameters. This parameter can only be the last one in a function. You can put other types of parameters before, but no after.

The function can be called like that:

HelperClass.FirstNotNull<int>(firstValue, secondValue, thirdValue, fourthValue);

The first not null value of these four is returned, or default value of the type, if all are nulls.

System.Reflection To the Rescue

2009-03-31T12:43:00.005+03:00

Many people ask if there is a possibility to call a method, if we have its name as string. Actually, it is very useful feature. Imagine we have an Object with several properties which represent the same thing, but in different languages.

class MyClass
{
    public string State_EN;
    public string State_DE;
    public string State_RU;
}

We want to show the state of MyClass object in proper language. We create a method for that

public string State(string language)
{
}

Language is the 2-letter code representation of language ("EN", "DE", "RU"...). So what should be inside the State method? Solutions with "if" and "switch" are not good - if you have to add more languages, you must rewrite the State method. But we are lazy and don't want to do that. What we need here is System.Reflection.

using System.Reflection;
[...]
public string State(string language)
{
    PropertyInfo property = typeof(MyClass).GetProperty("State_" + language);//find the property
    if (property != null)
        return (string)property.GetValue(this, null);//get value of the property
    return null;
}

The same way we can search for method, if we know the method's name (with GetMethod instead of GetProperty). And call it with "Invoke" and proper parameters.

Using Generics With System.Nullable

2009-03-18T12:41:00.009+02:00

When we have a Nullable type value and we want to assign it to some control, then we need to check if is not null first.

SomeLabel.Text = object.MyProperty.HasValue ? object.MyProperty.Value : String.Empty;

But if we have many nullable properties? I don't want to copy/paste this check on every line. So we need a method, that checks for nulls. But I also don't want several methods for every type. So we need to use generics.

I created some methods for myself

public static string ValueOrEmptyString<T>(Nullable<T> obj) where T : struct
{
  return obj.HasValue ? obj.Value.ToString() : "";
}

public static T ValueOrDefault<T>(Nullable<T> obj, T defaultValue) where T : struct
{
  return obj.HasValue ? obj.Value : defaultValue;
}

public static T ValueOrDefault<T>(Nullable<T> obj) where T : struct
{
  return obj.HasValue ? obj.Value : default(T);
}

"where T : struct" - is needed for compiler to understand that this method is allowed only for types that belong to System.ValueType.

I can use these methods like that

SomeLabel.Text = ValueOrEmptyString<int>( object.MyIntProperty );
SomeDateTimeControl.Date = ValueOrDefault<DateTime>( object.MyDateTimeProperty );
SomeReferenceControl.SelectedObjecId = ValueOrDefault<int>( object.MyIntProperty, -1 );

How To Split Audio CD Image (.flac) Into Several Tracs In Ubuntu

2009-02-18T12:12:00.009+02:00

$ sudo apt-get install cuetools shntool flac #install needed tools
$ cuebreakpoints sample.cue | shnsplit -o flac sample.flac #read breakpoints from cue and give them to splitter
$ cuetag sample.cue split-track*.flac #add tags to newly created files

More info is there.

Eee Control Tray For Ubuntu

2009-02-13T15:29:00.009+02:00

eee-control-tray is a package that one can install on Ubuntu (or other Debian system) to obtain an easy interface to configure Fn shortcuts and other useful options.

Comparing 2 Audio (*.wav) Files

2008-11-12T11:44:00.136+02:00

We already know the structure of wave file and thus we are able to read it byte by byte (actually we need to read the data chunk sample by sample). Now the next move is to get "fingerprints" from our files.

Fingerprint

A fingerprint can uniquely and compactly represent an audio file. It consists of several points of local energy maximum in audio spectral density. How the spectral density varies in time can be shown by a spectrogram. The most common format is a graph with two geometric dimensions: the horizontal axis represents time, the vertical axis is frequency; a third dimension indicating the amplitude of a particular frequency at a particular time is represented by the intensity or colour of each point in the image, e.g., the brighter the shade, the more energy is contained in the time-frequency point. The only thing we need is a amount of acoustic energy in predefined frequency and time.

A spectrogram of 30 seconds of the part of Pet Shop Boys "West End Girls" song starting from 1:00

Spectrograms can be obtained by Short Time Fourier Transform. The audio samples are grouped into analysis time windows (preferably overlapping) w_i of equal length N, with w_i denoting the i-th window. For each window the Fourier transform is calculated, giving a complex vector v_i = STFT(w_i) of the same length as the window. Because in this case the input given to the Fourier transform always are vectors of real numbers, the output complex vectors obey the symmetry:

v_i[q] == -v_i[N-q+1]

So the complete information is contained in the first N/2 components of the complex vector v_i.

The Fourier transform decomposes the signal given by the samples inside each input window in terms of sine waves of discrete frequencies. These frequencies are integer multiples of the fundamental frequency which is determined by the window length N and the sampling rate S of the waveform representation. The frequency F_k for a particular index k in the complex vector may be calculated by using the following formula:

F_k = k * S / N , where k = 0, ... ,N/2

The first frequency F₀ is always zero. If we have a sampling rate of 44100 Hz and a window length of 1024 samples, the base frequency F₁ is 43.0664 Hz and the maximum frequency F₅₁₂ is the Nyquist rate 22050 Hz.

Then we need the absolute value for each component of v_k to get a measure of how strongly a discrete frequency F_k is present in the decomposition of the i-th window of audio file. This data can then be used for plotting the spectrogram. When the spectrogram is plotted the fingerprint points are chosen to be points that are local maximum within regions of fixed size surrounding the point. Larger region size leads to fewer but possibly more significant points. The resulting features are saved as pairs of integer numbers (i, k) with i being the window index and k being the frequency index.

Structure Of *.wav Audio Files

2008-11-07T10:43:00.038+02:00

Wave file structure is very simple. The structure can be divided into 3 parts (chunks).

First chunk: The first 4 bytes should be "RIFF". Then come 4 bytes, which indicate the size of file. Then comes "WAVE".

Second chunk: It starts with "fmt ". Then come 4 bytes showing the length of "fmt " chunk. Then come audio format, number of channels, sample rate, Byterate, Block align and bits ber sample.

Third chunk: It is the audio data itself. As always 4 first bytes - name of the chunk. 4 bytes after that - the length of the chunk in bytes. After that come samples itself. 2 * number_of_channels bytes each sample.

There can be also other chunks between the first and the third, but they are really not widely used. If you got interested in it, a very good article about "Wave file format" is on The Sonic Spot.

So we have here an example. We see the first chunk (purple). It shows the length of the file - 0x(00 00 08 24) = 0x824 = 2084

Bytes should be read in reverse direction. First read byte has the smallest rank!

You can check yourself: left channel sample #5 = 0xE734 and right one is 0xA623.

Continued there...

Going to English

2008-11-07T10:42:00.001+02:00

I decided to continue writing here in English. So I can be read by much more audience. I hope my English is as good as my native language. Will see if it works so. :)

Install Ubuntu 8.04 on Asus Eee PC 1000h

2008-09-03T16:11:00.022+03:00

Приобрёл себе Asus Eee Pc 1000H. Установленный там Xandros что-то не очень вдохновил, поэтому решил поставить туда свою любимую Ubuntu. Что для этого нужно было сделать...

Создание загрузочной USB и установка Ubuntu.

Об создании загрузочной флэшки очень хорошо написано на официальном сайте Ubuntu. Я выбрал вариант с UNetbootin.

Загрузка и установка проблем вызвать не должна, поэтому детальное описание опускаю.

После установки

Не работает сеть (ни ethernet, ни wifi), некоторые комбинации клавиш (Fn+F2, Fn+F7, Fn+F8, Fn+F10/F11/F12 ), вебкамера.

Настройка сети

Самый простой способ на мой взгляд - это установка неофициального специального Ubuntu kernel, оптимизированного под Eee Pc.

Shortcuts

Шорткаты устанавливаются благодаря http://forum.eeeuser.com и его пользователю elmurato. Нужно скачать его скрипты и установить. К сожалению шорткаты начинают работать только после логина. Так что если вам надо отключить звук во время загрузки, у вас это получится только вставив наушники.

WebCam

BIOS. Onboard devices. WebCam Enabled.

Первые впечатления

2008-07-15T19:24:00.049+03:00

Итак, делюсь первыпи впечатлениями, как ощущения после перехода с Ruby на C#. Пока всё, с чем я столкнулся, это неудобства:

Null class.

Отсутствие null как объекта. Затрудняет жизнь многочисленными провернками на null. Паттерн introduce null object не особо спасает. Писать для каждого класса нулевой объект не радует. Можно ли реализовать 1 общий класс, от которого всё наследуется?

System.Linq библиотека

Вроде бы удобная вещь, но! Она была нагло ~~спи~~слизана с ruby, причём сделано это очень криво. Зачем-то нужно было менять названия методов. Плюс были портированы не 1 в 1. В результате имеем:

Method alternatives
Ruby	C#
array.collect	array.select
array.select	array.Where
array.detect ( = array.select.first )	array.first
array.join( token )	String.join(array, token)

Как видим, join метод стал вдруг методом String класса.

Много лишних слов

public overrride static void methodName() vs. def self.method_name

Консоль

Отсутствие консоли, где можно быстренько потестить какой-нибудь метод.

Или я просто предвзято отношусь к C# и Microsoft?

Моё рабочее место

2008-07-11T16:04:00.036+03:00

Так как недавно только сменил работу, и в памяти ещё осталось прошлое рабочее место, то напишу про оба: прошлое и настоящее.

Прошлое:

Программировал на ruby on rails. Использовал:

ОС: Ubuntu.

С тех пор, как я пересел на неё, прошло уже 4 года (4.10 была первая версия, выпущена соответственно в октябре 2004 года). Понравилась с первого взгляда. Теперь её использую повсюду.

Программы:

Jedit

Просто лучший редактор для программирования. Главное уметь пользваться и правильно настроить плагины. И, конечно, abbreviations.

Plugins:

SideKick: Позволяет создавать и работать с проектом, а не набором файлов.
JDiff: Очень удобный диффер, ищет различия посимвольно. Можно настроить игнорирование нескольких подряд идущих пробелов.
RubyPlugin: Незаменимая вешь для работы с руби
RE Tester: Удобно тестить регулярные выражения прежде чем их писать в код
XSLT: При работе с XML. Позволяет тестить xPath.

trac

Очень удобный багтракер. Имеет встроенный вики (например, для спецификации и/или документации). Интегрируется с svn.

svn

Контроль версий обязателен :). Пока пользовал только svn, интересно попробовать Git

Firefox

А как же без него-то программирование для веб?

Plugins:

Firebug: Без него сейчас не обходится ни одна разработка под web
YSlow: Позволяет тестировать скорость загрузки страниц
Web Developer: Позволяет отключать некоторые элементы страницы. Опять же нужен для тестирования
Console²: Этим пока не пользовался, но поставил на всякий случай. Изучаю...

Настоящее:

Программирую на C#, asp.Net. Использую всё те же Firefox, JEdit, плюс:

ОС: Windows

Что и следовало ожидать :). Очень непривычно. Почему под убунту нельзя было? :)

Программы:

Visual Studio 2008: Вещь, конечно, на редкость глючная, но без неё никак.
ReSharper: Когда-то давно (в университете) использовал IntelliJIDEA для Java. Руки быстро вспомнили старые шорткаты :)
TotalCommander: Двупанельный файловый менеджер. Намного удобнее обычного эксплорера

Проблемы с запуском графической части Ubuntu (gdm)

2008-05-31T09:32:00.009+03:00

Проблема была в кратце такова, что при нормальной загрузке Ubuntu моментально подвисала, как только показывалось графическое окно login. В то же время, если сначала загрузиться в recovery mode, а потом запустить графическую оболочку (startx), то всё работало нормально.

Напрашивается вывод, что при recovery mode Ubuntu не загружает некоторые модули, которые возможно конфликтуют с gdm. Как это выяснить?

Прежде всего загружаемся в recovery mode и из-под roota выполняем команду sysvconfig Там весь список загружаемых модулей. Убираем на время gdm. Сохраняем, выходим. Теперь при нормальной загрузке, компьютер не будет виснуть и мы сможем посмотреть какие модули им загружены.

Теперь всё в той же root консоли набираем dmesg > /home/[ваш username]/failsafe.log что сохранит лог загрузки в файл.

Также устанавливаем хороший diff'ер apt-get install meld Теперь можем спокойно перезагрузиться в нормальном режиме.

Так как мы в самом начале отключили загрузку gdm, то после перезагрузки мы снова в консоли. Нужно залогиниться и выполнить аналогичную команду, чтоб записать лог загрузки. dmesg > /home/[ваш username]/normal.log

Осталось только сравнить эти два лога. Я использовал удобство gdm,- загрузился туда через recovery mode, сравнил через meld эти 2 файла (!! meld сравнивает посимвольно а не построчно, поэтому различия в начале строк, которые являются временем загрузки не сильно волновали !!). В файлах явно читались названия модулей подгружаемых при обычном старте и игнорируемых в recovery mode. У меня это были bluetooth и powernowd. Поэтому, снова запустив sysvconfig, отключил bluetooth, powernowd и powernowd.early, не забыл включить gdm и перезагрузился в нормальном режиме.

Теперь всё работает.

Вопросы, которые можно задать при устройстве на работу

2008-05-30T16:11:00.006+03:00

В скором времени собираюсь переходить на новое место работы. Посмотрим, что из этого выйдет. На новом месте обещают привязанность к Microsoft. Используют практически все их технологии: .Net, Silverlight итд. Клепать сайты на Rails я уже научился :). Идём дальше...

В связи с вышесказанным, предлагаю сабж. Мне ими воспользоваться не посчастливилось - наткнулся уже после проведения собеседования.

Сколько новых версий программ вы выпустили за последний год?

слишком мало = scope creep: wtf мэнеджмент
слишком много = или "супербыстрые" или количество > качество

Почему ушёл человек, работавший до вас на этой должности?

уходит от ответа = что-то скрывает
он "ушёл" = почему так неопределённо?
конкретный ответ = похоже, что всё ок

Случались ли катастрофы и как они были решены (хотя бы последняя)

пахали 2 недели = недостаточное DR-планирование (Disaster Recovery) или код (или персонал) WTF
2 часа на поиск и устранение = полёт нормальный

Как часто (в год) устраиваются тренинги для персонала?

< 1 недели = хотят использовать тебя, но не инвестировать в тебя

Сколько обычно приходится перерабатывать?

редко = хорошо продуман проект и время / стабильный код
каждый день = плохое планирование, wtf код/персонал/управление

Зависит от деятельности: Размер суппорта/менеджеров по продаже по отношению к программерам?

100:1 = много клиентов: стабильный код
1:10 - очень новый, может код нестабилен
вероятно, новый проект (вполне нормально)

Как устроен DR?

"Колян из дома чинит всё" = никакого DR: валить!
"параллельные сервера, dbs, итд" = кто-то всё продумал и на это были выделены деньги

Можно заглянуть в серверную?

как птичье гнездо = АХТУНГ!
компы на холодильнике с вентиляторами = валить!
чистенько и прилично = хорошая поддержка сети

Hobo for Rails 2

2008-05-12T16:50:00.004+03:00

Пока я собирался попробовать это Хобо на вкус, они уже выпустили следущую версию. А пока времени на это нет вообще.

Hobo for Rails

2008-02-04T16:12:00.001+02:00

На днях был обнаружен плагин для Rails, который значительно расширяет возможности. Скоро напишу конкретнее, а пока только сайт проекта.

Rails database table names: singular Vs. plural

2008-02-01T00:06:00.008+02:00

Rails < 2.0 : You need to add into config/environment.rb file line

# Include your application configuration below
ActiveRecord::Base.pluralize_table_names = false #added line

Rails >= 2.0 : You need to add into config/environment.rb file inside block

Rails::Initializer.run do |config|
  config.active_record.pluralize_table_names = false #added line
end

Install Ruby Gem Postgres In Ubuntu Linux

2008-01-31T22:42:00.013+02:00

Installing ruby gem postgres in Ubuntu linux

sudo gem install postgres

gives the next error

ERROR:  While executing gem ... (Gem::Installer::ExtensionBuildError)
  ERROR: Failed to build gem native extension.

ruby extconf.rb ins postgres
extconf.rb:46: command not found: pg_config --includedir
extconf.rb:53: command not found: pg_config --libdir
checking for main() in -lpq... no

Can be solved by:

sudo apt-get install libpq-dev
sudo gem install postgres-pr

Hello world!

2008-01-08T14:43:00.002+02:00

Так уж повелось, что всё в этом мире начинается с Hello world!. Даже блоги. Вообще, так сказать, это первая тестовая попытка создать блог, имеющий какую-то конкретную специализацию. Опыт работы пока ещё небольшой (пара лет), поэтому некоторым мои открытия могут показаться уже давно известными и проверенными истинами. Однако, блог и создаётся главным образом для того, чтобы быстрее вырасти и набрать знаний и опыта. Первое время скорее всего буду делиться мыслями о Ruby и Rails. Просто последний мой проект написан именно на этом языке с использованием фрэймворка.