1 minute ago, 1024 said:

Don't forget that a deck of cards only has 4 cards of each value. The cases you wrote are therefore impossible  

Yeah, but otherwise the result is always the same.

Adding

if cur + numbers[0] > target:
	return False

after the if not numbers check makes it even faster

Here's the promised code. It seems to work just fine.

#include <iostream>
#include <vector>

bool partition_recursively(int counters[16], // How many of each number do we have?
			   int sum, // Sum of all the numbers (redundant, but handy)
			   int target,
			   int to_fill_current_bucket, // If a bucket is partially filled, how much more do we need to reach the target?
			   int max_next // Maximum integer to consider next (because we try to fit numbers in decreasing order)
			   ) {
  // Are we are starting a fresh new bucket?
  if (to_fill_current_bucket == target) {
    // Perhaps we are done?
    if (sum == 0)
      return true;

    // We can always start the new bucket with the largest number we have left.
    for (int x = max_next; ; --x) {
      if (counters[x] > 0) {
	counters[x]--;
	return partition_recursively(counters, sum - x, target, target - x, x);
      }
    }
    // The execution flow never gets here.
  }

  // If there is a number that fits exactly what we need to fill the current bucket, we can just pick it.
  if (max_next >= to_fill_current_bucket && counters[to_fill_current_bucket] > 0) {
    counters[to_fill_current_bucket]--;
    return partition_recursively(counters, sum - to_fill_current_bucket, target, target, target - 1);
  }

  // Try to place a next number of every possible size, in descending order.
  for (int x = std::min(max_next, to_fill_current_bucket); x > 0; --x) {
    if (counters[x] > 0) {
      counters[x]--;
      bool result = partition_recursively(counters, sum - x, target, to_fill_current_bucket - x, x);
      counters[x]++;
      if (result)
	return true;
    }
  }

  // Oh, well! That didn't work out!
  return false;
}

bool partition(std::vector<int> list, int target) {
  int counters[16] = {0};
  int sum = 0;
  for (auto x : list) {
    // That's not going to fit! (That's what she said.)
    if (x > target)
      return false;

    // We can ignore numbers that are equal to the target, as a micro-optimization.
    if (x < target) {
      counters[x]++;
      sum += x;
    }
  }

  // If the numbers don't add up to a multiple of the target, it can't be done.
  if (sum % target != 0)
    return false;
  
  // Start the actual search.
  return partition_recursively(counters, sum, target, target, target - 1);
}

int main() {
  std::cout << partition({2, 1, 5, 4}, 6) << '\n'; // true
  std::cout << partition({2, 1, 3, 5, 4}, 6) << '\n'; // false
  std::cout << partition({5, 2, 10, 3}, 10) << '\n'; // true
  std::cout << partition({6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2}, 12) << '\n'; // true
  std::cout << partition({7, 2, 7, 4}, 10) << '\n'; // false
  std::cout << partition({3, 3, 2, 2, 2, 2}, 7) << '\n'; // true
  std::cout << partition({6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2, 1}, 12) << '\n'; // false
  std::cout << partition({1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10}, 10) << '\n'; // true
  std::cout << partition({1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11}, 11) << '\n'; // false
}

Enjoy!

This thread has been most fulfilling.  I love this kind of stuff.

Can someone give me a layman's explanation of the N  P == NP,  N P != NP problem?

[ edit: thanks alvaro ]

5 minutes ago, Awoken said:

This thread has been most fulfilling.  I love this kind of stuff.

Can someone give me a layman's explanation of the N == NP,  N != NP problem?

I don't know what that problem is. There is a class of problems called "P", and you probably meant to ask about the problem of whether P==NP. This problem is basically whether searching is as hard as we think it is, or if there is a shortcut.

P is the class of problems that can be solved in polynomial time. That means that as the length of the input (in the case of this thread, the number of cards) grows, the time it takes for an algorithm to find a solution grows as some power of that length (for instance, as the cube of the length).

NP is the class of problems whose solution can be verified in polynomial time. The problem in this thread is in this class, because a small modification of the algorithm I posted could produce a "certificate" (the cards sorted into buckets that add up to the target) which allows anyone to verify the answer is correct in polynomial time (in this case in linear time).

NP problems are very often search problems, and programs that solve them often look like the program I posted, with a function that calls itself in a loop ("backtracking"). These programs typically take exponential time to run. But it is possible that a clever trick exists that would allow a polynomial-time solution to all such problems. The question of whether P==NP is precisely whether such a clever trick exists.

