JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums Marathon Matches Marathon Match 2 Re: Post your approach Revision History (2 edits)
 Re: Post your approach (response to post by MightyByte) 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 K-1 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).
 Re: Post your approach (response to post by MightyByte) 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 K-1 unicolor guesses to determine counts, but it turns out it wasn't necessary. This approach gets no information about ordering from the first giesses, and I've got ~100 score from it (my second submission).
 Re: Post your approach (response to post by MightyByte) 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, 1000*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 analitically. 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 K-1 unicolor guesses to determine counts, but it turns out it wasn't necessary. This approach gets no information about ordering from the first giesses, and I've got ~100 score from it (my second submission).