diff options
| -rw-r--r-- | challenge-243/paulo-custodio/Makefile | 2 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/c/ch-1.c | 64 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/c/ch-2.c | 66 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/c/utarray.h | 252 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/cpp/ch-1.cpp | 61 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/cpp/ch-2.cpp | 63 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/perl/ch-1.pl | 45 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/perl/ch-2.pl | 48 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/t/test-1.yaml | 10 | ||||
| -rw-r--r-- | challenge-243/paulo-custodio/t/test-2.yaml | 10 |
10 files changed, 621 insertions, 0 deletions
diff --git a/challenge-243/paulo-custodio/Makefile b/challenge-243/paulo-custodio/Makefile new file mode 100644 index 0000000000..c3c762d746 --- /dev/null +++ b/challenge-243/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-243/paulo-custodio/c/ch-1.c b/challenge-243/paulo-custodio/c/ch-1.c new file mode 100644 index 0000000000..39ffc3dc91 --- /dev/null +++ b/challenge-243/paulo-custodio/c/ch-1.c @@ -0,0 +1,64 @@ +/* +Challenge 243 + +Task 1: Reverse Pairs +Submitted by: Mohammad S Anwar + +You are given an array of integers. + +Write a script to return the number of reverse pairs in the given array. + +A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) +nums[i] > 2 * nums[j]. +Example 1 + +Input: @nums = (1, 3, 2, 3, 1) +Output: 2 + +(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1 +(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1 + +Example 2 + +Input: @nums = (2, 4, 3, 5, 1) +Output: 3 + +(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1 +(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1 +(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1 +*/ + +#include "utarray.h" +#include <stdio.h> +#include <stdlib.h> + +int num_reverse_pairs(UT_array* nums) { + int count = 0; + for (size_t i = 0; i < utarray_len(nums)-1; i++) { + for (size_t j = i+1; j < utarray_len(nums); j++) { + if (*(int*)utarray_eltptr(nums, i) > 2 * *(int*)utarray_eltptr(nums, j)) + count++; + } + } + return count; +} + +int main(int argc, char* argv[]) { + if (argc < 3) { + fputs("Usage: ch-1 n n n ...\n", stderr); + exit(EXIT_FAILURE); + } + + UT_array* nums; + utarray_new(nums, &ut_int_icd); + + for (int i = 1; i < argc; i++) { + int n = atoi(argv[i]); + utarray_push_back(nums, &n); + } + + int count = num_reverse_pairs(nums); + printf("%d\n", count); + + utarray_free(nums); +} diff --git a/challenge-243/paulo-custodio/c/ch-2.c b/challenge-243/paulo-custodio/c/ch-2.c new file mode 100644 index 0000000000..47974d633c --- /dev/null +++ b/challenge-243/paulo-custodio/c/ch-2.c @@ -0,0 +1,66 @@ +/* +Challenge 243 + +Task 2: Floor Sum +Submitted by: Mohammad S Anwar + +You are given an array of positive integers (>=1). + +Write a script to return the sum of floor(nums[i] / nums[j]) where +0 <= i,j < nums.length. The floor() function returns the integer part of the +division. + +Example 1 + +Input: @nums = (2, 5, 9) +Output: 10 + +floor(2 / 5) = 0 +floor(2 / 9) = 0 +floor(5 / 9) = 0 +floor(2 / 2) = 1 +floor(5 / 5) = 1 +floor(9 / 9) = 1 +floor(5 / 2) = 2 +floor(9 / 2) = 4 +floor(9 / 5) = 1 + +Example 2 + +Input: @nums = (7, 7, 7, 7, 7, 7, 7) +Output: 49 +*/ + +#include "utarray.h" +#include <stdio.h> +#include <stdlib.h> + +int sum_floor(UT_array* nums) { + int sum = 0; + for (size_t i = 0; i < utarray_len(nums); i++) { + for (size_t j = 0; j < utarray_len(nums); j++) { + sum += *(int*)utarray_eltptr(nums, i) / *(int*)utarray_eltptr(nums, j); + } + } + return sum; +} + +int main(int argc, char* argv[]) { + if (argc < 3) { + fputs("Usage: ch-2 n n n ...\n", stderr); + exit(EXIT_FAILURE); + } + + UT_array* nums; + utarray_new(nums, &ut_int_icd); + + for (int i = 1; i < argc; i++) { + int n = atoi(argv[i]); + utarray_push_back(nums, &n); + } + + int sum = sum_floor(nums); + printf("%d\n", sum); + + utarray_free(nums); +} diff --git a/challenge-243/paulo-custodio/c/utarray.h b/challenge-243/paulo-custodio/c/utarray.h new file mode 100644 index 0000000000..1fe8bc1c74 --- /dev/null +++ b/challenge-243/paulo-custodio/c/utarray.h @@ -0,0 +1,252 @@ +/* +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 array implementation using macros + */ +#ifndef UTARRAY_H +#define UTARRAY_H + +#define UTARRAY_VERSION 2.3.0 + +#include <stddef.h> /* size_t */ +#include <string.h> /* memset, etc */ +#include <stdlib.h> /* exit */ + +#ifdef __GNUC__ +#define UTARRAY_UNUSED __attribute__((__unused__)) +#else +#define UTARRAY_UNUSED +#endif + +#ifndef utarray_oom +#define utarray_oom() exit(-1) +#endif + +typedef void (ctor_f)(void *dst, const void *src); +typedef void (dtor_f)(void *elt); +typedef void (init_f)(void *elt); +typedef struct { + size_t sz; + init_f *init; + ctor_f *copy; + dtor_f *dtor; +} UT_icd; + +typedef struct { + unsigned i,n;/* i: index of next available slot, n: num slots */ + UT_icd icd; /* initializer, copy and destructor functions */ + char *d; /* n slots of size icd->sz*/ +} UT_array; + +#define utarray_init(a,_icd) do { \ + memset(a,0,sizeof(UT_array)); \ + (a)->icd = *(_icd); \ +} while(0) + +#define utarray_done(a) do { \ + if ((a)->n) { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + free((a)->d); \ + } \ + (a)->n=0; \ +} while(0) + +#define utarray_new(a,_icd) do { \ + (a) = (UT_array*)malloc(sizeof(UT_array)); \ + if ((a) == NULL) { \ + utarray_oom(); \ + } \ + utarray_init(a,_icd); \ +} while(0) + +#define utarray_free(a) do { \ + utarray_done(a); \ + free(a); \ +} while(0) + +#define utarray_reserve(a,by) do { \ + if (((a)->i+(by)) > (a)->n) { \ + char *utarray_tmp; \ + while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ + utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \ + if (utarray_tmp == NULL) { \ + utarray_oom(); \ + } \ + (a)->d=utarray_tmp; \ + } \ +} while(0) + +#define utarray_push_back(a,p) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ + else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ +} while(0) + +#define utarray_pop_back(a) do { \ + if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ + else { (a)->i--; } \ +} while(0) + +#define utarray_extend_back(a) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ + else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ + (a)->i++; \ +} while(0) + +#define utarray_len(a) ((a)->i) + +#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) +#define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j)))) + +#define utarray_insert(a,p,j) do { \ + if ((j) > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,1); \ + if ((j) < (a)->i) { \ + memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ + else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ + (a)->i++; \ +} while(0) + +#define utarray_inserta(a,w,j) do { \ + if (utarray_len(w) == 0) break; \ + if ((j) > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,utarray_len(w)); \ + if ((j) < (a)->i) { \ + memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ + _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { \ + unsigned _ut_i; \ + for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ + (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \ + } \ + } else { \ + memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ + utarray_len(w)*((a)->icd.sz)); \ + } \ + (a)->i += utarray_len(w); \ +} while(0) + +#define utarray_resize(dst,num) do { \ + unsigned _ut_i; \ + if ((dst)->i > (unsigned)(num)) { \ + if ((dst)->icd.dtor) { \ + for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \ + (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \ + } \ + } \ + } else if ((dst)->i < (unsigned)(num)) { \ + utarray_reserve(dst, (num) - (dst)->i); \ + if ((dst)->icd.init) { \ + for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \ + (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \ + } \ + } else { \ + memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \ + } \ + } \ + (dst)->i = (num); \ +} while(0) + +#define utarray_concat(dst,src) do { \ + utarray_inserta(dst, src, utarray_len(dst)); \ +} while(0) + +#define utarray_erase(a,pos,len) do { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for (_ut_i = 0; _ut_i < (len); _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \ + } \ + } \ + if ((a)->i > ((pos) + (len))) { \ + memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \ + ((a)->i - ((pos) + (len))) * (a)->icd.sz); \ + } \ + (a)->i -= (len); \ +} while(0) + +#define utarray_renew(a,u) do { \ + if (a) utarray_clear(a); \ + else utarray_new(a, u); \ +} while(0) + +#define utarray_clear(a) do { \ + if ((a)->i > 0) { \ + if ((a)->icd.dtor) { \ + unsigned _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \ + } \ + } \ + (a)->i = 0; \ + } \ +} while(0) + +#define utarray_sort(a,cmp) do { \ + qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ +} while(0) + +#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) + +#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) +#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((a)->i != utarray_eltidx(a,e)+1) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) +#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) +#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) +#define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz) + +/* last we pre-define a few icd for common utarrays of ints and strings */ +static void utarray_str_cpy(void *dst, const void *src) { + char *const *srcc = (char *const *)src; + char **dstc = (char**)dst; + if (*srcc == NULL) { + *dstc = NULL; + } else { + *dstc = (char*)malloc(strlen(*srcc) + 1); + if (*dstc == NULL) { + utarray_oom(); + } else { + strcpy(*dstc, *srcc); + } + } +} +static void utarray_str_dtor(void *elt) { + char **eltc = (char**)elt; + if (*eltc != NULL) free(*eltc); +} +static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; +static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL}; +static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL}; + + +#endif /* UTARRAY_H */ diff --git a/challenge-243/paulo-custodio/cpp/ch-1.cpp b/challenge-243/paulo-custodio/cpp/ch-1.cpp new file mode 100644 index 0000000000..ce52b9b8f2 --- /dev/null +++ b/challenge-243/paulo-custodio/cpp/ch-1.cpp @@ -0,0 +1,61 @@ +/* +Challenge 243 + +Task 1: Reverse Pairs +Submitted by: Mohammad S Anwar + +You are given an array of integers. + +Write a script to return the number of reverse pairs in the given array. + +A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) +nums[i] > 2 * nums[j]. +Example 1 + +Input: @nums = (1, 3, 2, 3, 1) +Output: 2 + +(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1 +(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1 + +Example 2 + +Input: @nums = (2, 4, 3, 5, 1) +Output: 3 + +(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1 +(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1 +(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1 +*/ + +#include <iostream> +#include <vector> +using namespace std; + +int num_reverse_pairs(const vector<int>& nums) { + int count = 0; + for (size_t i = 0; i < nums.size()-1; i++) { + for (size_t j = i+1; j < nums.size(); j++) { + if (nums[i] > 2 * nums[j]) + count++; + } + } + return count; +} + +int main(int argc, char* argv[]) { + if (argc < 3) { + cerr << "Usage: ch-1 n n n ..." << endl; + exit(EXIT_FAILURE); + } + + vector<int> nums; + + for (int i = 1; i < argc; i++) { + int n = atoi(argv[i]); + nums.push_back(n); + } + + int count = num_reverse_pairs(nums); + cout << count << endl; +} diff --git a/challenge-243/paulo-custodio/cpp/ch-2.cpp b/challenge-243/paulo-custodio/cpp/ch-2.cpp new file mode 100644 index 0000000000..8bcad05d7c --- /dev/null +++ b/challenge-243/paulo-custodio/cpp/ch-2.cpp @@ -0,0 +1,63 @@ +/* +Challenge 243 + +Task 2: Floor Sum +Submitted by: Mohammad S Anwar + +You are given an array of positive integers (>=1). + +Write a script to return the sum of floor(nums[i] / nums[j]) where +0 <= i,j < nums.length. The floor() function returns the integer part of the +division. + +Example 1 + +Input: @nums = (2, 5, 9) +Output: 10 + +floor(2 / 5) = 0 +floor(2 / 9) = 0 +floor(5 / 9) = 0 +floor(2 / 2) = 1 +floor(5 / 5) = 1 +floor(9 / 9) = 1 +floor(5 / 2) = 2 +floor(9 / 2) = 4 +floor(9 / 5) = 1 + +Example 2 + +Input: @nums = (7, 7, 7, 7, 7, 7, 7) +Output: 49 +*/ + +#include <iostream> +#include <vector> +using namespace std; + +int sum_floor(const vector<int>& nums) { + int sum = 0; + for (size_t i = 0; i < nums.size(); i++) { + for (size_t j = 0; j < nums.size(); j++) { + sum += nums[i] / nums[j]; + } + } + return sum; +} + +int main(int argc, char* argv[]) { + if (argc < 3) { + cerr << "Usage: ch-1 n n n ..." << endl; + exit(EXIT_FAILURE); + } + + vector<int> nums; + + for (int i = 1; i < argc; i++) { + int n = atoi(argv[i]); + nums.push_back(n); + } + + int sum = sum_floor(nums); + cout << sum << endl; +} diff --git a/challenge-243/paulo-custodio/perl/ch-1.pl b/challenge-243/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..157e5c0828 --- /dev/null +++ b/challenge-243/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,45 @@ +#!/usr/bin/env perl + +# Challenge 243 +# +# Task 1: Reverse Pairs +# Submitted by: Mohammad S Anwar +# +# You are given an array of integers. +# +# Write a script to return the number of reverse pairs in the given array. +# +# A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) +# nums[i] > 2 * nums[j]. +# Example 1 +# +# Input: @nums = (1, 3, 2, 3, 1) +# Output: 2 +# +# (1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1 +# (3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1 +# +# Example 2 +# +# Input: @nums = (2, 4, 3, 5, 1) +# Output: 3 +# +# (1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1 +# (2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1 +# (3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1 + +use Modern::Perl; + +@ARGV>0 or die "Usage: ch-1.pl n n ...\n"; +say num_reverse_pairs(@ARGV); + +sub num_reverse_pairs { + my(@n) = @_; + my $count = 0; + for my $i (0..$#n-1) { + for my $j ($i+1..$#n) { + $count++ if $n[$i] > 2* $n[$j]; + } + } + return $count; +} diff --git a/challenge-243/paulo-custodio/perl/ch-2.pl b/challenge-243/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..e8fd020119 --- /dev/null +++ b/challenge-243/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,48 @@ +#!/usr/bin/env perl + +# Challenge 243 +# +# Task 2: Floor Sum +# Submitted by: Mohammad S Anwar +# +# You are given an array of positive integers (>=1). +# +# Write a script to return the sum of floor(nums[i] / nums[j]) where +# 0 <= i,j < nums.length. The floor() function returns the integer part of the +# division. +# +# Example 1 +# +# Input: @nums = (2, 5, 9) +# Output: 10 +# +# floor(2 / 5) = 0 +# floor(2 / 9) = 0 +# floor(5 / 9) = 0 +# floor(2 / 2) = 1 +# floor(5 / 5) = 1 +# floor(9 / 9) = 1 +# floor(5 / 2) = 2 +# floor(9 / 2) = 4 +# floor(9 / 5) = 1 +# +# Example 2 +# +# Input: @nums = (7, 7, 7, 7, 7, 7, 7) +# Output: 49 + +use Modern::Perl; + +@ARGV>0 or die "Usage: ch-2.pl n n ...\n"; +say sum_floor(@ARGV); + +sub sum_floor { + my(@n) = @_; + my $sum = 0; + for my $i (0..$#n) { + for my $j (0..$#n) { + $sum += int($n[$i] / $n[$j]); + } + } + return $sum; +} diff --git a/challenge-243/paulo-custodio/t/test-1.yaml b/challenge-243/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..2156a4274d --- /dev/null +++ b/challenge-243/paulo-custodio/t/test-1.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: 1 3 2 3 1 + input: + output: 2 +- setup: + cleanup: + args: 2 4 3 5 1 + input: + output: 3 diff --git a/challenge-243/paulo-custodio/t/test-2.yaml b/challenge-243/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..fdbcf42adf --- /dev/null +++ b/challenge-243/paulo-custodio/t/test-2.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: 2 5 9 + input: + output: 10 +- setup: + cleanup: + args: 7 7 7 7 7 7 7 + input: + output: 49 |
