Sudoku

/* Su-Doku solver */

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

#define MAX 9

struct _nextS
{
   int res ;
   int r ;
   int c ;
} nextS[MAX][MAX] ;

int s[MAX][MAX], o[MAX][MAX] ;
int n=3, N=9, nosolution,
   first_r, first_c ; /*first non-zero (row,col) with the least number of possible candidates */

void print(void)
{
   int i, j ;

   for (i=0; i<N; i++) {
      printf("%d", s[i][0]) ;
      for (j=1; j<N; j++)
         printf(" %d", s[i][j]) ;
      printf("\n") ;
   }

   printf("\n") ;
}

int canbefilled(int r, int c, int nextD)
{
   int ans, si, sj, i, j ;

   if (r>=0&&r<=2) si = 0 ;
   else if (r>=3&&r<=5) si = 3 ;
   else if (r>=6&&r<=8) si = 6 ;

   if (c>=0&&c<=2) sj = 0 ;
   else if (c>=3&&c<=5) sj = 3 ;
   else if (c>=6&&c<=8) sj = 6 ;

   ans = nextD ;

   for (i=0; i<N; i++)
      if (s[r][i] == nextD)
         ans=0 ;

   for (i=0; i<N; i++)
      if (s[i][c] == nextD)
         ans=0 ;

   for (i=si; i<si+n; i++)
      for (j=sj; j<sj+n; j++)
         if (s[i][j] == nextD)
            ans=0 ;

   return ans ;
}

int compute_possible_candidates(void)
{
   int i, j, nextD, k, min=10, d, ans=0 ;

   for (i=0; i<N; i++) {
      for (j=0; j<N; j++) {
         if (o[i][j]==0) {
            k = 0 ;
            for (nextD=1; nextD<=9; nextD++) {
               if (canbefilled(i, j, nextD)) {
                  d = nextD ;
                  k++ ;
               }
            }

            if (k==1) {
               o[i][j] = d ;
               s[i][j] = d ;
               ans = 1 ;
            }
            else if (k<min) {
               min = k ;
               first_r = i ;
               first_c = j ;
            }
         }
      }
   }

   return ans ;
}

/* Return the next square which is not originally filled */
int getnext(int *nr, int*nc)
{
   int r, c ;

   if (*nc==N) {
      *nr = *nr+1 ;
      *nc=0 ;
   }

   if (*nr==N)
      *nr=0 ;

   for (r=*nr; r<N; r++) {
      for (c=*nc; c<N; c++)
         if (o[r][c]==0)
         {
            *nr = r ;
            *nc = c ;
            return 1 ;
         }
      *nc = 0 ;
   }

   for (r=0; r<N; r++) {
      for (c=0; c<N; c++)
         if (o[r][c]==0)
         {
            *nr = r ;
            *nc = c ;
            return 1 ;
         }
      *nc = 0 ;
   }

   return 0 ;
}

int nf ;
int fillpos(int r, int c)
{
   int i, j, ans, nextD, nr, nc ;
   nf++ ;
   do {
      for (nextD=(s[r][c]?s[r][c]:1); nextD<=N; nextD++)
         if (canbefilled(r, c, nextD)) {
            s[r][c] = nextD ;
            break ;
         }

      if (nextD>N) {
         if (r==first_r && c==first_c) {
         /* We tried everything, backtracking every path.
            Now even first_r,first_c can't be filled */
            nosolution = 1 ;
            return 1 ;
         }
         s[r][c] = 0 ;
         return 0 ;
      }

      if (nextS[r][c].res==0)
         return 1 ;
      else {
         nr = nextS[r][c].r ;
         nc = nextS[r][c].c ;
      }

      ans = fillpos(nr, nc) ;
   }
   while (!ans);

   return 1 ;
}

