example_belief = {'a', 'b'}

"""
Explanation: The idea of reasoning by following simple rules provides an attractively straightforward characterization of cognition. However, production systems can be very difficult to design in ways that are guaranteed to always work. In this problem, you will write some functions to help you work with production systems, and then you will use those functions to reason about several different sets of rules.
Part A (1 point)
We will represent a set of beliefs using Python sets: each element in the set corresponds to a true proposition. For example, the following belief states that 'a' and 'b' are true propositions:
End of explanation
"""


'a' in example_belief

'c' in example_belief

"""
Explanation: As a quick refresher, Python sets are unique, unordered collections of objects. You can check if an item is in a set with the in keyword:
End of explanation
"""


example_belief.add('c')
example_belief

"""
Explanation: You can add new things to the set using the .add() method, for example:
End of explanation
"""


example_belief = {'a', 'b'}
example_rules = [('a', 'b'), ('c', 'd')]

"""
Explanation: So, our beliefs will be represented using sets, and we will represent the rules of our production system using a list of 2-tuples. Each tuple contains a condition and a result. The rule can be applied if the condition is present in the set of beliefs; if the rule is applied, then the result should be added to the set of beliefs. For example, the following belief again consists of 'a' and 'b', and the rules state that "if a, then b" and that "if c, then d":
End of explanation
"""


def print_rules(rules):
    for rule in rules:
        print(str(rule[0]) + " --> " + str(rule[1]))

print_rules(example_rules)

"""
Explanation: To help visualize the rules a bit better, here is a function called print_rules that will print out each rule on a separate line:
End of explanation
"""


def match(belief, rules):
    """Determine whether a rule is triggered by the given set of beliefs.

    The *first* rule in the list of rules that is triggered should be
    returned (and you should only ever return one rule, even if multiple are
    triggered). If no rule is triggered, None should be returned.

    A rule should only be triggered if it adds something new to the set of 
    beliefs: for example, if the beliefs are `{'a', 'b'}`, and there is only 
    one rule, `('a', 'b')`, then it should not be triggered because it 
    doesn't add anything new. If the beliefs were just `{'a'}`, however, then 
    the rule *should* be triggered because it would add `b` to the set of 
    beliefs.

    Hint: you should be able to do this in four lines of code (or less),
    including the return statement.
    
    Parameters
    ----------
    belief : set
        A set of true propositions.
    rules : list of tuples
        A list of tuples, such that for each tuple, the first element implies
        the second (but not vice versa).
        
    Returns
    -------
    The first rule (tuple) that was triggered, or None if no rules were triggered.
    
    """
    ### BEGIN SOLUTION
    for rule in rules:
        if (rule[0] in belief) and (rule[1] not in belief):
            return rule
    return None
    ### END SOLUTION

"""
Explanation: <div class="alert alert-success">Using the representation of beliefs and rules specified above, write a function called <code>match</code> that searches through a given list of rules to find a rule that is triggered by the given set of beliefs.</div>
End of explanation
"""


print(match({'a'}, [('a', 'b')])) # should print ('a', 'b')

print(match({'a', 'b'}, [('a', 'b')])) # should print None

# add your own test cases here!


from nose.tools import assert_equal

# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b')]), ('a', 'b'))

# check that nothing is triggered, because 'b' does not trigger any rules
assert_equal(match({'b'}, [('a', 'b')]), None)

# check that nothing is triggered, because 'a' and 'b' are already in the belief
assert_equal(match({'a', 'b'}, [('a', 'b')]), None)

# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b'), ('b', 'c')]), ('a', 'b'))

# check that b --> c is triggered
assert_equal(match({'a', 'b'}, [('a', 'b'), ('b', 'c')]), ('b', 'c'))
    
# check that nothing is triggered, because 'a', 'b', and 'c' are already in the belief
assert_equal(match({'a', 'b', 'c'}, [('a', 'b'), ('b', 'c')]), None)

