I had first tired the Erdos Numbers problem back in 2004, and at the time I was having some odd problems with wrong answers, so ended up submitting the problem 160 times, using while(true); blocks to find which Scenario was the problem.
When I picked up the problem this time I got rid of my fancy std::map c++ code like this:
bool relations_less_both = true;
struct relations_less : public binary_function < pair<string,string>, pair<string,string>, bool>
{
bool operator()( const pair<string,string>& lhs, const pair<string,string>& rhs ) const
{
if( lhs.first < rhs.first )
{
return true;
} else if ( relations_less_both &&
lhs.first == rhs.first &&
lhs.second < rhs.second )
{
return true;
}
return false;
}
};
Which I loved, because you could sort a set of pairs, thus preserving uniqueness, while later do a range filter to find all pairs with the first parameter matching.
This time I threw that all way, got rid of the std::string also, and just used good old char*, rewriting the shortest-path-first, in a classic C style with fixed size array’s. And once I used a large enough node count (5000) the problem was solved.
I used to really like the std::vector, std::set and std::map because I didn’t have to do any pre-allocation of memory, but then last night I realised I could have just used realloc, to grow my data structures, which is what the std:: stuff is doing anyway.
So the guts of the problem are you need space to store 5000 unique names, you need to parse the papers, then run short-path-first.