from random import randint

"""
inputs: none
output: none
plays a single game of Master Mind, where the
computer picks a number and the human guesses
"""
def play_computer_picks():
    number_of_guesses = 0
    pick = pick_number()

    while True:
        guess = get_guess_from_user()
        number_of_guesses = number_of_guesses + 1
        if pick == guess:
            print "Congratulations!!! You found the answer in", number_of_guesses, "times."
            break

        if pick.lower() == "q":
            print "better luck next time!"
            print "the answer was", pick
            break
        
        feedback = compute_feedback(pick, guess)
        print "Feedback:", feedback

"""
inputs: none
output: returns a random string, containing four digits
        between 1 and 6
"""
def pick_number():
    pick = ""

    for i in range(0, 4):
        digit = randint(1, 6)
        pick = pick + str(digit)

    return pick

"""
inputs: none
output: returns a string entered by the user, containing
        four digits between 1 and 6. We also allow a "q"
        or "Q". Anything else is rejected and we ask the
        user to try again.
"""
def get_guess_from_user():
    while True:
        guess = raw_input("enter your guess: ")
        if (guess.lower() == "q"):
            return guess

        if (is_valid_guess(guess)):
            return guess

        print guess, "is not a valid guess, try again."

"""
inputs: a string represented a guess that the user has just entered.
output: returns True if the guess is a four-digit string
        containing digits from 1 to 6.
"""
def is_valid_guess(guess):
    if (len(guess) != 4):
        return False

    for character in guess:
        if not(character in "123456"):
            return False

    return True


"""
inputs:
- guess (a string, what the player has guessed)
- pick (a string, the original number that was picked)

output:
- a string of o's and x's that follows the rules of Master Mind
"""
def compute_feedback(guess, pick):
    os = compute_os(guess, pick)
    xs = compute_xs(guess, pick)
    answer = os + xs
    return answer


"""
inputs:
- guess (a string, what the player has guessed)
- pick (a string, the original number that was picked)

output:
- a string of o's (as many as the positions that have the same number)
"""
def compute_os(guess, pick):
    answer = ""
    for i in range(0, 4):
        if (guess[i] == pick[i]):
            answer = answer + "o"

    return answer

"""
inputs:
- guess (a string, what the player has guessed)
- pick (a string, the original number that was picked)

output:
- a string of o's (as many as the positions that have the same number)

comments: this is a recursive variation of compute_os.
"""
def compute_os_2(guess, pick):
    if (len(guess) == 0):
        return ""
    
    first_answer = ""
    if (guess[0] == pick[0]):
        first_answer = "o"

    rest_of_answer = compute_os_2(guess[1:], pick[1:])

    answer = first_answer + rest_of_answer
    return answer

"""
inputs: an integer n
output: the factorial of n
comment: This function is irrelevant to the MasterMind game, we just
         wrote it in class as a quick example of a recursive function.
"""
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

"""
inputs:
- guess (a string, what the player has guessed)
- pick (a string, the original number that was picked)

output:
- a string of x's 
"""
def compute_xs(guess, pick):
    [guess, pick] = remove_identical_positions(guess, pick)

    guess_list = list(guess)
    pick_list = list(pick)

    answer = ""
    for g in guess_list:
        for p in pick_list:
            if (p == g):
                answer = answer + "x"
                position = pick_list.index(p)
                del(pick_list[position])
                break

    return answer


"""
inputs:
- guess (a string, what the player has guessed)
- pick (a string, the original number that was picked)

output:
- [new_guess, new_pick] include those numbers from guess and pick,
  respectively, which appear in the same position in the guess and
  the pick.
  For example, remove_identical_positions("4341", "5362") returns:
  new_guess = "441", and new_pick = "562". We have removed the digit
  "3", which appears in the correct position in the guess.
"""
def remove_identical_positions(guess, pick):
    new_guess = ""
    new_pick = ""

    for i in range(0, len(guess)):
        if (guess[i] != pick[i]):
            new_guess = new_guess + guess[i]
            new_pick = new_pick + pick[i]

    return [new_guess, new_pick]


