Generates the smallest set of blank panels needed to fill any possible hole size in a modular synth from 1 to N

blanks.dart

void main(List<String> arguments) {
  // n is the largest space we're trying to fill. So we want to find the
  // smallest (fewest pieces and smallest total area) set of blanks that can be
  // used to fill a hole of any size from 1 to n.
  //
  // We know we will never need a single blank larger than n, since it couldn't
  // be used in any of the holes. So the basic process is to generate all
  // multisets from 1 to n. From those we discard the sets whose combinations
  // don't cover all holes up to n. Then we keep the smallest set. In practice,
  // the code generates multisets in smallest-to-largest order, so we can stop
  // as soon as we find a winner.
  for (var n = 1; n <= 50; n++) {
    findSmallestSet(n);
  }

  // Results:
  // 1 [1] = 1
  // 2 [1, 1] = 2
  // 3 [1, 2] = 3
  // 4 [1, 1, 2] = 4
  // 5 [1, 1, 3] = 5
  // 6 [1, 2, 3] = 6
  // 7 [1, 2, 4] = 7
  // 8 [1, 1, 2, 4] = 8
  // 9 [1, 1, 2, 5] = 9
  // 10 [1, 1, 3, 5] = 10
  // 11 [1, 1, 3, 6] = 11
  // 12 [1, 2, 3, 6] = 12
  // 13 [1, 2, 3, 7] = 13
  // 14 [1, 2, 4, 7] = 14
  // 15 [1, 2, 4, 8] = 15
  // 16 [1, 1, 2, 4, 8] = 16
  // 17 [1, 1, 2, 4, 9] = 17
  // 18 [1, 1, 2, 5, 9] = 18
  // 19 [1, 1, 2, 5, 10] = 19
  // 20 [1, 1, 3, 5, 10] = 20
  // 21 [1, 1, 3, 5, 11] = 21
  // 22 [1, 1, 3, 6, 11] = 22
  // 23 [1, 1, 3, 6, 12] = 23
  // 24 [1, 2, 3, 6, 12] = 24
  // 25 [1, 2, 3, 6, 13] = 25
  // 26 [1, 2, 3, 7, 13] = 26
  // 27 [1, 2, 3, 7, 14] = 27
  // 28 [1, 2, 4, 7, 14] = 28
  // 29 [1, 2, 4, 7, 15] = 29
  // 30 [1, 2, 4, 8, 15] = 30
  // 31 [1, 2, 4, 8, 16] = 31
  // 32 [1, 1, 2, 4, 8, 16] = 32
  // 33 [1, 1, 2, 4, 8, 17] = 33
  // 34 [1, 1, 2, 4, 9, 17] = 34
  // 35 [1, 1, 2, 4, 9, 18] = 35
  // 36 [1, 1, 2, 5, 9, 18] = 36
  // 37 [1, 1, 2, 5, 9, 19] = 37
  // 38 [1, 1, 2, 5, 10, 19] = 38
  // 39 [1, 1, 2, 5, 10, 20] = 39
  // 40 [1, 1, 3, 5, 10, 20] = 40
  // 41 [1, 1, 3, 5, 10, 21] = 41
  // 42 [1, 1, 3, 5, 11, 21] = 42
  // 43 [1, 1, 3, 5, 11, 22] = 43
  // 44 [1, 1, 3, 6, 11, 22] = 44
  // 45 [1, 1, 3, 6, 11, 23] = 45
  // 46 [1, 1, 3, 6, 12, 23] = 46
  // 47 [1, 1, 3, 6, 12, 24] = 47
  // 48 [1, 2, 3, 6, 12, 24] = 48
  // 49 [1, 2, 3, 6, 12, 25] = 49
  // 50 [1, 2, 3, 6, 13, 25] = 50
}

