An implementation of Student, a program capable of solving basic math problems in which a variable needs to be isolated

student.py

"""
Student was an AI program developed in the late sixties which used
pattern matching to solve basic algebraic word problems. This an
attempt to implement Student in Python through study of the Common
Lisp imlpementation outlined in Paradigms of Artificial Intelligence
Programming: Case Studies in Common Lisp (PAIP) by Peter Norvig.
"""
import operator
import re

# A list of rules used to power the pattern matching of the student
# algorithm. Each rule is of the form [pattern, translation] where
# pattern is a regex for matching and tranlation is where the matching
# portions of the regular expression should be transplanted. The name
# of the matching portions is where the translation should be placed.

student_rules = [(r"(?P<xvar>.+) is (?P<yvar>.+)", ["=", "xvar", "yvar"]),
                 (r"twice (?P<xvar>.+)", ["*", "2", "xvar"]),
                 (r"(?P<xvar>.+) plus (?P<yvar>.+)", ["+", "xvar", "yvar"])]


# Once we have things in there simplest form we need to conver them into
# numbers, variables, and mathematical symbols. The atomize function is
# what handles this step. These same symbols are used later when student
# tries to solve problems.

def solve(args):
    pass

DIVISION_SYMBOL = operator.div
MULTIPLICATION_SYMBOL = operator.mul
ADDITION_SYMBOL = operator.add
SUBTRACTION_SYMBOL = operator.sub
EQUALITY_SYMBOL = solve

MATH_SYMBOLS = {"+": ADDITION_SYMBOL,
                "-": SUBTRACTION_SYMBOL,
                "*": MULTIPLICATION_SYMBOL,
                "/": DIVISION_SYMBOL,
                "=": EQUALITY_SYMBOL}

SYMBOLS = MATH_SYMBOLS.values()

def atomize(x):
    """
    Converts to the simplest form. Numbers to numbers. Variables to themselves.
    Math symbols to functions. Returns the converted form.
    """
    # Anything that is a number should be converted into a number.
    try:
        return float(x)
    except ValueError:
        pass
    try:
        return MATH_SYMBOLS[x]
    except KeyError:
        pass
    return x

def match_rule(rule, string):
    """
    Accepts a rule which is a tuple containing a pattern with named
    group capturing and a translation list. Also accepts a string to
    match the regex pattern in the rule against.
    
    Returns a dictionary mapping the named groups in the regex to
    their matches. If there are no matches, returns None instead.
    """
    pattern = re.compile(rule[0])
    match = pattern.match(string)
    if match:
        match_groups = match.groups()
        match_dict = {}
        for key, value in pattern.groupindex.items():
            match_dict[key] = match_groups[value-1]
        return match_dict
    return None

def replace(l, bindings):
    """
    Accepts a list and a dictionary with bindings. All instances of
    the keys in the bindings dict will be replaced by the value at
    the location within the list.
    
    Returns a new list with the indicated replacements.
    """
    replace_indexes = {}
    for key, value in bindings.items():
        pos = 0
        # Get all matching indexes. If things go wrong then fail.
        try:
            while pos < len(l):
                pos = l.index(key, pos)
                replace_indexes[pos] = value
                pos = pos + 1
        except ValueError:
            pass
    new_l = l[:]
    for key, value in replace_indexes.items():
        new_l[key] = value
    return new_l
        
def translate_rule(rule, bindings):
    """
    Accepts a rule and a dictionary with bindings.
    
    Replaces a new list in which all the keys in the bindings list have been
    replaced by the value at those keys.
    """
    translation = rule[1]
    return replace(translation, bindings)
        
def run_rrbt_on_str(rules, string):
    """
    Attempts to match the string against the list of rules. If unable to match,
    the string is in its simplest form. If there is a match, translate the rule
    and translate its sub-components then return the result.
    
    Returns a list of fully recursively translated rules.
    """
    for rule in rules:
        match = match_rule(rule, string)
        if match:
            translation = translate_rule(rule, match)
            fully_translated = [run_rrbt_on_str(rules, s) for s in translation]
            return fully_translated
    return atomize(string)
        
