Extracting Similar items from sets of numbers

  • Thread starter Gotcha
  • Start date
11
0
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 proccess 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!

:smile:
 
32,384
4,148
The OP hasn't been around since 2005, but the problem is interesting enough that I thought it might deserve more discussion.
 
10,359
3,885
Is this like the mastermind board game?
 
529
216
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.
 
Last edited:
32,384
4,148
sysprog said:
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.
 
529
216
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 ...
 
10,359
3,885
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.
 
529
216
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.

Python:
'''
 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
 

Want to reply to this thread?

"Extracting Similar items from sets of numbers" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top