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.
 Re: Post your approach (response to post by aminallam) | Reply 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 keyb) 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 guessesc) 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 guessThere 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 key2) 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 guessIt's because of these two features that the method is tipically called "stepwise optimal strategy" and it has been already found to be near-optimal 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 NP-complete 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:* Divide-and-conquer: 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