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. >:-)

I have two questions.

Firstly, could you restrict the number of colors to at least two more than the number of positions? (The case when the number of colors is equal to the number of positions can be a bit tricky, so such a restriction would simplify the code we write while still allowing a contest.) Alternately, could you just choose two or three pairs of parameters to which we should optimize our solutions for the contest?

Secondly, could you clarify whether the v parameter is the number of colors, or one less than the number of colors as Limbic's post seems to imply?

Thanks in advance.

Solutions will be scored based on ... count of solutions where the minimum number of guesses was generated for that puzzle,

You're going to determine the best possible solution for all ~ 382 duodecillion possible puzzles?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP PCW It is as I've been saying!(Audio until 20090817)

The previous sentence says “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.” Obviously the next sentence refers to the number of solutions among those. Also, MidLifeXis will use his probability-fu to make sure the result is quite probably a good estimate of what you'd get from testing all solutions.

Please post solutions under here. I have included a framework....

I have a harness here as well that you can use to test.

Totally unreliable solution :-)

Read more... (628 Bytes)

--MidLifeXis

Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

Brute force solution. I wanted to have it near the top (along with my random solution) to show how an inefficient, but obvious solution would work. I would hope that solutions down the line would have much better performance and more creativity. :-)

Note: I have seen someone (cannot remember who) calling Knuth's algorithm for mastermind a brute force algorithm. If it is the one I am thinking of, it is not a brute force algorithm, but (1) trims impossible solutions, and (2) orders guesses by highest potential of helping do (1) on the next pass.

Read more... (1288 Bytes)

--MidLifeXis

Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

Not having repeats makes the job of the person with the code much simpler, at least I think it does. The work that the person guessing the code has to do would then be based on the size of V compared to P.

If you call each "color" C_n, and take the first P characters from a randomly sorted alphabet of size V, you essentially have a code of ...

C₁, C₂, C₃, ..., C_p

If my grey matter is working properly, it does not matter what characters the code maker chooses, other than as a psychological exercise against the choice of the initial selections.

If I ignore defending against the choice of initial selections, the code maker really only has 315 puzzles to generate.

(p=1,  v=1 ) .. (p=1,  v=36) => 36
(p=2,  v=2 ) .. (p=2,  v=36) => 35
...
(p=10, v=10) .. (p=10, v=36) => 27

((27 + 36) / 2) * 10 = 315
[download]

Now, that is not to say that the code maker will probably not be choosing '0', '01', '012', etc as the codes. It also does not mean that there will not be some carefully chosen sequences designed to test the robustness of certain types of implementations. :-)

--MidLifeXis

Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

JavaFan,
Years after this post, I discovered that my daughter is now playing a simplified version of this game in her 2nd grade classroom. I have yet to find a more optimal strategy then Knuth's although the game isn't exactly the same.

Cheers - L~R

Increasing the possible values of $v has a minimal effect on the computational complexity of this problem. For any given value of $v "colors" and $p colors per solution, this puzzle can always be solved with a maximum of ceiling($v/$p)-1+ $p! guesses. The total number of permutations possible for a particular value of $v and $p has no impact.

In the original bagel problem we have $p=3 and $v=10. Although there are 648 possible 3 digit permutations, according to this formula, the maximum number of guesses is never more than 9:

  ceiling($v/$p)=ceiling(10/3)=4
  $p! = 3*2*1 = 6

  #so... 
  ceiling($v/$p)-1 + $p! = 3 + 6
  = 9
[download]

If we increase $v to its maximum proposed value, 36, we only add 8 more guesses ceiling($v/$p) only increases from 4 to 12. On the other hand if we increase $p to its maximum of 10, then the maximum number of guesses becomes ~ 10! or about 3.6 million.

  ceiling($v/$p)=ceiling(36/10) = 4
  $p! = 10!
  #so...
  ceiling($v/$p)-1 + p! = 3 + 10!
[download]

My gut sense is that this puzzle is NP complete within solution space defined by ceiling($v/$p)-1+p!. That is, we have indeed exhausted all the information available if we following the guessing strategy that led to that formula. You can come up with fewer guesses than that by sheer chance and a smart use of what chance gives you. For example, clever use of information from an initial guess whose response is $p-2 fermi and 2 pico can be solved much more quickly than a puzzle whose initial $p guesses are 1 pico each. If the luck of the draw gives you such an initial set of guesses, you can't use any sort of logic to ensure that your number of guesses will be less than ceiling($v/$p)-1+p!.

Of course, all of this assumes that the maximum number of guesses really is ceiling($v/$p)-1+ $p!. The formula is based on the algorithm described below. I haven't converted it into code because I wanted to focus on explaining the logic, but it wouldn't be too difficult to do so. I'm often prone to overlook things when I do this kind of mathematical reasoning so a second pair of eyes for my argument would be much appreciated.

Best, beth

Upon further reflection I'm no longer convinced that this is an NP hard problem, but this may be because I'm a bit fuzzy on the nuances of the definition of NP hard.

Although the worst case is always proportional to $p!, this problem still isn't as "hard" as a problem where we simply got the number of non-bagels and "yes/no" about whether they were in the right order. If we just got "yes/no" then once we knew all the digits, every additional guess would at most eliminate one of $p! possible permutations. However, in our case we can sometimes know how many are in the right position. Each time we get lucky and make a guess with one additional fermi, we may be able to reduce the number of potential remaining solutions by more than just 1.

For example, suppose the problem selector chooses a solution that will yield $p-$x fermi and $x pico, on the first guess. The number of follow on guesses needed will always be ($p-1) + ($x-1)!. We need ($p-1) to find the identity of out of order elements and at most ($x-1)! guesses to put the elements in the correct position. We can identify the $x out of place digits by taking a known bagel and replacing each digit in turn. Any guess whose pico count drops by 1 will be replacing an out of order digit. After $p-1 such guesses we will know the identity of all out of place values. To put them in the right order, we need to potentially try all possible orderings where none of the $x elements are in their original position. The first of $x elements may be in ($x-1) locations, the second in any of the ($x-2) remaining and so on. Thus we need to consider ($x-1)! arrangements.

However, we only need to make ($x-1)! guesses to put things in the right order if the number of pico is $x for all but the final "guess" (the guess we make when we know the answer but have never actually guessed that particular permutation). If after Q guesses we get $y additional fermi, then instead of guessing each remaining ($x-1)! arrangement, the number of remaining guesses is the minimum of ($x-1)! - Q and ($x-1)+($x-$y-1)!.

However, as I stated earlier, we only have the possibility of making a more informative guess. If "fermis" come late enough in the guessing process we may not be able to use them to reduce the total number of guesses to less than ceiling($v/$p) - 1 + $p!. Some clarification by someone with a firmer understanding of what exactly is meant by NP-hard would be really appreciated so I can use these terms more appropriately.

Best, beth

If you are an ACM member, a pretty good description can be found at the beginning of The status of the P versus NP problem, an article in the September 2009 issue of Communications.

Update: It looks like a free web account (yeah, I know, NYT model) will allow reading of this article. It also looks like the digital edition may allow reading without registration.

--MidLifeXis

Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.