Merge pull request #4640 from adamcrussell/challenge-123

Challenge 123

8 files changed, 371 insertions, 0 deletions

diff --git a/challenge-123/adam-russell/blog.txt b/challenge-123/adam-russell/blog.txt
new file mode 100644
index 0000000000..5135eabf28
--- /dev/null
+++ b/challenge-123/adam-russell/blog.txt
@@ -0,0 +1 @@
+http://www.rabbitfarm.com/cgi-bin/blosxom/perl/2021/08/01
diff --git a/challenge-123/adam-russell/blog1.txt b/challenge-123/adam-russell/blog1.txt
new file mode 100644
index 0000000000..fd18ba9195
--- /dev/null
+++ b/challenge-123/adam-russell/blog1.txt
@@ -0,0 +1 @@
+http://www.rabbitfarm.com/cgi-bin/blosxom/prolog/2021/08/01
diff --git a/challenge-123/adam-russell/cxx/ch-1.cxx b/challenge-123/adam-russell/cxx/ch-1.cxx
new file mode 100644
index 0000000000..74b4d58f3b
--- /dev/null
+++ b/challenge-123/adam-russell/cxx/ch-1.cxx
@@ -0,0 +1,58 @@
+#include <vector>
+#include <iostream>
+
+/* 
+ * You are given an integer n >= 1.
+ * Write a script to find the nth Ugly Number.
+*/
+
+class Ugly{
+    private:
+        std::vector<int> factor(int);   
+        bool is_ugly(int);
+    public:
+        int nth_ugly(int); 
+};     
+
+std::vector<int> Ugly::factor(int n){
+    std::vector<int> factors;  
+    for (int i=2; i*i<=n; i++){
+        if (n%i==0){
+            if(i*i!=n){  
+                factors.push_back(i);
+                factors.push_back(n/i);
+            }
+            else
+                factors.push_back(i);
+        }
+    }
+    return factors;  
+}
+
+bool Ugly::is_ugly(int n){
+    std::vector<int> factors = this->factor(n);
+    for(int i = 0; i < factors.size(); i++){
+        if(factors[i] != 2 && factors[i] != 3 && factors[i] != 5)
+            return false; 
+    }    
+    return true;   
+} 
+
+int Ugly::nth_ugly(int n){
+    int ugly_count = 1; 
+    int i = 2; 
+    if(n == 1)
+        return 1; 
+    do{
+        if(is_ugly(i))
+            ugly_count++;  
+        i++;  
+    }while(ugly_count != n); 
+    return i; 
+} 
+
+int main(int argc, char** argv){
+    Ugly ugly;
+    int u = ugly.nth_ugly(10);   
+    std::cout << u << std::endl;
+}
diff --git a/challenge-123/adam-russell/cxx/ch-2.cxx b/challenge-123/adam-russell/cxx/ch-2.cxx
new file mode 100644
index 0000000000..c7a052c295
--- /dev/null
+++ b/challenge-123/adam-russell/cxx/ch-2.cxx
@@ -0,0 +1,107 @@
+#include <vector>
+#include <utility>
+#include <iostream>
+#include <algorithm>
+
+class SquarePoints{
+    private:
+        std::vector<std::pair<int, int>> sort_points_x(std::vector<std::pair<int, int>>);  
+        std::vector<std::pair<int, int>> sort_points_y(std::vector<std::pair<int, int>>);   
+    public:
+        std::vector<std::pair<int, int>> sort_points(std::vector<std::pair<int, int>>); 
+        bool is_square(std::vector<std::pair<int, int>>); 
+};
+
+int dot_product(std::pair<int, int> a, std::pair<int, int> b){
+    int product = 0;
+    product = product + a.first * b.first;
+    product = product + a.second * b.second;
+    return product;
+}
+
+bool point_x_compare(const std::pair<int, int> &a, const std::pair<int, int> &b){
+    return a.first < b.first;   
+} 
+
+bool point_y_compare(const std::pair<int, int> &a, const std::pair<int, int> &b){
+    return a.second < b.second;   
+} 
+
+std::vector<std::pair<int, int>> SquarePoints::sort_points_x(std::vector<std::pair<int, int>> points){
+    sort(points.begin(), points.end(), point_x_compare); 
+    return points; 
+} 
+
+std::vector<std::pair<int, int>> SquarePoints::sort_points_y(std::vector<std::pair<int, int>> points){
+    sort(points.begin(), points.end(), point_y_compare); 
+    return points; 
+} 
+        
+bool SquarePoints::is_square(std::vector<std::pair<int, int>> points){
+    std::vector<int> x_s;
+    std::vector<int> y_s;
+    for(int i = 0; i < points.size() ; i++){
+        if(!(std::find(x_s.begin(), x_s.end(), points[i].first) != x_s.end())) {
+            x_s.push_back(points[i].first);  
+        }
+        if(!(std::find(y_s.begin(), y_s.end(), points[i].first) != y_s.end())) {
+            y_s.push_back(points[i].first);  
+        }
+    }
+    /* if only 2 each of x and y then we have a level square */
+    if(x_s.size() == 2 && y_s.size() == 2)
+        return true;
+    /* sort points and compute side lengths */
+    std::vector<std::pair<int, int>> points_by_x = this->sort_points_x(points);  
+    std::vector<std::pair<int, int>> points_by_y = this->sort_points_y(points);  
+    std::pair<int, int> s = points_by_y[points_by_y.size() - 1];  
+    std::pair<int, int> t = points_by_x[points_by_x.size() - 1];  
+    std::pair<int, int> u = points_by_y[0];  
+    std::pair<int, int> v = points_by_x[0];  
+    if(s.first + u.first != t.first + v.first)
+        return false; 
+    if(s.second + u.second != t.second + v.second)
+        return false; 
+    if(s.second - u.second != t.first - v.first)
+        return false; 
+    /* compute angles */
+    std::pair<int, int> dv_st = std::make_pair(s.first - t.first, s.second - t.second);  
+    std::pair<int, int> dv_tu = std::make_pair(t.first - u.first, t.second - u.second);  
+    std::pair<int, int> dv_uv = std::make_pair(u.first - v.first, u.second - v.second);  
+    std::pair<int, int> dv_vs = std::make_pair(v.first - s.first, v.second - s.second);  
+    if(dot_product(dv_st, dv_tu) != 0)
+        return false;   
+    if(dot_product(dv_tu, dv_uv) != 0)
+        return false;   
+    if(dot_product(dv_uv, dv_vs) != 0)
+        return false;   
+    return true;  
+}  
+
+int main(int argc, char** argv){
+    SquarePoints sp; 
+    std::vector<std::pair<int, int>> points;
+    points.push_back(std::make_pair(10, 20));
+    points.push_back(std::make_pair(20, 20));
+    points.push_back(std::make_pair(20, 10));
+    points.push_back(std::make_pair(10, 10));
+    std::cout << sp.is_square(points) << std::endl;    
+    points.clear(); 
+    points.push_back(std::make_pair(12, 24));
+    points.push_back(std::make_pair(16, 10));
+    points.push_back(std::make_pair(20, 12));
+    points.push_back(std::make_pair(18, 16));
+    std::cout << sp.is_square(points) << std::endl;    
+    points.clear(); 
+    points.push_back(std::make_pair(-3, 1));
+    points.push_back(std::make_pair(4, 2));
+    points.push_back(std::make_pair(9, -3));
+    points.push_back(std::make_pair(2, -4));
+    std::cout << sp.is_square(points) << std::endl;    
+    points.clear(); 
+    points.push_back(std::make_pair(0, 0));
+    points.push_back(std::make_pair(2, 1));
+    points.push_back(std::make_pair(3, -1));
+    points.push_back(std::make_pair(1, -2));
+    std::cout << sp.is_square(points) << std::endl;    
+}  
diff --git a/challenge-123/adam-russell/perl/ch-1.pl b/challenge-123/adam-russell/perl/ch-1.pl
new file mode 100644
index 0000000000..07c0598302
--- /dev/null
+++ b/challenge-123/adam-russell/perl/ch-1.pl
@@ -0,0 +1,47 @@
+use strict;
+use warnings;
+##
+# You are given an integer $n >= 1.
+# Write a script to find the $nth Ugly Number.   
+##
+use boolean;
+
+sub prime_factor{
+    my $x = shift(@_); 
+    my @factors;    
+    for (my $y = 2; $y <= $x; $y++){
+        next if $x % $y;
+        $x /= $y;
+        push @factors, $y;
+        redo;
+    }
+    return @factors;  
+}
+
+sub is_ugly{
+    my($x) = @_; 
+    for my $factor (prime_factor($x)){
+        return false if $factor != 2 && $factor != 3 && $factor !=5; 
+    }
+    return true; 
+}
+
+sub nth_ugly{
+    my($n) = @_;  
+    return 1 if $n == 1; 
+    my $ugly_count = 1; 
+    my $i = 1;  
+    do{
+        $i++;
+        $ugly_count++ if is_ugly($i);   
+    }while($ugly_count != $n);
+    return $i;    
+} 
+
+MAIN:{
+    my($N);
+    $N = 7; 
+    print nth_ugly($N) . "\n"; 
+    $N = 10; 
+    print nth_ugly($N) . "\n"; 
+}   
diff --git a/challenge-123/adam-russell/perl/ch-2.pl b/challenge-123/adam-russell/perl/ch-2.pl
new file mode 100644
index 0000000000..e94a3f19bb
--- /dev/null
+++ b/challenge-123/adam-russell/perl/ch-2.pl
@@ -0,0 +1,58 @@
+use strict;
+use warnings;
+##
+# You are given co-ordinates for four points.
+# Write a script to find out if the given 
+# four points form a square.    
+##
+use boolean;  
+use Math::GSL::Vector;
+
+sub unique{
+    my %seen;
+    return grep {!$seen{$_}++} @_;
+} 
+
+sub is_square{
+    my @points = @_;
+    ##
+    # Definitely a square if there are only 2 x and 2 y values. 
+    ##
+    my @x = unique(map {$_->[0]} @points);  
+    my @y = unique(map {$_->[1]} @points);  
+    return true if @x == 2 && @y == 2;
+    ##
+    # sort the points and compute side lengths  
+    ##  
+    my @sorted_x = sort {$a->[0] <=> $b->[0]} @points;  
+    my @sorted_y = sort {$a->[1] <=> $b->[1]} @points;  
+    my($s, $t, $u, $v) = ($sorted_y[@sorted_y - 1], $sorted_x[@sorted_x - 1], $sorted_y[0], $sorted_x[0]);    
+    return false if $s->[0] + $u->[0] != $t->[0] + $v->[0];  
+    return false if $s->[1] + $u->[1] != $t->[1] + $v->[1];  
+    return false if $s->[1] - $u->[1] != $t->[0] - $v->[0];  
+    ##
+    # compute angles 
+    ##
+    my $dv_st = new Math::GSL::Vector([$s->[0] - $t->[0], $s->[1] - $t->[1]]); 
+    my $dv_tu = new Math::GSL::Vector([$t->[0] - $u->[0], $t->[1] - $u->[1]]); 
+    my $dv_uv = new Math::GSL::Vector([$u->[0] - $v->[0], $u->[1] - $v->[1]]); 
+    my $dv_vs = new Math::GSL::Vector([$v->[0] - $s->[0], $v->[1] - $s->[1]]); 
+    return false if $dv_st * $dv_tu != 0;
+    return false if $dv_tu * $dv_uv != 0;
+    return false if $dv_uv * $dv_vs != 0;
+    return true;  
+}
+
+
+
+MAIN:{
+    my @points;
+    @points = ([10, 20], [20, 20], [20, 10], [10, 10]);  
+    print is_square(@points) . "\n";  
+    @points = ([12, 24], [16, 10], [20, 12], [18, 16]);  
+    print is_square(@points) . "\n";  
+    @points = ([-3, 1], [4, 2], [9, -3], [2, -4]);  
+    print is_square(@points) . "\n";  
+    @points = ([0, 0], [2, 1], [3, -1], [1, -2]);  
+    print is_square(@points) . "\n";  
+}
diff --git a/challenge-123/adam-russell/prolog/ch-1.p b/challenge-123/adam-russell/prolog/ch-1.p
new file mode 100644
index 0000000000..cf4f659b5c
--- /dev/null
+++ b/challenge-123/adam-russell/prolog/ch-1.p
@@ -0,0 +1,42 @@
+:-initialization(main).  
+
+prime_factors(N, L):- 
+    N > 0,  
+    prime_factors(N, L, 2).
+prime_factors(1, [], _):- 
+    !.
+prime_factors(N, [F|L], F):-                     
+    R is N // F, 
+    N =:= R * F, 
+    !, 
+    prime_factors(R, L, F).
+prime_factors(N, L, F):-
+    next_factor(N, F, NF), 
+    prime_factors(N, L, NF).
+next_factor(_, 2, 3):- 
+    !.
+next_factor(N, F, NF):- 
+    F * F < N, 
+    !, 
+    NF is F + 2.
+next_factor(N, _, N).
+
+ugly(N, UglyNumber):-
+    ugly(N, 1, 1, _, UglyNumber).  
+ugly(1, _, _, _, 1).
+ugly(N, _, N, UglyNumber, UglyNumber).
+ugly(N, X, I, _, UglyNumber):-  
+    prime_factors(X, Factors), 
+    member(Factor, Factors),   
+    (Factor == 2; Factor == 3; Factor == 5), 
+    X0 is X + 1,  
+    I0 is I + 1,
+    ugly(N, X0, I0, X, UglyNumber).  
+ugly(N, X, I, UglyNext, UglyNumber):-  
+    X0 is X + 1,  
+    ugly(N, X0, I, UglyNext, UglyNumber).  
+
+main:-
+    ugly(10, UglyNumber),
+    write(UglyNumber), nl,
+    halt.   
diff --git a/challenge-123/adam-russell/prolog/ch-2.p b/challenge-123/adam-russell/prolog/ch-2.p
new file mode 100644
index 0000000000..3ca330adf5
--- /dev/null
+++ b/challenge-123/adam-russell/prolog/ch-2.p
@@ -0,0 +1,57 @@
+:-initialization(main).  
+
+dot_product(X0-Y0, X1-Y1, N):-
+    N0 is X0 * X1,
+    N is N0 + Y0 * Y1.  
+
+swap_key_value([], []).
+swap_key_value([A-B|R], [B-A|S]):-
+    swap_key_value(R, S). 
+
+square(Points):-
+    setof(X, member(X-_, Points),  Xs),    
+    setof(Y, member(_-Y, Points),  Ys),    
+    length(Xs, LXs),
+    length(Ys, LYs), 
+
+    keysort(Points, PointsByX),    
+    swap_key_value(Points, Swapped),
+    keysort(Swapped, PointsByY0),    
+    swap_key_value(PointsByY0, PointsByY),
+    last(PointsByY, Sx-Sy),  
+    last(PointsByX, Tx-Ty),  
+    nth(1, PointsByY, Ux-Uy),  
+    nth(1, PointsByX, Vx-Vy), 
+    SUx is Sx + Ux,
+    TVx is Tx + Vx,
+    SUy is Sy + Uy,
+    TVy is Ty + Vy,
+    SUym is Sy - Uy,
+    TVxm is Tx - Vx,
+
+    DVSTx is Sx - Tx,
+    DVSTy is Sy - Ty,
+    DVTUx is Tx - Ux,
+    DVTUy is Ty - Uy,
+    DVUVx is Ux - Vx,
+    DVUVy is Uy - Vy,
+    DVVSx is Vx - Sx,
+    DVVSy is Vy - Sy,
+
+    dot_product(DVSTx-DVSTy, DVTUx-DVTUy, DPSTU),   
+    dot_product(DVTUx-DVTUy, DVUVx-DVUVy, DPTUV),   
+    dot_product(DVUVx-DVUVy, DVVSx-DVVSy, DPUVS),   
+
+    ((LXs == 2, LYs == 2); (SUx == TVx, SUy == TVy, SUym == TVxm, DPSTU == 0, DPTUV == 0, DPUVS == 0)). 
+    
+
+main:-
+    ((square([10-20, 20-20, 20-10, 10-10]), write(1)); (write(0))), 
+    nl,
+    ((square([12-24, 16-10, 20-12, 18-16]), write(1)); (write(0))), 
+    nl,
+    ((square([-3-1, 4-2, -(9,-3), -(2,-4)]), write(1)); (write(0))), 
+    nl,
+    ((square([0-0, 2-1, -(3,-1), -(1,-2)]), write(1)); (write(0))), 
+    nl,
+    halt.