view STL container using gdb

I am always using the gdb-stl-view to view vector or string values. It is very convenient to view those containers using command like pvec or pstr. But for some reasons, I cannot view set or map or priority_queue using pset and pmap. 

Today, I searched for something to substitute it. I found a very useful webpage. The GDB 7.0 now include support for writing pretty-printers in Python. I followed the instruction and tried it. It works! The good thing is that you do not need to remember any command, just type "p vector_name", "p set_name" in terminal. 

p myvec 

std::vector of length 12, capacity 12 = {1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}

 p primeset

$15 = std::set with 17 elements = {
  [0] = 11,
  [1] = 17,
  [2] = 19,
  [3] = 23,
  [4] = 29,
  [5] = 31,
  [6] = 37,
  [7] = 41,
  [8] = 43,
  [9] = 47,
  [10] = 53,
  [11] = 59,
  [12] = 61,
  [13] = 67,
  [14] = 71,
  [15] = 73,
  [16] = 79

}
You can also view iterator in the same way. 

I do not know why I can not print an element of a vector(p myvec[2]) in my working place although I installed a gdb with-python. But I found that yolinux had updated the gdb-stl-view utility. I can view set or map using this utility again! I noticed the following comments in it.

#   Modified to work with g++ 4.3 by Anders Elton
#   Also added _member functions, that instead of printing the entire class in map, prints a member.

project euler problem 152

Writing 1/2 as a sum of inverse squares

I checked my old code, it looks like OK. I used some sort of brute force method(but I tried my best to minimize the number of candidates, try to group the candidates, and consider large ones first). It only takes 1 second to get the answer. But after I changed the number limit from 80 to 100, I can not get the answer in 80 seconds! So it definitely needs to be optimized.

I am still working on it ... 

The best solution is on page 2 in the discussion thread.

project euler problem 155

Counting Capacitor Circuits

My old code runs quite slow. I checked my code, I found that my code spent too much time on gcd. I optimized the code a little bit to reduce the cost and reduce the time from 18 second to 6 seconds. 

I read the discussion thread and removed "set" in my code. It works faster. Only 1.1 second needed to get the answer. If I changed the number of capacitor to 20, It takes 8.5 second to get the answer. 

Although I learned a little bit coding skill from the problem. This problem is somewhat flawed. The problem only considered simple connection in series or in parallel. It is possible to connect capacitors in Y or delta shape. Then the problem is very difficult to solve.

project euler problem 154

Exploring Pascal's pyramid

I lost my old code. What is embarrassing is that I do not know how to solve it after I read the problem. After sometime's thought, I decided to use brute force method(This proved to be the only way to solve it). After considering some symmetry property of this problem, I managed to reduce the run time to 6 seconds.

I checked some of the guy's code in c or c++, I found they can make it at 3 to 4 seconds!   I compared the code for quite some time. Finally, I found that the order of checking criteria was very important since we run them for so many times! Just like if several conditions need to be checked, if we need to check gcd, it should always be the last one. Finally I can get the result in 3.5 seconds.

project euler problem 153

Investigating Gaussian Integers

I checked my old code. It works, but the performance is poor, need 25 second to get the answer. I thought about it and then I found a very convenient formula for the problem when I was working on those real divisors. So I rewrote the code, and found the   performance is greatly improved. It was reduced to 3 second.

Then I read the discussion thread, Eigenray gave a very useful expression which can further improve the performance(it is not so difficult to prove). I tried it, the run time is reduced to 1.5 second. 

A great problem!

project euler problem 151

Paper sheets of standard sizes: an expected-value problem

I checked my old code today. I was surprised to find that I used monte carlo method to run simulations. I do not know how I get the right answer at that time. But I simulated 1e8 times, still quite far from the correct answer. Shame on me!

I rewrote the code, using an appropriate method to solve it. Actually it is a simple Markov chain problem. The size of the matrix is very small. But to generate the matrix, it takes me quite a while. Then it is solved in 50 ms. There are a few Markov chain problems in PE, this one being the simplest one.

Update: I read the discussion thread, I realized that my matrix solver is a dense one, so it cost a lot of unnecessary computation. I rewrote the code, in a recursive way, solved the problem in 2 ms.

project euler problem 383

Divisibility comparison between factorials

This problem is not quite interesting. But from this problem, I realize that learning something is more important than just solving some problems! 

I have been reviewing all my solved problems recently, and after I learned something from an old problem, I realized that I should give this problem a shot.

Since the problem asks n < 10^18, we can not check each number. The first thing is to find an equivalent problem that can be relatively easy solved. If you say you cannot find it, I would recommend you to review all problem between 140 and 150 and read TAOCP volume 1, 1.2.6 exercise. 

The second thing is to solve this relatively easy problem. I should admit that the logic is still not so straight forward to be translated into code. I spent quite some time debugging n=100 and n=1000 until I found that I have some logic error. After that, the problem is solved with in 1 ms!