Happy New Year!

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

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

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

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

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

Google AI Challenge. Final.

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.

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

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.

1. First change is to send as many ships as needed to conquer the planet, not just the half.
2. 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.
3. Don't send fleet to the planet where is was sent already. (Well, this is doubtable, but you can try.)
4. 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.
5. 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

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

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.

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

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

;this procedure calculates baseexp 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:

an-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 an-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

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

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

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

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.

1. We create a root node.
2. Read the next folder, we must create (with path).
3. Split the path.
4. Add folders one by one to the root node, counting how many of them we had to create.
5. 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)

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

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

#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

The "cleanest" code I have ever seen.

Google Code Jam 2010 - Qualification round

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()

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++

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++

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

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

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 

More info in Postgres manual.

Remove User List From Ubuntu Karmic Login

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

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

Should be something like that:

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

C++ Header Files With Classes and Makefile

2 good tutorials:

Class code and header files.

Makefile

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