Algorithms : complete 01-algorithmic_toolbox 04-dynamic_programming

5 files changed, 337 insertions, 43 deletions

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
index 0131b53..4ce529b 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
@@ -4,28 +4,128 @@
 
 using std::vector;
 
-vector<int> optimal_sequence(int n) {
-  std::vector<int> sequence;
-  while (n >= 1) {
-    sequence.push_back(n);
-    if (n % 3 == 0) {
-      n /= 3;
-    } else if (n % 2 == 0) {
-      n /= 2;
-    } else {
-      n = n - 1;
+// How to express C(n) through C(n/3), C(n/2), C(n − 1):q
+
+vector<int> optimal_sequence(int n)
+{
+    std::vector<int> sequence;
+    while (n >= 1) {
+        sequence.push_back(n);
+        if (n % 3 == 0) {
+            n /= 3;
+        } else if (n % 2 == 0) {
+            n /= 2;
+        } else {
+            n = n - 1;
+        }
     }
-  }
-  reverse(sequence.begin(), sequence.end());
-  return sequence;
+    reverse(sequence.begin(), sequence.end());
+    return sequence;
+}
+
+#define NAN std::numeric_limits<int>::max()
+
+static inline int best(int a, int b, int c)
+{
+    int r = std::numeric_limits<int>::max();
+
+    if (c != 0 && c < r)
+        r = c;
+    if (b != 0 && b < r)
+        r = b;
+    /* if (a != 0 && a < r) */
+    if (a < r)
+        r = a;
+
+    return r;
+}
+
+static inline int which(int a, int b, int c)
+{
+    int i = -1;
+    int r = std::numeric_limits<int>::max();
+
+    if (c != 0 && c < r) {
+        r = c;
+        i = 2;
+    }
+    if (b != 0 && b < r) {
+        r = b;
+        i = 1;
+    }
+    /* if (a != 0 && a < r) */
+    if (a < r)
+        i = 0;
+
+    return i;
+}
+
+vector<int> jzu(int n)
+{
+    vector<int> solution;
+
+    int N = n + 1;
+	int *add1  = new int[N];
+	int *mult2 = new int[N];
+	int *mult3 = new int[N];
+
+    add1[2] = mult2[2] = mult3[3] = 1;
+    add1[3] = 2;
+    /* std::cout << "0| " << add1[0] << " " << mult2[0] << " " << mult3[0] << std::endl; */
+    /* std::cout << "1| " << add1[1] << " " << mult2[1] << " " << mult3[1] << std::endl; */
+    /* std::cout << "2| " << add1[2] << " " << mult2[2] << " " << mult3[2] << std::endl; */
+    /* std::cout << "3| " << add1[3] << " " << mult2[3] << " " << mult3[3] << std::endl; */
+
+    int c3 = 0;
+    bool even = true;
+    for (size_t i = 4, j = 3; i < N ; i++, j++) {
+
+        add1[i] = best(add1[j], mult2[j], mult3[j]) + 1;
+
+        if (even) {
+            int k = i >> 1;
+            mult2[i] = best(add1[k], mult2[k], mult3[k]) + 1;
+        }
+
+        if (c3 == 2) {
+            int k = i / 3;
+            mult3[i] = best(add1[k], mult2[k], mult3[k]) + 1;
+            c3 = 0;
+        } else
+            c3++;
+
+        even = !even;
+        /* std::cout << i << "| " << add1[i] << " " << mult2[i] << " " << mult3[i] << std::endl; */
+    }
+
+    while (n > 1) {
+        solution.push_back(n);
+        int op = which(add1[n], mult2[n], mult3[n]);
+        if (op == 0) {
+            n--;
+        } else if (op == 1) {
+            n /= 2;
+        } else
+            n /= 3;
+    }
+    solution.push_back(1);
+
+    delete [] add1;
+    delete [] mult2;
+    delete [] mult3;
+
+    return solution;
 }
 
 int main() {
   int n;
   std::cin >> n;
-  vector<int> sequence = optimal_sequence(n);
+  /* vector<int> sequence = optimal_sequence(n); */
+  vector<int> sequence = jzu(n);
   std::cout << sequence.size() - 1 << std::endl;
-  for (size_t i = 0; i < sequence.size(); ++i) {
+  for (size_t i = sequence.size() - 1; i > 0; i--) {
     std::cout << sequence[i] << " ";
   }
+  std::cout << sequence[0] << " ";
+  std::cout << '\n';
 }
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
index c284560..5782461 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
@@ -3,15 +3,43 @@
 
 using std::vector;
 
-int optimal_weight(int W, const vector<int> &w) {
-  //write your code here
-  int current_weight = 0;
-  for (size_t i = 0; i < w.size(); ++i) {
-    if (current_weight + w[i] <= W) {
-      current_weight += w[i];
+int optimal_weight(int W, const vector<int> &w)
+{
+    int I = w.size();
+    int *m = new int[(W + 1) * (I + 1)];
+
+    int *current = &m[W + 2];
+    int *not_taken = &m[1];
+
+    // each item
+    for (int i = 1; i <= I; i++) {
+        int wi = w[i - 1];
+        for (int k = 1; k <= W; k++) {
+            if (k >= wi) {
+                int taken = *(not_taken - wi) + wi;
+                *current = ((taken > *not_taken) ? taken : *not_taken);
+            } else
+                *current = *not_taken;
+
+            current++;
+            not_taken++;
+        }
+        // skip first column
+        current++;
+        not_taken++;
     }
-  }
-  return current_weight;
+
+    /* for (int i = 0; i <= I; i++) { */
+    /*     for (int k = 0; k <= W; k++) */
+    /*         std::cout << m[(W +1) * i + k] << " "; */
+    /*     std::cout << std::endl; */
+    /* } */
+
+    int ret = *(current - 2);
+
+    delete [] m;
+
+    return ret;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp
index fd7d16e..8b124ed 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp
@@ -3,9 +3,44 @@
 
 using std::string;
 
-int edit_distance(const string &str1, const string &str2) {
-  //write your code here
-  return 0;
+int edit_distance(const string &str1, const string &str2)
+{
+    int s1 = str1.length() + 1;
+    int s2 = str2.length() + 1;
+    int *m = new int[s1 * s2];
+
+    for (int i = 0; i < s1; i++) m[i] = i;
+    for (int i = 0; i < s2; i++) m[i * s1] = i;
+
+    for (int i = 1; i < s2; i++) {
+        for (int j = 1; j < s1; j++) {
+            int insertion = m[i * s1 + j - 1] + 1;
+            int deletion = m[(i - 1 ) * s1 + j] + 1;
+            int match = m[(i - 1) * s1 + j - 1];
+            int mismatch = match + 1;
+            if (str2[i - 1] == str1[j - 1]) {
+                /* m[i, j] = ((insertion < deletion) ? */
+                m[i * s1 + j] = ((insertion < deletion) ?
+                        ((insertion < match) ? insertion : match)
+                        : ((deletion < match) ? deletion : match));
+            }
+            else {
+                m[i * s1 + j] = ((insertion < deletion) ?
+                        ((insertion < mismatch) ? insertion : mismatch)
+                        : ((deletion < mismatch) ? deletion : mismatch));
+            }
+        }
+    }
+
+    /* for (int i = 0; i < s2; i++) { */
+    /*     for (int j = 0; j < s1; j++) */
+    /*         std::cout << m[i * s1 + j] << " "; */
+    /*     std::cout << std::endl; */
+    /* } */
+
+    delete [] m;
+
+    return m[s1 * s2 - 1];
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
index 06861ab..8867a1e 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
@@ -2,27 +2,101 @@
 #include <cassert>
 #include <string>
 #include <vector>
+#include <limits>
 
 using std::vector;
 using std::string;
 using std::max;
 using std::min;
 
-long long eval(long long a, long long b, char op) {
-  if (op == '*') {
-    return a * b;
-  } else if (op == '+') {
-    return a + b;
-  } else if (op == '-') {
-    return a - b;
-  } else {
-    assert(0);
-  }
+long long eval(long long a, long long b, char op)
+{
+    if (op == '*') {
+        return a * b;
+    } else if (op == '+') {
+        return a + b;
+    } else if (op == '-') {
+        return a - b;
+    } else {
+        assert(0);
+    }
 }
 
-long long get_maximum_value(const string &exp) {
-  //write your code here
-  return 0;
+void get_min_max(int n, int x, int i, int j, const string &ops, long long *mins, long long *maxs)
+{
+    long long min = std::numeric_limits<long long>::max();
+    long long max = std::numeric_limits<long long>::min();
+
+    for (int k = i; k < j; k++) {
+        int x = i * n + k;
+        int y = (k + 1) * n + j;
+        long long a = eval(maxs[x], maxs[y], ops[k]);
+        long long b = eval(maxs[x], mins[y], ops[k]);
+        long long c = eval(mins[x], mins[y], ops[k]);
+        long long d = eval(mins[x], maxs[y], ops[k]);
+        if (a < min) min = a;
+        if (b < min) min = b;
+        if (c < min) min = c;
+        if (d < min) min = d;
+        if (a > max) max = a;
+        if (b > max) max = b;
+        if (c > max) max = c;
+        if (d > max) max = d;
+    }
+    mins[x] = min;
+    maxs[x] = max;
+}
+
+long long get_maximum_value(const string &exp)
+{
+    int n = (exp.length() + 1) / 2;
+    int nn = (n * n);
+
+    string ops;
+    long long *mins = new long long[nn];
+    long long *maxs = new long long[nn];
+
+    // collect the operators
+    for (int i = 1; i < exp.length(); i+=2)
+        ops += exp[i];
+
+    // feed both diagonals with operands
+    for (int i = 0, k = 0; i < nn; i+=(n + 1), k+=2)
+        maxs[i] = mins[i] = (exp[k] - '0');
+
+    // feed both first diagonals, result of pair
+    for (int i = 1, k = 1; i < nn; i+=(n + 1), k+=2)
+        maxs[i] = mins[i] = eval(mins[i - 1], mins[i + n], exp[k]);
+
+    for (int i = 2, k = (n - 2); i < n; i++, k-=1) {
+        for (int j = 0; j < k; j++) {
+            int x = i + j * (n + 1);
+            /* maxs[x] = mins[x] = k; */
+            /* std::cout << "[" << j <<";"<< j + i<<"]"<< std::endl; */
+            get_min_max(n, x, j, j + i, ops, mins, maxs);
+        }
+    }
+
+    /* std::cout << std::endl; */
+    /* for (int i = 0; i < nn; i+=n) { */
+    /* 	for (int j = 0; j < n; j++) */
+    /* 		std::cout << mins[i + j] << " "; */
+    /* 	std::cout << std::endl; */
+    /* } */
+    /* std::cout << std::endl; */
+    /* for (int i = 0; i < nn; i+=n) { */
+    /* 	for (int j = 0; j < n; j++) */
+    /* 		std::cout << maxs[i + j] << " "; */
+    /* 	std::cout << std::endl; */
+    /* } */
+    /* std::cout << std::endl; */
+
+    long long ret = maxs[n - 1];
+
+    delete [] mins;
+    delete [] maxs;
+
+    return ret;
 }
 
 int main() {
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
index 2ca0339..473830f 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
@@ -1,11 +1,68 @@
 #include <iostream>
 #include <vector>
 
-using std::vector;
+using namespace std;
 
-int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) {
-  //write your code here
-  return std::min(std::min(a.size(), b.size()), c.size());
+static inline int max(int a, int b, int c) {
+    if (a > b)
+        return (a > c ? a : c);
+    return (b > c ? b : c);
+}
+
+static inline int max(int a, int b, int c, int d, int e, int f, int g) {
+    int abc = max(a, b, c);
+    int def = max(d, e, f);
+    return max(abc, def, g);
+}
+
+int lcs3(vector<int> &a, vector<int> &b, vector<int> &c)
+{
+    vector<vector<vector<int> > > cost(a.size() + 1,
+            vector<vector<int> >(b.size() + 1,
+                vector<int>(c.size() + 1, 0)));
+
+    int max_cost;;
+    for (int k = 1; k <= c.size(); k++) {
+        for (int j = 1; j <= b.size(); j++) {
+            for (int i = 1; i <= a.size(); i++) {
+                int c1 = cost[i - 1][j - 1][k - 1];     // -1 ; -1 ; -1
+                int c2 = cost[i - 1][j - 1][k];         // -1 ; -1 ;  0
+                int c3 = cost[i - 1][j][k - 1];         // -1 ;  0 ; -1
+
+                int c4 = cost[i][j - 1][k - 1];         //  0 ; -1 ; -1
+                int c5 = cost[i - 1][j][k];             // -1 ;  0 ;  0
+                int c6 = cost[i][j - 1][k];             //  0 ; -1 ;  0
+                int c7 = cost[i][j][k - 1];             //  0 ;  0 ; -1
+
+                // (-1 ; -1 ; -1) + 1
+                int c8_match = cost[i - 1][j - 1][k - 1] + 1;
+
+                if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1]) {
+#if DEBUG
+                    cout << "match " << a[i - 1] << " at (i, j, k) = " << i << "," << j << "," << k << endl;
+#endif
+                    max_cost = max(c8_match, c2, c3, c4, c5, c6, c7);
+                } else {
+                    max_cost = max(c1, c2, c3, c4, c5, c6, c7);
+                }
+                cost[i][j][k] = max_cost;
+            }
+        }
+    }
+
+#if DEBUG
+    for (int k = 0; k <= c.size(); k++) {
+        cout << "======== k = " << k << " =========" << endl;
+        for (int j = 0; j <= b.size(); j++) {
+            for (int i = 0; i <= a.size(); i++) {
+                cout << cost[i][j][k] << " ";
+            }
+            cout << endl;
+        }
+    }
+#endif
+
+    return cost[a.size()][b.size()][c.size()];
 }
 
 int main() {