import(life): Add algorithm experiment 3.

6 files changed, 158 insertions, 0 deletions

diff --git a/works/life/.DS_Store b/works/life/.DS_Store
index 0c5479b..c4a5fe2 100644
--- a/works/life/.DS_Store
+++ b/works/life/.DS_Store
diff --git a/works/life/algorithm-experiment/.DS_Store b/works/life/algorithm-experiment/.DS_Store
new file mode 100644
index 0000000..58e50b9
--- /dev/null
+++ b/works/life/algorithm-experiment/.DS_Store
diff --git a/works/life/algorithm-experiment/.gitignore b/works/life/algorithm-experiment/.gitignore
new file mode 100644
index 0000000..0acb85f
--- /dev/null
+++ b/works/life/algorithm-experiment/.gitignore
@@ -0,0 +1,4 @@
+build
+.cache
+*.in
+*.out
\ No newline at end of file
diff --git a/works/life/algorithm-experiment/3.1.cpp b/works/life/algorithm-experiment/3.1.cpp
new file mode 100644
index 0000000..1796dc3
--- /dev/null
+++ b/works/life/algorithm-experiment/3.1.cpp
@@ -0,0 +1,38 @@
+#include <dlib/optimization/max_cost_assignment.h>
+#include <iostream>
+#include <vector>
+
+#include <dlib/optimization.h>
+
+int main() {
+  int n;
+  std::cin >> n;
+
+  dlib::matrix<int> matrix(n, n);
+
+  for (int i = 0; i < n; i++) {
+    for (int j = 0; j < n; j++) {
+      int l;
+      std::cin >> l;
+      matrix(i, j) = -l;
+    }
+  }
+
+  auto result = dlib::max_cost_assignment(matrix);
+
+  for (auto i : result) {
+    std::cout << i << ' ';
+  }
+
+  std::cout << '\n';
+
+  int sum = 0;
+
+  for (int i = 0; i < n; i++) {
+    sum += matrix(i, result[i]);
+  }
+
+  std::cout << sum;
+
+  return 0;
+}
diff --git a/works/life/algorithm-experiment/3.2.cpp b/works/life/algorithm-experiment/3.2.cpp
new file mode 100644
index 0000000..e4b8428
--- /dev/null
+++ b/works/life/algorithm-experiment/3.2.cpp
@@ -0,0 +1,100 @@
+#include <dlib/string.h>
+#include <dlib/string/string.h>
+#include <iostream>
+#include <istream>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+
+std::map<std::string, std::vector<std::string>> graph;
+std::map<std::string, std::vector<std::string>> reverse_graph;
+
+int max_depth;
+std::string conflict;
+std::string conflict_parent;
+
+std::vector<std::string> list;
+
+void DFS(const std::string &current) {
+  for (auto i = list.cbegin(); i != list.cend(); ++i) {
+    if (*i == current) {
+      conflict_parent = current;
+      conflict = list.back();
+      return;
+    }
+  }
+
+  list.push_back(current);
+
+  if (list.size() > max_depth) {
+    max_depth = list.size();
+  }
+
+  if (list.size() == 18) {
+    for (const auto &s : list) {
+      std::cout << s << "->";
+    }
+    std::cout << "The End!!!" << std::endl;
+  }
+
+  for (const auto &s : graph[current]) {
+    DFS(s);
+  }
+
+  list.pop_back();
+}
+
+void DFS() {
+  for (const auto &[k, v] : reverse_graph) {
+    if (v.empty()) {
+      list.clear();
+      DFS(k);
+    }
+  }
+}
+
+std::vector<std::string> SplitBySpace(const std::string &s) {
+  std::vector<std::string> result;
+  int current_pos = 0;
+
+  while (true) {
+    auto p = s.find_first_of(" ", current_pos);
+    if (p == std::string::npos) {
+      result.push_back(std::string(s.cbegin() + current_pos, s.cend()));
+      break;
+    } else {
+      result.push_back(std::string(s.cbegin() + current_pos, s.cbegin() + p));
+      current_pos = p + 1;
+    }
+  }
+
+  return result;
+}
+
+int main() {
+  std::string s;
+  while (std::getline(std::cin, s)) {
+    auto result = SplitBySpace(s);
+
+    std::string parent = result.front();
+
+    graph[parent];
+    reverse_graph[parent];
+
+    for (auto i = result.cbegin() + 1; i != result.cend(); i++) {
+      graph[parent].push_back(*i);
+      reverse_graph[*i].push_back(parent);
+    }
+  }
+
+  std::cout << "We have " << graph.size() << " items.\n";
+  std::cout << "We have " << reverse_graph.size() << " parent items.\n";
+
+  DFS();
+
+  std::cout << conflict << "->" << conflict_parent << '\n';
+  std::cout << "Max depth: " << max_depth << '\n';
+
+  return 0;
+}
diff --git a/works/life/algorithm-experiment/CMakeLists.txt b/works/life/algorithm-experiment/CMakeLists.txt
new file mode 100644
index 0000000..8f7c4d5
--- /dev/null
+++ b/works/life/algorithm-experiment/CMakeLists.txt
@@ -0,0 +1,16 @@
+cmake_minimum_required(VERSION 3.21)
+
+set(CMAKE_TOOLCHAIN_FILE $ENV{VCPKG_INSTALLATION_ROOT}/scripts/buildsystems/vcpkg.cmake
+  CACHE STRING "Vcpkg toolchain file")
+
+set(CMAKE_CXX_STANDARD 20)
+
+project(cru-algorithm-experiment)
+
+find_package(dlib CONFIG REQUIRED)
+
+add_executable(3.1 3.1.cpp)
+target_link_libraries(3.1 PRIVATE dlib::dlib)
+
+add_executable(3.2 3.2.cpp)
+target_link_libraries(3.2 PRIVATE dlib::dlib)