print("Success!")

"""
Explanation: Check that your function behaves as expected, based on the example given above:
End of explanation
"""


def forward_chain(belief, rules):
    """Fully execute a set of given rules that match a given belief, until
    no more new rules are triggered. That is, this function should:
    (i) Scan through the rules until it finds rule(s) which are applicable,
    (ii) trigger such rules and update beliefs,
    (iii) repeat (i) and (ii) until no further rules can be triggered.
    
    Returns a new set of beliefs (without changing the original set of beliefs) 
    based on which rules were triggered.

    Note: this function should employ a `while` loop and should call the `match` 
    function you implemented in the first part of this problem.

    Hint: you should be able to do this in 8 lines of code, including the
    return statement.
    
    Parameters
    ----------
    belief : set
        A set of true propositions.
    rules : list of tuples
        A list of tuples, such that for each tuple, the first element implies
        the second (but not vice versa).
        
    Returns
    -------
    tuple of (new_belief, triggered_rules):
        new_belief is an updated set of true propositions, and triggered_rules
        is the list of rules that were triggered, in order.
        
    """
    ### BEGIN SOLUTION
    new_belief = belief.copy()
    rule = match(new_belief, rules)
    triggered_rules = []
    while rule:
        triggered_rules.append(rule)
        new_belief.add(rule[1])
        rule = match(new_belief, rules)
    return new_belief, triggered_rules
    ### END SOLUTION

b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c')])
print_rules(r) # should print both 'a --> b' and 'b --> c'
b              # should be {'a', 'b', 'c'}

# add your own test cases here!


"""Check that `forward_chain` uses the `match` function."""
from nose.tools import assert_raises
orig_match = match
del match
try:
    assert_raises(NameError, forward_chain, {'a'}, [('a', 'b')])
finally:
    match = orig_match

print("Success!")

"""Ensure that the new belief is a different object from the original belief."""
b1 = {'a'}
b2 = forward_chain(b1, [('a', 'b')])
assert_equal(b1, {'a'})
assert_equal(b2, ({'a', 'b'}, [('a', 'b')]))

print("Success!")

"""Check that full forward chaining works."""
b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c'), ('c', 'd')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])

