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 (1 edit)
 Re: Post your approach (response to post by MightyByte) My approach was very similar to what has been already posted:* Phase 1 Calculate frequency of each color (K-1 guesses at most)* Phase 2 Generate random permutation (1 guess)* Phase 3Search 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 zeroBTW, I also thought about adding the brute-force 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 brute-forcing the smaller cases?
 Re: Post your approach (response to post by MightyByte) My approach was very similar to what has been already posted:* Phase 1 Calculate frequency of each color (K-1 guesses at most)* Phase 2 Generate random permutation (1 guess)* Phase 3Search 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) calculating 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 zeroBTW, I also thought about adding the brute-force 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 brute-forcing the smaller cases?