Showing Revision 1 created 10/24/2012 by Amara Bot.

1. Title:
   13ps-08 Reduced Satisfaction Solution
2. Description:

3. 0 0:00 - 0:02
   Let's take a look at the code.
4. 2170 0:02 - 0:06
   Now the first thing we do is we set a variable called rules affable to be true.
5. 6450 0:06 - 0:11
   And this is so that we know when we can continue applying to the given rules
6. 10820 0:11 - 0:14
   and that way we know when we can simply be done with the function.
7. 13870 0:14 - 0:17
   We also get a temporary assignment to all of the variables of none
8. 17410 0:17 - 0:22
   since we haven't assigned that neither true or false values yet.
9. 21610 0:22 - 0:24
   Now in this loop, well, we can still apply rules.
10. 24490 0:24 - 0:30
    We first set rules affable to false and let's say that unless we come into a situation
11. 30380 0:30 - 0:33
    where we might be able to apply the rules again,
12. 33340 0:33 - 0:37
    we just assume that this is the last time we'll be able to do this.
13. 37240 0:37 - 0:41
    We first deal with single occurrence variables,
14. 40730 0:41 - 0:46
    so we set a counter to be zero for each of the variables here
15. 46190 0:46 - 0:52
    and we'll also set the variable setting to none for each of the variables.
16. 51550 0:52 - 0:56
    And then, for each of the clauses and each variable in each clause,
17. 56000 0:56 - 1:03
    we set the absolute value of the variable and then we increment variable counter of that variable
18. 63300 1:03 - 1:09
    by 1 since we've seen that variable now and we set this variable to 1
19. 69160 1:09 - 1:13
    if it does greater than 0 or 0, otherwise.
20. 73110 1:13 - 1:18
    Or we set it to 1 is 0 to represent true or false if it is positive or negative.
21. 78280 1:18 - 1:22
    Now, we enumerate all of the variable counters with i and var,
22. 82480 1:22 - 1:26
    and if var is not equal to 1 then we go ahead and just continue.
23. 86340 1:26 - 1:31
    And if our temporary assignment is not none, that is it's already going to assign to something,
24. 91120 1:31 - 1:34
    we also continue, otherwise, we fall through
25. 94200 1:34 - 1:39
    and we set the contemporary assignment to the current setting available.
26. 98950 1:39 - 1:42
    In here, we try to deal with single variable clauses.
27. 102250 1:42 - 1:48
    Now, for each clause in the list of clauses, we first check that the length of the clause is not zero.
28. 108390 1:48 - 1:53
    If the length of the clause is greater than 1, we go ahead and just continue to do it.
29. 113240 1:53 - 1:57
    We don't need to check any further; otherwise, we set the variable
30. 117280 1:57 - 2:02
    equal to the only element in the list in the clause
31. 121610 2:02 - 2:05
    and we set a var to the absolute value of that variable.
32. 125320 2:05 - 2:08
    Now if the temporary assignment of avar is not none,
33. 128380 2:08 - 2:13
    if it's already assigned something, then if the temporary assignment of avar is not equal to 1,
34. 133390 2:13 - 2:19
    if the variable is greater than 0 else 0, then we return 1, -1
35. 138550 2:19 - 2:23
    and this is because that means that the variable cannot be satisfied.
36. 142930 2:23 - 2:28
    This clause and that cannot be satisfied, and if not, then we go ahead and fall through
37. 147600 2:28 - 2:32
    and we set the temporary assignment of this variable to 1
38. 151990 2:32 - 2:34
    if the variable is greater than 0 and else 0.
39. 154430 2:34 - 2:38
    Now, we need to go ahead and clean up all of these clauses.
40. 158040 2:38 - 2:44
    In order to do this, we are going to accumulate all of the current clauses into a new list of clauses,
41. 164290 2:44 - 2:49
    so that we can remove the ones that we don't need to worry about anymore.
42. 168570 2:49 - 2:54
    And we enumerate all the current clauses and we also enumerate all the variables in each clause
43. 174450 2:54 - 3:00
    and we set the assignment equal to the temporary assignment for each of these variables.
44. 179520 3:00 - 3:05
    If the assignment is none, then we go ahead and append that variable to the new clause
45. 184660 3:05 - 3:08
    because it's still haven't determined what it should be, otherwise,
46. 187510 3:08 - 3:12
    we said that, well, we might be able to continue applying rules here
47. 191710 3:12 - 3:14
    because we're about to remove some clauses.
48. 194190 3:14 - 3:21
    Now, if the current variable is assigned true, 1 and the variable is greater than 0
49. 201360 3:21 - 3:26
    or the assignment is false, 0 and the variable is less than 0,
50. 206080 3:26 - 3:30
    that is it's negated then we can go ahead and remove the entire clause.
51. 210160 3:30 - 3:34
    So we set this new clause equal to none and we continue on.
52. 213740 3:34 - 3:39
    Otherwise, well, then we just have to remove the variable and we pass through.
53. 218790 3:39 - 3:44
    Now, if clause could not be satisfied then if the new clause is the empty set
54. 224290 3:44 - 3:49
    then we go ahead and return 1, -1 to indicate they cannot be satisfied.
55. 228780 3:49 - 3:52
    Now if the clause instead is greater than 0 then we go ahead
56. 231950 3:52 - 3:57
    and append this clause to the new list of clauses and at the end of this double for loop,
57. 236870 3:57 - 4:04
    we set the current list of clauses to the new list of clauses and if we have set rules applicable to true,
58. 243520 4:04 - 4:08
    then we go ahead and loop that through until that is not true.
59. 247530 4:08 -
    At the end of all this, we go ahead and return the list of clauses and that's it.