Merge pull request #4341 from pauloscustodio/paulo-custodio

Add C and C++ solutions to challenge 010

8 files changed, 502 insertions, 32 deletions

diff --git a/challenge-010/paulo-custodio/c/ch-1.c b/challenge-010/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..958c6684e5
--- /dev/null
+++ b/challenge-010/paulo-custodio/c/ch-1.c
@@ -0,0 +1,86 @@
+/*
+Challenge 010
+
+Challenge #1
+Write a script to encode/decode Roman numerals. For example, given Roman
+numeral CCXLVI, it should return 246. Similarly, for decimal number 39, it
+should return XXXIX. Checkout wikipedia page for more information.
+*/
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#define MAXLINE 1024
+
+int decode_roman(const char* str) {
+    int num = 0;
+    for (const char* p = str; *p; p++) {
+        switch (*p) {
+        case 'M': num += 1000; break;
+        case 'D': num += 500; break;
+        case 'C':
+            if (p[1] == 'D') { num += 400; p++; }
+            else if (p[1] == 'M') { num += 900; p++; }
+            else { num += 100; }
+            break;
+        case 'L': num += 50; break;
+        case 'X':
+            if (p[1] == 'L') { num += 40; p++; }
+            else if (p[1] == 'C') { num += 90; p++; }
+            else { num += 10; }
+            break;
+        case 'V': num += 5; break;
+        case 'I':
+            if (p[1] == 'V') { num += 4; p++; }
+            else if (p[1] == 'X') { num += 9; p++; }
+            else { num += 1; }
+            break;
+        default:
+            fprintf(stderr, "invalid roman numeral %c\n", *p);
+            exit(EXIT_FAILURE);
+        }
+    }
+    return num;
+}
+
+char* encode_roman(char* buffer, int num) {
+    buffer[0] = '\0';
+    while (num >= 1000) { strcat(buffer, "M"); num -= 1000; }
+    if (num >= 900) { strcat(buffer, "CM"); num -= 900; }
+    if (num >= 500) { strcat(buffer, "D"); num -= 500; }
+    if (num >= 400) { strcat(buffer, "CD"); num -= 400; }
+    while (num >= 100) { strcat(buffer, "C"); num -= 100; }
+    if (num >= 90) { strcat(buffer, "XC"); num -= 90; }
+    if (num >= 50) { strcat(buffer, "L"); num -= 50; }
+    if (num >= 40) { strcat(buffer, "XL"); num -= 40; }
+    while (num >= 10) { strcat(buffer, "X"); num -= 10; }
+    if (num >= 9) { strcat(buffer, "IX"); num -= 9; }
+    if (num >= 5) { strcat(buffer, "V"); num -= 5; }
+    if (num >= 4) { strcat(buffer, "IV"); num -= 4; }
+    while (num >= 1) { strcat(buffer, "I"); num--; }
+    return buffer;
+}
+
+int main(int argc, char* argv[]) {
+    char str[MAXLINE];
+
+    if (argc != 2) return EXIT_FAILURE;
+    if (strcmp(argv[1], "-test") == 0) {
+        for (int i = 1; i <= 3000; i++) {
+            int num = decode_roman(encode_roman(str, i));
+            assert(num == i);
+        }
+    }
+    else if(isdigit(argv[1][0])) {
+        int num = atoi(argv[1]);
+        encode_roman(str, num);
+        printf("%d => %s\n", num, str);
+    }
+    else {
+        int num = decode_roman(argv[1]);
+        printf("%s => %d\n", argv[1], num);
+    }
+}
diff --git a/challenge-010/paulo-custodio/c/ch-2.c b/challenge-010/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..9e949e3777
--- /dev/null
+++ b/challenge-010/paulo-custodio/c/ch-2.c
@@ -0,0 +1,96 @@
+/*
+Challenge 010
+
+Challenge #2
+Write a script to find Jaro-Winkler distance between two strings. For more
+information check wikipedia page.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define MAXLINE 1024
+
+#define MIN(a,b)    ((a)<(b)?(a):(b))
+#define MAX(a,b)    ((a)>(b)?(a):(b))
+
+float jaro_similarity(const char* s1, const char* s2) {
+    if (strcmp(s1, s2) == 0) return 1.0;    // equal strings
+
+    int len1 = strlen(s1);
+    int len2 = strlen(s2);
+
+    // max distance between matching characters
+    int max_dist = (MAX(len1, len2) / 2) - 1;
+
+    // count number of unique matches - same letters less than max_dist appart
+    int match = 0;
+    char found_s1[MAXLINE]; memset(found_s1, 0, sizeof(found_s1));
+    char found_s2[MAXLINE]; memset(found_s2, 0, sizeof(found_s2));
+
+    for (int i = 0; i < len1; i++) {
+        int min_j = MAX(0, i - max_dist);
+        int max_j = MIN(len2-1, i + max_dist);
+        for (int j = min_j; j <= max_j; j++) {
+            if (s1[i] == s2[j] && !found_s2[j]) {   // same and not already matched
+                found_s1[i] = 1;                    // mark as found
+                found_s2[j] = 1;
+                match++;
+                break;
+            }
+        }
+    }
+
+    if (match == 0) return 0.0;                     // no matches
+
+    // count transpositions : The first assigned character on one string is
+    // compared to the first assigned character on the other string.If the
+    // characters are not the same, half of a transposition has occurred.Then
+    // the second assigned character on one string is compared to the second
+    // assigned character on the other string, etc.The number of mismatched
+    // characters is divided by two to yield the number of transpositions.
+    float transp = 0.0;
+    int pos_s2 = 0;
+    for (int i = 0; i < len1; i++) {
+        if (found_s1[i]) {      // there is a match in s1, find first match in s2
+            while (!found_s2[pos_s2] && pos_s2 < len2)
+                pos_s2++;
+            if (s1[i] != s2[pos_s2++])
+                transp++;
+        }
+    }
+    transp /= 2;
+
+    float js = ((float)match / (float)len1
+        + (float)match / (float)len2
+        + ((float)match - (float)transp) / (float)match) / 3.0f;
+    return js;
+}
+
+float jaro_winkler_similarity(const char* s1, const char* s2) {
+    int len1 = strlen(s1);
+    int len2 = strlen(s2);
+
+    // find longest common prefix l
+    int l = 0;
+    while (l < MIN(4, MIN(len1, len2)) && s1[l] == s2[l])
+        l++;
+
+    // constant p
+    float p = 0.1f;
+
+    float js = jaro_similarity(s1, s2);
+    float jws = js + l * p * (1 - js);
+    return jws;
+}
+
+float jaro_winkler_distance(const char* s1, const char* s2) {
+    return 1.0f - jaro_winkler_similarity(s1, s2);
+}
+
+
+int main(int argc, char* argv[]) {
+    if (argc != 3) return EXIT_FAILURE;
+    printf("%.2f\n", jaro_winkler_distance(argv[1], argv[2]));
+}
diff --git a/challenge-010/paulo-custodio/cpp/ch-1.cpp b/challenge-010/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..ccae7f88fa
--- /dev/null
+++ b/challenge-010/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,82 @@
+/*
+Challenge 010
+
+Challenge #1
+Write a script to encode/decode Roman numerals. For example, given Roman
+numeral CCXLVI, it should return 246. Similarly, for decimal number 39, it
+should return XXXIX. Checkout wikipedia page for more information.
+*/
+
+#include <cassert>
+#include <iostream>
+#include <string>
+#include <cctype>
+using namespace std;
+
+int decode_roman(const string& str) {
+    int num = 0;
+    for (const char* p = str.c_str(); *p; p++) {
+        switch (*p) {
+        case 'M': num += 1000; break;
+        case 'D': num += 500; break;
+        case 'C':
+            if (p[1] == 'D') { num += 400; p++; }
+            else if (p[1] == 'M') { num += 900; p++; }
+            else { num += 100; }
+            break;
+        case 'L': num += 50; break;
+        case 'X':
+            if (p[1] == 'L') { num += 40; p++; }
+            else if (p[1] == 'C') { num += 90; p++; }
+            else { num += 10; }
+            break;
+        case 'V': num += 5; break;
+        case 'I':
+            if (p[1] == 'V') { num += 4; p++; }
+            else if (p[1] == 'X') { num += 9; p++; }
+            else { num += 1; }
+            break;
+        default:
+            cerr << "invalid roman numeral " << *p << endl;
+            exit(EXIT_FAILURE);
+        }
+    }
+    return num;
+}
+
+string encode_roman(int num) {
+    string str;
+    while (num >= 1000) { str += "M"; num -= 1000; }
+    if (num >= 900) { str += "CM"; num -= 900; }
+    if (num >= 500) { str += "D"; num -= 500; }
+    if (num >= 400) { str += "CD"; num -= 400; }
+    while (num >= 100) { str += "C"; num -= 100; }
+    if (num >= 90) { str += "XC"; num -= 90; }
+    if (num >= 50) { str += "L"; num -= 50; }
+    if (num >= 40) { str += "XL"; num -= 40; }
+    while (num >= 10) { str += "X"; num -= 10; }
+    if (num >= 9) { str += "IX"; num -= 9; }
+    if (num >= 5) { str += "V"; num -= 5; }
+    if (num >= 4) { str += "IV"; num -= 4; }
+    while (num >= 1) { str += "I"; num--; }
+    return str;
+}
+
+int main(int argc, char* argv[]) {
+    if (argc != 2) return EXIT_FAILURE;
+    if (string(argv[1]) == "-test") {
+        for (int i = 1; i <= 3000; i++) {
+            int num = decode_roman(encode_roman(i));
+            assert(num == i);
+        }
+    }
+    else if(isdigit(argv[1][0])) {
+        int num = atoi(argv[1]);
+        string str = encode_roman(num);
+        cout << num << " => " << str << endl;
+    }
+    else {
+        int num = decode_roman(argv[1]);
+        cout << argv[1] << " => " << num << endl;
+    }
+}
diff --git a/challenge-010/paulo-custodio/cpp/ch-2.cpp b/challenge-010/paulo-custodio/cpp/ch-2.cpp
new file mode 100644
index 0000000000..6df9e65d81
--- /dev/null
+++ b/challenge-010/paulo-custodio/cpp/ch-2.cpp
@@ -0,0 +1,94 @@
+/*
+Challenge 010
+
+Challenge #2
+Write a script to find Jaro-Winkler distance between two strings. For more
+information check wikipedia page.
+*/
+
+#include <iostream>
+#include <string>
+#include <cmath>
+using namespace std;
+
+float jaro_similarity(const string& s1, const string& s2) {
+    if (s1 == s2) return 1.0;    // equal strings
+
+    int len1 = static_cast<int>(s1.size());
+    int len2 = static_cast<int>(s2.size());
+
+    // max distance between matching characters
+    int max_dist = (max(len1, len2) / 2) - 1;
+
+    // count number of unique matches - same letters less than max_dist appart
+    int match = 0;
+    bool found_s1[len1] = {0};
+    bool found_s2[len2] = {0};
+
+    for (int i = 0; i < len1; i++) {
+        int min_j = max(0, i - max_dist);
+        int max_j = min(len2-1, i + max_dist);
+        for (int j = min_j; j <= max_j; j++) {
+            if (s1[i] == s2[j] && !found_s2[j]) {   // same and not already matched
+                found_s1[i] = true;                 // mark as found
+                found_s2[j] = true;
+                match++;
+                break;
+            }
+        }
+    }
+
+    if (match == 0) return 0.0;                     // no matches
+
+    // count transpositions : The first assigned character on one string is
+    // compared to the first assigned character on the other string.If the
+    // characters are not the same, half of a transposition has occurred.Then
+    // the second assigned character on one string is compared to the second
+    // assigned character on the other string, etc.The number of mismatched
+    // characters is divided by two to yield the number of transpositions.
+    float transp = 0.0;
+    int pos_s2 = 0;
+    for (int i = 0; i < len1; i++) {
+        if (found_s1[i]) {      // there is a match in s1, find first match in s2
+            while (!found_s2[pos_s2] && pos_s2 < len2)
+                pos_s2++;
+            if (s1[i] != s2[pos_s2++])
+                transp++;
+        }
+    }
+    transp /= 2;
+
+    float js = ((float)match / (float)len1
+        + (float)match / (float)len2
+        + ((float)match - (float)transp) / (float)match) / 3.0f;
+    return js;
+}
+
+float jaro_winkler_similarity(const string& s1, const string& s2) {
+    int len1 = static_cast<int>(s1.size());
+    int len2 = static_cast<int>(s2.size());
+
+    // find longest common prefix l
+    int l = 0;
+    while (l < min(4, min(len1, len2)) && s1[l] == s2[l])
+        l++;
+
+    // constant p
+    float p = 0.1f;
+
+    float js = jaro_similarity(s1, s2);
+    float jws = js + l * p*(1 - js);
+    return jws;
+}
+
+float jaro_winkler_distance(const string& s1, const string& s2) {
+    return 1.0f - jaro_winkler_similarity(s1, s2);
+}
+
+
+int main(int argc, char* argv[]) {
+    if (argc != 3) return EXIT_FAILURE;
+    float jwd = jaro_winkler_distance(argv[1], argv[2]);
+    jwd = round(jwd*100.0f)/100.0f;     // show 2 decimals
+    cout << jwd << endl;
+}
diff --git a/challenge-010/paulo-custodio/perl/ch-2.pl b/challenge-010/paulo-custodio/perl/ch-2.pl
index 22b9340025..a55e5512d9 100644
--- a/challenge-010/paulo-custodio/perl/ch-2.pl
+++ b/challenge-010/paulo-custodio/perl/ch-2.pl
@@ -101,4 +101,4 @@ sub max {
 }
 
 
