

Hmmm, it appears that the new Intel Marathon has distracted people from the usual discussion of approaches. I'll get it started.
I started with the relatively straightforward approach of first determining the number of times each color occurred in the code, and then working through to find the correct color for each position. Then I tried a few approaches to optimizing that basic idea.
I also tried combining this approach with the "brute force" method for small subsets of the problem.
I wanted to try a genetic algorithm approach, but I decided that it would be better to start with something that was guaranteed to take less than 3000 guesses. Unfortunately there were enough possibilities there that I never got back to trying a GA. Did anyone else try that? 

Let C be the number of colors and P be number of pegs.
Major idea: Phase 1: Find the number of occurrence of all colors with at most C1 queries.
Phase 2: Pick a reference color. I need to know all the location of occurence of this color. If there is a color with zero occurence (This happens with probability roughly 70%), I pick this color as the reference color at no cost. Otherwise, pick the two most frequent colors, the exact location of these two color can be obtained with at most P1 queries. Either of them can be reference color.
Phase 3: Enumerate all possible code for the first few positions until the number of possible code exceeds a predefined capacity. For the rest of the positions, fill them all with the reference color. Pick a random code from the enumeration as query. Then filter out those impossible code and generate more code by appending all possible colors to the unknown position as long as the total number of code is still within the capacity. Repeat querying until only one possible code is left and this is the final answer.
Minor improvement: 1. Instead of picking a random code in phase 3, pick a code with color frequency which matches the already known color frequency. 2. Switch to a completely exhaustiveserachapproach at the beginning if pow(C,P)<2.5e8 

My approach was simply to generate guesses compatible with results of previous guesses. The problem is that I didn't find guarantied way to find this compatible guess in time. So I was looking for guess with as small error as possible. The error I've used = sum(guesses, 10000*abs(guess.a  current.a)+abs(guess.b  current.b)), where b is number of perfectly matched pegs, and a is number of total matched colors (results[0]+results[1] from nextGuess arguments). Now, I generate each guess candidate by first generating compatible color counts (first part of error sum), then generating most compatible order. In both of those steps I first quickly make some reasonable initial state, then optimize it by some number of randomized changes, each taking into account possible reduction of error. To speed up things a lot I've maintained arrays of error changes for various modification of the state, and look up for the best moves in this array. I have found it's much more efficient to have this array maintained, than to recalculate errors after each move. I've managed to generate up to 50000000/(L*L*L) candidates per each guess, using reasonable runtime  up to 15 seconds in worst case. If any candidate has perfect match (zero error) I return the guess immediately.
Another part of my solution is the code for getting as much as possible information from guesses analytically. The code estimates possible minimum and maximum values for color counts, possible assignment bits of colors in each place, etc. It allowed me to determine exact numbers of each color in reasonably few guesses  about K. Initially, I've tried to issue first K1 unicolor guesses to determine counts, but it turns out it wasn't necessary. This approach gets no information about ordering from the first guesses, and I've got ~100 score from it (my second submission). 

The problem is that I didn't find guarantied way to find this compatible guess in time. So I was looking for guess with as small error as possible.
You would have won a much bigger prize if you had: http://tw.arxiv.org/abs/cs.CC/0512049 

I was almost sure it's NPcomplete. :) But I'm not theory expert, so I've formulated it in this way. :) 

