Extracting Similar items from sets of numbers

[Gotcha]

Hi There Everyone!

I was wondering if any of you could guide me in the right direction concerning the following problem (an algorithm would be much appreciated):

I am writing a program for a Computer Science Project.
The Program works as follows:
1. It generates a random number with a set amount of digits.
2. The user then enters a set of numbers.
3. The program then outputs how many of these numbers are in the right position
4. This process continues until the user has entered the initial the random number.

I now want to add a feature where the user enters a number of sets, each containg the same number of digits, as well as how many numbers are in the right position.
My program should then work out which numbers are in the right positions, if any.

I want to know if there is some algorithm or mathematical logical process by which I could program this.

I don't require any code as such, any help on how to go about this problem or an algorithm would be much appreciated!

 

[Mark44]

The OP hasn't been around since 2005, but the problem is interesting enough that I thought it might deserve more discussion.

 

[jedishrfu]

Is this like the mastermind board game?

 

[sysprog]

Is this like the mastermind board game?

It seemed so to me on first pass, but I'm not sure I correctly understood the proposed added feature part.

I think the OP was originally looking at a scenario in which the user implements some heuristic procedure, even if it's just eliminating whatever's already established to be not the right answer, and iteratively passes tries to the machine, each informed by the results from its predecessor, and the machine checks them against its hidden PRN, and outputs the onto mappings.

It seems to me that the added feature was intended to allow batch guessing instead of strictly one-at-time interactive guessing, but if that were to be implemented, the guesses would all start with the same amount of prior knowledge.

I think that a definitively good answer to this question would require more information from its positor.

In particular, I'd like to see what the machine is supposed to do with "as well as how many numbers are in the right position" and how the user is to decide the value for that to pass to the machine.

 

[Mark44]

In particular, I'd like to see what the machine is supposed to do with "as well as how many numbers are in the right position" and how the user is to decide the value for that to pass to the machine.

I agree that more information would be helpful, but I doubt that will happen, as the OP was last seen in 2005. Also, I don't see that adding a feature for batch guesses is very useful.

Regarding what you quoted, I think we have a lot of room for interpretation. As well as how many numbers are in the right position, it wouldn't be hard to identify where those positions are. The OP was asking about whether there is an existing algorithm (AFAIK, there isn't), but solving the problem as I'm interpreting it seemed interesting to me, and worthy of being reopened. Of the digits that the user enters, the program could match the digits in the hidden number, and do something like re-display whatever digits the user entered that are in the right position in green.

So if anyone is interested, this isn't homework (at least it isn't any more), so if you want to post a full solution, have at it.

 

[sysprog]

The OP didn't ask for code -- given the antiquity of the thread, may I presume that it's ok to post working code? Any preferred language? I suggest javascript, as it can run in any browser, but other languages can be run on readily available online interpreters ...

 

[jedishrfu]

My favorites are Processing and python for this kind of problem. Processing because it’s standalone and works across platforms and your programs are exportable sketches.

Python because it’s easy for students to grasp and available everywhere even on Processing as jython ie python v2.7 on a jvm.

I think it would be neat to implement on a variety of languages with a variety of techniques ie command line, GUI or web based.

 

[sysprog]

Thanks, @jedishrfu,

You guys being Mentors here, I entreat you or @Mark44 to countenance a set of program specifications (minimal game rules). I'll propose one if you like.

As a starting point, anyone who cares to attempt it, and doesn't want to start from scratch, can review the page for a similar game at https://rosettacode.org/wiki/Bulls_and_cows. Bulls and Cows is a game which is a predecessor of Mastermind. There's also a Mastermind task page on Rosettacode, which is a partially implemented fork off the Bulls and Cows task page.

Spoiler: Python version of Bulls and Cows, a predecessor of Mastermind

'''
 Bulls and cows. A game pre-dating, and similar to, Mastermind.
'''
 
import random
 
digits = '123456789'
size = 4
chosen = ''.join(random.sample(digits,size))
#print chosen # Debug
print '''I have chosen a number from %s unique digits from 1 to 9 arranged in a random order.
You need to input a %i digit, unique digit number as a guess at what I have chosen''' % (size, size)
guesses = 0
while True:
    guesses += 1
    while True:
        # get a good guess
        guess = raw_input('\nNext guess [%i]: ' % guesses).strip()
        if len(guess) == size and \
           all(char in digits for char in guess) \
           and len(set(guess)) == size:
            break
        print "Problem, try again. You need to enter %i unique digits from 1 to 9" % size
    if guess == chosen:
        print '\nCongratulations you guessed correctly in',guesses,'attempts'
        break
    bulls = cows = 0
    for i in range(size):
        if guess[i] == chosen[i]:
            bulls += 1
        elif guess[i] in chosen:
            cows += 1
    print '  %i Bulls\n  %i Cows' % (bulls, cows)

Sample output:

I have chosen a number from 4 unique digits from 1 to 9 arranged in a random order.
You need to input a 4 digit, unique digit number as a guess at what I have chosen

Next guess [1]: 79
Problem, try again. You need to enter 4 unique digits from 1 to 9

Next guess [1]: 7983
2 Bulls
2 Cows

Next guess [2]: 7938

Congratulations you guessed correctly in 2 attempts