JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Marathon Matches Marathon Match 2 Post your approach << PREV    [ 1 2 3 ]    NEXT >
 Re: Post your approach (response to post by MightyByte) | Reply My approach had 3 parts:1. count colors in c-1 guesses (ideally this would be nearly skipped)2. find a totally wrong guess3. keep a set of all possible combinations of a subset of each position color pair. generate guesses isolated to the subset (simulate to find best avg guess) and filter out the ones which are not consistant. if this set gets below a certain size add another position color pair subset.
 Re: Post your approach (response to post by dskloet) | Reply What I've managed to intuit is that, more often than not, NP complete problems tend to have solutions which can be completely different if the inputs are modified by a constant number of 'elements' (like a constant size graph attachment, or something). This is the case in Minimal Vertex Covers, the Knapsack Problem, Integer programming, K-coloring a graph, the traveling salesman problem, probably most of the others as well. I don't think that the converse is true.Also, it's not true that you need to iterate over the entire, or most of the state space for NP complete problems: there are some pretty interesting new results which drastically reduce the number of states you need to examine in integer programming, not to mention the classes branch and bound. It's pretty cool.
 Re: Post your approach (response to post by MightyByte) | Reply My approach was very similar to gsais's. As a first step, I used up to (K-1) guesses to find the color counts, but at every step, I used the previous information and random swaps to extract more information (so if the first guess 00..00 shows that there are 2 0s in the code, my second guess was a random permutation of 2 0s and L-2 1s, and so on).In the second stage, I generated a few random permutations of the correct colors, and using single swaps, I tried to get a code, which is as consistent with the previous answers as possible. My consistency metric was the same as gsais's, Sum(Abs(Expected matched - Actual matches)).This algorithm works the best, if at each step a large number of random permutations are examined, so after TheFaxman told that inline assembly is allowed I rewrote my optimize-by-swaps code to use SSE2, giving it about six-sevenfold speed increase. So my final code examines 3.7e10 / (L^4 * log2(K)^2) combinations at each call to nextGuess(), that ensures that runtime will remain around 12-14 seconds even in worst case (according to local test, that means a score of 1.6).
 Re: Post your approach (response to post by vdave) | Reply Several coders have mentioned random swaps as the way to find compatible guess.My code does a bit more. It repeatedly removes 2-8 worst pegs, then adds them back in the best places. In each step if there are several possibilities with the same change in error, I pick one randomly.Similar algorithm was used in the first stage when I don't know color counts yet for finding compatible set of counts.