Last update: 2009/09/26 06:58 GMT -0500 (American/Chicago)

Sure, open my mouth, and get volunteered :-)

Corrections and Interpretations

1. Restrictions on the number of colors to v >= p + 2

   I need to mull this one over and try it myself to see where the difficulty lies. If someone has a link to a paper that demonstrates why this is a difficult case, I would appreciate it. Due to the "no repeated colors" restriction, it is an unstated requirement in Limbic~Region's description that v >= p.

2. Definition of v

   I am going to assume that Limbic~Region made a typo, unless it can be shown otherwise.

3. v will define the alphabet as the first v characters of ( 0 .. 9, A .. Z ).

So, the restrictions on p and v are as follows:

• 1 <= p <= 10
• p <= v <= 36

You may assume that only values within these ranges will be given to your solution.

Scoring

To enable automated scoring, I propose that each solution be provided as a function accepting 3 parameters: p, v, and f (for example, solution(p, v, sub {check_solution(@_)}). The algorithm should return the solution. check_solution() (see below) will keep track of the number of tries and to verify that the algorithm actually found a solution. If the last check was not the correct solution when the algorithm terminates, the algorithm will not be successful.

A function will be provided as the third parameter: check_solution(guess). check_solution will return a two element list: (picocount {number of correct, but wrong location}, fermicount {number of correct, and correct location}), or if you are familiar with bulls and cows, (cowcount, bullcount).

Proposed scoring: open to suggestions. How should we handle possibly different results based on initial choice of the solution by the algorithm? How should we score invalid values submitted to check_solution, for example, 'AABB', which has repeated colors.

My proposal: the same series of N challenges will be presented to each solution. The set of challenges may be hand selected, random, or some combination of both. Solutions will be scored based on number of correct solutions, then count of solutions where the minimum number of guesses was generated for that puzzle, then total guesses for all correct solutions, then speed (Ugh, this needs work. I would like to get the intent of LR's original challenge - finding the algorithm that provides the shortest path to every solution). If the check function receives an illegal solution, that challenge will be marked as incorrect. Time will be allocated while the solution is running, but not while it is in the provided check function (why should you be penalized when the check function could be inconsistently timed).

Execution

Your solution should be a sub as specified above. It will be run in a harness like the following:

# I will write a working one of these for testing,
# unless someone beats me to it.  For testing purposes,
# it should just need to record the number of times it
# is called, and calculate pico and fermi.
sub check_solution {
    # Update statistics
    # ...
    # Determine $pico and $fermi here
    # ...
    return ($picocount, $fermicount);
}

# Setup record keeping
# ...
# Choose number to pose to your_solution
# ...
# Launch individual solution
$solution = your_solution( $p, $v, sub { check_solution(@_) } );

# Check statistics and record
# ...
[download]

Notes

Note: I will be periodically updating this node. Please note the last update tag. Time is GMT -0500.

Note 2: Runtime for p = 10, v = 36 may be prohibitively large for some solutions. >:-)