Bits of Discovery

Stuff I Like to Learn About

Wildcard Programming Challenge

I came across a neat programming question at a tech company called WildCard and decided and I’d take a crack at it in C. The idea here is pretty simple using some basic combinatorics. If you have fewer than 5 available spots in any given row/column, clearly you can’t place 5 cards there. However, if you have >= 5 open spots, you can do the following: place the cards in (EmptySpots choose 5) places, and once you’ve placed them there, you can shuffle the cards in those 5 places in 5! ways. So when you multiply these together you get the number of possibilities for a single row or column. All we have to do now is iterate over the table and sum these values up! Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 50
#define NUM_CARDS 5

int fact(int n){
  int i;
  for(i=n- 1; i>0; i--){
    n *= i;
  }

  return n;
}

int nck(int n, int k){
  if(n < k) {
    return 0;
  }
  else if(n == k) {
    return 1;
  }
  int sol = fact(n) / (fact(k) * fact(n-k));
  return sol;
}

int main(){
  char ch;
  FILE *fp = fopen("problem1input.txt", "r");

  int cols[TABLE_SIZE];
  memset(cols, 0, TABLE_SIZE * sizeof(int));

  int answer = 0;
  int num_empty = 0;

  int i;
  int j;

  for(i = 0; i < TABLE_SIZE; i++){
    for(j = 0; j < TABLE_SIZE; j++){
      fscanf(fp, "%c", &ch);
      if (ch == '*') {
        cols[j]++;
        num_empty++;
      }
    }
    fscanf(fp, "%c", &ch);
    answer += nck(num_empty, NUM_CARDS);
    num_empty = 0;
  }
  fclose(fp);

  for(j = 0; j < TABLE_SIZE; j++){
    answer += nck(cols[j], NUM_CARDS);
  }

  //120 is the number of ways I can arrange the 5 cards in 5 spots, ie 5!
  printf("%d\n", answer * 120);
  return 0;
}

And if you’re interested in the answer, there are a whopping 167,160 ways to do this! Crazy how numbers work.