The challenge is... given a set of clues and results from the game "Mastermind", determine the answer, and whether or not there's many or no possible answers.

can anyone help me improve my algorithm:
i mean a very bad algorithm is : start from 0000 to 9999 and see which one satisfies the clues.. what i ve done so far is look for a clue with score [0,0] and eliminate those numbers..
but if there not such a clue, i do not improve nothing..
any further improvements..??

What's wrong with checking all 10000 combinations?

Bayesian inference.

That is all.

Quote: Original post by ghostrider_
The challenge is... given a set of clues and results from the game "Mastermind", determine the answer, and whether or not there's many or no possible answers.

Quote: Original post by InnocuousFox
Bayesian inference.

That is all.

Are you sure that's how you would do it? There is nothing probabilistic about the problem...

my fault... the number of the digits is given as an input N.. so imagine that if N=6 then i have 1.000.000 combinations.. furthermore i think that there is a better algorithm as far as complexicity is concerned..

Quote: Original post by InnocuousFox
Bayesian inference.

That is all.

i dont get how to use it.... :s

let me give you an example..
if N=4 and the clues are:

9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0

Then the number 3411 is the only one that satisfies the rules.

Quote: Original post by alvaro

Quote: Original post by InnocuousFox
Bayesian inference.

Are you sure that's how you would do it? There is nothing probabilistic about the problem...

It's a decent way. Sure, on a small scale, the problem is tractable and you can just brute-force it as you suggested. However, that doesn't scale well.

Bottom line, you are dealing with uncertainty based on limited or slightly ambiguous information. By narrowing down the percentages of what is more likely to possibly be in any given slot, you can then take the best option that pops out and try that.

Quote: Original post by ghostrider_
my fault... the number of the digits is given as an input N.. so imagine that if N=6 then i have 1.000.000 combinations.. furthermore i think that there is a better algorithm as far as complexicity is concerned..

Yep.

Quote: Original post by ghostrider_

Quote: Original post by InnocuousFox
Bayesian inference.

That is all.

i dont get how to use it.... :s

There's plenty of reading material available. In general, though, each slot has an equal chance of being each color. When you get clues back, you bias those percentages for or against colors. If you have a 0/1, you know that you can inch up the %s of all 4 colors in all 4 slots... just not much. If you get a 1/0, you can bump up the %s of all 4 slots with the colors currently in those slots. Eventually, by trying different combinations, the right answers will bubble to the top for each slot.

Incidentally, you can do this for games like Bridge, too, where you need to ferret out the locations of cards in other people's hands.

It's one way of doing things...

Quote: Original post by InnocuousFox

Quote: Original post by alvaro

Quote: Original post by InnocuousFox
Bayesian inference.

Are you sure that's how you would do it? There is nothing probabilistic about the problem...

It's a decent way. Sure, on a small scale, the problem is tractable and you can just brute-force it as you suggested. However, that doesn't scale well.

Bottom line, you are dealing with uncertainty based on limited or slightly ambiguous information. By narrowing down the percentages of what is more likely to possibly be in any given slot, you can then take the best option that pops out and try that.

I really think you are thinking of the wrong problem here, and that's why I quoted what the original question was. The problem as described is not probabilistic at all.

EDIT: It looks like you did read the problem correctly. Then I'll just have to disagree with your approach. There is a set of possible hidden patterns, and each result you get restricts you to a subset of them. You need to find the intersection set. The Bayesian approach reduces to all probabilities being 0 or 1, which makes it not very interesting.

It's somewhat similar to the SAT problem, and I believe most non probabilistic algorithms for it are similar to this one: DPLL, which is really just backtracking, so I think something like this can be good choice.

You can try to do something like enumerating all the combinations using backtracking, and terminate as soon as you find that one of the results is inconsistent with the part of the combination you have built so far. But I doubt this will result in anything much better than brute-force enumeration.

If you are fed the results one by one, you can have a container with the surviving possibilities, and filtering from it will get faster and faster as its size is reduced.