

Ofcourse, but that wasn't the kind property I was looking for. 

A few seconds with google will usually tell you if a problem is NPcomplete. With this problem, about ten seconds. 

In the worst case, My method takes (k/2 * L) + k  1 guesses.
that is, k  1 initial guesses; for each position, issue a guess with two candidate colors, one as background color. for example, X Y X X after this, we can know whether this position is color X or color Y or neither.
This brings me 85 scores. I didn't make full use of the 20 secs. in fact, for most cases it finishes in 1 sec...
If i make use of previous guesses by introducing a formula like yours, the result may turn out better. 

Thank you very much Mr gsais for this perfect explanation. 

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). I did not participate in this match, but I thought of the first phase of finding the counts of colors: First try k1 guesses with 2 colors in each guess (half of one color, half of other, randomy sorted).
let`s call the numbers of pegs in each color A,B,C,D. Then (for 6 pegs) You have: guess: ababba, result:1 miss,1 hit, equation: C+D=62 guess: ccacaa, result:1 miss,0 hit, equation: B+D=61 etc.. and last equation: A+B+C+D=6
Assuming that no peg color constitutes more than a half of the key, this will give the number of pegs and some information about placement in k guesses. But I guess the further part of telling which peg goes where was the difficult one :) 

Actually, my taking the second spot is rather due to some inline assembly (SSE2) code and not only the "smart" discovery phase. SSE2 allowed the checking of about 67 times more random candidates than a Conly version. My best standard C code scored around 112114. 

Yes, I've understood that part and already edited my post so that the cost formula would read "hits + hints". I've previously misread your approach description and that's why I thought that the 10000 factor was giving more weight to hits (perhaps because I tried that in my entry giving more weight to hits before I gave up and switched to discovering the color frequencies the "easy" way...)
By the way, I think your idea of giving more weight to hits+hints is brilliant (sure, I wish I'd had come up with it myself :) 

hits = feedback[0] = pegs with correct color and correct position; hints = feedback[1] = pegs with correct color but incorrect position
Here is one more difference. I've used total number of matching colors as value hints in cost formula, no matter if it's they are on correct place or not. It can be calculated as results[0]+results[1] from nextGuess argument. This way hints is plain measure of how good is your guess in terms of choosing various colors of pegs, and hits is the measure of order quality. 

venco: Thanks for clarifying that! Now I can start to understand how you managed to skip the singlecolor guesses discovery phase. 

venco used the following cost formula (note: hits = pegs with correct color and correct position; hints = pegs with correct color but incorrect position):
cost = sum { 10000 * abs(hits  hits') + abs(hints  hints') }
The 10000 factor is used to give more weight to hits than to hints.
Actually it's the other way around. I give more weight to hints to find correct color counts as quick as possible: cost = sum { 10000 * abs(hints  hints') + abs(hits  hits') } After all counts are found (it usually happens slightly later than after K guesses) I start to use correct number of different colors, so the first part of cost always yield zero, and algorithm concentrates on ordering. 

I've got to say, this was a great summary post of what the leaders did (I haven't had a ton of time to skim through this thread). Nicely done. 

I did not get the method of guessing based on previous guesses. Can you please explain what is: Sum(Abs(Expected matched  Actual matches)), and how the new guess is selected? The method is very simple (in theory): always return a guess that is completely consistent with all the previous feedbacks. It goes like this:
a) A code is somehow choosed and postulated to be the secret key b) The postulated code is used as the key to score each of the previous guesses and the resulting scores are compared against the codemaker's feedbacks for those previous guesses c) If any of the comparisions fails (ie. we calculated a score of [3,5] but the codemaker's feedback was [4,5] for that guess) then it's said that the postulated code is "inconsistent" with the feedbacks (thus it can't possibly be the secret key)  another code must be choosed (repeat from step a) d) Otherwise, if all the comparisions are successful, then it's said that the postulated code is "consistent" with the feedbacks (thus it can possibly be the secret key)  the postulated code is returned as the next guess
There are two important observations to make about this method:
1) All of the returned guesses have a greater than zero probability of being the secret key 2) The total number of consistent codes always decreases with each guess made  therefore the probability of finding the secret key always increases with each successive guess
It's because of these two features that the method is tipically called "stepwise optimal strategy" and it has been already found to be nearoptimal on average (of course, optimal in this sense means relative to other algorithms  not to the ultimate optimal of always finding the answer in the first guess using shamanic powers). Strategies that are not stepwise optimal include "human" approaches (ie. slowly changing the guess to arrive at the answer by reasoning), and all the approaches that use a "background" color (ie. a color which is known to not occur in the answer or else that it's known where it's located within the answer).
As good and simple as the stepwise strategy is, it has a very important complication: altough finding a consistent code for small problems is rather easy, for larger problems is extremely hard. In fact, it has been already proved that just deciding if there exists a consistent code (a subset of the problem of finding it) is a NPcomplete problem; see lbackstrom's post above. Even for not so large problems (~ K=10 L=15) you can't actually hope to find a consistent code by simply generating random codes, you really need to use some heuristic to guide the search. However, even with good heuristics, for slightly larger problems it's almost impossible to find a consistent code (unless you already have enough hints), and for the very large problems the only thing that becomes easy is understanding the true meaning of "finding the needle in a haystack". This is where the "almost" stepwise strategies come, and they come in basically two flavors:
* Divideandconquer: use a background color or an analytical method to divide the problem in smaller problems and apply a stepwise approach for the smallest problems; see the approaches of lyc1977 (background color; discarding the impossible combinations is a way to find the consistent codes) and OvejaCarnivora.
* Least inconsistent code: instead of finding a completely consistent code with all the previous feedbacks, find the code that is the least inconsistent (within a subset of the search space). Essentially, a cost formula is used that measures how much inconsistent a code is, and any optimizing algorithm is used to minimize the cost. venco used the following cost formula (note: hits = feedback[0] = pegs with correct color and correct position; hints = feedback[1] = pegs with correct color but incorrect position):
cost = sum { abs(hits  hits') + 10000 * abs((hits + hints)  (hits' + hints')) } The 10000 factor is used to give more weight in the first moves to the total number of correct colors (hits + hints) than to the number of correct positioned colors (later, once the color frequencies are discovered the term becomes automatically zero). Now, since both vdave and I started the search already knowing how many pegs of each color were in the answer, the number of hints was completely irrelevant (because hits + hints = L if the code is a permutation of the right colors), thus the cost formula reduces to:
cost = sum { abs(hits  hits') } Furthermore, knowing the frequency of each color greatly limited the search space and also simplified the operation of finding the closest neighbours of a code (ie. codes with an approximate cost) to swaps. But these advantages didn't come without a price: as venco himself has already stated, his 14+ points advantage over vdave (in the tests) are very likely due to his algorithm skipping the color's frequencies discovery phase  yet he doesn't say that achieving that was far away from being an easy task at all (I can bet I wasn't the only one that unsuccessfully attempted that, so I'm looking forward to read exactly how he did it in the match editorial  right now I'm clueless edit: ok, now I understand how he accomplished it: it's thanks to the brilliant 10000 * diff(hits + hints) term in the cost function). On the other hand, vdave's "smart" discovery phase is rather intuitive (after one is told about it, of course...), easy to understand and implement, and it's also likely what allowed him to take the second spot in the tests.
It's interesting to notice that the first and second places used a stepwise strategy consistently during the whole game (ie. a wrong move was never knowingly played); what it's more interesting to notice is that the third place (flagitious) and probably the fourth place too (cae) used the almost exact opposite strategy: playing knowingly wrong positions throughout most of the game! I believe that each of these two strategies have strengths and weaknesses in different areas so none can be considered better "overall" than the other. In particular, I believe that flagitious's approach has a bigger potential to be much more scalable than any stepwise approach, but I don't want to speculate too much before the final results are published and we can see the results...
Edit  Fixed venco's cost formula 

This is provably true! With K1 guess it is almost always possible to split the code in two equally sized parts and know the color distribution in both parts. That's how my solution basically works.
It continues to split each part in two until each part has less than about 1Million permutions and bute forces these. Additionally there are a few special cases for small lenghts. This gave me ~110 points so it can't be too bad. 

I did not get the method of guessing based on previous guesses. Can you please explain what is: Sum(Abs(Expected matched  Actual matches)), and how the new guess is selected? 