b, r = forward_chain({'a'}, [('b', 'c'), ('c', 'd'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])

b, r = forward_chain({'a'}, [('a', 'c'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [('a', 'c'), ('a', 'b')])

b, r = forward_chain({'b'}, [('a', 'b'), ('b', 'c')])
assert_equal(b, {'b', 'c'})
assert_equal(r, [('b', 'c')])

b, r = forward_chain({'a', 'b', 'c'}, [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [])

b, r = forward_chain(set(), [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, set())
assert_equal(r, [])

print("Success!")

"""
Explanation: Part B (1.5 points)
Now that we have a way to trigger rules based on a set of beliefs, we want to engage in a process called forward chaining. The idea behind forward chaining is that we want to execute rules that are triggered by our beliefs, and to continue triggering rules until no more can be triggered. For example, if we have:
python
rules = [("belief1", "belief2"), ("belief2", "belief3")]
belief = {"belief1"}
To start out, we have belief_1, but we also have a rule "if belief_1, then belief_2". So, we should update our belief with belief_2.
Then, we have another rule that says "if belief_2, then belief_3". Because our belief now consists of both belief_1 and belief_2 (due to triggering the first rule), this second rule should also be triggered, and should add belief_3 to our total set of beliefs.
<div class="alert alert-success">Write a function, <code>forward_chain</code>, to automatically perform forward chaining using a given set of initial beliefs and rules.</div>

Make sure your function does in fact perform full forward chaining -- if there are two matching rules, but only one matches at the beginning, they should still both be triggered:
End of explanation
"""


rules_1 = [
    ('switch is flipped', 'sprinkler was on'),
    ('sprinkler was on', 'grass is wet'),
    ('it rained', 'car is wet'),
    ('it rained', 'path is slippery'),
    ('it rained', 'grass is wet')
]

"""
Explanation: Part C (0.5 points)
Imagine you have a small sprinkler that can water your grass, but does not reach the path you walk on, or your car. However, if it rains, then the car and the path both get wet. The sprinkler definitely comes on if the appropriate switch is flipped. We might try to capture this information in a production system as follows:
IF switch is flipped THEN sprinkler was on
IF sprinkler was on THEN grass is wet
IF it rained THEN car is wet
IF it rained THEN path is slippery
IF it rained THEN grass is wet

Or, in Python:
End of explanation
"""


# perform forward chaining on the belief that 'switch is flipped'
belief_1, triggered_rules_1 = forward_chain({'switch is flipped'}, rules_1)

# print which rules were triggered
print_rules(triggered_rules_1)

# show the final belief
belief_1

"""
Explanation: If you now observed switch is flipped but nothing else, what would the above production system lead you to conclude? Use your forward_chain function to find out:
End of explanation
"""


rules_2 = [
    ('sprinkler was on', 'switch is flipped'),
    ('car is wet', 'it rained'),
    ('path is slippery', 'it rained'),
    ('grass is wet', 'it rained')
]

"""
Explanation: <div class="alert alert-success">
In words, what do the production rules have to say about the states of the sprinkler, grass, car, and the path given that you observed that the switch is flipped? Be careful to only report beliefs that are justified by your observations and the triggered rules of our production system and _not_ what you personally believe!
</div>

If your code was correct, the triggered rules would be:
switch is flipped --&gt; sprinkler was on
sprinkler was on --&gt; grass is wet
Which would lead to the beliefs that the switch is flipped, the sprinkler was on, and the grass is wet and nothing else. Students needed to say that they had no belief about the state of the path, not that the path was/was not slippery.
Part D (0.5 points)
For this next section, let's imagine a different production system that is similar but ultimately unrelated to the one we defined in Part C:
IF sprinkler was on THEN switch is flipped
IF car is wet THEN it rained
IF path is slippery THEN it rained
IF grass is wet THEN it rained

Or, in Python:
End of explanation
"""


# perform forward chaining on the belief that 'grass is wet'
belief_2, triggered_rules_2 = forward_chain({'grass is wet'}, rules_2)

# print which rules were triggered
print_rules(triggered_rules_2)

# show the final belief
belief_2

"""
Explanation: In this new production system, if you knew only that the grass is wet what would you conclude? Again, you can use your forward_chain function to find out:
End of explanation
"""


# perform forward chaining on the belief that 'sprinkler was on'
belief_3, triggered_rules_3 = forward_chain({'sprinkler was on'}, rules_1 + rules_2)

# print which rules were triggered
print_rules(triggered_rules_3)

# show the final belief
belief_3

"""
Explanation: <div class="alert alert-success">
What conclusion(s) do you draw? Intuitively, do they seem like valid or reasonable inferences to make given the rules of your production system? Explain.
</div>

If your code was correct, the triggered rule would be:
grass is wet --&gt; it rained
Which would lead to the belief that the grass is wet and that it rained, but nothing else. Common sense tells us that the fact that it rained should also imply that the car is wet and the path is slippery, although this inference is not  supported by the production rules in our new system. Other answers were accepted if they were well-justified.
Part E (1.5 points)
Finally, we can imagine a third production system where the rules apply in both directions:
IF switch is flipped THEN sprinkler was on
IF sprinkler was on THEN grass is wet
IF it is raining THEN car is wet
IF it is raining THEN path is slippery
IF it is raining THEN grass is wet
IF sprinkler was on THEN switch is flipped
IF car is wet THEN it is raining
IF path is slippery THEN it is raining
IF grass is wet THEN it is raining

If you observed sprinkler was on, what would you conclude? You can again use forward_chain:
End of explanation
"""


