Programming Challenges: 110206 Erdos Numbers

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.

Programming Challenges: 110208 Yahtzee

I completed the Yahtzee problem today, after a couple of days effort.

I first double checked my previous 2004 solution’s scoring function, there were a few gems in there that I had to reprove, like how the full house was worked out.

        // a - e are the five dice rolls
	int array[7] = { 0,0,0,0,0,0,0 };

	array[a]++;
	array[b]++;
	array++;
	array[d]++;
	array[e]++;

	// full house
	if ( ( array[a] + array[b] + array + array[d] + array[e] ) == 13 )
	{
		scores[count][12] = 40;
	}

I then rewrote the recursive function to remove my fancy std::list<int> stuff and used simple arrays of ints, and wrote a completely naive checker. But at 6 billions checks per score set, it was never going to fit the time limit.

I then thought about it for a day, and this morning, wrote a version the skipped the skippable stuff, but it got the wrong answer, then I noticed a case I’d skipped that I shouldn’t have. I added that back in, and all of a sudden my code started giving really bad (low) score results.

I noticed the my best score function was entering (new_score > best_score) when they were the same values.

Much muttering, explaining to my wife and children later…

I noticed a compiler warning:

warning C4390: ';' : empty controlled statement found; is this the intent?
	if( new_value > best_value );
	{
		//cout << "b: " << best_value << " n: " << new_value << endl;
		memcpy(best_set, current_set, sizeof(int)*13);
		best_value = new_value;
	}

after removing the stupid semicolon and debugging text, my solution solved the puzzle!