Merge pull request #4334 from pauloscustodio/paulo-custodio

Add Perl solution to challenge 118

15 files changed, 524 insertions, 31 deletions

diff --git a/challenge-001/paulo-custodio/test.pl b/challenge-001/paulo-custodio/test.pl
index a8a46745f3..2bc0715c09 100644
--- a/challenge-001/paulo-custodio/test.pl
+++ b/challenge-001/paulo-custodio/test.pl
@@ -68,7 +68,7 @@ for my $lang (grep {-d} sort keys %LANG) {
                     # build test command line
                     my $cmd;
                     if ($lang eq 'bc') {        # needs args in stdin
-                        $cmd = "echo ".$spec->{args}."|$exec";
+                        $cmd = "echo ".($spec->{args}//"")."|$exec";
                     }
                     else {
                         $cmd = "$exec ".value_or_eval($spec->{args});
diff --git a/challenge-004/paulo-custodio/bc/ch-1.bc b/challenge-004/paulo-custodio/bc/ch-1.bc
new file mode 100644
index 0000000000..d63c247440
--- /dev/null
+++ b/challenge-004/paulo-custodio/bc/ch-1.bc
@@ -0,0 +1,6 @@
+#!/usr/bin/bc -ql
+scale=100
+pi=4*a(1)
+scale=56
+pi/1
+quit
diff --git a/challenge-006/paulo-custodio/bc/ch-2.bc b/challenge-006/paulo-custodio/bc/ch-2.bc
new file mode 100644
index 0000000000..631718706d
--- /dev/null
+++ b/challenge-006/paulo-custodio/bc/ch-2.bc
@@ -0,0 +1,8 @@
+#!/usr/bin/bc -ql
+scale=100
+pi=4*a(1)
+ex=pi*sqrt(163)
+rk=e(ex)
+scale=12
+rk/1
+quit
\ No newline at end of file
diff --git a/challenge-008/paulo-custodio/c/ch-1.c b/challenge-008/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..4043dada86
--- /dev/null
+++ b/challenge-008/paulo-custodio/c/ch-1.c
@@ -0,0 +1,69 @@
+/*
+Challenge 008
+
+Challenge #1
+Write a script that computes the first five perfect numbers. A perfect number
+is an integer that is the sum of its positive proper divisors (all divisors
+except itself). Please check Wiki for more information. This challenge was
+proposed by Laurent Rosenfeld.
+*/
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+bool is_prime(int n) {
+    if (n <= 1)
+        return false;
+    if (n <= 3)
+        return true;
+    if ((n % 2) == 0 || (n % 3) == 0)
+        return false;
+    for (int i = 5; i * i <= n; i += 6)
+        if ((n % i) == 0 || (n % (i + 2)) == 0)
+            return false;
+    return true;
+}
+
+int next_prime(int n) {
+    if (n <= 1)
+        return 2;
+    do {
+        n++;
+    } while (!is_prime(n));
+    return n;
+}
+
+int ipow(int base, int exp) {
+    int result = 1;
+    for (;;) {
+        if (exp & 1)
+            result *= base;
+        exp >>= 1;
+        if (!exp)
+            break;
+        base *= base;
+    }
+    return result;
+}
+
+// Euclid proved that 2 ^ (p-1) * (2 ^ p - 1) is an even perfect number
+// whenever 2^p - 1 is prime
+int next_perfect(void) {
+    static int p = 1;
+    while (true) {
+        p = next_prime(p);
+        int f = ipow(2, p) - 1;
+        if (is_prime(f))
+            return ipow(2, p - 1) * f;
+    }
+}
+
+int main(int argc, char* argv[]) {
+    int n = 5;
+    if (argc == 2)
+        n = atoi(argv[1]);
+    for (int i = 0; i < n; i++) {
+        printf("%d\n", next_perfect());
+    }
+}
diff --git a/challenge-008/paulo-custodio/c/ch-2.c b/challenge-008/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..c1f470df1d
--- /dev/null
+++ b/challenge-008/paulo-custodio/c/ch-2.c
@@ -0,0 +1,60 @@
+/*
+Challenge 008
+
+Challenge #2
+Write a function, ‘center’, whose argument is a list of strings, which will
+be lines of text. The function should insert spaces at the beginning of the
+lines of text so that if they were printed, the text would be centered, and
+return the modified lines.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define MAXLINE 1024
+
+void* check_mem(void* p) {
+    if (!p) {
+        fputs("Out of memory", stderr);
+        exit(EXIT_FAILURE);
+    }
+    return p;
+}
+
+void center(int nlines, char* lines[]) {
+    int max_len = 0;
+
+    for (int i = 0; i < nlines; i++) {
+        int len = strlen(lines[i]);
+        if (len > max_len)
+            max_len = len;
+    }
+
+    for (int i = 0; i < nlines; i++) {
+        char buffer[MAXLINE];
+        int len = strlen(lines[i]);
+        sprintf(buffer, "%*s%s", (max_len - len) / 2, "", lines[i]);
+        strcpy(lines[i], buffer);
+    }
+}
+
+int main(int argc, char* argv[]) {
+    argc--; argv++;
+
+    int nlines = argc;
+    char** lines = check_mem(malloc(nlines * sizeof(char*)));
+    for (int i = 0; i < nlines; i++) {
+        lines[i] = check_mem(malloc(MAXLINE));
+        strcpy(lines[i], argv[i]);
+    }
+
+    center(nlines, lines);
+
+    for (int i = 0; i < nlines; i++)
+        printf("%s\n", lines[i]);
+
+    for (int i = 0; i < nlines; i++)
+        free(lines[i]);
+    free(lines);
+}
diff --git a/challenge-008/paulo-custodio/cpp/ch-1.cpp b/challenge-008/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..9915f46bb8
--- /dev/null
+++ b/challenge-008/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,67 @@
+/*
+Challenge 008
+
+Challenge #1
+Write a script that computes the first five perfect numbers. A perfect number
+is an integer that is the sum of its positive proper divisors (all divisors
+except itself). Please check Wiki for more information. This challenge was
+proposed by Laurent Rosenfeld.
+*/
+
+#include <iostream>
+using namespace std;
+
+bool is_prime(int n) {
+    if (n <= 1)
+        return false;
+    if (n <= 3)
+        return true;
+    if ((n % 2) == 0 || (n % 3) == 0)
+        return false;
+    for (int i = 5; i * i <= n; i += 6)
+        if ((n % i) == 0 || (n % (i + 2)) == 0)
+            return false;
+    return true;
+}
+
+int next_prime(int n) {
+    if (n <= 1)
+        return 2;
+    do {
+        n++;
+    } while (!is_prime(n));
+    return n;
+}
+
+int ipow(int base, int exp) {
+    int result = 1;
+    for (;;) {
+        if (exp & 1)
+            result *= base;
+        exp >>= 1;
+        if (!exp)
+            break;
+        base *= base;
+    }
+    return result;
+}
+
+// Euclid proved that 2 ^ (p-1) * (2 ^ p - 1) is an even perfect number
+// whenever 2^p - 1 is prime
+int next_perfect(void) {
+    static int p = 1;
+    while (true) {
+        p = next_prime(p);
+        int f = ipow(2, p) - 1;
+        if (is_prime(f))
+            return ipow(2, p - 1) * f;
+    }
+}
+
+int main(int argc, char* argv[]) {
+    int n = 5;
+    if (argc == 2)
+        n = atoi(argv[1]);
+    for (int i = 0; i < n; i++)
+        cout << next_perfect() << endl;
+}
diff --git a/challenge-008/paulo-custodio/cpp/ch-2.cpp b/challenge-008/paulo-custodio/cpp/ch-2.cpp
new file mode 100644
index 0000000000..aeca0d65e4
--- /dev/null
+++ b/challenge-008/paulo-custodio/cpp/ch-2.cpp
@@ -0,0 +1,38 @@
+/*
+Challenge 008
+
+Challenge #2
+Write a function, ‘center’, whose argument is a list of strings, which will
+be lines of text. The function should insert spaces at the beginning of the
+lines of text so that if they were printed, the text would be centered, and
+return the modified lines.
+*/
+
+#include <iostream>
+#include <vector>
+#include <string>
+using namespace std;
+
+void center(vector<string>& lines) {
+    size_t max_len = 0;
+
+    for (auto& line : lines)
+        if (line.size() > max_len)
+            max_len = line.size();
+
+    for (auto& line : lines)
+        line = string((max_len - static_cast<int>(line.size())) / 2, ' ') + line;
+}
+
+int main(int argc, char* argv[]) {
+    argc--; argv++;
+
+    vector<string> lines;
+    for (int i = 0; i < argc; i++)
+        lines.push_back(argv[i]);
+
+    center(lines);
+
+    for (auto& line : lines)
+        cout << line << endl;
+}
diff --git a/challenge-008/paulo-custodio/t/test-1.yaml b/challenge-008/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..90fe6af462
--- /dev/null
+++ b/challenge-008/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     5
+  input:
+  output:   |
+    6
+    28
+    496
+    8128
+    33550336
diff --git a/challenge-008/paulo-custodio/t/test-2.yaml b/challenge-008/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..254dc33be8
--- /dev/null
+++ b/challenge-008/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,9 @@
+- setup:
+  cleanup:
+  args:     "'This' 'is' 'a test of the' 'center function'"
+  input:
+  output:   |
+            |     This
+            |      is
+            | a test of the
+            |center function
diff --git a/challenge-008/paulo-custodio/test.pl b/challenge-008/paulo-custodio/test.pl
index 6897ad608e..ba6c37260b 100644
--- a/challenge-008/paulo-custodio/test.pl
+++ b/challenge-008/paulo-custodio/test.pl
@@ -1,31 +1,4 @@
-#!/usr/bin/perl
-
-use strict;
-use warnings;
-use 5.030;
+#!/usr/bin/env perl
+use Modern::Perl;
 use Test::More;
-
-is capture("perl perl/ch-1.pl 5"), <<END;
-6
-28
-496
-8128
-33550336
-END
-
-is capture("perl perl/ch-2.pl 'This' 'is' 'a test of the' 'center function'"), <<END;
-     This
-      is
- a test of the
-center function
-END
-
-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';
diff --git a/challenge-118/paulo-custodio/perl/ch-1.pl b/challenge-118/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..678ccbc4d9
--- /dev/null
+++ b/challenge-118/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,24 @@
+#!/usr/bin/env perl
+
+# Challenge 118
+#
+# TASK #1 - Binary Palindrome
+# Submitted by: Mohammad S Anwar
+# You are given a positive integer $N.
+#
+# Write a script to find out if the binary representation of the given integer
+# is Palindrome. Print 1 if it is otherwise 0.
+#
+# Example
+# Input: $N = 5
+# Output: 1 as binary representation of 5 is 101 which is Palindrome.
+#
+# Input: $N = 4
+# Output: 0 as binary representation of 4 is 100 which is NOT Palindrome.
+
+use Modern::Perl;
+
+my $N = shift // 0;
+my $bits = sprintf("%b", $N);
+my $rbits = reverse($bits);
+say $bits eq $rbits ? 1 : 0;
diff --git a/challenge-118/paulo-custodio/perl/ch-2.pl b/challenge-118/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..2463830515
--- /dev/null
+++ b/challenge-118/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,200 @@
+#!/usr/bin/env perl
+
+# Challenge 118
+#
+# TASK #2 - Adventure of Knight
+# Submitted by: Cheok-Yin Fung
+# A knight is restricted to move on an 8×8 chessboard. The knight is denoted by
+# N and its way of movement is the same as what it is defined in Chess.
+# * represents an empty square. x represents a square with treasure.
+#
+# The Knight’s movement is unique. It may move two squares vertically and one
+# square horizontally, or two squares horizontally and one square vertically
+# (with both forming the shape of an L).
+#
+# There are 6 squares with treasures.
+#
+# Write a script to find the path such that Knight can capture all treasures.
+# The Knight can start from the top-left square.
+#
+#       a b c d e f g h
+#     8 N * * * * * * * 8
+#     7 * * * * * * * * 7
+#     6 * * * * x * * * 6
+#     5 * * * * * * * * 5
+#     4 * * x * * * * * 4
+#     3 * x * * * * * * 3
+#     2 x x * * * * * * 2
+#     1 * x * * * * * * 1
+#       a b c d e f g h
+#
+
+# https://en.m.wikipedia.org/wiki/Knight%27s_tour
+
+use Modern::Perl;
+use Clone 'clone';
+
+{
+    package Board;
+    use Object::Tiny::RW qw( board treasures path );
+
+    sub new {
+        my($class) = @_;
+        my $self = bless {
+            board => [[],[],[],[],[],[],[],[]],
+            treasures => {},
+            path => [],
+        }, $class;
+        return $self;
+    }
+
+    sub parse {
+        my($self) = @_;
+        $self->board([[],[],[],[],[],[],[],[]]);
+        $self->treasures({});
+        $self->path([]);
+
+        local $_;
+        $_ = <>;
+        /a b c d e f g h/i or die "expected header";
+        for my $row (0..7) {
+            my $y = 8 - $row;
+            $_ = <>;
+            s/^ \s* $y \s*//x or die "expected row $y";
+            for my $col (0..7) {
+                my $x = chr(ord('a') + $col);
+                s/^ (\S) \s* //x or die "expected cell $x$y";
+                my $cell = $1;
+                if ($cell eq 'N') {
+                    push @{$self->path}, [$row, $col];
+                    $self->board->[$row][$col] = 1;
+                }
+                elsif ($cell eq 'x') {
+                    $self->treasures->{"$row$col"} = 1;
+                }
+            }
+        }
+        $_ = <>;
+        /a b c d e f g h/i or die "expected footer";
+    }
+
+    sub next_moves {
+        my($self, $row, $col) = @_;
+        my @next;
+        for ([-2, -1], [-2, +1], [+2, -1], [+2, +1],
+             [+1, -2], [-1, -2], [+1, +2], [-1, +2]) {
+            my($drow, $dcol) = @$_;
+            my $nrow = $row + $drow;
+            my $ncol = $col + $dcol;
+            if ($nrow >= 0 && $nrow < 8) {
+                if ($ncol >= 0 && $ncol < 8) {
+                    if (!$self->board->[$nrow][$ncol]) {
+                        push @next, [$nrow, $ncol];
+                    }
+                }
+            }
+        }
+        return @next;
+    }
+
+    sub next_possible_moves {
+        my($self) = @_;
+
+        # get current position
+        my($row, $col) = @{$self->path->[-1]};
+
+        # get possible moves from here
+        my @next = $self->next_moves($row, $col);
+
+        # count possible moves from each destination
+        my $min_count = 1e10;
+        for (@next) {
+            my($nrow, $ncol) = @$_;
+            my $count = $self->next_moves($nrow, $ncol);
+            push @$_, $count;
+            $min_count = $count if $min_count > $count;
+        }
+
+        # select move(s) with less count
+        @next = grep {$_->[2] == $min_count} @next;
+
+        return @next;
+    }
+
+    sub path_str {
+        my($self) = @_;
+        my @moves;
+        for (@{$self->path}) {
+            my($row, $col) = @$_;
+            my $x = chr(ord('a') + $col);
+            my $y = 8 - $row;
+            push @moves, "$x$y";
+        }
+        return "@moves";
+    }
+
+    sub str {
+        my($self) = @_;
+        my $ret = "  a b c d e f g h\n";
+        for my $row (0..7) {
+            my $y = 8 - $row;
+            $ret .= "$y ";
+            for my $col (0..7) {
+                if (exists $self->treasures->{"$row$col"}) {
+                    $ret .= "x ";
+                }
+                elsif ($self->board->[$row][$col]) {
+                    $ret .= "N ";
+                }
+                else {
+                    $ret .= "* ";
+                }
+            }
+            $ret .= "$y\n";
+        }
+        $ret .= "  a b c d e f g h\n";
+        $ret .= $self->path_str . "\n";
+
+        return $ret;
+    }
+
+}
+
+sub solve {
+    my($board) = @_;
+
+    my @queue = clone($board);
+    while (@queue) {
+        $board = shift @queue;
+        if (%{$board->treasures} == 0) { # all treasures found
+            return $board;
+        }
+        else {
+            my @next = $board->next_possible_moves;
+            # if any matches a treasure, move it forward
+            for (0..$#next) {
+                my($row, $col) = @{$next[$_]};
+                if (exists $board->treasures->{"$row$col"}) {
+                    @next = ($next[$_], @next[0..$_-1], @next[$_+1..$#next]);
+                    last;
+                }
+            }
+
+            for (@next) {
+                my($row, $col) = @$_;
+                my $new_board = clone($board);
+                $new_board->board->[$row][$col] = 1;
+                push @{$new_board->path}, [$row, $col];
+                delete $new_board->treasures->{"$row$col"};
+
+                push @queue, $new_board;
+            }
+        }
+    }
+    die "no solution found\n";
+}
+
+my $board = Board->new;
+$board->parse;
+$board = solve($board);
+say $board->path_str;
diff --git a/challenge-118/paulo-custodio/t/test-1.yaml b/challenge-118/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..bdb0c9139c
--- /dev/null
+++ b/challenge-118/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     5
+  input:
+  output:   1
+- setup:
+  cleanup:
+  args:     4
+  input:
+  output:   0
diff --git a/challenge-118/paulo-custodio/t/test-2.yaml b/challenge-118/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..d3149a283f
--- /dev/null
+++ b/challenge-118/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,15 @@
+- setup:
+  cleanup:
+  args:
+  input:    |
+            |   a b c d e f g h
+            | 8 N * * * * * * * 8
+            | 7 * * * * * * * * 7
+            | 6 * * * * x * * * 6
+            | 5 * * * * * * * * 5
+            | 4 * * x * * * * * 4
+            | 3 * x * * * * * * 3
+            | 2 x x * * * * * * 2
+            | 1 * x * * * * * * 1
+            |   a b c d e f g h
+  output:   a8 c7 a6 b8 d7 f8 h7 g5 h3 g1 e2 c1 a2 b4 c2 a1 b3 a5 b7 d8 e6 c5 a4 b2 d1 c3 b1 a3 b5 a7 c8 b6 c4
diff --git a/challenge-118/paulo-custodio/test.pl b/challenge-118/paulo-custodio/test.pl
new file mode 100644
index 0000000000..ba6c37260b
--- /dev/null
+++ b/challenge-118/paulo-custodio/test.pl
@@ -0,0 +1,4 @@
+#!/usr/bin/env perl
+use Modern::Perl;
+use Test::More;
+require '../../challenge-001/paulo-custodio/test.pl';