Summary for the week.

This was a very long week!

Most of my free time I was at the gym or on my combinatorics book learning fancy details about the pigeonhole principle, which is very simple but with large implications in problem solving.

The pigeonhole principle basically say that if you want to put three pigeon in two holes, then one hole will be fill up with two pigeons! On this basic idea was developed a whole set of techniques to analyze and solve problem or ways to understand the implications of certain phenomenon.

For example:

• If you put six people in the same place, it can be proved that at least three of them are –pairwise– mutual stranger or  –again, pairwise– mutual acquaintances.
• Ten people are competing in a chess tournament, each player must play with each other, if one player win gains +1 points, if lose -1, if a game draw then both player gain 0 points. If 70% of the games results in draw, it can be proved that exactly two players scored the same number of points.
• Given a set A={A1,A2…,An} with |A|=N, it can be proved that is always possible to find a subset of A, say A’, for which the element summation of A’ is divisible by N.
• Given five points on a sphere, there must be a closed hemisphere that contains four of them.
• The Kronecker theorem can be proved by pigeonhole principle means.
• The birthday paradox..

In general, there’s a long list of problems strictly related with the pigeonhole principle, from the perspective of computer programmers like me, what is most important are some of the implication on set theory and probability.

The second topic of the week was about c++ metaprogamming, what I’m trying to do is to  build at compile time a pascal triangle by pure template metaprogramming. This can be achieved, but still I don’t know how.  Building sequences on the other hand is very simple, obtaining the Fibonacci sequence require just few lines of code:

#include <iostream>
using ll = long long;

template<typename type,type...data>
struct sequence
{
    //This is where the data are going to be stored
    static const type seq_data[sizeof...(data)];
    static const type size;
    type operator[](ll index){
        return seq_data[size-index-2];
    }
};
//Initialize properly the variable in sequence
template<typename type,type...data>
const type sequence<type,data...>::seq_data[sizeof...(data)] = { data... };
template<typename type,type...data>
const type sequence<type,data...>::size{sizeof...(data)};
//Create the sequence
template<ll n,ll p1,ll p2,ll...other>
struct build_fibo_impl
{
    typedef typename build_fibo_impl<n-1,p1+p2,p1,p2,other...>::seq seq;
};
template<ll p1,ll p2,ll...other>
struct build_fibo_impl<0,p1,p2,other...>
{
    typedef sequence<ll,p1,p2,other...> seq;
};
template<ll N>
struct create_fibonacci
{
    typedef typename build_fibo_impl<N,0,1>::seq fibonacci;
};
int main()
{
    create_fibonacci<50>::fibonacci fib;
    for(int i{0};i<50;i++)
        std::cout<<fib[i]<<",";
    std::cout<<std::endl;
}

This code calculate at compile time the first fifty elements of the Fibonacci sequence, those elements are then printed when the code is executed.

I’m even able to build a simple table with per row numeration from one to n, but at the moment still I’ve found no way of building up more complex tables, like the one for the pascal triangle.

This week Amazon also delivered –finally!– Jewels of stringology, an amazing book on text algorithms, I always wanted to deepen my knowledge on this topic, all that I know will now came from CLRS which include just a short –but good– introduction to a very large field of study.

The book was delivered with two copies of “The girl on the train“, those books are for Magda. I miss-clicked something during the order submission and I got two books instead of one.. Did anyone of you want one of them as giveaway?

Ah, I was at the shooting range, it was a very funny experience and I must admit I really enjoyed to shot with a real shotgun! Also the AK47 was nice, but I think that in case of a zombie apocalypse i really prefer to shot zombies with a shotgun 🙂

I didn’t go out for running this week, had no time, just some indoor training which I really hate. I plan to go out for a trail running session tomorrow, really hope in some good time.

Thanks for reading!