"""
plays a game where the human picks and the computer guesses.
No arguments, no return values
"""
def play_human_picks():
    number_of_guesses = 0
    guess_list = []
    feedback_list = []

    guess = first_computer_guess()
    while True:
        number_of_guesses = number_of_guesses + 1
        feedback = provide_feedback(guess)
        
        if (feedback == "oooo"):
            print "I'm awesome, got it in", number_of_guesses, "guesses!"
            break

        guess_list.append(guess)
        feedback_list.append(feedback)
        guess = computer_guess(guess_list, feedback_list)
        if (guess == None):
            print("you did not give me correct feedback")
            break
    

"""
inputs: none
output: a string that represents a random guess by the computer
"""
def first_computer_guess():
    result = pick_number()
    return result

"""
inputs:
- guess_list: a list of the first i guesses that the computer made,
- feedback_list: list of the first i feedbacks that the user provided

output:
- a string, representing the next guess made by the computer

description: this function tries exhaustively all possible guesses,
until it identifies a guess that is consistent with the previous
history of guesses and feedbacks.
"""
def computer_guess(guess_list, feedback_list):
    # generate a list of all possible answers
    all_answers = generate_all_answers()

    # check each possible answer to see if it is consistent
    # with guess_list and feedback_list
    for answer in all_answers:
        check = check_consistency(answer, guess_list, feedback_list)
        if (check == True):
            return answer


"""
inputs: none
output: a list of strings representing all 1296 possible picks
        for the MasterMind game (1296 = 6^4, six raised to the
        fourth power).
"""
def generate_all_answers():
    answers = []
    digits = "123456"
    for digit1 in digits:
        for digit2 in digits:
            for digit3 in digits:
                for digit4 in digits:
                    answer = digit1 + digit2 + digit3 + digit4
                    answers.append(answer)

    return answers

"""
inputs:
- answer: a string, representing one of the 1296 possible answers
- guess_list: a list of the first i guesses that the computer made,
- feedback_list: list of the first i feedbacks that the user provided

output:
- a boolean, true if the answer is consistent with the history
  of guesses and feedbacks. In that case, the answer can possibly
  be the correct answer and be equal to the picked number.
"""
def check_consistency(answer, guess_list, feedback_list):
    for position in range(0, len(guess_list)):
        guess = guess_list[position]
        feedback = feedback_list[position]
        feedback2 = compute_feedback(guess, answer)
        if (feedback != feedback2):
            return False

    return True
        
    
"""
inputs:
- computer guess: a string representing the most recent
  guess made by the computer.

output:
- a string representing the feedback that the user provides
  to the computer, based on computer_guess

note: There is no way for the program to know if the provided
      feedback is correct or not, that is up to the user.
      If the feedback is not correct, the computer at some point
      will realize that no possible answer remains, because of
      inconsistent feedback.
"""
def provide_feedback(computer_guess):
    while (True):
        feedback = raw_input("enter feedback for " + computer_guess + ": ");
        check = check_feedback(feedback)
        if (check == False):
            print("Invalid feedback:", feedback)
        else:
            break

    return feedback

"""
input: feedback that the user just provided
output: True if the feedback is a legal feedback.
Note: the computer has no way of knowing if
the feedback is actually correct.
"""
def check_feedback(feedback):
    # length cannot be more than four
    if (len(feedback) > 4):
        return False

    # should only have os and xs
    check = os_and_xs_check(feedback)
    if (check == False):
        return False

    # the os should come before the xs
    check = os_before_xs_check(feedback)
    if (check == False):
        return False

    return True

"""
input: feedback provided by the user
output: True if feedback contains only os and xs
def os_and_xs_check(feedback)
"""
def os_and_xs_check(feedback):
    for i in feedback:
        if not(i in "ox"):
            return False

    return True

"""
input: feedback provided by the user
output: True if feedback if os show up only before xs
"""
def os_before_xs_check(feedback):
    sorted_feedback = sort_string(feedback)
    if (feedback == sorted_feedback):
        return True
    else:
        return False

"""
input: a string s
output: a sorted version of the input string
"""
def sort_string(s):
    s_list = list(s)
    s_list.sort()
    result = list_to_string(s_list)
    return result

def list_to_string(l):
    result = ""
    for i in l:
        result = result + i

    return result