2.1.1 Description

Group 1;             Group 2; Group 3
11 9       (QE= 99); 10 8 2;  7 5 4 3 1
10 9 1     (QE= 90); 11 7 2;  8 5 4 3
10 8 2     (QE=160); 11 9;    7 5 4 3 1
10 7 3     (QE=210); 11 9;    8 5 4 2 1
10 5 4 1   (QE=200); 11 9;    8 7 3 2
10 5 3 2   (QE=300); 11 9;    8 7 4 1
10 4 3 2 1 (QE=240); 11 9;    8 7 5
9 8 3      (QE=216); 11 7 2;  10 5 4 1
9 7 4      (QE=252); 11 8 1;  10 5 3 2
9 5 4 2    (QE=360); 11 8 1;  10 7 3
8 7 5      (QE=280); 11 9;    10 4 3 2 1
8 5 4 3    (QE=480); 11 9;    10 7 2 1
7 5 4 3 1  (QE=420); 11 9;    10 8 2

2.1.2 Solution

We use a backtracking algorithm in C++ as always when we need to backtack a significant amount of time with heavy data structures (R would make endless copies and slowing down the process significantly).

The workhorse function is can_partition which checks whether the numbers can be split into partition of the same sum. If we want to partition a vector into k groups, the sum of all numbers must be dividable by k, and the sum divided by k must be the target sum. Then in the backtracking algorithm, we try to add a number to the partition and recurse. If the sum of selected numbers equals the target, we recurse again, decreasing the number of groups by one. Thta is, we found one partition and check whtehr the remaining numbers can also form partitions of the same sum, but we need one group less (the very one we just formed).

If there is only one number left, the algorithm returns true, as per definition this number must equal the target. If at any stage the recursion returned false, we backtrack by deslecting this number and tring the next one. If we did not return with true from the recursion we return false as we could not find a valid partition.

With this workhorse function what is left is to loop through all group sizes from 1 to the number of elements in our vector. We create all combinations of this size, form the first group with these combinations (only if the partial sum equals the target) and check whether we can partition the remaining numbers into k - 1 groups. If this is possible, we store the result, keeping the best solution (minimum group size, and minimum quantum energy).

As soon as we found the first minimum solution, we stop, as we do not need to look for larger groups.

#ifndef STANDALONE
#include <Rcpp.h>
using namespace Rcpp;
#else
#include <iostream>
#endif

#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>

long long product(const std::vector<int>& nums) {
  long long p = 1;
  for (int n : nums)
    p *= n;
  return p;
}

bool can_partition(const std::vector<int>& nums,
                   int k,
                   int target,
                   int start,
                   std::vector<bool>& used) {
  if (k == 1) {
    return true;
  }
  std::function<bool(int, int)> dfs = [&](int idx, int group_sum) {
    if (group_sum == target) {
      return can_partition(nums, k - 1, target, 0, used);
    }
    for (size_t i = idx; i < nums.size(); ++i) {
      if (used[i] || group_sum + nums[i] > target) {
        continue;
      }
      used[i] = true;
      if (dfs(i + 1, group_sum + nums[i])) {
        return true;
      }
      used[i] = false;
    }
    return false;
  };

  return dfs(start, 0);
}

long long find_min_quantum_entanglement(std::vector<int> nums, int k) {
  int total = std::accumulate(nums.begin(), nums.end(), 0);
  if (total % k != 0) {
    return -1;
  }
  int target = total / k;
  std::sort(nums.begin(), nums.end(), std::greater<>());

  int n = nums.size();
  long long best_qe = LLONG_MAX;
  size_t min_group_size = INT_MAX;

  for (int size = 1; size <= n; ++size) {
    std::vector<bool> bitmask(size, true);
    bitmask.resize(n, false);

    do {
      std::vector<int> group;
      for (int i = 0; i < n; ++i) {
        if (bitmask[i]) {
          group.push_back(nums[i]);
        }
      }

      if (std::accumulate(group.begin(), group.end(), 0) != target) {
        continue;
      }

      std::vector<bool> used(n, false);
      for (int i = 0; i < n; ++i) {
        if (bitmask[i]) {
          used[i] = true;
        }
      }

      if (can_partition(nums, k - 1, target, 0, used)) {
        long long qe = product(group);
        if (group.size() < min_group_size || (group.size() == min_group_size && qe < best_qe)) {
          min_group_size = group.size();
          best_qe = qe;
        }
      }

    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));

    if (best_qe != LLONG_MAX) {
      // we found a solution, no need to check groups with more elements
      break;
    }
  }

  return (best_qe == LLONG_MAX) ? -1 : best_qe;
}
#ifndef STANDALONE
// [[Rcpp::export]]
long long find_min_quantum_entanglement(IntegerVector weights, int k) {
  std::vector<int> nums = as<std::vector<int>>(weights);
  return find_min_quantum_entanglement(nums, k);
}
#else
int main() {
  std::vector<int> weights = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
  int k = 4;
  long long result = find_min_quantum_entanglement(weights, k);
  std::cout << "Minimum quantum entanglement: " << result << std::endl;
}
#endif

find_min_quantum_entanglement(puzzle_data, 3L)

## [1] 10439961859

2.2.1 Description

11 4    (QE=44); 10 5;   9 3 2 1; 8 7
10 5    (QE=50); 11 4;   9 3 2 1; 8 7
9 5 1   (QE=45); 11 4;   10 3 2;  8 7
9 4 2   (QE=72); 11 3 1; 10 5;    8 7
9 3 2 1 (QE=54); 11 4;   10 5;    8 7
8 7     (QE=56); 11 4;   10 5;    9 3 2 1

2.2.2 Solution

find_min_quantum_entanglement(puzzle_data, 4L)

## [1] 72050269