Add C solution

3 files changed, 522 insertions, 0 deletions

diff --git a/challenge-019/paulo-custodio/c/ch-1.c b/challenge-019/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..f943e6d6cc
--- /dev/null
+++ b/challenge-019/paulo-custodio/c/ch-1.c
@@ -0,0 +1,47 @@
+/*
+Challenge 019
+
+Task #1
+Write a script to display months from the year 1900 to 2019 where you find
+5 weekends i.e. 5 Friday, 5 Saturday and 5 Sunday.
+
+Solution: 4 weeks are 28 days, to have 5 week-ends we need additional 3 days
+(29,30,31),
+therefore 31st must be a Sunday
+*/
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdbool.h>
+
+enum { Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday };
+
+int day_of_week(int y, int m, int d) {
+    return (d += m < 3 ? y-- : y - 2, 23*m/9 + d + 4 + y/4- y/100 + y/400)%7;
+}
+
+bool is_leap_year(int y) {
+    return y%400==0 ? true : y%100==0 ? false : y%4==0 ? true : false;
+}
+
+int days_of_month(int y, int m) {
+    switch (m) {
+        case 1: case 3: case 5: case 7: case 8: case 10: case 12: return 31;
+        case 4: case 6: case 9: case 11: return 30;
+        case 2: return is_leap_year(y) ? 29 : 28;
+        default: assert(0);
+    }
+}
+
+bool five_weekends(int y, int m) {
+    return days_of_month(y, m) == 31 && day_of_week(y, m, 31) == Sunday;
+}
+
+int main() {
+    for (int y = 1900; y <= 2019; y++) {
+            for (int m = 1; m <= 12; m++) {
+                if (five_weekends(y, m))
+                    printf("%04d-%02d\n", y, m);
+            }
+    }
+}
diff --git a/challenge-019/paulo-custodio/c/ch-2.c b/challenge-019/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..edb7ffcea7
--- /dev/null
+++ b/challenge-019/paulo-custodio/c/ch-2.c
@@ -0,0 +1,68 @@
+/*
+Challenge 019
+
+Task #2
+Write a script that can wrap the given paragraph at a specified column using
+the greedy algorithm.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "utstring.h"
+
+#define WRAP_COLUMN     72
+#define BLANKS          " \t\r\n\v\f"
+
+void read_text(UT_string* text, const char* file) {
+    utstring_clear(text);
+
+    FILE* fp = fopen(file, "r");
+    if (fp == NULL) {
+        perror(file);
+        exit(EXIT_FAILURE);
+    }
+
+    char line[BUFSIZ];
+    while (fgets(line, sizeof(line), fp)) {
+        utstring_printf(text, "%s ", line);
+    }
+
+    fclose(fp);
+}
+
+void wrap_text(UT_string* result, char* text, int column) {
+    utstring_clear(result);
+    int pos = 0;
+    const char* word = strtok(text, BLANKS);
+    while (word != NULL) {
+        if (pos + 1 + strlen(word) >= column) {
+            utstring_printf(result, "\n%s", word);
+            pos = strlen(word);
+        }
+        else {
+            utstring_printf(result, " %s", word);
+            pos += 1 + strlen(word);
+        }
+
+        word = strtok(NULL, BLANKS);
+    }
+}
+
+int main(int argc, char* argv[]) {
+    if (argc != 2) {
+        fputs("usage: ch-2 file\n", stderr);
+        return EXIT_FAILURE;
+    }
+
+    UT_string* text;
+    utstring_new(text);
+    UT_string* wrapped;
+    utstring_new(wrapped);
+
+    read_text(text, argv[1]);
+    wrap_text(wrapped, utstring_body(text), WRAP_COLUMN);
+    printf("%s\n", utstring_body(wrapped));
+
+    utstring_free(text);
+    utstring_free(wrapped);
+}
diff --git a/challenge-019/paulo-custodio/c/utstring.h b/challenge-019/paulo-custodio/c/utstring.h
new file mode 100644
index 0000000000..f0270fb632
--- /dev/null
+++ b/challenge-019/paulo-custodio/c/utstring.h
@@ -0,0 +1,407 @@
+/*
+Copyright (c) 2008-2022, Troy D. Hanson  https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic string implementation using macros
+ */
+#ifndef UTSTRING_H
+#define UTSTRING_H
+
+#define UTSTRING_VERSION 2.3.0
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+
+#ifdef __GNUC__
+#define UTSTRING_UNUSED __attribute__((__unused__))
+#else
+#define UTSTRING_UNUSED
+#endif
+
+#ifdef oom
+#error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code."
+#define utstring_oom() oom()
+#endif
+
+#ifndef utstring_oom
+#define utstring_oom() exit(-1)
+#endif
+
+typedef struct {
+    char *d;  /* pointer to allocated buffer */
+    size_t n; /* allocated capacity */
+    size_t i; /* index of first unused byte */
+} UT_string;
+
+#define utstring_reserve(s,amt)                            \
+do {                                                       \
+  if (((s)->n - (s)->i) < (size_t)(amt)) {                 \
+    char *utstring_tmp = (char*)realloc(                   \
+      (s)->d, (s)->n + (amt));                             \
+    if (!utstring_tmp) {                                   \
+      utstring_oom();                                      \
+    }                                                      \
+    (s)->d = utstring_tmp;                                 \
+    (s)->n += (amt);                                       \
+  }                                                        \
+} while(0)
+
+#define utstring_init(s)                                   \
+do {                                                       \
+  (s)->n = 0; (s)->i = 0; (s)->d = NULL;                   \
+  utstring_reserve(s,100);                                 \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_done(s)                                   \
+do {                                                       \
+  if ((s)->d != NULL) free((s)->d);                        \
+  (s)->n = 0;                                              \
+} while(0)
+
+#define utstring_free(s)                                   \
+do {                                                       \
+  utstring_done(s);                                        \
+  free(s);                                                 \
+} while(0)
+
+#define utstring_new(s)                                    \
+do {                                                       \
+  (s) = (UT_string*)malloc(sizeof(UT_string));             \
+  if (!(s)) {                                              \
+    utstring_oom();                                        \
+  }                                                        \
+  utstring_init(s);                                        \
+} while(0)
+
+#define utstring_renew(s)                                  \
+do {                                                       \
+   if (s) {                                                \
+     utstring_clear(s);                                    \
+   } else {                                                \
+     utstring_new(s);                                      \
+   }                                                       \
+} while(0)
+
+#define utstring_clear(s)                                  \
+do {                                                       \
+  (s)->i = 0;                                              \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_bincpy(s,b,l)                             \
+do {                                                       \
+  utstring_reserve((s),(l)+1);                             \
+  if (l) memcpy(&(s)->d[(s)->i], b, l);                    \
+  (s)->i += (l);                                           \
+  (s)->d[(s)->i]='\0';                                     \
+} while(0)
+
+#define utstring_concat(dst,src)                                 \
+do {                                                             \
+  utstring_reserve((dst),((src)->i)+1);                          \
+  if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \
+  (dst)->i += (src)->i;                                          \
+  (dst)->d[(dst)->i]='\0';                                       \
+} while(0)
+
+#define utstring_len(s) ((s)->i)
+
+#define utstring_body(s) ((s)->d)
+
+UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
+   int n;
+   va_list cp;
+   for (;;) {
+#ifdef _WIN32
+      cp = ap;
+#else
+      va_copy(cp, ap);
+#endif
+      n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
+      va_end(cp);
+
+      if ((n > -1) && ((size_t) n < (s->n-s->i))) {
+        s->i += n;
+        return;
+      }
+
+      /* Else try again with more space. */
+      if (n > -1) utstring_reserve(s,n+1); /* exact */
+      else utstring_reserve(s,(s->n)*2);   /* 2x */
+   }
+}
+#ifdef __GNUC__
+/* support printf format checking (2=the format string, 3=start of varargs) */
+static void utstring_printf(UT_string *s, const char *fmt, ...)
+  __attribute__ (( format( printf, 2, 3) ));
+#endif
+UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) {
+   va_list ap;
+   va_start(ap,fmt);
+   utstring_printf_va(s,fmt,ap);
+   va_end(ap);
+}
+
+/*******************************************************************************
+ * begin substring search functions                                            *
+ ******************************************************************************/
+/* Build KMP table from left to right. */
+UTSTRING_UNUSED static void _utstring_BuildTable(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = 0;
+    j = i - 1;
+    P_KMP_Table[i] = j;
+    while (i < (long) P_NeedleLen)
+    {
+        while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j];
+        }
+        i++;
+        j++;
+        if (i < (long) P_NeedleLen)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i] = P_KMP_Table[j];
+            }
+            else
+            {
+                P_KMP_Table[i] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Build KMP table from right to left. */
+UTSTRING_UNUSED static void _utstring_BuildTableR(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = P_NeedleLen - 1;
+    j = i + 1;
+    P_KMP_Table[i + 1] = j;
+    while (i >= 0)
+    {
+        while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j + 1];
+        }
+        i--;
+        j--;
+        if (i >= 0)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
+            }
+            else
+            {
+                P_KMP_Table[i + 1] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i + 1] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Search data from left to right. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_find(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from left to right. */
+    i = j = 0;
+    while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
+    {
+        while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i];
+        }
+        i++;
+        j++;
+        if (i >= (int)P_NeedleLen)
+        {
+            /* Found. */
+            V_FindPosition = j - i;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_findR(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from right to left. */
+    j = (P_HaystackLen - 1);
+    i = (P_NeedleLen - 1);
+    while ( (j >= 0) && (j >= i) )
+    {
+        while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i + 1];
+        }
+        i--;
+        j--;
+        if (i < 0)
+        {
+            /* Found. */
+            V_FindPosition = j + 1;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from left to right. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_find(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = s->i - V_StartPosition;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_find(s->d + V_StartPosition,
+                                            V_HaystackLen,
+                                            P_Needle,
+                                            P_NeedleLen,
+                                            V_KMP_Table);
+            if (V_FindPosition >= 0)
+            {
+                V_FindPosition += V_StartPosition;
+            }
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_findR(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = V_StartPosition + 1;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_findR(s->d,
+                                             V_HaystackLen,
+                                             P_Needle,
+                                             P_NeedleLen,
+                                             V_KMP_Table);
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+/*******************************************************************************
+ * end substring search functions                                              *
+ ******************************************************************************/
+
+#endif /* UTSTRING_H */