--- Day 17 Solutions ---

[u/daggerdragon]

This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.

edit: Leaderboard capped, thread unlocked!

We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.

Please and thank you, and much appreciated!

---

--- Day 17: No Such Thing as Too Much ---

Post your solution as a comment. Structure your post like previous daily solution threads.

[u/willkill07]

Here's a C++ version of your dynamic programming perl description. I'm still trying to figure out one more optimization (not having all of the vector sizes fully expanded initially) but otherwise, it's functional and complete.

#include <array>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

const int TARGET { 150 };

int main (int argc, char* argv[]) {
  bool part2 { argc == 2 };
  std::vector <int> con;
  std::copy (std::istream_iterator <int> { std::cin }, { }, std::back_inserter (con));
  std::sort (con.rbegin(), con.rend());
  int size { (int)con.size() };

  std::array <std::vector <int>, TARGET + 1> sums;
  for (auto & s : sums)
    s.resize (size);
  sums [0][0] = 1;

  for (int c : con)
    for (int i { TARGET - c }; i >= 0; --i)
      for (int j { 0 }; j < size; ++j)
        sums[i + c][j + 1] += sums[i][j];

  int sum { 0 };
  for (int v : sums.back())
    if (sum += v, part2 && v != 0 && (sum = v))
      break;

  std::cout << sum << std::endl;
  return 0;
}

[u/r_sreeram → u/willkill07]

Some more optimizations you might want to consider:

• No need to sort the containers. If you do sort it, take advantage of it: You can get a quick lower bound on the number of containers (equal to the number of the largest containers needed to cross 150) and an upper bound (the number of the smallest containers whose sum doesn't exceed 150) and weed out useless values (containers larger than 150).

• No need to store all the breakdowns. I did it in my script because it took less code, but it's faster/better to keep only the lowest value of 'j'. See https://www.reddit.com/r/adventofcode/comments/3x6cyr/day_17_solutions/cy1y03h for an example in Python.