-say jaro_winkler_distance(@ARGV);
+say sprintf("%.2f", jaro_winkler_distance(@ARGV));
diff --git a/challenge-010/paulo-custodio/t/test-1.yaml b/challenge-010/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..9b961df223
--- /dev/null
+++ b/challenge-010/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,125 @@
+- setup:
+  cleanup:
+  args:     -test
+  input:
+  output:   ""
+- setup:
+  cleanup:
+  args:     XXXIX
+  input:
+  output:   XXXIX => 39
+- setup:
+  cleanup:
+  args:     39
+  input:
+  output:   39 => XXXIX
+- setup:
+  cleanup:
+  args:     CCXLVI
+  input:
+  output:   CCXLVI => 246
+- setup:
+  cleanup:
+  args:     246
+  input:
+  output:   246 => CCXLVI
+- setup:
+  cleanup:
+  args:     DCCLXXXIX
+  input:
+  output:   DCCLXXXIX => 789
+- setup:
+  cleanup:
+  args:     789
+  input:
+  output:   789 => DCCLXXXIX
+- setup:
+  cleanup:
+  args:     MMCDXXI
+  input:
+  output:   MMCDXXI => 2421
+- setup:
+  cleanup:
+  args:     2421
+  input:
+  output:   2421 => MMCDXXI
+- setup:
+  cleanup:
+  args:     CLX
+  input:
+  output:   CLX => 160
+- setup:
+  cleanup:
+  args:     160
+  input:
+  output:   160 => CLX
+- setup:
+  cleanup:
+  args:     CCVII
+  input:
+  output:   CCVII => 207
+- setup:
+  cleanup:
+  args:     207
+  input:
+  output:   207 => CCVII
+- setup:
+  cleanup:
+  args:     MIX
+  input:
+  output:   MIX => 1009
+- setup:
+  cleanup:
+  args:     1009
+  input:
+  output:   1009 => MIX
+- setup:
+  cleanup:
+  args:     MLXVI
+  input:
+  output:   MLXVI => 1066
+- setup:
+  cleanup:
+  args:     1066
+  input:
+  output:   1066 => MLXVI
+- setup:
+  cleanup:
+  args:     MDCCLXXVI
+  input:
+  output:   MDCCLXXVI => 1776
+- setup:
+  cleanup:
+  args:     1776
+  input:
+  output:   1776 => MDCCLXXVI
+- setup:
+  cleanup:
+  args:     MCMXVIII
+  input:
+  output:   MCMXVIII => 1918
+- setup:
+  cleanup:
+  args:     1918
+  input:
+  output:   1918 => MCMXVIII
+- setup:
+  cleanup:
+  args:     MCMLIV
+  input:
+  output:   MCMLIV => 1954
+- setup:
+  cleanup:
+  args:     1954
+  input:
+  output:   1954 => MCMLIV
+- setup:
+  cleanup:
+  args:     MMXIV
+  input:
+  output:   MMXIV => 2014
+- setup:
+  cleanup:
+  args:     2014
+  input:
+  output:   2014 => MMXIV
diff --git a/challenge-010/paulo-custodio/t/test-2.yaml b/challenge-010/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..d9f57f08d4
--- /dev/null
+++ b/challenge-010/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,15 @@
+- setup:
+  cleanup:
+  args:     DwAyNE DuANE
+  input:
+  output:   0.16
+- setup:
+  cleanup:
+  args:     TRATE  TRACE
+  input:
+  output:   0.09
+- setup:
+  cleanup:
+  args:     arnab  aranb
+  input:
+  output:   0.05
diff --git a/challenge-010/paulo-custodio/test.pl b/challenge-010/paulo-custodio/test.pl
index b764bf5b59..ba6c37260b 100644
--- a/challenge-010/paulo-custodio/test.pl
+++ b/challenge-010/paulo-custodio/test.pl
@@ -1,32 +1,4 @@
-#!/usr/bin/perl
-
-use strict;
-use warnings;
-use 5.030;
+#!/usr/bin/env perl
+use Modern::Perl;
 use Test::More;
-
-ok 0==system("perl perl/ch-1.pl -test");
-
-for ([XXXIX => 39], [CCXLVI => 246], [DCCLXXXIX => 789], [MMCDXXI => 2421],
-     [CLX => 160], [CCVII => 207], [MIX => 1009], [MLXVI => 1066],
-     [MDCCLXXVI => 1776], [MCMXVIII => 1918], [MCMLIV => 1954], [MMXIV => 2014]) {
-    my($roman, $arabic) = @$_;
-
-    is capture("perl perl/ch-1.pl $roman"),     "$roman => $arabic\n";
-    is capture("perl perl/ch-1.pl $arabic"),    "$arabic => $roman\n";
-}
-
-is capture("perl perl/ch-2.pl DwAyNE DuANE"),   "0.16\n";
-is capture("perl perl/ch-2.pl TRATE  TRACE"),   "0.0933333333333333\n";
-is capture("perl perl/ch-2.pl arnab  aranb"),   "0.0533333333333335\n";
-
-
-done_testing;
-
-
-sub capture {
-    my($cmd) = @_;
-    my $out = `$cmd`;
-    $out =~ s/[ \r\t]*\n/\n/g;
-    return $out;
-}
+require '../../challenge-001/paulo-custodio/test.pl';