--- a/dynprog.cc	Sun Mar 12 22:48:09 2023 +0100
+++ b/dynprog.cc	Sun Mar 12 22:50:42 2023 +0100
@@ -1,11 +1,11 @@
 
 #include "lib/exec.h"
 
+#include <functional>
 #include <iostream>
-#include <functional>
 #include <ranges>
+#include <sstream>
 #include <string>
-#include <sstream>
 #include <tuple>
 #include <unordered_map>
 #include <vector>
@@ -14,15 +14,18 @@
 
 using MemoKey = tuple<size_t, size_t, size_t>;
 
-class TupleHash : function<size_t(const MemoKey&)> {
+class TupleHash : function<size_t(const MemoKey &)> {
 public:
-    size_t operator()(const MemoKey& k) const { return get<0>(k) ^ get<1>(k) ^ get<2>(k); }
+  size_t operator()(const MemoKey &k) const {
+    return get<0>(k) ^ get<1>(k) ^ get<2>(k);
+  }
 };
 
 template <typename T>
-size_t lcss_inner(const vector<T> &a, const vector<T> &b, size_t i, size_t j,
-                  size_t length, size_t &longest, vector<T> &longest_seq,
-                  unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> &cache) {
+size_t lcss_inner(
+    const vector<T> &a, const vector<T> &b, size_t i, size_t j, size_t length,
+    size_t &longest, vector<T> &longest_seq,
+    unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> &cache) {
   if (i >= a.size() || j >= b.size()) {
     return length;
   }
@@ -32,7 +35,6 @@
     return get<1>(*cache.find(key));
   }
 
-
   if (a.at(i) == b.at(j)) {
     // Current (i, j) is member of a common subsequence.
     longest = max(longest, length + 1);
@@ -57,123 +59,148 @@
   }
 }
 
-template<typename T>
-vector<T> lcss(const vector<T>& a, const vector<T>& b) {
-    size_t longest = 0;
-    vector<T> longest_seq(min(a.size(), b.size()));
-    unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> cache(100);
-    size_t longest_r = lcss_inner(a, b, 0, 0, 0, longest, longest_seq, cache);
+template <typename T> vector<T> lcss(const vector<T> &a, const vector<T> &b) {
+  size_t longest = 0;
+  vector<T> longest_seq(min(a.size(), b.size()));
+  unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> cache(100);
+  size_t longest_r = lcss_inner(a, b, 0, 0, 0, longest, longest_seq, cache);
 
-    fmt::print("Length: {} / {}\n", longest, longest_r);
+  fmt::print("Length: {} / {}\n", longest, longest_r);
 
-    return longest_seq;
+  return longest_seq;
 }
 // g++ only
-template<typename T, template<typename> typename C>
-void evaluate_lcss(const C<T>& a, const C<T>& b) requires ranges::range<C<T>> {
-    vector<T> va(a.begin(), a.end());
-    vector<T> vb(b.begin(), b.end());
-    auto result = timeit_f(function([&va, &vb]() { return lcss(va, vb); }));
+template <typename T, template <typename> typename C>
+void evaluate_lcss(const C<T> &a, const C<T> &b)
+  requires ranges::range<C<T>>
+{
+  vector<T> va(a.begin(), a.end());
+  vector<T> vb(b.begin(), b.end());
+  auto result = timeit_f(function([&va, &vb]() { return lcss(va, vb); }));
 
-    fmt::print("{}\n", va);
-    fmt::print("{}\n", vb);
-    fmt::print("{}\n", result);
+  fmt::print("{}\n", va);
+  fmt::print("{}\n", vb);
+  fmt::print("{}\n", result);
 }
 
 template <typename T>
 size_t longest_increasing_subsequence(const vector<T> &a, size_t i, size_t prev,
                                       size_t length, size_t &longest,
                                       vector<size_t> &seqixs) {
-    longest = max(length, longest);
-    if (i >= a.size()) return length;
+  longest = max(length, longest);
+  if (i >= a.size())
+    return length;
 
-    size_t length_with_current = a.at(i) < a.at(prev) ? length : longest_increasing_subsequence(a, i+1, i, length+1, longest, seqixs);
-    size_t length_without_current = longest_increasing_subsequence(a, i+1, prev, length, longest, seqixs);
-    size_t result = max(length_with_current, length_without_current);
+  size_t length_with_current =
+      a.at(i) < a.at(prev) ? length
+                           : longest_increasing_subsequence(
+                                 a, i + 1, i, length + 1, longest, seqixs);
+  size_t length_without_current =
+      longest_increasing_subsequence(a, i + 1, prev, length, longest, seqixs);
+  size_t result = max(length_with_current, length_without_current);
 
-    if (result == length_with_current && result == longest) {
-        seqixs.at(length) = i;
-    }
-    return result;
+  if (result == length_with_current && result == longest) {
+    seqixs.at(length) = i;
+  }
+  return result;
 }
 
 // Bug: if first element is 0 or negative, may repeat last index in seqixs
-template<typename T>
-T max_sum_incr_subseq(const vector<T>& a, size_t i, size_t prev, size_t length, T sum, T& highest_sum, vector<size_t>& seqixs) {
-    highest_sum = max(sum, highest_sum);
-    if (i >= a.size()) return sum;
+template <typename T>
+T max_sum_incr_subseq(const vector<T> &a, size_t i, size_t prev, size_t length,
+                      T sum, T &highest_sum, vector<size_t> &seqixs) {
+  highest_sum = max(sum, highest_sum);
+  if (i >= a.size())
+    return sum;
 
-    T sum_with_this = a.at(i) < a.at(prev) ? sum : max_sum_incr_subseq(a, i+1, i, length+1, sum + a.at(i), highest_sum, seqixs);
-    T sum_without_this = max_sum_incr_subseq(a, i+1, prev, length, sum, highest_sum, seqixs);
-    T result = max(sum_with_this, sum_without_this);
+  T sum_with_this =
+      a.at(i) < a.at(prev)
+          ? sum
+          : max_sum_incr_subseq(a, i + 1, i, length + 1, sum + a.at(i),
+                                highest_sum, seqixs);
+  T sum_without_this =
+      max_sum_incr_subseq(a, i + 1, prev, length, sum, highest_sum, seqixs);
+  T result = max(sum_with_this, sum_without_this);
 
-    if (result == sum_with_this && sum_with_this > sum_without_this && sum_with_this == highest_sum) {
-        if (i == 7 && length == 3) fmt::print("{} {} {} {} {} / {} - {}\n", i, prev, length, sum, highest_sum, sum_with_this, sum_without_this);
-        seqixs.at(length) = i;
-    }
+  if (result == sum_with_this && sum_with_this > sum_without_this &&
+      sum_with_this == highest_sum) {
+    seqixs.at(length) = i;
+  }
 
-    return result;
+  return result;
 }
 
+template <typename T, template <typename> typename C>
+void evaluate_liss(const C<T> &v)
+  requires ranges::range<C<T>>
+{
+  vector<T> a(v.begin(), v.end());
+  size_t longest = 0;
+  vector<size_t> seqixs(a.size());
+  size_t result = timeit_f(function([&a, &longest, &seqixs]() -> size_t {
+                             return longest_increasing_subsequence(
+                                 a, 0, 0, 0, longest, seqixs);
+                           }),
+                           "longest incr. subsequence");
 
-template<typename T, template<typename> typename C>
-void evaluate_liss(const C<T>& v) requires ranges::range<C<T>> {
-    vector<T> a(v.begin(), v.end());
-    size_t longest = 0;
-    vector<size_t> seqixs(a.size());
-    size_t result = timeit_f(function([&a,&longest,&seqixs]() -> size_t { return longest_increasing_subsequence(a, 0, 0, 0, longest, seqixs); }), "longest incr. subsequence");
+  fmt::print("Longest incr. subsequence has length {}/{} and has indices: {}\n",
+             longest, result, seqixs);
 
-    fmt::print("Longest incr. subsequence has length {}/{} and has indices: {}\n", longest, result, seqixs);
-    
-    vector<T> seq(longest);
-    for (int i = 0; i < seq.size(); i++)
-        seq.at(i) = a.at(seqixs.at(i));
-    fmt::print("Longest incr. subsequence is: {}\n", seq);
+  vector<T> seq(longest);
+  for (int i = 0; i < seq.size(); i++)
+    seq.at(i) = a.at(seqixs.at(i));
+  fmt::print("Longest incr. subsequence is: {}\n", seq);
 }
 
-template<typename T, template<typename> typename C>
-void evaluate_msis(const C<T>& v) requires ranges::range<C<T>> {
-    vector<T> a(v.begin(), v.end());
-    T highest = 0;
-    vector<size_t> seqixs(a.size());
-    size_t result =
-        timeit_f(function([&a, &highest, &seqixs]() -> size_t {
-                   return max_sum_incr_subseq(a, 0, 0, 0, static_cast<T>(0), highest, seqixs);
-                 }),
-                 "max sum incr. subsequence");
+template <typename T, template <typename> typename C>
+void evaluate_msis(const C<T> &v)
+  requires ranges::range<C<T>>
+{
+  vector<T> a(v.begin(), v.end());
+  T highest = 0;
+  vector<size_t> seqixs(a.size());
+  size_t result =
+      timeit_f(function([&a, &highest, &seqixs]() -> size_t {
+                 return max_sum_incr_subseq(a, 0, 0, 0, static_cast<T>(0),
+                                            highest, seqixs);
+               }),
+               "max sum incr. subsequence");
 
-    fmt::print("Max incr sum subseq subsequence has sum {}/{} and has indices: {}\n", highest, result, seqixs);
-    
-    vector<T> seq(seqixs.size());
-    for (int i = 0; i < seq.size(); i++) {
-        if (i > 0 && seqixs.at(i) == 0) break;
-        seq.at(i) = a.at(seqixs.at(i));
-    }
-    fmt::print("Max sum incr. subsequence is: {}\n", seq);
+  fmt::print(
+      "Max incr sum subseq subsequence has sum {}/{} and has indices: {}\n",
+      highest, result, seqixs);
+
+  vector<T> seq(seqixs.size());
+  for (int i = 0; i < seq.size(); i++) {
+    if (i > 0 && seqixs.at(i) == 0)
+      break;
+    seq.at(i) = a.at(seqixs.at(i));
+  }
+  fmt::print("Max sum incr. subsequence is: {}\n", seq);
 }
 
 int lcss_main(void) {
 
-    vector<int> a{1,6,2,-1,3,55,2,4,23,5,6,7,8,9,10};
-    vector<int> b{-3, 1, 5, 7, 2, 4, -1, 3, 6, 7, 9, 11, 10};
+  vector<int> a{1, 6, 2, -1, 3, 55, 2, 4, 23, 5, 6, 7, 8, 9, 10};
+  vector<int> b{-3, 1, 5, 7, 2, 4, -1, 3, 6, 7, 9, 11, 10};
 
-    evaluate_lcss(a, b);
-    evaluate_lcss(views::single(11), views::single(11));
-    return 0;
+  evaluate_lcss(a, b);
+  evaluate_lcss(views::single(11), views::single(11));
+  return 0;
 }
 
 int main(void) {
-    vector<int> a{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
-    // Expect: 0,2,6,9,13 or ,11
-    // or 0,4,6,9,13
-    evaluate_liss(a);
-    return 0;
+  vector<int> a{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
+  // Expect: 0,2,6,9,13 or ,11
+  // or 0,4,6,9,13
+  evaluate_liss(a);
+  return 0;
 }
 
 int msis_main(void) {
-    vector<int> a{-1, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
-    // Expect: 0,2,6,9,13 or ,11
-    // or 0,4,6,9,13
-    evaluate_msis(a);
-    return 0;
+  vector<int> a{-1, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
+  // Expect: 0,2,6,9,13 or ,11
+  // or 0,4,6,9,13
+  evaluate_msis(a);
+  return 0;
 }