int main()
{
   int i, j, a, b, cases ;

   freopen("sudoku.in", "r", stdin) ;
   freopen("sudoku.out", "w", stdout) ;

   scanf("%d", &cases) ;
   while (cases--) {
      for (i=0; i<N; i++)
         for (j=0; j<N; j++) {
            scanf("%d", &s[i][j]) ;
            o[i][j] = s[i][j] ;
            nextS[i][j].res = 0 ;
         }

      first_r = first_c = 0 ;
      while (compute_possible_candidates()) ;

      i = first_r ;
      j = first_c ;
      a = first_r ;
      b = first_c + 1 ;
      while (getnext(&a, &b)) {
         if (a==first_r && b==first_c)
            break ;

         nextS[i][j].res = 1 ;
         nextS[i][j].r = a ;
         nextS[i][j].c = b ;
         i = a ;
         j = b ;
         b = b+1 ;
      }

      a = first_r ;
      b = first_c ;
      nosolution = 0 ;
      if (getnext(&a, &b))
         fillpos(a, b) ;
      if (nosolution)
         printf("NO SOLUTION\n") ;
      else print() ;
   }

   return 0;
}

/* sudoku.in */

1

0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0

Binary Search Tree

/* Binary Search Tree */

/* @BEGIN_OF_SOURCE_CODE */

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

struct tree_node
{
     struct tree_node *left ;
     struct tree_node *right ;
     struct tree_node *parent ;
     int key ;
};

typedef struct tree_node *TREENODEPTR ;

TREENODEPTR bst_search(TREENODEPTR r, int k)
{
     while (r != NULL && k != r->key)
          if (k < r->key)     r = r->left ;
          else r = r->right ;

     return r ;
}

/* 
     r : points to root of the tree
     n : pointer to the new node to be inserted
*/
void bst_insert(TREENODEPTR *r, TREENODEPTR n)
{
     TREENODEPTR p = NULL ;
     TREENODEPTR x = *r ;

     while (x != NULL) {
          p = x ;
          if (n->key < x->key)
               x = x->left ;
          else x = x->right ;
     }

     n->parent = p ;
     if (p == NULL)
          *r = n ;
     else if (n->key < p->key)
          p->left = n ;
     else p->right = n ;
}

void clear(TREENODEPTR r)
{
   if (r==NULL)
      return ;

   if (r->left) clear(t, r->left) ;
   if (r->right) clear(t, r->right) ;

   free(r) ;
}

int main()
{
     int n ;
     TREENODEPTR root, tmp ;

     #ifndef ONLINE_JUDGE
     freopen("bst.in", "r", stdin) ;
     #endif

     root = NULL ;

     while (scanf("%d", &n) != EOF) {
          if ((tmp = bst_search(root, n)) == NULL) {
               tmp = (TREENODEPTR) malloc(sizeof(struct tree_node)) ;
               tmp->key = n ;
               tmp->left = NULL ;
               tmp->right = NULL ;
               tmp->parent = NULL ;
               bst_insert(&root, tmp) ;
          }
          else {
               printf("Element [%d] already exists\n", n) ;
          }
     }

     if (root) {
          clear(root) ;
          free(root) ;
     }

     return 0;
}

/* @END_OF_SOURCE_CODE */

Difference in time

/* 
   Returns difference in time between a given start hour, 
   start min and end hour and end min 
*/

int difftime(int sh, int sm, int eh, int em)
{
   int s, e ;
   s = 60*(sh-0) + sm ;
   e = 60*(eh-0) + em ;
   e -=s ;

   if (e < 0)
   e += 60 * 24 ;
   return e ;
}

Josephus Problem

Given n (number of people) and m (every mth person eliminated), this code returns the index of the last person to be eliminated.

Josephus on wiki
Josephus on Wolfram MathWorld

/* Josephus Problem */

#include <stdio.h>

#define CAL_UPTO     100000

int cq[CAL_UPTO + 1] ;

/* count e from p and return new p */
int move(int e, int p, int left, int n)
{
     if (e==0) e=left ;

     while (e>0) {
          if (p>n) p = 1 ;
          if (cq[p]==1) e-- ;
          p++ ;
     }

     if (--p>n) p=1 ;
     return p ;
}

/* out of n persons, eliminate every mth person */
/* returns the last survisor */
int compute(int n, int m)
{
     int i, p=1, e, left=n, j ;

     for (j=1; j<=n; j++) cq[j] = 1 ;

     while (left) {
          e = m%left ;
          p = move(e, p, left, n) ;
          if (!(p==0 || cq[p]==0)) cq[p] = 0, left-- ;
     }
     return p ;
}

int main()
{
     int i, j, n, k ;

     scanf("%d%d", &n, &k) ;
     printf("Survivor: %d\n", i, compute(n, k)) ;

     return 0;
}

