From bc75b20fc0e80d6037ee14e3dccc2d88823f5f2f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 21:18:32 +0100
Subject: Algorithms : add 01-algorithmic_toolbox 04-dynamic_programming

---
 .../00_dynamic_programming.pdf                     | Bin 0 -> 331902 bytes
 .../primitive_calculator.cpp                       |  31 +++++++++++++++++
 .../01-primitive_calculator/tests/01               |   1 +
 .../01-primitive_calculator/tests/01.a             |   2 ++
 .../01-primitive_calculator/tests/02               |   1 +
 .../01-primitive_calculator/tests/02.a             |   2 ++
 .../01-primitive_calculator/tests/03               |   1 +
 .../01-primitive_calculator/tests/03.a             |   2 ++
 .../02-knapsack/knapsack.cpp                       |  25 ++++++++++++++
 .../04-dynamic_programming/02-knapsack/tests/01    |   2 ++
 .../04-dynamic_programming/02-knapsack/tests/01.a  |   1 +
 .../03-edit_distance/edit_distance.cpp             |  17 +++++++++
 .../03-edit_distance/tests/01                      |   2 ++
 .../03-edit_distance/tests/01.a                    |   1 +
 .../03-edit_distance/tests/02                      |   2 ++
 .../03-edit_distance/tests/02.a                    |   1 +
 .../03-edit_distance/tests/03                      |   2 ++
 .../03-edit_distance/tests/03.a                    |   1 +
 .../04-placing_parentheses/placing_parentheses.cpp |  32 +++++++++++++++++
 .../04-placing_parentheses/tests/01                |   1 +
 .../04-placing_parentheses/tests/01.a              |   1 +
 .../04-placing_parentheses/tests/02                |   1 +
 .../04-placing_parentheses/tests/02.a              |   1 +
 .../04-dynamic_programming/05-lcs3/lcs3.cpp        |  31 +++++++++++++++++
 .../04-dynamic_programming/05-lcs3/tests/01        |   6 ++++
 .../04-dynamic_programming/05-lcs3/tests/01.a      |   1 +
 .../04-dynamic_programming/05-lcs3/tests/02        |   6 ++++
 .../04-dynamic_programming/05-lcs3/tests/02.a      |   1 +
 .../04-dynamic_programming/check                   |  38 +++++++++++++++++++++
 29 files changed, 213 insertions(+)
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a
 create mode 100755 01-algorithmic_toolbox/04-dynamic_programming/check

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf b/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf
new file mode 100644
index 0000000..51f84fa
Binary files /dev/null and b/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf differ
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
new file mode 100644
index 0000000..0131b53
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
@@ -0,0 +1,31 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+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;
+    }
+  }
+  reverse(sequence.begin(), sequence.end());
+  return sequence;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> sequence = optimal_sequence(n);
+  std::cout << sequence.size() - 1 << std::endl;
+  for (size_t i = 0; i < sequence.size(); ++i) {
+    std::cout << sequence[i] << " ";
+  }
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
@@ -0,0 +1 @@
+1
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
new file mode 100644
index 0000000..2734518
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
@@ -0,0 +1,2 @@
+0
+1 
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
@@ -0,0 +1 @@
+5
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
new file mode 100644
index 0000000..fc544c9
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
@@ -0,0 +1,2 @@
+3
+1 2 4 5 
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
new file mode 100644
index 0000000..c18d157
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
@@ -0,0 +1 @@
+96234
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a
new file mode 100644
index 0000000..55a1c62
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a
@@ -0,0 +1,2 @@
+14
+1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
new file mode 100644
index 0000000..c284560
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <vector>
+
+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];
+    }
+  }
+  return current_weight;
+}
+
+int main() {
+  int n, W;
+  std::cin >> W >> n;
+  vector<int> w(n);
+  for (int i = 0; i < n; i++) {
+    std::cin >> w[i];
+  }
+  std::cout << optimal_weight(W, w) << '\n';
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01
new file mode 100644
index 0000000..3fa3706
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01
@@ -0,0 +1,2 @@
+10 3
+1 4 8
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a
new file mode 100644
index 0000000..ec63514
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a
@@ -0,0 +1 @@
+9
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
new file mode 100644
index 0000000..fd7d16e
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+#include <string>
+
+using std::string;
+
+int edit_distance(const string &str1, const string &str2) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+  string str1;
+  string str2;
+  std::cin >> str1 >> str2;
+  std::cout << edit_distance(str1, str2) << std::endl;
+  return 0;
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01
new file mode 100644
index 0000000..367ac87
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01
@@ -0,0 +1,2 @@
+ab
+ab
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a
new file mode 100644
index 0000000..573541a
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a
@@ -0,0 +1 @@
+0
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02
new file mode 100644
index 0000000..3ef52c8
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02
@@ -0,0 +1,2 @@
+short
+ports
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a
new file mode 100644
index 0000000..00750ed
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a
@@ -0,0 +1 @@
+3
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03
new file mode 100644
index 0000000..cc5b276
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03
@@ -0,0 +1,2 @@
+editing
+distance
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a
@@ -0,0 +1 @@
+5
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
new file mode 100644
index 0000000..06861ab
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+#include <cassert>
+#include <string>
+#include <vector>
+
+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 get_maximum_value(const string &exp) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+  string s;
+  std::cin >> s;
+  std::cout << get_maximum_value(s) << '\n';
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01
new file mode 100644
index 0000000..cea3f71
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01
@@ -0,0 +1 @@
+1+5
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a
new file mode 100644
index 0000000..1e8b314
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a
@@ -0,0 +1 @@
+6
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02
new file mode 100644
index 0000000..92a372d
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02
@@ -0,0 +1 @@
+5-8+7*4-8+9
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a
new file mode 100644
index 0000000..08839f6
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a
@@ -0,0 +1 @@
+200
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
new file mode 100644
index 0000000..2ca0339
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
@@ -0,0 +1,31 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+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());
+}
+
+int main() {
+  size_t an;
+  std::cin >> an;
+  vector<int> a(an);
+  for (size_t i = 0; i < an; i++) {
+    std::cin >> a[i];
+  }
+  size_t bn;
+  std::cin >> bn;
+  vector<int> b(bn);
+  for (size_t i = 0; i < bn; i++) {
+    std::cin >> b[i];
+  }
+  size_t cn;
+  std::cin >> cn;
+  vector<int> c(cn);
+  for (size_t i = 0; i < cn; i++) {
+    std::cin >> c[i];
+  }
+  std::cout << lcs3(a, b, c) << std::endl;
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01
new file mode 100644
index 0000000..354d6f0
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01
@@ -0,0 +1,6 @@
+3
+1 2 3
+3
+2 1 3
+3
+1 3 5
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a
@@ -0,0 +1 @@
+2
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02
new file mode 100644
index 0000000..3969ebb
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02
@@ -0,0 +1,6 @@
+5
+8 3 2 1 7
+7
+8 2 1 3 8 10 7
+6
+6 8 3 1 4 7
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a
new file mode 100644
index 0000000..00750ed
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a
@@ -0,0 +1 @@
+3
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/check b/01-algorithmic_toolbox/04-dynamic_programming/check
new file mode 100755
index 0000000..8bdb3d4
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+BLACK="\033[0;30m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
-- 
cgit v1.1-2-g2b99