My favourite astro-ph papers

I've just added a section on the right called:
My favourite astro-ph papers

There I will be posting (much like this guy) every day the new papers on astro-ph that I find interesting or noteworthy. This is a personal selection based on my research interests. There is a feed available just in case you like my tastes :-)

Secret Tape with the Lost Writers

Given the speed that the series is taking, I guess we'll soon see the magic turtle ;-)

ACM ICPC, Problem B

This time in spanish :-)
Bueno, ya he escrito mi propuesta, ha costado un poco más de lo que esperaba y al final lo he hecho en C++. La idea básica es buscar la cadena más larga que sea decreciente, y quitarla. Aplicamos esto recursivamente hasta que se acaben los caracteres.

Bueno, ahí va el código:

#include <iostream>
#include <string>
#include <list>
#include <algorithm>

using namespace std;

int streak(list<char> &sl)
{
    list<char>::iterator i=sl.begin(), start=i;
    while(i!=sl.end())
    {
        if(*i<=*start)
        {
            start=i;
            i=sl.erase(i);
        }
        else i++;
    }
    return sl.size();
}

int main()
{
    string s;
    cin >> s;
    int line = 1;
    while (s != "end")
    {
        int n=1;
        list<char> sl(s.size());
        copy(s.begin(),s.end(),sl.begin());
        while(streak(sl)>0)
            n++;
        cout << "Case " << line++ << ": " << n << endl;
        cin >> s;
    }
}

Y el test de que funciona:

franjesus@altamira:~/tmp$ ./test
ABC
Case 1: 3
CBA
Case 2: 1
CBACBA
Case 3: 2
CCCCCCCCCBBBBBBBBBAAAAAAAAAAA
Case 4: 1
CCCNBBBNAAA
Case 5: 2
CBACBACBA
Case 6: 3
ACMICPC
Case 7: 4
ANABMCAANABMCA
Case 8: 4
end

Me estoy cansando (he estado casi 3 horas con el problemita de marras). El problema C puede que tarde :-)

ACM Programming contest. Problem A

I've seen the ACM programming contest 2007 on Barrapunto, and I think I know how to solve some of the problems. The problems are here. Here's the ones that I have thought so far:

Problem A
To solve this problem, I would start by defining an UnorderedSet class, containing element of type T (typical template C++ stuff), but since I don't want to get into the programming details, I will just say that we can deal with unordered sets that have elements that are unique. So let G be the set of all different combinations of alleles possible: OO, AO, AA, BO, BB, AB. Let F be the set of possible alleles for the father, M for the mother and C for the child, with F,M,C ⊆ G.

Our task for the first part would be to derive C from F and M. The second part consists on deriving M (F) from F (M) and C. In the last case the result can be the empty set.

Two basic functions are required to convert from and to our combinations in G to the "observed" genetic characteristics, so D(A) would give a set {AO, AA}, D(B)={BO,BB} D(AB)={AB}, D(O)={OO}. And similarly the reverse relation from elements of G (not subgroups as in the direct relation) towards blood types, we call this function R.

The first part (parents -> child) can be easily solved by taking the cartesian product of sF by sM where the s indicates the "simplify operation", that is taking all the alleles in F or M separately (and eliminating repeated ones), in that way, s{AB} -> {A, B} or s{AO, AA}->{A, O}. Since we are not interested in probabilities this will do. The result (after removing repeated results taking into account that alleles are commutative (AB=BA)) is C. Now just apply R to the elements of C. That is the result.

To solve the second part we need to make another formulation which serves us to solve the first part too, and takes into account the probabilities, so maybe it would be better to start with the second part and use the functions developed to easily solve the first part. It works like this:

1. We define a function f: G³ ->{0,1} that takes 3 elements of G and returns 1 if it is a possible combination in the sense that f(x,y,z), where x ∈ F, y ∈ M, z ∈ C, is feasible ({AB,OO,AO} is a possible combination, {AO,AA,OO} is not), and 0 otherwise. This function is easily defined just by taking the cartesian product (as in the previous) of x and y and looking for z in the result. More programmatically, we evaluate the cartesian product for the 21 possible combinations (the cartesian product is abelian), or 36 if we don't want to bother with optimisations for such a small problem, of G x G and save the results in a 6 x 6 x 6 matrix (that we call by extension f).
2. This second step is best explained in pseudocode:
   

   
           for i in F
                   for k in C
                           for j in G
                                   if (f(i,j,k)==1)
                                           M.add(j)
           end
   

   
   of course, M is a set and the add method avoids having repeated entries.
   

We're done. The same algorithm could be applied to infer C from F and M (or F from M and C, for that matter). The only job remaining is to apply R to M to get the possible blood types for the mother.

The same algorithm can be applied to the +- alleles (this time the problem is smaller). The results should be the cartesian product of the ABO alleles and the +- alleles.

I haven't tested this solution. There's no guarantee that it will work, maybe it's dead wrong. Any comments are welcome. Problems B, C and I will surely follow when I get time to write them down. The rest... maybe, only if I can solve them :-)