JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 3 ]    NEXT >
Post your approach | Reply
Hmmm, it appears that the new Intel Marathon has distracted people from the usual discussion of approaches. I'll get it started.

I started with the relatively straightforward approach of first determining the number of times each color occurred in the code, and then working through to find the correct color for each position. Then I tried a few approaches to optimizing that basic idea.

I also tried combining this approach with the "brute force" method for small subsets of the problem.

I wanted to try a genetic algorithm approach, but I decided that it would be better to start with something that was guaranteed to take less than 3000 guesses. Unfortunately there were enough possibilities there that I never got back to trying a GA. Did anyone else try that?
Re: Post your approach (response to post by MightyByte) | Reply
Let C be the number of colors and P be number of pegs.

Major idea:
Phase 1:
Find the number of occurrence of all colors with at most C-1 queries.

Phase 2:
Pick a reference color. I need to know all the location of occurence of this color. If there is a color with zero occurence (This happens with probability roughly 70%), I pick this color as the reference color at no cost. Otherwise, pick the two most frequent colors, the exact location of these two color can be obtained with at most P-1 queries. Either of them can be reference color.

Phase 3:
Enumerate all possible code for the first few positions until the number of possible code exceeds a predefined capacity. For the rest of the positions, fill them all with the reference color. Pick a random code from the enumeration as query.
Then filter out those impossible code and generate more code by appending all possible colors to the unknown position as long as the total number of code is still within the capacity. Repeat querying until only one possible code is left and this is the final answer.

Minor improvement:
1. Instead of picking a random code in phase 3, pick a code with color frequency which matches the already known color frequency.
2. Switch to a completely exhaustive-serach-approach at the beginning if pow(C,P)<2.5e8
Re: Post your approach (response to post by MightyByte) | Reply
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 venco) | Reply

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.

You would have won a much bigger prize if you had: http://tw.arxiv.org/abs/cs.CC/0512049
Re: Post your approach (response to post by lars2520) | Reply
I was almost sure it's NP-complete. :)
But I'm not theory expert, so I've formulated it in this way. :)
Re: Post your approach (response to post by MightyByte) | Reply
I had tried a genetic algorithm but it took far too long to converge. So instead I used a two phase approach:

In the first phase (same as in lyc1977's solution) I used k-1 guesses to determine the number of pegs of each color.

In the second phase I searched for permutations of the pegs that were as consistent as possible with the previous observed responses. I measured the "consistency" of a potential guess as the sum, over all previous guesses, of squared differences between the actual number of exact matches for the guess and the number of matches that my potential guess would generate.

To do the search, I started with my prior guess. Then I did a brute-force iteration over all pairs of pegs, looking for swaps that improved the consistency. If there was enough time, I also did a brute-force iteration over all 3-cycles of pegs, again looking for permutations that improved the consistency.

If a search ever failed to find any improvements over the prior guess (which actually didn't happen very often), I guessed a random permutation of the pegs.
Re: Post your approach (response to post by lars2520) | Reply
I find it intriguing how often I've thought "this is probably NP-complete" and it turned out to be true while I did absolutely no analysis. Are there any easy to regocnize common properties of NP-complete problems I might be recognizing without knowing?
Re: Post your approach (response to post by dskloet) | Reply
My guess is any problem that looks like it would take some exhaustive search to arrive at an optimal answer?
Re: Post your approach (response to post by lyc1977) | Reply
ok here's mine

let K= k, L=l (from init)

step 1 - do k passes (i was being sloppy)
with 0000...,11111..., ..., kkkkk... (k=K-1)
to find out how many of each color there are.

step 2- randomly generate all the rest of my guesses with permutations
of
000112222555... (assuming there were 3 0's based on first k guesses, 2 1's, 0 3s, 0 4's 3 5's...);

step 3
for guessnum=k until 3000?

let p[K,L] = 1/K be an array of double representing the probability that the lth color is k

estimate current p matrix
repeat 100 times or until done
{
let sum1(x) = sum of p[i,x] where i in [0,K)}
divide each p[i,x] by sum1(x)

let sum2(n) = sum of p[guess[guessnum][i],i] where i in [0,L]
the expected value is results[guessnum][0]
force the sum of p[guess[guessnum][i],i] to the expected value (mult by something)
done if Abs(sum- expected)<1e-8
}

generate a vector based on highest p for each slot
check to see if consistant with previous guesses if so then we are finished - return it...
otherwise return the permutation generated in step 2

there was a lot of room for optimization but I didn't get what i did working until last night.

I was pleased to get scores approaching 2
Re: Post your approach (response to post by MightyByte) | Reply
My approach seems to be quite different from what other people have posted, and because I hacked a lot of it together on very little sleep, it probably would probably be quite difficult to reverse engineer. Here it is in plain english for any who are interested.

Phase 1: Count the number of pegs of each color with at most k-1 solid color queries

Phase 2: Split the code in half and find the number of pegs of each color in each half. This took at most k-1 queries with half color i and half color i+1 which combined with the total count for each color yields a system of linear equations with a unique solution. Repeat this recursively. Exactly how many queries this takes varies considerably, but O(l*log(l)) is an upper bound.

Phase 3: When the size of the blocks being split up in phase 2 gets small (around 10) then switch over to a brute force method of making the next query consistent with all previous queries. The count of each color in the block was known from phase 2, so I only had at most d! instead of kd possibilities to sift through (d being the length of the small blocks)
Re: Post your approach (response to post by MightyByte) | Reply
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 3
Search 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 zero

BTW, 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 lars2520) | Reply
It looks like from the paper you mentioned i took the "static" route.
http://tw.arxiv.org/abs/cs.CC/0512049

btw - when is the testing for MM2 going to run?
Re: Post your approach (response to post by gsais) | Reply
I thought about brute-force solution for small cases, but I've found that my generic algorithm almost always finds compatible guess for lengths up to 20, and larger cases are not brute-forceable anyway.
Re: Post your approach (response to post by inrm) | Reply
We're holding off on testing while we do some verification of a few things, testing will most likely start tomorrow morning.
Re: Post your approach (response to post by TheFaxman) | Reply
thanks!
[ 1 2 3 ]    NEXT >

RSS