# Assuming you have an equation like [= this [* 2 5]] you would then need to
# solve for the missing variable. Well, you would need to isolate the unknown
# varible. Variables are strings. 
# Which I would be able to do with run_rrbt_on_str. 
# I now need to solve the equation. How do I do that?
# Solve was implemented by Norvig by actually going through the process of
# solving a problem. That means you need to check to see if there is an equation
# which you already know the answer to. You know an equations solutions if there
# is only one unkown variable within it. So the trick to solving an equation has
# a first step. We need to find how many unkowns the equation has.
# Knowing this implies that we actually have a way of telling variables apart
# from numbers. So the next step for me is to do something along the lines of
# treating any string I find as a variable named that string while also having
# a dictionary that I keep which holds the name of all the variables.
# I'll once again assume that I have this going forward. I'll write the solution
# assuming that I'll be able to get this dictionary at some point in the future.

def is_variable(variable):
    """
    Returns True if variable is a variable.
    """
    return isinstance(variable, str)

def is_unknown(variable, known):
    """
    Returns True if variable is an unkown variable.
    """
    return is_variable(variable) and variable not in known
    
from matplotlib.cbook import flatten
def has_one_unknown(equation, known):
    """
    Returns if the equation has only one unkown variable.
    """
    return 1 == len(filter(lambda x: is_unknown(x, known), flatten(equation)))
    
# When solving a math problem in which you already have all the information
# needed to solve, solving the problem is just a matter of isolating the
# variable. Isolating the variable means getting the variable on the left
# hand side of the equation while all other terms are on the right hand side
# of the equation. In order to do that I need to have the symbols for addition,
# subtraction, multipication, and division. Without them I can't actually do the
# operations that allow me to place the variable on the right side. Before I can
# even do that I need to also be able to tell where the variable is too. The
# act of isolation is 'communtative'(??). I think you can treat solving for the
# right hand side the same way that you would for solving for the left hand side.
# So once I find out what side the equation is on, I can flip things if I don't
# like what side they are on. This brings me to a case in which all my changes
# are fairly simple.
# So what I'm going to do next is I'm going to make a test to figure out what
# side of the equation I'm working on. Then I'm going to call a program which
# flips the equation so that I'm always working with the equation I want to be
# working with.
# I can use the has_one_unkown code to check to see if the variable is where it
# should be. However, the fact that some equatoins are made up of multiple vars
# means that this code must actually have all known variables in its map.
# Actually, it is kind of required that I already know what side of the equation
# the thing I'm working on is on. Moreover, I kind of need to know the actual
# name of the variable I'm trying to find. At least, I'll need to know that
# information eventually so I can pick out exactly how I'm suppose to manipulate
# the symbols I've been given.
# I read up a little bit in my PAIP textbook to doublecheck my assumptions. I
# got the word communicative a bit wrong on my first writethrough. I should have
# said that it has the property of being commutative. I was also right about
# needing to know the name of the unknown variable. At the very least I know
# that Norvig had a function to get the name of the variable in his program.
# Since my program is modeled after his it isn't suprising that I would find the
# same need arising.

def get_unknown(equation, known):
    """
    Assuming the equation has only one unkown, returns the name of that unkown.
    """
    assert(has_one_unknown(equation, known))
    return filter(lambda x: is_unknown(x, known), flatten(equation))[0]

# I've decided to use assert to make sure that my code is getting the input
# it expects since the code that will use it has not yet been implemented, but
# I still have expectations for that code which need to be satisfied.

def has_unknown_lhs(equation, known):
    assert(equation[0] in SYMBOLS)
    unknown = get_unknown(equation, known)
    lhs = equation[1]
    return unknown == lhs or (isinstance(lhs, list) and unknown in flatten(lhs))

def swap(l1, index1, index2):
    l2 = l1[:]
    l2[index1] = l1[index2]
    l2[index2] = l1[index1]
    return l2

def put_unknown_on_lhs(equation, known):
    if has_unknown_lhs(equation, known):
        return equation
    else:
        return swap(equation, 1, 2)

