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 ]
 Re: Post your approach (response to post by gsais) | Reply 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.
 Re: Post your approach (response to post by gsais) | Reply 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.
 Re: Post your approach (response to post by venco) | Reply venco: Thanks for clarifying that! Now I can start to understand how you managed to skip the single-color guesses discovery phase.
 Re: Post your approach (response to post by gsais) | Reply hits = feedback[0] = pegs with correct color and correct position; hints = feedback[1] = pegs with correct color but incorrect positionHere 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.
 Re: Post your approach (response to post by venco) | Reply 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 :-)
 Re: Post your approach (response to post by gsais) | Reply 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 6-7 times more random candidates than a C-only version. My best standard C code scored around 112-114.
 Re: Post your approach (response to post by venco) | Reply 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).I did not participate in this match, but I thought of the first phase of finding the counts of colors:First try k-1 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=6-2 guess: ccacaa, result:1 miss,0 hit, equation: B+D=6-1etc..and last equation: A+B+C+D=6Assuming 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 :)
 Re: Post your approach (response to post by gsais) | Reply Thank you very much Mr gsais for this perfect explanation.
 Re: Post your approach (response to post by venco) | Reply 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 Xafter this, we can know whether this position is color X or color Yor 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.
 Re: Post your approach (response to post by dskloet) | Reply A few seconds with google will usually tell you if a problem is NP-complete. With this problem, about ten seconds.
 Re: Post your approach (response to post by Rustyoldman) | Reply Ofcourse, but that wasn't the kind property I was looking for.
 Forums Marathon Matches Marathon Match 2 Post your approach Previous Thread  |  Next Thread << PREV    [ 1 2 3 ]