Summary: Discover the way computers work mathematically.
- ReadySetBoole.hpp, ReadySetBoole.cpp
- RPNtree.hpp, RPNtree.cpp
For the project structure, there are two classes called RSB, RPNNode. The first is a class that contains all the methods of the exercises and the second is a class to do the parsing and check the syntax of the propositional formula.
- exercise.hpp, exercise.cpp
- main.cpp
Then, there are two files exercise.cpp, exercise.hpp to perform the exercises with main.cpp
Exercise 00 - Adder
Exercise 01 - Multiplier
Exercise 02 - Gray code
Exercise 03 - Boolean evaluation
Exercise 04 - Truth table
Exercise 05 - Negation Normal Form
Exercise 06 - Conjunctive Normal Form
Exercise 07 - SAT
Exercise 08 - Powerset
Exercise 09 - Set evaluation
Exercise 10, 11 - Curve, Inverse function
Exercise 00 - Adder |
---|
Allowed mathematical functions : None |
Maximum time complexity : O(1) |
Maximum space complexity : O(1) |
unsigned int RSB::adder(unsigned int a, unsigned int b)
{
unsigned int carry = 0;
while (b != 0)
{
carry = a & b;
a = a ^ b;
b = carry << 1;
}
return (a);
};
- It takes two unsigned integer parameters
a
andb
. - It initializes a
carry
variable to 0 to store the carry. - It enters a
while
loop untilb
is equal to 0. - On each iteration of the loop, it does the following:
- It performs a logical AND between
a
andb
to get the carry value. - It performs a XOR between
a
andb
to get the sum without carry. - It shifts the value of
carry
one position to the left by adding a leading zero. - It reassigns the value of
a
to the obtained sum and the value ofb
to carry.
- It performs a logical AND between
- Once the value of
b
is equal to 0, the loop ends and the function returns the final value ofa
which is the sum of the two numbers.
The complexity of this function is O(1), which means that the execution time doesn't depend on the size of the numbers a
and b
. No matter the size of the numbers, the number of iterations of the loop remains constant.
Exercise 01 - Multiplier |
---|
Allowed mathematical functions : None |
Maximum time complexity : O(1) |
Maximum space complexity : O(1) |
unsigned int RSB::multiplier(unsigned int a, unsigned int b)
{
unsigned int result = 0;
while (b != 0)
{
// check the least significant bit of b
if (b & 1)
result = adder(result, a);
a <<= 1;
b >>= 1;
}
return (result);
};
- It takes two unsigned integer parameters
a
andb
. - It initializes a
result
variable to 0 to store the result of the multiplication. - It enters a
while
loop untilb
is equal to 0. - On each iteration of the loop, it does the following:
- It checks the least significant bit of
b
using a logical AND with 1. - If the bit is equal to 1, it calls the
adder
function to add the value ofa
toresult
. - It shifts the value of
a
one position to the left by adding a leading zero. - It shifts the value of
b
one position to the right, losing the least significant bit.
- It checks the least significant bit of
- Once the value of
b
is equal to 0, the loop ends and the function returns the final value ofresult
, which is the product of the two numbers.
The complexity of this function is O(1), because the number of iterations of the while
loop depends on the number of bits of b
that remains constant regardless of the size of the numbers a
and b
.
Exercise 02 - Gray code |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : N/A |
unsigned int RSB::grayCode(unsigned int n)
{
// perform XOR operation between n and n shifted right by 1 bit
return (n ^ (n >> 1));
};
- It takes one unsigned integer parameter
n
. - It performs a XOR between
n
and the result of then
shifted right by 1 bit (n >> 1). - The result of XOR is returned as the Gray code corresponding to
n
.
Gray code is a binary number system in which two adjacent numbers differ by only one bit.
Gray code is used in a variety of fields, including electronics, telecommunications, and information theory. It is used to avoid switching errors when switching one binary number to another adjacent binary number.
// une image d'un example du code Gray
Exercise 03 - Boolean evaluation |
---|
Allowed mathematical functions : None |
Maximum time complexity : O(n) |
Maximum space complexity : N/A |
bool RSB::evalFormula(const std::string& formula)
{
std::stack<bool> eval_stack;
if (!checkFormula(formula, false, false))
return false;
for (char c: formula)
{
if (std::isdigit(c))
{
bool value = c == '1';
eval_stack.push(value);
}
else if (c == '!')
{
bool operand = eval_stack.top();
eval_stack.pop();
eval_stack.push(!operand);
}
else if (c == '&' || c == '|' || c == '^' || c == '>' || c == '=')
{
bool operand2 = eval_stack.top();
eval_stack.pop();
bool operand1 = eval_stack.top();
eval_stack.pop();
bool result = evalOperator(c, operand1, operand2);
eval_stack.push(result);
}
else
runtimeException("Invalid symbol");
}
return eval_stack.top();
};
The evalOperator
function evaluates an operation between two operands and returns the result. It takes three parameters: the operator (op) and the two operands (operand1, operand2).
The evalFormula
function evaluates the boolean formula represented by a character string. It uses a stack to evaluate operations and operands.
- It first checks the validity of the formula by calling
checkFormula
function from theRPNtree.cpp
file with theformula
parameter. If the formula isn't valid, the function returnsfalse
. - Then, it loops through each character in the formula using a
for
loop. - If the character is a digit (0 or 1), it creates a boolean
value
based on the value of the digit and pushes it into theeval_stack
stack. - If the character is
!
, it retrieves the operand from the top of the stack, pops it off the stack, performs the negation, and pushes the result into the stack. - If the character is one of the operators
&
,|
,^
,>
ou=
, it retrieves the top two operands from the stack, pops them off the stack, calls theevalOperator
function with the operator and the operands and pushes the result into the stack. - If the character isn't none of the valid digits or operators, an "Invalid symbol" exception is thrown.
- After looping through all the characters of the formula, the function returns the final result which is at the top of the
eval_stack
stack.
The complexity of this function depends on the length of the formula (n), so it is O(n).
Exercise 04 - Truth table |
---|
Allowed mathematical functions : None |
Maximum time complexity : O(2^n) |
Maximum space complexity : N/A |
void RSB::printTruthTable(const std::string& formula, bool ordered)
{
std::vector<std::pair<char, size_t> > variables;
std::string temp_formula;
size_t variable_count = 0;
size_t rows = 0;
if (!checkFormula(formula, true, false))
return ;
variables = getVariables(formula, ordered);
variable_count = std::max_element(variables.begin(), variables.end(),
[](const std::pair<char, size_t>& lhs, const std::pair<char, size_t>& rhs) {
return lhs.second < rhs.second;
})->second;
// print column headers
std::cout << "| ";
for (size_t i = 0; i <= variable_count - 1; ++i)
std::cout << variables[i].first << " | ";
std::cout << "= |\n";
for (size_t i = 0; i <= variable_count; ++i)
std::cout << "|---";
std::cout << "|\n";
rows = 1 << variable_count;
for (size_t i = 0; i < rows; ++i)
{
std::cout << "| ";
temp_formula = formula;
for (int j = variables.size() - 1; j >= 0; --j)
{
size_t value = (i >> (variables[j].second - 1)) & 1;
std::cout << value << " | ";
std::replace(temp_formula.begin(), temp_formula.end(), variables[j].first, (char)(value + '0'));
}
std::cout << evalFormula(temp_formula) << " |\n";
}
};
The getVariables
function retrieves the variables present in a given boolean formula. it returns a vector of pairs where each pair represents a variable and its order number.
The printTruthTable
function prints the truth table of a given boolean formula.
- It initializes the local variables:
variables
to store the variables present in the formula,temp_formula
to create a temporary copy of the formula,variable_count
to determine the number of variables,rows
for the total number of rows in the truth table. - It first checks the validity of the formula by calling the
checkFormula
function with theformula
parameter. If the formula isn't valid, the function returns. - It calls the
getVariables
function to get the variables of the formula, specifying whether they should be sorted or not. - It determines the value of
variable_count
usingstd::max_element
function on thevariables
vector. - it prints the column headers and a separator line.
- It calculates the total number of rows in the truth table using the binary shift operator (
<<
). - It iterates over each row of the truth table.
- for each row, it prints the variables values by iterating over the variables and using the binary shift operator (
>>
) and the mask (1
) to extract each bit from the variable value. - It replaces the occurrences of the variables in the temporary formula
temp_formula
with the corresponding values (0 or 1) usingstd::replace
function. - It evaluates the temporary formula by calling
evalFormula
function with the modified formula. - It prints the value resulting from the evaluation of the formula.
- for each row, it prints the variables values by iterating over the variables and using the binary shift operator (
The complexity of this function depends on the number of the distinct variables present in the formula because the number of rows in the truth table is n
is the number of distinct variables. Therefore, the complexity of this function is
Exercise 05 - Negation Normal Form |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : N/A |
const std::string RSB::negationNormalForm(const std::string& formula)
{
std::stack<std::string> stack;
std::string temp, temp2, temp_formula;
if (!checkFormula(formula, true, false))
return formula;
temp_formula = rewriteFormula(formula);
for (char c : temp_formula)
{
if (isalpha(c))
stack.push(std::string(1, c));
else if (c == '!')
{
if (!stack.empty())
{
temp = stack.top(); stack.pop();
temp2 = applyNegation(temp);
stack.push(temp2);
}
}
else if (c == '&' || c == '|')
{
temp = stack.top(); stack.pop();
temp2 = stack.top(); stack.pop();
stack.push(temp2 + temp + c);
}
else
runtimeException("Invalid symbol", std::string(1, c));
}
return stack.top();
};
The applyNegation
is used to apply the negation to a variable or to a subformula in a boolean formula.
The rewriteFormula
function is used to simplify a boolean formula using simplification rules.
The negationNormalForm
is used to convert a boolean formula to Negation Normal Form (NNF) using applyNegation
and rewriteFormula
functions.
- It uses a stack to store the intermediate subformulas.
- It simplifies the original formula by calling the
rewriteFormula
function with the formula. - It loops through each character of the simplified formula using a
for
loop. - If the character is a letter (a variable), it simply pushes it into the stack.
- If the character is
!
, it applies the negation to the last subformula on the stack usingapplyNegation
function and then pushes the resulting subformula into the stack. - If the character is
&
or|
, it retrieves the last two subformulas from the stack, pops them off the stack, then pushes a new resulting subformula into the stack using the character as an operator. - If the character isn't a
!
,&
or|
letter, an "Invalid symbol" exception is thrown. - After all the characters in the formula have been processed, the function returns the final subformula which is at the top of the stack.
Exercise 06 - Conjunctive Normal Form |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : N/A |
const std::string RSB::conjunctiveNormalForm(const std::string& formula)
{
std::unique_ptr<RPNNode> cnf;
std::string temp_formula;
std::string result;
if (!checkFormula(formula, true, false))
return formula;
temp_formula = negationNormalForm(formula);
temp_formula = rearrangeOnlyAndOr(temp_formula);
cnf = buildTree(temp_formula);
if (checkAndBeforeOr(temp_formula))
cnf = applyDistributiveLaw(cnf);
cnf = rearrangeConjunctions(cnf);
result = preorder(cnf);
return result;
};
The rearrangeOnlyAndOr
function checks if the formula contains only conjunction(&
) or disjunction(|
) operators. If it so, it rearranges the modified formula by moving all the operators to the end of the formula, otherwise, it returns the origin formula.
The checkAndBeforeOr
function checks if the conjunction operator appears before the disjunction operator in the formula. If so, it returns true
, otherwise it returns false
.
The applyDistributiveLaw
and rearrangeConjunctions
functions are used to manipulate a tree structure representing a formula in Reverse Polish Notation (RPN). applyDistributiveLaw
applies the distributive law to the formula tree. rearrangeConjunctions
allows to rearrange the conjunctions in the formula tree.
The conjunctiveNormalForm
function is used to convert a boolean formula to Conjunctive Normal From (CNF).
- It first checks the validity of the formula by calling the
checkFormula
function with the formula. If the formula is not valid, the function returns the origin formula. - It applies the Negation Normal From (NNF) to the formula by calling the
negationNormalForm
function. - It rearranges the conjunction and disjunction operators by calling the
rearrangeOnlyAndOr
function. - It checks if the conjunction operator appears before the disjunction operator by calling the
checkAndBeforeOr
function. If so, the function applies the distributive law by calling theapplyDistributiveLaw
function. - It rearranges the conjunctions in the syntax tree by calling the
rearrangeConjunctions
function. - It retrieves the resulting formula by traversing the syntax tree in prefix order using the
preorder
function. - It returns the resulting formula.
Exercise 07 - SAT |
---|
Allowed mathematical functions : None |
Maximum time complexity : O(2^n) |
Maximum space complexity : N/A |
bool RSB::sat(const std::string& formula)
{
std::vector<std::pair<char, size_t> > variables;
std::string temp_formula = formula;
size_t variable_count = 0;
size_t rows = 0;
if (!checkFormula(formula, true, false))
return false;
variables = getVariables(formula, false);
variable_count = std::max_element(variables.begin(), variables.end(),
[](const std::pair<char, size_t>& lhs, const std::pair<char, size_t>& rhs) {
return lhs.second < rhs.second;
})->second;
rows = 1 << variable_count;
for (size_t i = 0; i < rows; ++i)
{
temp_formula = formula;
for (const auto& variable : variables)
{
size_t m_value = (i >> (variable.second - 1)) & 1;
std::replace(temp_formula.begin(), temp_formula.end(), variable.first, (char)(m_value + '0'));
}
if (evalFormula(temp_formula))
return true;
}
return false;
};
The getVariables
function retrieves the variables present in a given boolean formula. it returns a vector of pairs where each pair represents a variable and its order number.
The evalFormula
function evaluates the boolean formula represented by a character string. it uses a stack to evaluate operators and operands.
The sat
function is used to check if a given logic formula is satisfiable, which means if there exists an assignment of values to the variables of the formula that makes the formula true.
- It starts by checking if the formula is valid by calling the
checkFormula
function, if the formula isn't valid, it returnsfalse
because it can't be satisfiable. - It uses the
getVariables
function to get the distinct variables present in the formula. - It determines the number of rows needed to generate the possible combinations of values for the variables.
- It iterates through each possible row of values for the variables.
- for each row, it creates a temporary copy of the initial formula.
- for each row, it retrieves the values of the variables by iterating over the variables and using the binary shift operator (
>>
) and the mask (1
) to extract each bit from the value of the variable. - It replaces the occurrences of the variables in the temporary formula
temp_formula
with the corresponding values (0 or 1) using thestd::replace
function. - It evaluates the temporary formula by calling the
evalFormula
function with the modified formula. - If the temporary formula is evaluated as true, it means that the initial formula is satisfiable, and the function returns
true
.
- If no combination of values satisfies the formula, the function returns
false
.
The complexity of this function depends on the number of variables in the formula. the total number of rows generated is 2^n, where n
is the number of distinct variables. For each row, the function performs a replace operation in the temporary formula and evaluates the modified formula by calling the evalFormula
function. Therefore, the complexity of this function is n
is the number of distinct variables.
Exercise 08 - Powerset |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : O(2^n) |
static void generatePowerset(const t_set& set, t_set& current_set, int index, t_powerset& powerset)
{
powerset.push_back(current_set);
for (size_t i = index; i < set.size(); ++i)
{
current_set.push_back(set[i]);
generatePowerset(set, current_set, i + 1, powerset);
current_set.pop_back();
}
};
t_powerset RSB::powerset(t_set& set)
{
t_powerset powerset;
t_set current_set;
generatePowerset(set, current_set, 0, powerset);
return powerset;
};
The generatePowerset
and powerset
functions are used to generate the powerset (set of subsets) from a given set.
generatePowerset
is a recursive function that takes as input aset
set, acurrent_set
set (which contains the current elements of the subset being generated), anindex
(to tract the current position during generation), apowerset
(which will contain all generated subsets).- It starts by adding the
current_set
to the powerset, because it is a valid subset. - Then, it iterates through the elements of the set
set
starting at the given index. - For each element from the index, it adds it to the set
current_set
, then it recursively calls thegeneratePowerset
function by incrementing the index by 1. This generates the subsets containing this element. - After the recursive call, it removes the last element added to
current_set
using thepop_back
function. This makes it possible to return to the previous state and to generate the subsets without this element. - The function terminates when all the elements of the
set
set have been traversed. - The final powerset is returned.
The complexity of this function is n
is the size of the given set. This is because the powerset contains 2^n distinct subsets, and each subset is generated once.
Exercise 09 - Set evaluation |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : N/A |
t_set RSB::evalSet(const std::string& formula, const t_powerset& sets)
{
std::stack<t_set> stack;
std::vector<char> variables;
std::string temp_formula;
t_set universal_set;
size_t variable_count = 0;
for (const t_set& set : sets)
{
for (int element : set)
{
if (std::find(universal_set.begin(), universal_set.end(), element) == universal_set.end())
universal_set.push_back(element);
}
}
temp_formula = negationNormalForm(formula);
for (char c : temp_formula)
{
if (isalpha(c))
{
bool exist = false;
for (size_t j = 0; j < variables.size(); ++j)
{
if (variables[j] == c)
{
exist = true;
stack.push(sets[j]);
break;
}
}
if (!exist)
{
stack.push(sets[variable_count]);
variables.emplace_back(c);
variable_count++;
}
}
else if (c == '!') // Negation
{
t_set operand = stack.top(); stack.pop();
t_set result;
for (int element : universal_set)
{
if (std::find(operand.begin(), operand.end(), element) == operand.end())
result.push_back(element);
}
stack.push(result);
}
else if (c == '&' || c == '|' || c == '^' || c == '=' || c == '>')
{
t_set operand2 = stack.top(); stack.pop();
t_set operand1 = stack.top(); stack.pop();
t_set result;
if (c == '&') // Intersection
{
std::unordered_map<int, bool> set1_elements;
for (int element : operand1)
set1_elements[element] = true;
for (int element : operand2)
{
if (set1_elements[element])
result.push_back(element);
}
}
else if (c == '|') // Union
{
result = operand1;
for (int element : operand2)
{
if (std::find(result.begin(), result.end(), element) == result.end())
result.push_back(element);
}
}
else if (c == '^') // Symmetric difference
{
std::unordered_map<int, bool> set1_elements;
std::unordered_map<int, bool> set2_elements;
for (int element : operand1)
set1_elements[element] = true;
for (int element : operand2)
{
if (!set1_elements[element])
result.push_back(element);
}
for (int element : operand2)
set2_elements[element] = true;
for (int element : operand1)
{
if (!set2_elements[element])
result.push_back(element);
}
}
stack.push(result);
}
}
return stack.top();
};
The evalSet
function is used to evaluate a logic formula with sets.
- It creates a stack to store the temporary sets generated while evaluating the formula.
- It creates a
variables
vector to store the distinct variables present in the formula. - It creates a universal set
universal_set
which contains all the elements present in the setpowerset
. It is necessary for handling the negation operation. - It converts the formula to Negation Normal Form (NNF) by calling the
negationNormalForm
function. - It iterates over each character of the converted formula:
- If the character is a letter (variable), it checks if the variable has already been encountered. If so, it retrieves the corresponding set in the
sets
powerset, and pushes it into the stack. Otherwise, it creates a new variable, retrieves the corresponding set from thesets
powerset and pushes it into the stack, while adding the variable to thevariables
vector. - If the character is a negation operation
!
, it retrieves the set which is located on top of the stack, performs the negation using the universal set, and pushes the result into the stack. - If the character is an operation (
&
,|
,^
,=
,>
), it retrieves the top two sets from the stack, performs the corresponding operation, and pushes the result into the stack.
- If the character is a letter (variable), it checks if the variable has already been encountered. If so, it retrieves the corresponding set in the
- At the end of the iteration, the resulting set is located on top of the stack and it is returned.
Exercise 10, 11 - Curve, Inverse function |
---|
Allowed mathematical functions : None |
Maximum time complexity : N/A |
Maximum space complexity : N/A |
#define MAX_VALUE ((1ULL << 32) - 1)
double RSB::map(unsigned short x, unsigned short y)
{
// combine x and y into a 64-bit value
unsigned long long value = (static_cast<unsigned long long>(x) << 16) | y;
// map the value to the range [0; 1]
double result = static_cast<double>(value) / MAX_VALUE;
return result;
};
t_vec2s RSB::reverseMap(double n)
{
// reverse normalize the value
unsigned long long value = static_cast<unsigned long long>(n * MAX_VALUE);
// extract the x coordinate
unsigned short x = static_cast<unsigned short>(value >> 16);
// extract the y coordinate
unsigned short y = static_cast<unsigned short>(value & 0xFFFF);
t_vec2s result;
result.x = x;
result.y = y;
return result;
};
The map
function is used to map two unsigned integer values (x
and y
) into a real value in the range [0, 1].
- It combines the values
x
andy
into a 64-bit integer value using a bit shift and a OR logic. - Then, it converts this integer value into a double and divides it by the constant
MAX_VALUE
to get a real value in the range [0, 1]. - The real value is returned.
The reverseMap
function performs the reverse operation of the map
function.
- It takes as input a real value in the range [0, 1]/
- The value first is multiplied by the constant
MAX_VALUE
to get a 64-bit integer value. - Then, this integer value is used to extract the
x
andy
values using the bit shift and masking operations. - The
x
andy
values are stored in at_vec2s
structure and returned.