An NP problem is said to be "NP-complete" if any other problem in NP can be polynomially reduced to it. This implies that if you figured out a way to solve one of these problems in polynomial time, that would give you a mechanism to solve any problem in NP in polynomial time. There is a long list of problems that are known to be NP-complete. If you could find a polynomial-time solution to any of them, you would have proven P==NP.

Most of us expect P!=NP, meaning no clever trick can solve any search problem in polynomial time. But we don't have a proof [yet].

I think that's about the simplest explanation I can give you.

@alvaro, I'm trying to understand just what polynomial time is and so far every youtube video and link on the internet references polynomial time in their description of polynomial time.  Many of the terms you've introduced are new to me.  What is polynomial time?

Is there a difference between polynomial time and exponential time?

[ edit ]

K I'm attempting to answer my own question.  If the problem we're attempting to solve via an algorithm has a set limit on the number of lines of code to be executed then it is considered Polynomial time.  If however, the number of lines of code to be executed to solve a problem ( knowing a solution is possible ) is unknown then it is not considered Polynomial time? 

So then the question is whether there is a clever trick that allows ALL problems with known possible solutions to be solvable in a known limit of the number of lines of code to be executed?

"Lines of code executed" is an unusual metric to define execution time, because depending on the programming language, some lines of code might take much longer to execute than others. People usually think of clock cycles, or number of arithmetic operations, or something like this. These metrics are usually proportional to each other, so the exact details don't matter for the discussion of whether something runs in polynomial time or in exponential time.

The time an algorithm takes to run is a function of the length of the input N. As N increases, the time it takes to run the algorithm typically grows. If this growth is about as fast as some polynomial (the precise definition is confusing, so I'll skip it), the algorithm is said to take "polynomial time".

A polynomial in N is an expression like 5*N^4 + 20*N^3 - 2*N^2 + 1. The things we are adding or subtracting are called "terms", and each term consists of a number called "coefficient" times N raised to a natural number called "degree". The term with the highest degree is called the "leading term" (5*N^4 in this case). As N becomes very large, the leading term will dwarf all the others. So you can think of "polynomial time" as being roughly proportional to N raised to some integer power.

"Exponential time" by analogy means the algorithm takes time roughly proportional to an exponential function, i.e. some constant raised to the N-th power. For instance, 2^N.

Exponential-time algorithms take much longer to run than polynomial-time algorithms, for large enough inputs.

To give you an idea of how different exponential time and polynomial times are, if you multiply N by 2, a polynomial algorithm will see its execution time multiplied by 2^degree. In an exponential-time algorithm, you only need to add a constant to N to see the time multiplied by a constant.

You can also experiment plugging in large values of N into polynomial formulas and into exponential formulas. If N=1000, the polynomial formula I posted above evaluates to

5*N^4 + 20*N^3 - 2*N^2 + 1 = 5019998000001 (notice how 5*N^4 is a good approximation)

By contrast, 2^N is

10715086071862673209484250490600018105614048117055336074437503883703\
51051124936122493198378815695858127594672917553146825187145285692314\
04359845775746985748039345677748242309854210746050623711418779541821\
53046474983581941267398767559165543946077062914571196477686542167660\
429831652624386837205668069376
 

If anything is still not clear, try to ask very concise questions.

Hmmm... I wanted to fix some issue with the code above, but I don't seem to be able to edit the post. Here's the updated code.

#include <iostream>
#include <vector>

bool partition_recursively(int counters[16], // How many of each number do we have?
			   int sum, // Sum of all the numbers (redundant, but handy)
			   int target,
			   int to_fill_current_bucket, // If a bucket is partially filled, how much more do we need to reach the target?
			   int max_next // Maximum integer to consider next (because we try to fit numbers in decreasing order)
			   ) {
  // Are we are starting a fresh new bucket?
  if (to_fill_current_bucket == target) {
    // Perhaps we are done?
    if (sum == 0)
      return true;

    // We can always start the new bucket with the largest number we have left.
    for (int x = max_next; ; --x) {
      if (counters[x] > 0) {
	counters[x]--;
	bool result = partition_recursively(counters, sum - x, target, target - x, x);
	counters[x]++;
	return result;
      }
    }
    // The execution flow never gets here.
  }

  // If there is a number that fits exactly what we need to fill the current bucket, we can just pick it.
  if (max_next >= to_fill_current_bucket && counters[to_fill_current_bucket] > 0) {
    counters[to_fill_current_bucket]--;
    bool result = partition_recursively(counters, sum - to_fill_current_bucket, target, target, target - 1);
    counters[to_fill_current_bucket]++;
    return result;
  }

  // Try to place a next number of every possible size, in descending order.
  for (int x = std::min(max_next, to_fill_current_bucket); x > 0; --x) {
    if (counters[x] > 0) {
      counters[x]--;
      bool result = partition_recursively(counters, sum - x, target, to_fill_current_bucket - x, x);
      counters[x]++;
      if (result)
	return true;
    }
  }

  // Oh, well! That didn't work out!
  return false;
}

bool partition(std::vector<int> list, int target) {
  int counters[16] = {0};
  int sum = 0;
  for (auto x : list) {
    // That's not going to fit! (That's what she said.)
    if (x > target)
      return false;

    // We can ignore numbers that are equal to the target, as a micro-optimization.
    if (x < target) {
      counters[x]++;
      sum += x;
    }
  }

  // If the numbers don't add up to a multiple of the target, it can't be done.
  if (sum % target != 0)
    return false;
  
  // Start the actual search.
  return partition_recursively(counters, sum, target, target, target - 1);
}

int main() {
  std::cout << partition({2, 1, 5, 4}, 6) << '\n'; // true
  std::cout << partition({2, 1, 3, 5, 4}, 6) << '\n'; // false
  std::cout << partition({5, 2, 10, 3}, 10) << '\n'; // true
  std::cout << partition({6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2}, 12) << '\n'; // true
  std::cout << partition({7, 2, 7, 4}, 10) << '\n'; // false
  std::cout << partition({3, 3, 2, 2, 2, 2}, 7) << '\n'; // true
  std::cout << partition({6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2, 1}, 12) << '\n'; // false
  std::cout << partition({1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10}, 10) << '\n'; // true
  std::cout << partition({1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11}, 11) << '\n'; // false
}

On 2/27/2019 at 2:56 PM, l0calh05t said:

You are right.

Yes, something was lost in translation (are you sorting the array? this looks a bit wierd in general). Works just fine for the example. However, as a light breeze pointed out, it does not work in general.

Actually, code was ok. I just needed to wait 5 minutes for it to finish

Alvaro's version is few thousand times faster (here is C++ to Ruby rewrite, I'm not sure if I did it right, but seems to produce results as expected)

