# Algorithmic problem: Picking Cards

The problem below appeared on the last Code Sprint 2 programming competition (it's over already). The base cases are clear, but developing an algorithm that solves all possible cases has been a challenge so far.

There are N cards on the table and each has a number between 0 and N on it. Let us denote the number on the Nth Ni. You want to pick up all the cards, but you can only pick a specific Nth card if you already picked Ni cards before. (As an example, if a card has a value of 3 on it, you can’t pick that card up unless you’ve already picked up 3 cards previously) In how many ways can all the cards be picked up?

Input are the cards with their respective numbers, and the output should be the total number of ways possible to pick them up.

``````Sample Input:
0 0 0
Sample Output:
6

Sample Input:
0 0 0 0
Sample Output:
24

Sample Input:
0 0 1
Sample Output
4

Sample Input:
0 3 3
Sample Output:
0
``````
-

Here's a quick implementation in java. The idea is to find how many cards can be picked each step by counting the number of cards with a number below this step and subtracting the number of cards already picked. Of course a lot of work is unnecessarily repeated, but this should give a good idea of how to approach this problem.

``````public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
int count = 0;
for (int number : cards) {
if(number <= max) count++;
}
return count;
}

public static void main(String[] args) {
int[] cards = {0, 1, 2, 4, 3};
int numberOfWays = 1;
for(int i = 0; i < cards.length; i++) {
int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
numberOfWays *= ways;
}
System.out.println(numberOfWays);
}
``````

}

-
This answer is correct: you can reduce the running time to linear by using counting sort on the cards, precomputing the answers of countLessOrEqualThanMax and then iterating over the cards in their sorted order. – Alex ten Brink Jan 9 '12 at 15:39

As a starting point, for the case where all cards are zero:

Output = N!

For example:

Sample Input: 0 0 0

Sample Output: 3 x 2 x 1 = 6.

Clearly, any card with a number higher than 0 will reduce the number of possible ways of picking up the cards.

Any card with "N" on it will make it impossible to pick up the cards.

Edit:

Consider N=4 cards where:

A=0, B=0, C=1, D=2

C can't appear in column 1. D can't appear in column 1 or 2.

1. A, B, C, D - Y
2. A, B, D, C - Y
3. A, C, B, D - Y
4. A, C, D, B - Y
5. A, D, B, C - N
6. A, D, C, B - N

7. B, A, C, D - Y

8. B, A, D, C - Y
9. B, C, A, D - Y
10. B, C, D, A - Y
11. B, D, A, C - N
12. B, D, C, A - N

13. C, A, B, D - N

14. C, A, D, B - N
15. C, B, A, D - N
16. C, B, D, A - N
17. C, D, A, B - N
18. C, D, B, A - N

19. D, A, B, C - N

20. D, A, C, B - N
21. D, B, A, C - N
22. D, B, C, A - N
23. D, C, A, B - N
24. D, C, B, A - N
-
Yep that far I had arrived as well. The challenge is to create an algorithm that will solve all the possible cases. – daniels Jan 9 '12 at 12:23
@daniels: I've expanded my answer. – Kramii Jan 9 '12 at 12:46
Kramil, that helps, but having the algorithm itself would help even more. I am taking a look FranKL's algo now. Looks like he nailed it, do you agree? – daniels Jan 9 '12 at 13:09
@daniels: FrankL's method looks fine, but is a lot of work when a simple formula can give the answer. – Kramii Jan 9 '12 at 13:16
@Kramil, And what's that formula? Cause I agree a formula would be ideal, but I fail to see how we could develop one single formula that solves all possible inputs. – daniels Jan 9 '12 at 13:36

The algorithm in pseudocode isn't efficient, but it will find ALL cases

``````   //Create an array that stores card number,
//position, and a flag that denotes it is picked or not,
//initialize with not picked:
(1, 10 , false) , ( 2, 9, false) .....

// try to pick each item in array,
// and spawn a new sub-process tree for each possible move
trypick(ARRAY)
// try all cards one by one
for i = 1 until N
if ARRAY[i].ispicked
// just skip it if its already picked
do nothing
else
// if its pickable hurray, but we are not
// generating a sub-process tree if it is not a valid case
if ARRAY[i].number <= ARRAY[].Count(ispicked)
// pick it
ARRAY[i].ispicked = true
// spawn a new array tree for each possible
// move for the subtree generated
trypick(ARRAY)
if ARRAY[].Count(ispicked) = N
// we have picked all cards, lets ad plus one to our total
totalways++
``````
-