JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< 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 position

Here 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-1
etc..
and last equation: A+B+C+D=6

Assuming 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 X
after this, we can know whether this position is color X or color Y
or 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.
<< PREV    [ 1 2 3 ]

RSS