Password recovery puzzle – my solution in C language

Standard

Recently, I went through a programming competition “Password Recovery Puzzle” hosted on GILD, provides you with unique tools to certify your skills, find great jobs, and advance your career all while competing and sharing with friends and peers. The details of the competition can be found at Coderloop.

Basically, the problem was to restore a password from a file that had the encrypted password using crypt(3) in the first line and lines of texts starting from the second line that contains two words those will generate the password by having a number ( 0, 2, 4 or 8 ) within them. The input files were in ASCII. The program should output the decoded password with a newline character.

I want to share the code that I wrote using C and here it is.

/*
 * passrecovery.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <search.h>

char *content=NULL, *encrypted_pass=NULL, *tempstr=NULL;
char salt[3];
char *glue[] = {"0","2","4","8"};
char **wordslist;
size_t word_array_length = 0;
int var; // general purpose variable

char *strtolower(char *str) {
  for(var=0; str[var]; var++) str[var] = tolower(str[var]);
  return str;
}

int compare(char** s1, char** s2) {
  return (strcmp(*s1, *s2));
}

int is_duplicate() {
  return lfind(&content, wordslist, &word_array_length,
                sizeof(char*), (int (*)(const void *, const void *)) compare) ? 0 : 1;
}

int is_correct_password(char *word1, char *word2) {
  var = strlen(word1) + strlen(word2);
  if (var < 4 || var > 7) { return 1; }
  int counter;
  tempstr = (char*) malloc(9*sizeof(char));
  for(var=0; var<4; var++) {
    for(counter = 0; counter < 2; counter++) {
      if (counter == 0) {
        sprintf(tempstr, "%s%s%s", word1, glue[var], word2);
      }
      else {
        sprintf(tempstr, "%s%s%s", word2, glue[var], word1);
      }
      if(strcmp(crypt(tempstr, salt), encrypted_pass) == 0) {
        printf("%s\n", tempstr); free(tempstr);
        return 0;
      }
    }
  }
  free(tempstr); return 1;
}

void scan_for_password(void) {
  qsort(wordslist, word_array_length, sizeof(char*), 
         (int (*)(const void *, const void *)) compare);
  int left = 0, right = word_array_length - 1, oleft=left;
  while (left < word_array_length) {
    if (is_correct_password(wordslist[left], wordslist[right]) == 0) {
      return;
    }
    if (right - left == 1) {
      left += 2; right = word_array_length - 1;
    }
    else if (left > right) {
      right = left - 1; left = oleft;
    }
    else {
      oleft = left; left = right; right = oleft + 1;
    }
  }
  return;
}

void tokenize(void) {
  encrypted_pass = strtok_r(content, "\n", &tempstr);
  strncpy(salt, encrypted_pass, 2);
  wordslist = (char**) malloc(sizeof(char*));
  for
    (
      content = strtok_r(strtolower(tempstr), " \n,'-.!:;0123456789(){}[]", &tempstr);
      content != NULL;
      content = strtok_r(NULL, " \n,'-.!:;0123456789(){}[]", &tempstr)
    ) {
    if (strlen(content) < 7 && is_duplicate()==1) { // remove all strings more than 7 characters
      if (word_array_length > 0) {
        wordslist = (char**) realloc(wordslist, (word_array_length+1) * sizeof(content));
      }
      wordslist[word_array_length++] = content;
    }
  }
  free(content);
  return;
}

int main(int argc, char **argv) {
  // accept only one parameter
  if (argc > 2 || argc < 2) {
    printf("Usage: %s path/to/filename\n", *argv);
    return 1;
  }

  // read the entire file
  FILE *fp = fopen(argv[1],"r");
  if(fp == NULL) { exit(-1); }
  fseek(fp, 0, SEEK_END);
  var = ftell(fp);
  rewind(fp);
  content = (char*) malloc((var)*sizeof(char));
  fread(content,1,var,fp);
  fclose(fp);

  tokenize();
  scan_for_password();
  free(wordslist);
  return 0;
}

For more formatted code, get it from Pastebin.

This code gave me 662 out of 800 in the competition. I would like to have your views on how to improve this script to execute it faster and with lesser memory consumption.

Advertisements

I will be happy to answer your queries

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s