Prime Number Generator

The function sieveOfAtkin() generates all primes numbers up to (less than) the integer PRIMES_UPTO.

For an explanation of Sieves of Atkin method, see here. Also see Sieve of Eratosthenes of which Sieve of Atkins is an optimized version.

#include <stdio.h>
#include <math.h>

#define PRIMES_UPTO     100

int list[PRIMES_UPTO+1]={0,0,1,1},n;
int primes[PRIMES_UPTO] ;

/* flip() and clean() are supporting routines called by sieveOfAtkin()
*/
int flip(void)
{
     if (list[n]==1) list[n]=0;
     else list[n]=1;
     return 0;
}

int clean(int n, int upto)
{
     int k,l=n*n,i;
     for (i=2,k=l;k<=upto;i++,k=i*l) list[k]=0;
     return 0;
}

/* Generates prime numbers upto the integer specified by PRIMES_UPTO.
    Stores the result in the array primes[] and returns index of the
    last prime number in the sequence.
*/
int sieveOfAtkin(void)
{
     int i, j, x, y, d_limit;

     d_limit=(int)(sqrt((float) PRIMES_UPTO));

     for (i=5;i<=PRIMES_UPTO;i++) list[i]=0;

     for (x=1;x<=d_limit;x++) {
         for (y=1;y<=d_limit;y++) {
             n=4*(x*x)+(y*y);
             if (n <= PRIMES_UPTO && (n % 12 == 1 || n % 12 == 5)) flip();

             n=3*(x*x)+(y*y);
             if (n <= PRIMES_UPTO && n % 12 == 7) flip();

             n=3*(x*x)-(y*y);
             if (x>y && n <= PRIMES_UPTO && n % 12 == 11) flip();
         }
     }

     for (n=5;n<=d_limit;n++) {
         if (list[n]) clean(n,PRIMES_UPTO);
     }

     for (i=2, j=0;i<=PRIMES_UPTO;i++) {
         if (list[i]) primes[j++] = i ;
     }

     return j-1 ;
}

int main()
{
     int i, k ;

     printf("Prime numbers between 0 and %d:\n", PRIMES_UPTO) ;
     k = sieveOfAtkin() ;
     for (i=0; i<=k; i++)
          printf("%d\n", primes[i]) ;

     return 0;
}

Maximum 1-D Sum

#include <stdio.h>
#define MAX_N     100

int dp_max(int a, int b)
{
     return (a > b) ? a : b ;
}

/*
  * Problem - Maximum Value Contiguous Subsequence / Maximum 1-D sum
  * From a sequence of n integers a(1) ... a(n), determine a 
  * contiguous sub-sequence a(i) ... a(j) having the maximum sum of 
  * its elements.
  *
*/
int dp_max_contiguous_subseq(int *arr, int len)
{
     int i, j, m[MAX_N], max,
          s=0,     /* index of start of the sub-sequence */
          e=0 ;     /* index of end of the sub-sequence */

     if (arr[0]<0) max = 0 ;
     else max = arr[0] ;

     for (m[0]=arr[0], j=1; j<len; j++) {
          m[j] = dp_max(m[j-1]+arr[j], arr[j]) ;
          if (m[j]>=max) {
               max = m[j] ;
               e = j ;
               if (m[j] == arr[j])
                    s = j ;
          }
     }

     printf("\n\nMax Contiguous Sequence starts@ %d and ends@ %d and sums to %d\n", s, e, max) ;

     return max ;
}

int main()
{
     int i, arr[MAX_N] ;

     #ifndef ONLINE_JUDGE
     freopen("dp_max_contiguous_subseq.in", "r", stdin) ;
     #endif

     i = 0 ;
     while (scanf("%d", &arr[i]) != EOF) i++ ;
     dp_max_contiguous_subseq(arr, i) ;

     return 0;
}

Useful Bit-manipulation Functions

/* Function to print binary representation of a number */
void printBinary(int n)
{
     int i ;
     for (i=31; i>=0; i--)
          printf("%d", ((1<<i & n))?1:0) ;
     printf("\n") ;
}

/* Function to get 2's complement of a number */
int get2scomplement(int n)
{
     int i, k=0 ;
     for (i=0; i<32; i++)
          k |= ~(1<<i | n) ;
     k+=1 ;

     return k ;
}