I'm trying to make a card game called Tablic, and I'm struggling with logic.

Simplified, it comes to this:

- I have an array filled with numbers from 1 to 14. (array size doesn't matter, but since we have 52 cards it can't be larger than that) - random example: [2,9,2,9,8,11,14,7]

- I need to check if all elements of array can be used in addition (no other math operation is allowed) to get one specific number (1 < number < 14)

Few examples:

[2, 1, 5, 4] == 6   //true --> 2+4==6; 1+5==6 .. all elements of array are used

[2, 1, 3, 5, 4] == 6  //false --> we can not calculate 6 using all elements, there is always one or more extra ... 2+4==6; 5+1==6; .. 3 is unused!! ... or .. 1+2+3==6; 4 and 5 are unused

[5, 2, 10, 3] == 10  //true --> 2+3+5==10; 10==10 .. again, every number from array is used, so true

[6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2] == 12  //true --> 6+6==12; 12==12; 8+4==12; 9+3==12; 10+2==12; 2+3+3+4==12 ... all numbers from array used

I hope I was clear enough (and I hope I am at the right place to ask questions like this)

There is no fast solution for this.  The slow solution looks something like this:

def f(array, target_number, n = 0):
  if len(array) == 0:
    return n == 0
  if n == 0:
    n = target_number
  for x in array:
    if x > target_number:
      return False
    if x > n:
      continue
    array_without_x = array.copy()
    array_without_x.remove(x)
    if f(array_without_x, target_number, n - x):
      return True
  return False

There are numerous possible optimizations, but  that's the basic idea.

Would the following work?

function checkArray( array , targetNumber ){
  
  let total=0;
  
  for( var i=0, ii=array.length; i<ii; i++ ){
    total += array[ i ];
  }
  
  if( total % targetNumber == 0 ){
    return true;
  }
  
  return false; 
}

6 hours ago, Awoken said:

Would the following work?

function checkArray( array , targetNumber ){
  
  let total=0;
  
  for( var i=0, ii=array.length; i<ii; i++ ){
    total += array[ i ];
  }
  
  if( total % targetNumber == 0 ){
    return true;
  }
  
  return false; 
}

 

That only checks if the total is divisible by the target number. so something like [7, 2, 7, 4] with a target of 10 would return true, but neither 7 + 4 nor 7 + 2 sum to 10.

I'm not 100% sure if the following works in ALL cases, but I think it should:

def check(numbers, target):
	numbers = sorted(numbers)
	while numbers:
		csum = numbers.pop(-1)
		# print(csum, end=' ')
		for i in reversed(range(len(numbers))):
			if csum + numbers[i] <= target:
				# print('+', numbers[i], end=' ')
				csum += numbers.pop(i)
		# print('=', csum)
		if csum != target:
			return False
	return True

It always tries to combine the largest number with the next largest number that can be added without going above the target until the target is either reached, or not.

38 minutes ago, l0calh05t said:

I'm not 100% sure if the following works in ALL cases, but I think it should:

def check(numbers, target):
	numbers = sorted(numbers)
	while numbers:
		csum = numbers.pop(-1)
		# print(csum, end=' ')
		for i in reversed(range(len(numbers))):
			if csum + numbers[i] <= target:
				# print('+', numbers[i], end=' ')
				csum += numbers.pop(i)
		# print('=', csum)
		if csum != target:
			return False
	return True

 

Obvious counter-example: numbers = [3, 3, 2, 2, 2, 2]; target=7

This is an NP-hard problem, similar to the partition problem, but generalized to N partitions where N = sum(numbers)/target.  If you manage to solve it in polynomial time, you will have solved one of the great unsolved problems in computer science.

Your first solution works with all examples I listed in original post, but it gets stuck if I add any number at the fourth case:

f( [6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2, 1], 12 ) //I just added number 1 at the end of array. Without it, code works.

But I converted your Python code to Ruby (language I'm using), might be something is lost in "translation":

def f(array, target_number, n = 0)
  return (n == 0) if array.size == 0
  (n = target_number) if n == 0
  array.each do |x|
    return false if x > target_number
    next if x > n
    array_without_x = array.dup
    array_without_x.delete_at(array_without_x.index(x))
    return true if f(array_without_x, target_number, n - x)
  end
  return false
end

4 hours ago, a light breeze said:

Obvious counter-example: numbers = [3, 3, 2, 2, 2, 2]; target=7

This is an NP-hard problem, similar to the partition problem, but generalized to N partitions where N = sum(numbers)/target.  If you manage to solve it in polynomial time, you will have solved one of the great unsolved problems in computer science.

Well, except the target cannot be more than 14, so the asymptotic cost of the computation is kind of irrelevant here.

I have to go to work now, but I'll write something tonight that I think will run fast in practice.

4 hours ago, a light breeze said:

Obvious counter-example: numbers = [3, 3, 2, 2, 2, 2]; target=7

This is an NP-hard problem, similar to the partition problem, but generalized to N partitions where N = sum(numbers)/target.  If you manage to solve it in polynomial time, you will have solved one of the great unsolved problems in computer science.

You are right.

1 hour ago, BOOGIEMAN said:

Your first solution works with all examples I listed in original post, but it gets stuck if I add any number at the fourth case:

f( [6, 4, 3, 4, 9, 3, 2, 12, 6, 8, 10, 3, 2, 1], 12 ) //I just added number 1 at the end of array. Without it, code works.

But I converted your Python code to Ruby (language I'm using), might be something is lost in "translation":

def f(array, target_number, n = 0)
  return (n == 0) if array.size == 0
  (n = target_number) if n == 0
  array.each do |x|
    return false if x > target_number
    next if x > n
    array_without_x = array.dup
    array_without_x.delete_at(array_without_x.index(x))
    return true if f(array_without_x, target_number, n - x)
  end
  return false
end

 

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.

Here's a recursive version that (while not polynomial in time) should be fast enough:

def list_without(vs, v):
	vs = list(vs)
	vs.remove(v)
	return vs

def memoize(f):
    memo = {}
    def helper(*args):
        if args not in memo:            
            memo[args] = f(*args)
        return memo[args]
    return helper
	
def check(numbers, target):
	total = sum(numbers)
	if(
		not numbers or
		total % target != 0 or
		any(n > target for n in numbers)
	):
		return False
	numbers = sorted(numbers)
	evaluations = [0]
	def recursion(numbers, cur, offset):
		evaluations[0] += 1
		if(
			cur > target or
			(total + cur - offset) % target != 0
		):
			return False
		if not numbers:
			return cur == target
		cur = cur % target
		unums = reversed(sorted(set(numbers)))
		return any(
			recursion(
				tuple(list_without(numbers, n)),
				cur + n,
				offset + n
			)
			for n in unums
		)
	recursion = memoize(recursion)
	x = numbers.pop(-1)
	r = recursion(tuple(numbers), x, x)
	print(evaluations[0], 'evaluations')
	return r

Although there are a few "degenerate" cases that take a lot of time (assuming a full deck of 52 cards, so this really is a worst case scenario:

numbers = [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]

target = 10

works well with only 124 recursive evaluations, but

numbers = [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]

target = 11

took 18489550 evaluations, so yeah, not always great. Generally speaking, combinations that work are quick to check, while combinations that don't are slow.

24 minutes ago, l0calh05t said:

assuming a full deck of 52 cards

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