# Now I have the means to get an equation in a standard starting position.
# Every one-unknown equation can start out the same way. The next step is
# to create transformations between states. The easiest ones to do this for
# are the ones that obey the commutative property. That is to say the easiest
# ones to do this for are the ones which have addition and subtraction. I can
# declare an addittion symbol and a subtraction symbol to stand in for the 
# values I need.
# Then when I see that the  equation I'm solving has that symbol at the start of
# it I can take out the symbols that are in the equation and put them on the
# other side. What I want to do, I think, is unwrap the equation. I don't want
# to take anything but the topmost symbol. This might mean that I need to change
# the code I wrote earlier to return what side of the equation the thing I am
# grabbing is on. Actually, it does. There is no way that the code can not tell
# me explicilty regardless of the type of equation. I think I can modify it to
# check against being in a table of valid symbols though, instead of checking to
# see if its only an equation. Put in the simplest terms I can, I need a boolean
# function which tells me whether the unkown is in the left hand side or right
# hand side of an equation or the left hand term or right hand term of an
# expression.
# Alright I went back up and fixed that. Now I'm going to take a brief break. My
# hope is that when I return I can read the above and quickly get back up to
# speed. I want to think about the idea of unwrapping while not needing to type
# to make sure I'm actually doing this the right way.

def is_isolated(equation, known):
    return get_unknown(equation, known) == equation[1]

def isolate(equation, known):
    """
    Given an equation [= expression expresssion] and a dict of known variables
    returns the same equation, but with the unkown variable isolated on the
    right hand side of the equation.
    """
    new_equation = equation[:]
    if not has_unknown_lhs(new_equation, known):
        return isolate(put_unknown_on_lhs(new_equation, known), known)
    if is_isolated(new_equation, known):
        return new_equation
    lhs = new_equation[1]
    rhs = new_equation[2]
    # Break up the expression into two parts while making sure that there are no
    # changes to equation.
    on_left = has_unknown_lhs(lhs, known)
    unknown_part = lhs[1] if on_left else lhs[2]
    known_part = lhs[2]   if on_left else lhs[1]
    symbol = lhs[0]
    new_equation[1] = unknown_part
    if symbol == MULTIPLICATION_SYMBOL:
        new_equation[2] = [DIVISION_SYMBOL, rhs, known_part]
    elif symbol == DIVISION_SYMBOL:
        if on_left:
            new_equation[2] = [MULTIPLICATION_SYMBOL, rhs, known_part]
        else:
            new_equation[2] = [DIVISION_SYMBOL, known_part, rhs]
    elif symbol == ADDITION_SYMBOL:
        new_equation[2] = [SUBTRACTION_SYMBOL, rhs, known_part]
    elif symbol == SUBTRACTION_SYMBOL:
        if on_left:
            new_equation[2] = [ADDITION_SYMBOL, rhs, known_part]
        else:
            new_equation[2] = [SUBTRACTION_SYMBOL, known_part, rhs]
    if is_isolated(new_equation, known):
        return new_equation
    else:
        return isolate(new_equation, known)

# Once you have the ability to isolate a variable, everything else quickly falls
# into place. Given an equation with only one unkown variable in it, solving the
# equation is only a matter of computation. The following function converts an
# equation with its known part on the right hand side into its value.
def compute(expression, known):
    """
    Given an expression and a list of known variables, computes the expression
    and returns the result.
    """
    if isinstance(expression, list):
        first_part = compute(expression[1], known)
        second_part = compute(expression[2], known)
        return expression[0](first_part, second_part)
    elif isinstance(expression, str):
        return known[expression]
    else:
        return expression

def solve(equation, known):
    """
    Given an equation with unknown variable returns a dict that includes the
    that is knonw plus the result of solving for the unknown variable.
    """
    new_known = known.copy()
    isolated = isolate(equation, known)
    unknown = get_unknown(isolated, known)
    new_known[unknown] = compute(isolated[2], known)
    return new_known

def repl():
    while True:
        raw = raw_input("Give me a problem:")
        equations = run_rrbt_on_str(student_rules, raw)
        solutions = solve(equations, {})
        print solutions


# Alright, I've proven to myself that I get this concept and even how to
# continue to extend it to multiple equations. I think it is a pretty neat tool
# to have. I can translate things based on simple rules and also manipulate the
# translated symbols (or really any symbols) in order to do things with them.
# For example, I could probably use this same idea to have rules that would
# translate "today" and "tommorow" such that it would convert them into datetime
# functions.