Number of ways decoding a message

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ => 1
‘B’ => 2
…
‘Z’ => 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example, given encoded message “12″, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12″ is 2.

Solution:

1. Find all the subsets where we have 1 and 2 in the sequence continuously and keep the counts of total no of elements in each subset.
   • If the next element is 0 and count is more than 1, subtract the count by 1
   • Else increase the count by 1
2. find the fibonacci number for each count [0]=1 [1]=1 [2]=2 [3]=3 ...
3. Multiply all the fibonacci numbers gives the result

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

int main (int argc, char **argv)
{
  int length = strlen(argv[1]);
  char *result = (char *) calloc (length + 1, sizeof (char));
  int noofways = 1;

  int *fibonacci = (int *) calloc (length, sizeof(int));
  *fibonacci = 1;
  *(fibonacci+1) = 2;

  for (int i=2; i<length; i++)
  {
    *(fibonacci+i) = *(fibonacci+i-1) + *(fibonacci+i-2);
  }

  for (int i=1; i<=26; i++)
  {
    printf ("[%c:%d] ", 'A'+i-1, i);
  }
  printf ("\n");


  char *input = argv[1];

  while (*input != '\0')
  {
    if (*input >= '1' && *input <='2')
    {
      int count = 0;
      for (;*input >= '1' && *input <='2'; input++, count++)
        ;
      if (*input != '\0')
      {
        if ((*(input-1) == '1' && *input >= '1' && *input <= '9') ||
            (*(input-1) == '2' && *input >= '1' && *input <= '6'))
        {        
          count++;
        }
        else if ((*(input-1) == '1' && *input == '0') ||
                 (*(input-1) == '2' && *input == '0'))
        {
          count--;
          if (count == 0)
            count = 1;
        }
      }
      else if (*input == '\0')
      {
        noofways = noofways * *(fibonacci+count-1);
        break;
      }
      noofways = noofways * *(fibonacci+count-1);
    }
    else if (*input == '0')
    {
      noofways = 0;
      break;
    }
    input++;
  }
  printf ("No of ways: %d\n", noofways);
  return 0;
}

Code to get all the decoded strings
Function call: {decode (input, result, 0);}
[input]   => Input String
[output] => Temporary buffer to form the decoded string
[index]   => Index to decoded character

typedef enum boolean { FALSE=0, TRUE=1}bool;

bool decode (char *input, char *output, int index)
{
  static int count = 0;
  if (*input == '\0')
  {
    *(output+index) = '\0';
    count++;
    printf ("%-4d%s\n", count, output);
    return TRUE;
  }
  else if (*input == '0')
  {
    return FALSE;
  }
  else if ((*input == '1' && *(input+1) == '0') ||
           (*input == '2' && *(input+1) == '0'))
  {
    *(output+index) = 'A' + ((*input - '0') * 10) - 1;
    return decode (input+2, output, index+1);
  }
  else
  {
    *(output+index) = 'A' + (*input - '1');
    decode (input+1, output, index+1);
    
    if ((*input == '1' && *(input+1) >= '1' && *(input+1) <= '9') ||
        (*input == '2' && *(input+1) >= '1' && *(input+1) <= '6'))
    {
      *(output+index) = 'A' + (*input - '0') * 10 + *(input+1) - '0' - 1;
      decode (input+2, output, index+1);
    }
  }

  return TRUE;
}

Prime numbers

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <string.h>
#include <errno.h>

#define ERRNUM -1

typedef enum bool {
  FALSE =0,
  TRUE
} e_bool;

typedef enum stauts {
  FAILURE = 0,
  SUCCESS
} e_status;

typedef struct list* tsp_list;
struct list{
  unsigned int val;
  unsigned int index;
  tsp_list next;
};

e_status Append (unsigned int num, tsp_list *list)
{
  tsp_list lsp_primeNode = NULL;
  lsp_primeNode = (tsp_list) calloc (1, sizeof (struct list));
  if (NULL == lsp_primeNode)
  {
    fprintf (stderr, "ERROR: memory allocation failed.\n");
    return FAILURE;
  }
  lsp_primeNode->val = num;
  lsp_primeNode->next = NULL;

  if (NULL == *list)
  {
    *list = lsp_primeNode;
    lsp_primeNode->index = 1;
  }
  else
  {
    tsp_list node = *list;
    while (NULL != node->next)
    {
      node = node->next;
    }

    node->next = lsp_primeNode;
    lsp_primeNode->index = node->index + 1;
  }

  return SUCCESS;
}


e_bool IsPrime (unsigned int num, tsp_list list)
{
  if (1 >= num)
  {
    return FALSE;
  }

  switch (num)
  {
    case 2:
    case 3:
      return TRUE;
    default:
      {
        unsigned int lv_max_limit = (unsigned int) sqrt (num);
        
        while (list && list->val <= lv_max_limit)
        {
          if (0 == num % list->val)
          {
            return FALSE;
          }
          list = list->next;
        }
        return TRUE;
      }
  }
}

void GetPrimeList (tsp_list *list, unsigned count)
{
  unsigned int i = 2;
  unsigned int index = 1;
  struct timeval start;
  struct timeval end;
  struct timeval diff;

  if(-1 == gettimeofday(&start, NULL))
  {
    fprintf (stderr, "ERROR: %s\n", strerror (errno));
    return;
  }

  for (; i && 0 < count; i++)
  {
    if (TRUE == IsPrime (i, *list))
    {
      if(-1 == gettimeofday(&end, NULL))
      {
        fprintf (stderr, "ERROR: %s\n", strerror (errno));
        return;
      }

      /* Ref [http://www.linuxquestions.org/questions/programming-9/how-to-calculate-time-difference-in-milliseconds-in-c-c-711096] */
      diff.tv_sec =end.tv_sec - start.tv_sec ;
      diff.tv_usec=end.tv_usec - start.tv_usec;

      if(diff.tv_usec<0)
      {
        diff.tv_usec+=1000000;
        diff.tv_sec -=1;
      }

      printf ("%d (index: %d) (Time taken: %f sec)\n", i, index++, (float)(1000000LL*diff.tv_sec + diff.tv_usec)/1000000);
      
      if (FAILURE == Append (i, list))
      {
        return;
      }
      else
      {
        count --;
      }
    }
  }
}

int main (int argc, char *argv[])
{
  tsp_list primeList = NULL;
  int dig = 0;

  if ( 2 != argc)
  {
    return 0;
  }

  GetPrimeList (&primeList, (int) atoi(argv[1]));

  return 0;
}