/// Finds the first smallest set of integers whose combinations include sums
/// from 1 to [n].
void findSmallestSet(int n) {
  var multisetSize = 1;
  while (true) {
    var found = false;
    forEachMultisubset(n, multisetSize, (multiset) {
      if (!combinationsCoverAll(multiset, n)) return false;
      print('$n ${multiset} = ${listSum(multiset)}');
      found = true;
      return true;
    });

    if (found) break;
    multisetSize++;
  }
}

/// Finds all smallest sets of integers whose combinations include sums from 1
/// to [n].
void findAllSmallestSets(int n) {
  var multisetSize = 1;
  while (true) {
    var matching = <List<int>>[];
    var multisets = generateMultisubsets(n, multisetSize);
    for (var multiset in multisets) {
      var sums = allCombinationSums(multiset);
      if (sumsCoverAll(sums, n)) matching.add(multiset);
    }

    if (matching.isNotEmpty) {
      // Print all of the sets with the smallest total area.
      matching.sort((a, b) => listSum(a).compareTo(listSum(b)));
      var smallest = listSum(matching[0]);
      for (var combination in matching) {
        if (listSum(combination) > smallest) break;
        print('${listSum(combination)} : $combination');
      }
      break;
    } else {
      multisetSize++;
    }
  }
}

/// Generates all of the multisubsets of the ints [1, max] with [size] elements.
List<List<int>> generateMultisubsets(int max, int size) {
  var result = <List<int>>[];
  void generate(List<int> soFar, int n) {
    if (n <= max) {
      for (var i = size - soFar.length; i >= 0; i--) {
        var list = soFar.toList();
        for (var j = 1; j <= i; j++) {
          list.add(n);
        }
        generate(list, n + 1);
      }
    } else if (soFar.length == size) {
      result.add(soFar);
    }
  }
  generate([], 1);
  return result;
}

/// Generates all of the multisubsets of the ints [1, max] with [size] elements.
///
/// Invokes [callback] on each multiset. Stops generating when the callback
/// returns `true`.
void forEachMultisubset(int max, int size, bool Function(List<int> multiset) callback) {
  var done = false;
  void generate(List<int> soFar, int n) {
    if (done) return;

    if (n <= max) {
      for (var i = size - soFar.length; i >= 0; i--) {
        var list = soFar.toList();
        for (var j = 1; j <= i; j++) {
          list.add(n);
        }
        generate(list, n + 1);
      }
    } else if (soFar.length == size) {
      done = callback(soFar);
    }
  }
  generate([], 1);
}

/// Returns `true` if [values] contains combinations whose sums cover all
/// values from 1 to [max], inclusive.
bool combinationsCoverAll(List<int> values, int max) {
  // The sums we haven't found in combinations yet.
  var missing = {for (var i = 1; i <= max; i++) i};

  void combinations(int sumSoFar, int position) {
    // If we've covered everything already, stop recursing.
    if (missing.isEmpty) return;

    if (position < values.length) {
      // Generate the combinations without the element at [position].
      combinations(sumSoFar, position + 1);
      // And with the element at [position].
      combinations(sumSoFar + values[position], position + 1);
    } else {
      missing.remove(sumSoFar);
    }
  }

  combinations(0, 0);
  return missing.isEmpty;
}

/// Generates all combinations of [values] and then returns the set of all of
/// their unique sums.
Set<int> allCombinationSums(List<int> values) {
  var result = <int>{};

  void combinations(int sumSoFar, int position) {
    if (position < values.length) {
      // Generate the combinations without the element at [position].
      combinations(sumSoFar, position + 1);
      // And with the element at [position].
      combinations(sumSoFar + values[position], position + 1);
    } else {
      result.add(sumSoFar);
    }
  }

  combinations(0, 0);
  return result;
}

/// Returns `true` if [sums] contains all values from 1 to [max],
/// inclusive.
bool sumsCoverAll(Set<int> sums, int max) {
  for (var i = 1; i <= max; i++) {
    if (!sums.contains(i)) return false;
  }
  return true;
}

int listSum(List<int> list) => list.fold<int>(0, (a, b) => a + b);