Olimex Week #69 Programming Challenge

/******Weekend Programming Challenge Week #69 Levenshtein Distance**************************/

https://github.com/OLIMEX/WPC/blob/master/ISSUE-69/SOLUTION-2/Levenshtein2.ino

Problem:

Levenshtein Distance  is string metrics for measuring the difference between two sequences. Make code which inputs two strings and calculate Levenshtein Distance between them.

My solution for Arduino:

/*

Weekend Programming Challenge – Week #69 Levenshtein Distance

Problem:

Levenshtein Distance  is string metrics for measuring the difference between two sequences.

Make code which inputs two strings and calculate Levenshtein Distance between them.

Code based on: http://www.lemoda.net/c/levenshtein/

and modified for Arduino by: Javier Vela

What is Levenshtein Distance?

Levenshtein distance (or edit distance) between two strings is the number of deletions, insertions, or substitutions required to transform source string into target string.

For example, if source is "book" and target is "back", to transform "book" to "back" you will need to change first "o" to "a", second "o" to "c", without additional deletions and insertions, thus, levenshtein distance will be 2.

Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965.

This has a wide range of applications, for instance, spell checkers, correction systems for optical character recognition, etc.

You can find more information in: http://es.wikipedia.org/wiki/Distancia_de_Levenshtein

*/

void setup()

{

  String palabra1, palabra2;

  int len1, len2, d;

  Serial.begin(9600);

  Serial.println("Welcome Levenshtein calculator");

  Serial.println("\nPlease, insert the first word: ");

  while (!Serial.available()) //Wait until something is written in the serial port

  delay(100);

  while (Serial.available() > 0)//Reading the message from the serial port

      palabra1.concat((char)Serial.read());

  Serial.print(" -The first word is: "); Serial.println(palabra1);

  len1 = palabra1.length();

  Serial.print(" -Length: "); Serial.println(len1);

  Serial.println("\nPlease, insert the second word: ");

  while (!Serial.available()) //Wait until something is written in the serial port   

  delay(100);

  while (Serial.available() > 0)//Reading the message from the serial port

      palabra2.concat((char)Serial.read());

  Serial.print(" -The second word is: "); Serial.println(palabra2);

  len2 = palabra2.length();

  //len2 = strlen (word2);

  Serial.print(" -Length: "); Serial.println(len2);

  d = distance (palabra1, len1, palabra2, len2);

  Serial.print ("\nLevenshtein Distance between '"+palabra1+"' and '"+palabra2 + " is: " +d);

}

void loop()

{

}

static int distance (String palabra1, int len1, String palabra2, int len2)

{

  int matrix[len1 + 1][len2 + 1];

  int i;

  for (i = 0; i <= len1; i++)    matrix[i][0] = i;

  for (i = 0; i <= len2; i++)    matrix[0][i] = i;

  for (i = 1; i <= len1; i++)

  {

    int j;

    char c1;

    c1 = palabra1.charAt(i-1);

    for (j = 1; j <= len2; j++)

    {

      char c2;

      c2 = palabra2.charAt(j-1);

      if (c1 == c2)

      {

        matrix[i][j] = matrix[i - 1][j - 1];

      }

      else

      {

        int delet = matrix[i - 1][j] + 1;

        int insert = matrix[i][j - 1] + 1;

        int substitute = matrix[i - 1][j - 1] + 1;

        int minimum = delet;

        if (insert < minimum)      minimum = insert;

        if (substitute < minimum)  minimum = substitute;

        matrix[i][j] = minimum;

      }

    }

  }

  return matrix[len1][len2];

}

Olimex Week #43 Programming Challenge

/******Weekend Programming Challenge – Week #43 Bank Card validation *********/

http://olimex.wordpress.com/2014/02/18/weekend-prorgamming-challenge-week-43-solutions/

Problem:

Bank card numbers are not random, they carry information for the card processor (Visa/Mastercard etc), bank which issued the card, the account and checksum. More on the subject is available at http://en.wikipedia.org/wiki/Bank_card_number

Make code which enters card number and validate it i.e. writes VALID or INVALID number has been entered.

My solution for Arduino:

//Test number:1234567812345670->ok;1234567812345678-NOK

int test;

void setup()

{

  Serial.begin(9600);

  Serial.println("This program valid or invalid the code of a credit card number, according with the Luhn Method.");

  Serial.println("Please Write your credit card number in the serial monitor and push enter.\n");

}

void loop()

{  

  String CardNumber="";

  if(Serial.available())//Wait until something is writen in the serial port

  { //Reading the message from the serial port  

    delay(100);

    while(Serial.available()>0)  CardNumber.concat((char)Serial.read());

 

    Serial.print("Card Number introduced: "); Serial.println(CardNumber);

    test=luhn(CardNumber);  

   

    Serial.print("The number: ");

    Serial.print(CardNumber);

    if(test==0) Serial.println(" is VALID.");

    else Serial.println(" is INVALID.");

    Serial.println();

  } 

}

/************************************************************************************************************

The Luhn test is used by some credit card companies to distinguish valid credit card numbers from what could be a random selection of digits.

Those companies using credit card numbers that can be validated by the Luhn test have numbers that pass the following test:

   1. Reverse the order of the digits in the number.

   2. Take the first, third, ... and every other odd digit in the reversed digits and sum them to form the partial sum s1

   3. Taking the second, fourth ... and every other even digit in the reversed digits:

      1. Multiply each digit by two and sum the digits if the answer is greater than nine to form partial sums for the even digits

      2. Sum the partial sums of the even digits to form s2

   1. If s1 + s2 ends in zero then the original number is in the form of a valid cre

************************************************************************************************************/

int luhn(String number)

{

 int numberlength=number.length();

 char charBuf[numberlength+1];//I add one more because I've to take account the end of string('\0')

 char copyBuf[numberlength+1];

 int odd=0,even=0,sum=0,checkdigit=0;//Variable that help me in the the process of calculation the validation number

 //String to char array

 number.toCharArray(charBuf,numberlength+1);//This array has the account number in char

 Serial.print("Reverse the order of the digits: ");

 for(int i=0;i<numberlength;i++)

 {

   copyBuf[i]=charBuf[numberlength-1-i];

   Serial.print(copyBuf[i]);

 }

 Serial.println("\n'Double the digits in the odd position of the array and if they are bigger than 9 I must sum the two digits between them.'");

 Serial.print("Array of digits: ");

 for(int i=0;i<numberlength;i++)

 {    

    if(i%2!=0)

    {

       odd=(((int)copyBuf[i])-48)*2;//I sustract 48 for passing char to int according to the ASCII table

       if(odd>9)        odd=1+(odd-10);

       copyBuf[i]=odd;

       Serial.print(odd);

       sum+=odd;

    }

    else

    {

      even=((int)copyBuf[i]-48);//char to int

      copyBuf[i]=even;

      Serial.print(even);

      sum+=even;

    }

 }

 Serial.print("\nSum of all these digits: "); Serial.println(sum);

 Serial.print("Multiply the sum by 9: "); Serial.println(sum*=9);

 checkdigit=sum%10;

 Serial.print("The last digit is the check digit: "); Serial.println(checkdigit);

 Serial.println("The check digit must be 0 for be valid,else will be invalid");

 return checkdigit;

}