I had tried a genetic algorithm but it took far too long to converge. So instead I used a two phase approach:
In the first phase (same as in lyc1977's solution) I used k1 guesses to determine the number of pegs of each color.
In the second phase I searched for permutations of the pegs that were as consistent as possible with the previous observed responses. I measured the "consistency" of a potential guess as the sum, over all previous guesses, of squared differences between the actual number of exact matches for the guess and the number of matches that my potential guess would generate.
To do the search, I started with my prior guess. Then I did a bruteforce iteration over all pairs of pegs, looking for swaps that improved the consistency. If there was enough time, I also did a bruteforce iteration over all 3cycles of pegs, again looking for permutations that improved the consistency.
If a search ever failed to find any improvements over the prior guess (which actually didn't happen very often), I guessed a random permutation of the pegs. 

I find it intriguing how often I've thought "this is probably NPcomplete" and it turned out to be true while I did absolutely no analysis. Are there any easy to regocnize common properties of NPcomplete problems I might be recognizing without knowing? 

My guess is any problem that looks like it would take some exhaustive search to arrive at an optimal answer? 

ok here's mine
let K= k, L=l (from init)
step 1  do k passes (i was being sloppy) with 0000...,11111..., ..., kkkkk... (k=K1) to find out how many of each color there are.
step 2 randomly generate all the rest of my guesses with permutations of 000112222555... (assuming there were 3 0's based on first k guesses, 2 1's, 0 3s, 0 4's 3 5's...);
step 3 for guessnum=k until 3000?
let p[K,L] = 1/K be an array of double representing the probability that the lth color is k
estimate current p matrix repeat 100 times or until done { let sum1(x) = sum of p[i,x] where i in [0,K)} divide each p[i,x] by sum1(x)
let sum2(n) = sum of p[guess[guessnum][i],i] where i in [0,L] the expected value is results[guessnum][0] force the sum of p[guess[guessnum][i],i] to the expected value (mult by something) done if Abs(sum expected)<1e8 }
generate a vector based on highest p for each slot check to see if consistant with previous guesses if so then we are finished  return it... otherwise return the permutation generated in step 2
there was a lot of room for optimization but I didn't get what i did working until last night.
I was pleased to get scores approaching 2 

My approach seems to be quite different from what other people have posted, and because I hacked a lot of it together on very little sleep, it probably would probably be quite difficult to reverse engineer. Here it is in plain english for any who are interested.
Phase 1: Count the number of pegs of each color with at most k1 solid color queries
Phase 2: Split the code in half and find the number of pegs of each color in each half. This took at most k1 queries with half color i and half color i+1 which combined with the total count for each color yields a system of linear equations with a unique solution. Repeat this recursively. Exactly how many queries this takes varies considerably, but O(l*log(l)) is an upper bound.
Phase 3: When the size of the blocks being split up in phase 2 gets small (around 10) then switch over to a brute force method of making the next query consistent with all previous queries. The count of each color in the block was known from phase 2, so I only had at most d! instead of k^{d} possibilities to sift through (d being the length of the small blocks) 

My approach was very similar to what has been already posted:
* Phase 1 Calculate frequency of each color (K1 guesses at most)
* Phase 2 Generate random permutation (1 guess)
* Phase 3 Search for a code that minimizes: cost = sum over all guesses{ abs(expected hits  code hits) }
(in other words, search for the code "more consistent" with all the previous guesses)
The search was performed in the following way:
a) start with the best guess so far (the one with the most hits) b) randomly mutate the guess by swapping two pegs (of different color) c) calculate the delta of the cost; improvements (ie. negative deltas) are always kept while degradations are randomly kept (I used a simulated annealing probability schedule) d) repeat from step b until the temperature reaches zero
BTW, I also thought about adding the bruteforce algorithm for the smaller cases since it scored way higher (more than 3 on average on my tests) but I didn't wanted to take (again) the risk of submitting in the final hours (my entries have already "suffered" enough because of that). Anyway, I keep wondering how big an improvement I did despise... lyc1977: do you have an estimate on your improvement for bruteforcing the smaller cases? 

It looks like from the paper you mentioned i took the "static" route. http://tw.arxiv.org/abs/cs.CC/0512049
btw  when is the testing for MM2 going to run? 

I thought about bruteforce solution for small cases, but I've found that my generic algorithm almost always finds compatible guess for lengths up to 20, and larger cases are not bruteforceable anyway. 

We're holding off on testing while we do some verification of a few things, testing will most likely start tomorrow morning. 
