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