def partition_recursively(counters, sum, target, to_fill_current_bucket, max_next) 
  if (to_fill_current_bucket == target) 
    return true if (sum == 0)
    x = max_next
    loop do
      if (counters[x] > 0) then
        counters[x] -= 1
        result = partition_recursively(counters, sum - x, target, target - x, x)
        counters[x] += 1
        return result
      end
      x -= 1
    end
  end

  if (max_next >= to_fill_current_bucket && counters[to_fill_current_bucket] > 0)
    counters[to_fill_current_bucket] -= 1
    result = partition_recursively(counters, sum - to_fill_current_bucket, target, target, target - 1)
    counters[to_fill_current_bucket] += 1
    return result
  end

  x = [max_next, to_fill_current_bucket].min
  while x > 0  
    if (counters[x] > 0) 
      counters[x] -= 1
      result = partition_recursively(counters, sum - x, target, to_fill_current_bucket - x, x)
      counters[x] += 1
      return true if result
    end
    x -= 1
  end

  return false
end 

def partition(list, target)
  counters = Array.new(16, 0)
  sum = 0
  list.each do |x|
    return false if (x > target)
      
    if (x < target) 
      counters[x] += 1
      sum += x
    end
  end

  return false if (sum % target != 0)
    
  return partition_recursively(counters, sum, target, target, target - 1);
end 


p partition([2, 1, 5, 4], 6) # true
p partition([2, 1, 3, 5, 4], 6) # false
p partition([5, 2, 10, 3], 10) # true
p partition([6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2], 12) # true
p partition([7, 2, 7, 4], 10) # false
p partition([3, 3, 2, 2, 2, 2], 7) # true
p partition([6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2, 1], 12) # false
p partition([1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 10], 10) # true
p partition([1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11], 11) # false

Thanks everyone for your your time. I was considering dumbing it down and force the player to pick up cards in a logical sequence, but this is much better.

16 hours ago, Awoken said:

Is there a difference between polynomial time and exponential time?

The problem width for exponential time is in exponent, thus problem width genrates much more time then if it is in the base,

The polynomial time puts problem width to base, while allowing for linear combination of them , such as 3*base5 + 5*base4