Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

please solve this lab in c++ in virtual machine I will be very thankful to you I have edited it more information in the bottom.

please solve this lab in c++ in virtual machine

I will be very thankful to you

I have edited it more information in the bottom.

please let me know if you still need more information. image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

inheritance.cpp

#include
#include
#include
#include
using namespace std;
class Animal {
public:
Animal(string name) : name(name) {}
virtual void talk() = 0; // pure virtual function
string getName() const { return name; }
private:
// every Animal has a name
string name;
};
class Cat : public Animal {
public:
Cat(string name) : Animal(name) {}
void talk() override { cout
};
class Dog : public Animal {
public:
Dog(string name) : Animal(name) {}
void talk() override { cout
};
int main() {
auto c = make_shared("Lonzo");
auto d = make_shared("Cisco");
vector> v = {c, d};
for (auto x : v) {
cout getName()
x->talk();
}
return 0;
}

possibilities.rkt

#lang racket
(define (print-possibilities unchosen-vars chosen-vars)
(cond
[(empty? unchosen-vars)
;; base case: unchosen-vars is empty (we've chosen everything)
;; print out the current chosen-vars
(displayln (reverse chosen-vars))]
[else
;; recursive case: unchosen-vars is nonempty
;; take one var out of unchosen-vars, and put it into chosen vars
;; (trying each possibility)
;; to extract the first thing in the list, we use first
(define var (first unchosen-vars))
;; to get everything except the first element, use rest
(define rest-of-vars (rest unchosen-vars))
;; try the tree possibilities for the var
;; cons adds an element to the front of a list (and it also makes pairs)
(print-possibilities rest-of-vars (cons `(,var "A") chosen-vars)) #| try A |#
(print-possibilities rest-of-vars (cons `(,var "B") chosen-vars)) #| try B |#
(print-possibilities rest-of-vars (cons `(,var "C") chosen-vars)) #| try C |# ]))
(define (print-possibilities-prettier vars)
(print-possibilities vars '()))
;; initially, everything is unchosen and nothing is chosen
(print-possibilities '("x" "y" "z") '())
;; could also call the prettier version with:
;; (print-possibilities-prettier '("x" "y" "z"))

smart-pointers

#include
#include
using namespace std;
class C {
public:
int x;
~C() { cout
};
int main() {
// p points to a new int on the heap, with the value 42
// unique_ptr is kind of like int*
unique_ptr p = make_unique(42);
cout
unique_ptr p2 = make_unique();
// unique_ptr p_2_copy = p2;
// can't do the above because the ptr is supposed to be
// unique (you can use move to move it, though)
// The points inside p and p2 get deleted automatically for us right before
// main returns
shared_ptr p3 = make_shared(43);
cout
shared_ptr p4 = make_shared();
shared_ptr p5 = p4; // it's okay to copy around shared_ptrs
p5->x = 44;
cout x
return 0;
}
Lab 1: SAT Solving CSCI 26 Due date: February 11, 5pm Objectives: Practice using our logical skills with code Remember how trees, recursion, and inheritance work Part 1: Get the starter code First, get the latest starter code on your virtual machine by running the following command in the terminal: refresh-starter-code Next, cd into the folder where you store your class files (e.g../media/sf_CSCI/). Copy the starter code there with the following line: cp -R /starter-code/csci26/1ab01 . The dot at the end is important! This will make a lab01 folder in whatever directory you were in. Then, if you cd into that folder and run ls you should see the following files: $ ls expected-output.txt logic.h testing.cpp testLogic.cpp logic.cpp Makefile testing.h Now you're ready to start working. Part 2: SAT solve like there's no tomorrow Make sure to watch the introduction video that explains everything! You won't need to write more than 50 lines of code for this lab, but you'll have to think hard about every line. SAT solving is the process of taking a Boolean formula and determining whether or not it is satisfiable--that is, whether it is possible to set the variables just right to make the formula be true. For example, the formula p V (q^r) is satisfiable because you could set p = T. q = F, and r = F and the formula would evaluate to T. In this lab we want to find all the ways to make a formula satisfiable. Take a look at logic.h and testLogic.cpp, and notice how we're using subclasses of Formula to represent logical formulae. In particular, notice how I build the formula from above in testEval. Part 2.1: Implement evaluate for each Formula subclass Each logical formula is represented as a tree. The tree in blue below is essentially what p V (q) looks like: Or Ivaraval p> true recupive / la false ry talge Var (p) And subtres Varla) Var (r) ) ) evals to true Not I subtree evals to false To evaluate any non-Var Formula to true or false, you can recursively evaluate its children and combine their result(s). For example, suppose you're evaluating Or(x, y), where x and y are any Formula. To evaluate the entire Or(x, y), you can evaluate x and y individually first-then you can combine them together using II. since that's what Or means! The leaves in Formula trees are always Vars. A Var could stand for anything, so that is why we pass along the var2Val map (shown in green) when we call evaluate-the user must pick ahead of time what each variable's value is. Evaluating a Var, then, is as simple as looking up its value in the map. Implement the proper overridden evaluate method for each subclass of Formula. Part 2.2: Implement satSolve and satSolveHelper These two functions do the actual satisfiability checking, and they'll take the most work to get right. The goal of satSolve is to take a Formula, try every possible combination of values for every variable, and remember each combination that evaluated to true. A solution to a Formula is an assignment of variables that makes the Formula evaluate to true. The easiest way to do all this is with a recursive helper function. satSolveHelper takes four parameters: The Formula you're trying to SAT solve. The variables you haven't make choices for yet. The variables you have made choices for and the values you're currently trying for them). A reference to the set that contains all the satisfying solutions. Every time you find a new solution, you'll add it to this set. . Read the comments for an in-depth explanation of how the recursion needs to work. Here's a quick summary of what happens in each case: In the base case, you've made choices for each variable in the Formula f, and you're ready to try them out. If f evaluates to true with your current choices for variables, then you should add the solution to your set of solutions. In the recursive case, you're still guessing values for each variable. You'll take out a variable v that hasn't been assigned to yet, and make two different recursive calls--you do this because you need to try setting v to true and to false. o Each time you make a recursive call, the number of variables left to choose shrinks by one. That guarantees that you'll never get stuck in an infinite loop! When you make your initial call to satSolveHelper from inside satSolve, no decisions have been made yet. So, you'll start with a full set of remainingVars and an empty map of choices ForVars. You can compile with make testLogic and run with ./testLogic. Compare your output with expected-output.txt to know if you're on the right track. Part 3: Submit your code Once you're satisfied with your solution (or if you want to get some partial credit in), you can submit your code to the autograder. Do not submit and assume you got 100%-you may be unpleasantly surprised. Always check your grade. From your solution directory, submit your code to the autograder using the following command on the terminal: turnin lab01@csci26 logic.cpp The autograder will grade your code within 15-30 minutes. If it's not working, please yell at Lawton to fix it. Run refresh-grades to download your updated grades, and view-grades to look at them. You may resubmit as much as you want before the due date. Rubric Rubric Item Points (24 pts total) The evaluate tests pass 4 pts (2 for each test) 20 pts (5 for each test) The satSolve tests pass UAWN C testing.hx C testing.h>... i #ifndef TESTING_H 2 #define TESTING_H 3 4 #include 5 #include 6 7 void assertTrue(bool b, std::string description); 8 9 template 10 void assertEquals(const T& X, const u& y, std::string description) { 11 if (x == y) { 12 std::cout ... 1 #include "testing.h" 2 3 using namespace std; 4 5 void assertTrue(bool b, string description) { 6 if (!b) { 7 cout ... 1 #ifndef LOGIC_H 2 #define LOGIC_H 3 4 #include #include 7 #include 8 #include 9 #include 10 11 Il combine the elements of two sets into a new set template 13 std::set operator+(const std::set& a, const std::set& b) { 14 std::set res; 15 std::set_union (a.begin(), a.end(), b.begin(). b.end(), 16 std::inserter(res, res.begin())); 17 return res; 18 } 19 20 class Var; 21 22 // Base class for logical formulae 23 class Formula 24 public: 25 1/ evaluates the Formula with a given assignment of Vars to values 26 virtual bool evaluate(std::map varVal) = 0; 27 // returns all the variables that exist in the Formula 28 virtual std::set extractvarNames() = 0; 29 virtual -Formula() = default; et une C logic.h> 27 1/ returns all the variables that exist in the rormula 28 virtual std::set Var> extractvarNames() = 0; 29 virtual -Formula( ) = default; 30 }; 31 32 // You can and together two logical formulae 33 class And : public Formula { 34 public: 35 And(std::shared_ptr lhs, std::shared_ptr varaval) override; 37 std::set extractVarNames() override; 38 39 private: 40 Il you can And together two formulae and produce a bigger Formula! 41 // lhs: left-hand side 42 std::shared_ptr lhs; 43 std::shared_ptr rhs; 44 }; 45 46 // You can Or together two logical formulae 47 class or : public Formula { 48 public: 49 Or(std::shared_ptr lhs, std::shared_ptr rhs); 50 bool evaluate(std::map var2Val) override; 51 std::set extractvarNames() override; 52 53 private: 54 std::shared_ptr lhs; 55 std::shared_ptr rhs; 56 in 1, Col1 Spaces: 2 UTF-8 LF C++ Linux ? PEL 59 62 65 C logich C logic.h>... 54 std::shared_ptrsFormula> lhs; 55 std::shared_ptrsFormulas rhs; 56 }; 57 58 // You can negate any logical formula class Not: public Formula { 60 public: 61 Not(std::shared_ptr inside); bool evaluate(std::map varaval) override; 63 std::set extractvarNames() override; 64 private: 66 std::shared_ptr inside; }; 68 69 // A single propositional variable by itself is a logical formula 70 // You can use Vars inside of bigger formulae class Var : public Formula { 72 public: Var(std::string name); 74 bool evaluate(std:: map varaval) override; 75 std::set extractvarNames() override; 76 77 bool operator. 78 friend std::ostream& operator> satsolve (Formula& f); 88 1/ Helper function for sat solve that does the heavy lifting 89 void satSolveHelper (Formulas f, std::set remainingVars, 90 std::map choicesForVars, 91 std::set<:map bool>>& satisfyingSolutions); 92 93 #endif /* LOGIC_H / 94 87 2 C logic.cpp x Glogic.cpp p>... 1 #include "logic.h" using namespace std; 3 4 // Stuff I've implemented for you (don't touch pls) And::And (shared_ptreFormula> ths, shared_ptr rhs) : lhs(ths), rhs(rhs) () set And::extractVarNames() { return lhs->extractvarNames() + rhs->extractvarNames(); } Or::Or(shared_ptr rhs) : lhs(lhs), rhs(rhs) { set Or::extractVarNames() { return lhs->extractVarNames() + rhs->extractvarNames(); } Not :: Not (shared_ptr inside) : inside (inside) {} setextractVarNames(); } Var::Var(string name) : name (name) () 24 25 set Var::extract VarNames() { return {name}; } 26 27 bool Var::operator ... DOOL var::operator var2val) { 41 return true; // fix this 42 } 43 44 // FIXME: implement Or's evaluation method 45 46 // FIXME: implement Not's evaluation method 47 48 // FIXME: implement Var's evaluation method 49 // How can you turn a variable into a boolean? 50 // (This is the base case, so no recursive calls needed here) 51 52 1/ Given a formula f, try all the possibilities for the variables, and 53 // return all the ways to make it true. 54 set> satSolve (Formula& f) { 55 set> solutions; 56 ... 58 60 61 62 63 64 65 G logic.cpp X logic.cpp).. 53 il return all the ways to make it true. 54 set> satsolve(Formula& f) { 55 set> solutions; 56 57 // FIXME: call satSolveHelper with the proper values // use the solutions variable to store every solution you find 59 return solutions; } // FIXME: implement this function to recursively find all the satisfying 1/ solutions for a Formula f. You will do this by trying both true and false fc // every variable in the formula. 66 // 67 // Explanations of the other parameters: remainingVars: the variables that you have not yet picked values for 69 choices ForVars: the variables that you have* picked values for (and // those values) 71 // satisfyingSolutions: a set of all the different variable choices 72 // (represented as a map) // that make the Formula f true. This is a reference, // so you'll extend it each time you find a new 75 // solution. 76 void satSolveHelper (Formula& f, set remainingVars, 77 map choicesForVars, set>& satisfyingSolutions) { 79 1/ Base case: There are no remaining vars. This means you've made choices // for everybody, and now it's time to see if those choices paid off. Check if f is true when evaluated using our current 68 - 70 73 74 78 80 81 T logic.cpp Clogic.cpp > 78 set>& satisfying Solutions) { 79 1/ Base case: There are no remaining vars. This means you've made choices for everybody, and now it's time to see if those choices paid // off. Check if f is true when evaluated using our current choices forvars. If it is, add our current choices ForVars to the satisfyingSolutions. // Recursive case: There is at least one Var to pick a value for. Try both true and false for it recursively. // Steps to follow in this case: // extract one Var (call it nextChoice) out of the remaing Vars // (remainingVars.begin() is a good way to get a Var out of a set) // create a new set of remaining variables, removing the one you just // chose for your next Choice variable recursively try to solve the Formula f using nextChoice set to true // recursively try to solve the Formula fusing nextChoice set to false } 95 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 B FA 4 8 CtestLogic.cpp testLogic.cpp > ... i #include 2 using namespace std; 3 #include "logic.h" 5 #include "testing.h" 6 7 void testEval(); void testSATO(); 9 void testSATI(); 10 void testSAT2(); 11 void testSAT3(); 12 13 int main() { testEval(); 15 testSATO(); 16 test SAT1(); 17 test SAT2(); testSAT3(); 19 20 return 0; 21 } 22 23 1/ helper functions to make Formulas 24 shared_ptr _And (shared_ptr lhs, shared ptr Formula rhs) { 25 return make_shared(lhs, rhs); } 27 28 shared_ptr _Or(shared_ptr lhs, shared_ptreFormulas rhs) { 29 return make_shared(lhs, rhs); 14 18 26 8 21 29 30 33 34 38 GtestLogic.cpp C testLogic.cpp .. 28 shared_ptr _Or(shared_ptr lhs, shared_ptr rhs) { return make_shared(ihs, rhs); } 31 32 shared_ptr _Not (shared_ptr inside) { return make_shared(inside); } 35 36 shared_ptr _Var(const string& s) { return make_shared(s); } 37 1/ helper function to print all the solutions our satSolve function finds 39 void printSolutions (set>& solutions) { 40 int i = 1; 41 for (auto m: solutions) { 42 cout " p = make_shared q = make_shared("q"); 59 shared_ptr r = make_shared("r"); shared_ptr not r = make_shared(r); 61 shared_ptreAnd> q_and_not_r - make_shared(q, not_r); 62 shared_ptr p_or_q_and_not_r - make_shared(p. q_and_not_r); map varzvali = {{*p, false}, {*q, true}, {*r, false}}; 65 // try evaluating the formula with p = false, q = true, and r = false assertTrue(p_or_9_and_not_r->evaluate (varavall) == true, "false || (true && 67 mapevaluate(var2Val2) == false, "false || (false & 71 72 cout > solutions - satSolve(f); 66 68 69 73 78 79 80 81 82 B testLogic.cpp testLogic.cpp). shared_ptr> solutions - satsolve(**); 80 82 92 83 printsolutions(solutions); 84 } 85 86 // pva 87 void testSATI() { 88 cout > solutions = satsolve(*f); 93 94 printSolutions (solutions); 95} 96 97 11 (p ^ (9^ -r)) v (p (- A-r)) void testSAT2() { 99 cout > solutions = satsolve(*f); 106 107 printSolutions (solutions); 108 } 98 6 testLogic.cpp testLogic.cpp >.. 104 _And(_var("P"), _And(_NOT (_var(-9")), _NOT (_var("r"))))); 105 set> solutions = satSolve(*f); 106 107 printSolutions (solutions); 108 } 109 110 11 (pv a) v (ir vs) v (t ^ -u)) 111 void testSAT3() { 112 cout f = _Or( 116 _Or(_Var("p"), Var("q")), 117 Or(_or(_Not (_Var("r")), _Var("s")), _And(_Var("t"), _Not (_Var("u"))))); 118 set> solutions = satSolve(*f); 119 120 printSolutions (solutions); 121 } 122 Lab 1: SAT Solving CSCI 26 Due date: February 11, 5pm Objectives: Practice using our logical skills with code Remember how trees, recursion, and inheritance work Part 1: Get the starter code First, get the latest starter code on your virtual machine by running the following command in the terminal: refresh-starter-code Next, cd into the folder where you store your class files (e.g../media/sf_CSCI/). Copy the starter code there with the following line: cp -R /starter-code/csci26/1ab01 . The dot at the end is important! This will make a lab01 folder in whatever directory you were in. Then, if you cd into that folder and run ls you should see the following files: $ ls expected-output.txt logic.h testing.cpp testLogic.cpp logic.cpp Makefile testing.h Now you're ready to start working. Part 2: SAT solve like there's no tomorrow Make sure to watch the introduction video that explains everything! You won't need to write more than 50 lines of code for this lab, but you'll have to think hard about every line. SAT solving is the process of taking a Boolean formula and determining whether or not it is satisfiable--that is, whether it is possible to set the variables just right to make the formula be true. For example, the formula p V (q^r) is satisfiable because you could set p = T. q = F, and r = F and the formula would evaluate to T. In this lab we want to find all the ways to make a formula satisfiable. Take a look at logic.h and testLogic.cpp, and notice how we're using subclasses of Formula to represent logical formulae. In particular, notice how I build the formula from above in testEval. Part 2.1: Implement evaluate for each Formula subclass Each logical formula is represented as a tree. The tree in blue below is essentially what p V (q) looks like: Or Ivaraval p> true recupive / la false ry talge Var (p) And subtres Varla) Var (r) ) ) evals to true Not I subtree evals to false To evaluate any non-Var Formula to true or false, you can recursively evaluate its children and combine their result(s). For example, suppose you're evaluating Or(x, y), where x and y are any Formula. To evaluate the entire Or(x, y), you can evaluate x and y individually first-then you can combine them together using II. since that's what Or means! The leaves in Formula trees are always Vars. A Var could stand for anything, so that is why we pass along the var2Val map (shown in green) when we call evaluate-the user must pick ahead of time what each variable's value is. Evaluating a Var, then, is as simple as looking up its value in the map. Implement the proper overridden evaluate method for each subclass of Formula. Part 2.2: Implement satSolve and satSolveHelper These two functions do the actual satisfiability checking, and they'll take the most work to get right. The goal of satSolve is to take a Formula, try every possible combination of values for every variable, and remember each combination that evaluated to true. A solution to a Formula is an assignment of variables that makes the Formula evaluate to true. The easiest way to do all this is with a recursive helper function. satSolveHelper takes four parameters: The Formula you're trying to SAT solve. The variables you haven't make choices for yet. The variables you have made choices for and the values you're currently trying for them). A reference to the set that contains all the satisfying solutions. Every time you find a new solution, you'll add it to this set. . Read the comments for an in-depth explanation of how the recursion needs to work. Here's a quick summary of what happens in each case: In the base case, you've made choices for each variable in the Formula f, and you're ready to try them out. If f evaluates to true with your current choices for variables, then you should add the solution to your set of solutions. In the recursive case, you're still guessing values for each variable. You'll take out a variable v that hasn't been assigned to yet, and make two different recursive calls--you do this because you need to try setting v to true and to false. o Each time you make a recursive call, the number of variables left to choose shrinks by one. That guarantees that you'll never get stuck in an infinite loop! When you make your initial call to satSolveHelper from inside satSolve, no decisions have been made yet. So, you'll start with a full set of remainingVars and an empty map of choices ForVars. You can compile with make testLogic and run with ./testLogic. Compare your output with expected-output.txt to know if you're on the right track. Part 3: Submit your code Once you're satisfied with your solution (or if you want to get some partial credit in), you can submit your code to the autograder. Do not submit and assume you got 100%-you may be unpleasantly surprised. Always check your grade. From your solution directory, submit your code to the autograder using the following command on the terminal: turnin lab01@csci26 logic.cpp The autograder will grade your code within 15-30 minutes. If it's not working, please yell at Lawton to fix it. Run refresh-grades to download your updated grades, and view-grades to look at them. You may resubmit as much as you want before the due date. Rubric Rubric Item Points (24 pts total) The evaluate tests pass 4 pts (2 for each test) 20 pts (5 for each test) The satSolve tests pass UAWN C testing.hx C testing.h>... i #ifndef TESTING_H 2 #define TESTING_H 3 4 #include 5 #include 6 7 void assertTrue(bool b, std::string description); 8 9 template 10 void assertEquals(const T& X, const u& y, std::string description) { 11 if (x == y) { 12 std::cout ... 1 #include "testing.h" 2 3 using namespace std; 4 5 void assertTrue(bool b, string description) { 6 if (!b) { 7 cout ... 1 #ifndef LOGIC_H 2 #define LOGIC_H 3 4 #include #include 7 #include 8 #include 9 #include 10 11 Il combine the elements of two sets into a new set template 13 std::set operator+(const std::set& a, const std::set& b) { 14 std::set res; 15 std::set_union (a.begin(), a.end(), b.begin(). b.end(), 16 std::inserter(res, res.begin())); 17 return res; 18 } 19 20 class Var; 21 22 // Base class for logical formulae 23 class Formula 24 public: 25 1/ evaluates the Formula with a given assignment of Vars to values 26 virtual bool evaluate(std::map varVal) = 0; 27 // returns all the variables that exist in the Formula 28 virtual std::set extractvarNames() = 0; 29 virtual -Formula() = default; et une C logic.h> 27 1/ returns all the variables that exist in the rormula 28 virtual std::set Var> extractvarNames() = 0; 29 virtual -Formula( ) = default; 30 }; 31 32 // You can and together two logical formulae 33 class And : public Formula { 34 public: 35 And(std::shared_ptr lhs, std::shared_ptr varaval) override; 37 std::set extractVarNames() override; 38 39 private: 40 Il you can And together two formulae and produce a bigger Formula! 41 // lhs: left-hand side 42 std::shared_ptr lhs; 43 std::shared_ptr rhs; 44 }; 45 46 // You can Or together two logical formulae 47 class or : public Formula { 48 public: 49 Or(std::shared_ptr lhs, std::shared_ptr rhs); 50 bool evaluate(std::map var2Val) override; 51 std::set extractvarNames() override; 52 53 private: 54 std::shared_ptr lhs; 55 std::shared_ptr rhs; 56 in 1, Col1 Spaces: 2 UTF-8 LF C++ Linux ? PEL 59 62 65 C logich C logic.h>... 54 std::shared_ptrsFormula> lhs; 55 std::shared_ptrsFormulas rhs; 56 }; 57 58 // You can negate any logical formula class Not: public Formula { 60 public: 61 Not(std::shared_ptr inside); bool evaluate(std::map varaval) override; 63 std::set extractvarNames() override; 64 private: 66 std::shared_ptr inside; }; 68 69 // A single propositional variable by itself is a logical formula 70 // You can use Vars inside of bigger formulae class Var : public Formula { 72 public: Var(std::string name); 74 bool evaluate(std:: map varaval) override; 75 std::set extractvarNames() override; 76 77 bool operator. 78 friend std::ostream& operator> satsolve (Formula& f); 88 1/ Helper function for sat solve that does the heavy lifting 89 void satSolveHelper (Formulas f, std::set remainingVars, 90 std::map choicesForVars, 91 std::set<:map bool>>& satisfyingSolutions); 92 93 #endif /* LOGIC_H / 94 87 2 C logic.cpp x Glogic.cpp p>... 1 #include "logic.h" using namespace std; 3 4 // Stuff I've implemented for you (don't touch pls) And::And (shared_ptreFormula> ths, shared_ptr rhs) : lhs(ths), rhs(rhs) () set And::extractVarNames() { return lhs->extractvarNames() + rhs->extractvarNames(); } Or::Or(shared_ptr rhs) : lhs(lhs), rhs(rhs) { set Or::extractVarNames() { return lhs->extractVarNames() + rhs->extractvarNames(); } Not :: Not (shared_ptr inside) : inside (inside) {} setextractVarNames(); } Var::Var(string name) : name (name) () 24 25 set Var::extract VarNames() { return {name}; } 26 27 bool Var::operator ... DOOL var::operator var2val) { 41 return true; // fix this 42 } 43 44 // FIXME: implement Or's evaluation method 45 46 // FIXME: implement Not's evaluation method 47 48 // FIXME: implement Var's evaluation method 49 // How can you turn a variable into a boolean? 50 // (This is the base case, so no recursive calls needed here) 51 52 1/ Given a formula f, try all the possibilities for the variables, and 53 // return all the ways to make it true. 54 set> satSolve (Formula& f) { 55 set> solutions; 56 ... 58 60 61 62 63 64 65 G logic.cpp X logic.cpp).. 53 il return all the ways to make it true. 54 set> satsolve(Formula& f) { 55 set> solutions; 56 57 // FIXME: call satSolveHelper with the proper values // use the solutions variable to store every solution you find 59 return solutions; } // FIXME: implement this function to recursively find all the satisfying 1/ solutions for a Formula f. You will do this by trying both true and false fc // every variable in the formula. 66 // 67 // Explanations of the other parameters: remainingVars: the variables that you have not yet picked values for 69 choices ForVars: the variables that you have* picked values for (and // those values) 71 // satisfyingSolutions: a set of all the different variable choices 72 // (represented as a map) // that make the Formula f true. This is a reference, // so you'll extend it each time you find a new 75 // solution. 76 void satSolveHelper (Formula& f, set remainingVars, 77 map choicesForVars, set>& satisfyingSolutions) { 79 1/ Base case: There are no remaining vars. This means you've made choices // for everybody, and now it's time to see if those choices paid off. Check if f is true when evaluated using our current 68 - 70 73 74 78 80 81 T logic.cpp Clogic.cpp > 78 set>& satisfying Solutions) { 79 1/ Base case: There are no remaining vars. This means you've made choices for everybody, and now it's time to see if those choices paid // off. Check if f is true when evaluated using our current choices forvars. If it is, add our current choices ForVars to the satisfyingSolutions. // Recursive case: There is at least one Var to pick a value for. Try both true and false for it recursively. // Steps to follow in this case: // extract one Var (call it nextChoice) out of the remaing Vars // (remainingVars.begin() is a good way to get a Var out of a set) // create a new set of remaining variables, removing the one you just // chose for your next Choice variable recursively try to solve the Formula f using nextChoice set to true // recursively try to solve the Formula fusing nextChoice set to false } 95 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 B FA 4 8 CtestLogic.cpp testLogic.cpp > ... i #include 2 using namespace std; 3 #include "logic.h" 5 #include "testing.h" 6 7 void testEval(); void testSATO(); 9 void testSATI(); 10 void testSAT2(); 11 void testSAT3(); 12 13 int main() { testEval(); 15 testSATO(); 16 test SAT1(); 17 test SAT2(); testSAT3(); 19 20 return 0; 21 } 22 23 1/ helper functions to make Formulas 24 shared_ptr _And (shared_ptr lhs, shared ptr Formula rhs) { 25 return make_shared(lhs, rhs); } 27 28 shared_ptr _Or(shared_ptr lhs, shared_ptreFormulas rhs) { 29 return make_shared(lhs, rhs); 14 18 26 8 21 29 30 33 34 38 GtestLogic.cpp C testLogic.cpp .. 28 shared_ptr _Or(shared_ptr lhs, shared_ptr rhs) { return make_shared(ihs, rhs); } 31 32 shared_ptr _Not (shared_ptr inside) { return make_shared(inside); } 35 36 shared_ptr _Var(const string& s) { return make_shared(s); } 37 1/ helper function to print all the solutions our satSolve function finds 39 void printSolutions (set>& solutions) { 40 int i = 1; 41 for (auto m: solutions) { 42 cout " p = make_shared q = make_shared("q"); 59 shared_ptr r = make_shared("r"); shared_ptr not r = make_shared(r); 61 shared_ptreAnd> q_and_not_r - make_shared(q, not_r); 62 shared_ptr p_or_q_and_not_r - make_shared(p. q_and_not_r); map varzvali = {{*p, false}, {*q, true}, {*r, false}}; 65 // try evaluating the formula with p = false, q = true, and r = false assertTrue(p_or_9_and_not_r->evaluate (varavall) == true, "false || (true && 67 mapevaluate(var2Val2) == false, "false || (false & 71 72 cout > solutions - satSolve(f); 66 68 69 73 78 79 80 81 82 B testLogic.cpp testLogic.cpp). shared_ptr> solutions - satsolve(**); 80 82 92 83 printsolutions(solutions); 84 } 85 86 // pva 87 void testSATI() { 88 cout > solutions = satsolve(*f); 93 94 printSolutions (solutions); 95} 96 97 11 (p ^ (9^ -r)) v (p (- A-r)) void testSAT2() { 99 cout > solutions = satsolve(*f); 106 107 printSolutions (solutions); 108 } 98 6 testLogic.cpp testLogic.cpp >.. 104 _And(_var("P"), _And(_NOT (_var(-9")), _NOT (_var("r"))))); 105 set> solutions = satSolve(*f); 106 107 printSolutions (solutions); 108 } 109 110 11 (pv a) v (ir vs) v (t ^ -u)) 111 void testSAT3() { 112 cout f = _Or( 116 _Or(_Var("p"), Var("q")), 117 Or(_or(_Not (_Var("r")), _Var("s")), _And(_Var("t"), _Not (_Var("u"))))); 118 set> solutions = satSolve(*f); 119 120 printSolutions (solutions); 121 } 122

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Logics For Databases And Information Systems

Authors: Jan Chomicki ,Gunter Saake

1st Edition

1461375827, 978-1461375821

More Books

Students also viewed these Databases questions