Merge pull request #4357 from jaldhar/challenge-118

Challenge 118 by Jaldhar H. vyas.

6 files changed, 566 insertions, 0 deletions

diff --git a/challenge-118/jaldhar-h-vyas/blog.txt b/challenge-118/jaldhar-h-vyas/blog.txt
new file mode 100644
index 0000000000..ffab2a8338
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/blog.txt
@@ -0,0 +1 @@
+https://www.braincells.com/perl/2021/06/perl_weekly_challenge_week_118.html
diff --git a/challenge-118/jaldhar-h-vyas/c++/ch-2.cpp b/challenge-118/jaldhar-h-vyas/c++/ch-2.cpp
new file mode 100644
index 0000000000..055532f6db
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/c++/ch-2.cpp
@@ -0,0 +1,193 @@
+// Compile with g++ -std=c++17 -O2 -g -Wall -Wextra -pedantic -o ch-2 ch-2.cpp
+
+#include <algorithm>
+#include <array>
+#include <climits>
+#include <cmath>
+#include <iostream>
+#include <iterator>
+#include <optional>
+#include <vector>
+
+struct Position {
+    int row_;
+    int col_;
+};
+
+using Targets = std::array<Position, 6>;
+using Deltas = std::array<Position, 8>;
+using Path = std::vector<Position>;
+
+std::ostream& operator<<(std::ostream& out, const Position& position) {
+    out << (char)('a' + position.col_)  << 8 - position.row_;
+    return out;
+}
+
+bool operator==(const Position& a, const Position& b) {
+    return a.row_ == b.row_ && a.col_ == b.col_;
+}
+
+bool operator!=(const Position& a, const Position& b) {
+    return !operator==(a, b);
+}
+
+bool operator<(const Position& a, const Position& b) {
+    return (8 * a.row_ + a.col_) < (8 * b.row_ + b.col_);
+}
+
+// Unused in this program but hey why not...
+bool operator>(const Position& a, const Position& b) {
+    return !operator<(a, b);
+}
+
+std::optional<Position> tryMove(const Position& pos, const Position& delta) {
+    auto dest = pos;
+    dest.row_ += delta.row_;
+    dest.col_ += delta.col_;
+    return (dest.row_ >= 0 && dest.row_ < 8 && dest.col_ >= 0 && dest.col_ < 8)
+        ? std::make_optional(dest)
+        : std::nullopt;
+}
+
+std::vector<Position> possibleMoves(const Position& pos,const Position& target){
+    static const Deltas deltas{{
+        {-2, -1},
+        {-2, 1},
+        {-1, 2},
+        {1, 2},
+        {2, 1},
+        {2, -1},
+        {-1, -2},
+        {1, -2}
+    }};
+
+    std::vector<Position> moves;
+
+    std::for_each(deltas.begin(), deltas.end(),
+    [&pos, &moves](const auto& delta) {
+        if (auto move = tryMove(pos, delta)) {
+            moves.push_back(*move);
+        }
+    });
+
+    std::sort(moves.begin(), moves.end(),
+    [&target](const auto& a, const auto& b) {
+        return estimatedCost(a, target) < estimatedCost(b, target);
+    });
+
+    return moves;
+}
+
+// size_t used here because we will be comparing with path size.
+std::size_t estimatedCost(const Position& position, const Position& goal){
+    static const std::array<std::size_t, 64> distance{
+        0, 3, 2, 3, 2, 3, 4, 5,
+        3, 2, 1, 2, 3, 4, 3, 4,
+        2, 1, 4, 3, 2, 3, 4, 5,
+        3, 2, 3, 2, 3, 4, 3, 4,
+        2, 3, 2, 3, 4, 3, 4, 5,
+        3, 4, 3, 4, 3, 4, 5, 4,
+        4, 3, 4, 3, 4, 5, 4, 5,
+        5, 4, 5, 4, 5, 4, 5, 6
+    };
+
+    return distance[std::abs(position.row_ - goal.row_) * 8 +
+        std::abs(position.col_ - goal.col_)];
+}
+
+int search(const Position& target, Path& path, std::size_t estimate) {
+    const auto& current = path.back();
+    const auto cost = path.size() + estimatedCost(current, target);
+
+    if (cost > estimate) {
+        return cost;
+    }
+
+    if (current == target) {
+        return INT_MIN;
+    }
+
+    int min = INT_MAX;
+
+    for (const auto& move: possibleMoves(current, target)) {
+        if (std::find(path.begin(), path.end(), move) == path.end()) {
+            path.push_back(move);
+            int t = search(target, path, estimate);
+
+            if (t == INT_MIN) {
+                return INT_MIN;
+            }
+
+            if (t < min) {
+                min = t;
+            }
+            path.pop_back();
+        }
+    }
+
+    return min;
+}
+
+Path makePath(Position& knight, const Targets& targets) {
+    Path path;
+    path.push_back(knight);
+
+    for(const auto& target: targets) {
+        Path stage;
+        stage.push_back(knight);
+        auto estimate = estimatedCost(knight, target);
+
+        while (true) {
+            int t = search(target, stage, estimate);
+
+            if (t == INT_MIN) {
+                break;
+            }
+
+            // Can't solve; this shouldn't happen.
+            if (t == INT_MAX) {
+                break;
+            }
+
+            estimate = t;
+        }
+
+        std::copy(std::next(stage.begin()), stage.end(),
+            std::back_inserter(path));
+
+        stage.clear();
+        knight = target;
+    }
+
+    return path;
+}
+
+int main() {
+    Targets treasures{{
+        {2, 4},
+        {4, 2},
+        {5, 1},
+        {6, 0},
+        {6, 1},
+        {7, 1},
+    }};
+
+    std::size_t shortest = INT_MAX;
+    Path shortestPath;
+    do {
+        Position knight{0, 0};
+
+        auto path = makePath(knight, treasures);
+        if (path.size() < shortest) {
+            shortest = path.size();
+            shortestPath = path;
+        }
+
+    } while (std::next_permutation(treasures.begin(), treasures.end()));
+
+    std::copy(shortestPath.begin(), shortestPath.end(),
+            std::ostream_iterator<Position>(std::cout, " "));
+    std::cout << '\n';
+
+    return 0;
+}
\ No newline at end of file
diff --git a/challenge-118/jaldhar-h-vyas/perl/ch-1.pl b/challenge-118/jaldhar-h-vyas/perl/ch-1.pl
new file mode 100755
index 0000000000..4ff70a55f1
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/perl/ch-1.pl
@@ -0,0 +1,8 @@
+#!/usr/bin/perl
+use 5.020;
+use warnings;
+
+my $N = shift // die "Must specify an integer.\n";
+
+my $binary = sprintf "%b", $N;
+say 0+($binary eq reverse $binary) ? 1 : 0;
\ No newline at end of file
diff --git a/challenge-118/jaldhar-h-vyas/perl/ch-2.pl b/challenge-118/jaldhar-h-vyas/perl/ch-2.pl
new file mode 100755
index 0000000000..e73148644a
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/perl/ch-2.pl
@@ -0,0 +1,194 @@
+#!/usr/bin/perl
+
+package Position;
+use Moo;
+use namespace::clean;
+
+has row => (
+    is => 'rw',
+);
+
+has col => (
+    is => 'rw',
+);
+
+around BUILDARGS => sub {
+    my ($orig, $class, @args) = @_;
+    return { row => $args[0], col => $args[1] };
+};
+
+sub str {
+    my ($self) = @_;
+    return chr(ord('a') + $self->col) . (8 - $self->row);
+}
+
+1;
+
+package main;
+use 5.020;
+use warnings;
+
+sub permute (&@) {
+    my $code = shift;
+    my @idx = 0..$#_;
+    while ( $code->(@_[@idx]) ) {
+        my $p = $#idx;
+        --$p while $idx[$p-1] > $idx[$p];
+        my $q = $p or return;
+        push @idx, reverse splice @idx, $p;
+        ++$q while $idx[$p-1] > $idx[$q];
+        @idx[$p-1,$q]=@idx[$q,$p-1];
+    }
+}
+
+sub compare {
+    my ($a, $b) = @_;
+    return $a->row == $b->row && $a->col == $b->col;
+}
+
+sub estimatedCost {
+    my ($position, $goal) = @_;
+
+    state @distance = (
+        0, 3, 2, 3, 2, 3, 4, 5,
+        3, 2, 1, 2, 3, 4, 3, 4,
+        2, 1, 4, 3, 2, 3, 4, 5,
+        3, 2, 3, 2, 3, 4, 3, 4,
+        2, 3, 2, 3, 4, 3, 4, 5,
+        3, 4, 3, 4, 3, 4, 5, 4,
+        4, 3, 4, 3, 4, 5, 4, 5,
+        5, 4, 5, 4, 5, 4, 5, 6
+    );
+
+    return $distance[abs($position->row - $goal->row) * 8 +
+        abs($position->col - $goal->col)];
+}
+
+sub tryMove {
+    my ($position, $delta) = @_;
+
+    my $dest = Position->new($position->row + $delta->row, $position->col + $delta->col);
+    return ($dest->row >= 0 && $dest->row < 8 && $dest->col >= 0 && $dest->col < 8)
+        ? $dest
+        : undef;
+}
+
+sub possibleMoves {
+    my ($position, $target) = @_;
+
+    state @deltas = (
+        Position->new(-2, -1),
+        Position->new(-2, 1),
+        Position->new(-1, 2),
+        Position->new(1, 2),
+        Position->new(2, 1),
+        Position->new(2, -1),
+        Position->new(-1, -2),
+        Position->new(1, -2)
+    );
+
+    my @moves;
+    for my $delta (@deltas) {
+        my $move = tryMove($position, $delta);
+        if (defined $move) {
+            push @moves, $move;
+        }
+    }
+
+    @moves = sort { estimatedCost($a, $target) < estimatedCost($b, $target); } @moves;
+
+    return @moves;
+}
+
+sub search {
+    my ($target, $path, $estimate) = @_;
+    my $current = $path->[-1];
+    my $cost = (scalar @{$path}) + estimatedCost($current, $target);
+
+    if ($cost > $estimate) {
+        return $cost;
+    }
+
+    if (compare($current, $target)) {
+        return '-inf';
+    }
+
+    my $min = 'inf';
+
+    for my $move (possibleMoves($current, $target)) {
+        if (!grep { $_ if compare($_, $move); } @{$path}) {
+            push @{$path}, $move;
+            my $t = search($target, $path, $estimate);
+
+            if ($t == '-inf') {
+                return '-inf';
+            }
+
+            if ($t < $min) {
+                $min = $t;
+            }
+
+            pop @{$path};
+        }
+    }
+
+    return $min;
+}
+
+sub makePath {
+    my ($knight, $targets) = @_;
+    my @path = ( $knight );
+
+    for my $target (@{$targets}) {
+        my @stage = ( $knight );
+        my $estimate = estimatedCost($knight, $target);
+
+        while(1) {
+            my $t = search($target, \@stage, $estimate);
+
+            if ($t == '-inf') {
+                last;
+            }
+
+            # Can't solve; this shouldn't happen.
+            if ($t == 'inf') {
+                last;
+            }
+
+            $estimate = $t;
+        }
+
+        push @path, splice(@stage, 1);
+        @stage = ();
+        $knight = $target;
+    }
+
+    return @path;
+}
+
+my @treasures = (
+    Position->new(2, 4),
+    Position->new(4, 2),
+    Position->new(5, 1),
+    Position->new(6, 0),
+    Position->new(6, 1),
+    Position->new(7, 1),
+);
+
+my $shortest = 'inf';
+my @shortestPath;
+my @permutations;
+permute { push @permutations, \@_; } @treasures;
+
+for my $perm (@permutations) {
+    my $knight = Position->new(0, 0);
+
+    my @path = makePath($knight, $perm);
+
+    if (scalar @path < $shortest) {
+        $shortest = scalar @path;
+        @shortestPath = @path;
+    }
+}
+
+say join q{ }, map { $_-> str } @shortestPath;
diff --git a/challenge-118/jaldhar-h-vyas/raku/ch-1.raku b/challenge-118/jaldhar-h-vyas/raku/ch-1.raku
new file mode 100755
index 0000000000..2b14fcb249
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/raku/ch-1.raku
@@ -0,0 +1,8 @@
+#!/usr/bin/raku
+
+sub MAIN(
+    Int $N #= an integer
+) {
+    my $binary = $N.base(2);
+    say ($binary eq $binary.flip) ?? 1 !! 0;
+}
\ No newline at end of file
diff --git a/challenge-118/jaldhar-h-vyas/raku/ch-2.raku b/challenge-118/jaldhar-h-vyas/raku/ch-2.raku
new file mode 100755
index 0000000000..6373471fe3
--- /dev/null
+++ b/challenge-118/jaldhar-h-vyas/raku/ch-2.raku
@@ -0,0 +1,162 @@
+#!/usr/bin/raku
+
+class Position {
+    has Int $.row is rw;
+    has Int $.col is rw;
+
+    method new( $row, $col ) {
+        self.bless(:$row, :$col);
+    }
+
+    method Str {
+        ('a'.ord + $!col).chr ~ (8 - $!row).Str;
+    }
+}
+
+multi sub infix:<==>(Position $a, Position $b) returns Bool {
+    return $a.row == $b.row && $a.col == $b.col;
+}
+
+sub estimatedCost(Position $position, Position $goal) {
+    state @distance = [
+        0, 3, 2, 3, 2, 3, 4, 5,
+        3, 2, 1, 2, 3, 4, 3, 4,
+        2, 1, 4, 3, 2, 3, 4, 5,
+        3, 2, 3, 2, 3, 4, 3, 4,
+        2, 3, 2, 3, 4, 3, 4, 5,
+        3, 4, 3, 4, 3, 4, 5, 4,
+        4, 3, 4, 3, 4, 5, 4, 5,
+        5, 4, 5, 4, 5, 4, 5, 6
+    ];
+
+    return @distance[abs($position.row - $goal.row) * 8 +
+        abs($position.col - $goal.col)];
+}
+
+sub tryMove(Position $position, Position $delta) {
+    my $dest = $position.clone;
+    $dest.row += $delta.row;
+    $dest.col += $delta.col;
+    return ($dest.row >= 0 && $dest.row < 8 && $dest.col >= 0 && $dest.col < 8)
+        ?? $dest
+        !! Nil;
+}
+
+sub possibleMoves(Position $position, Position $target) {
+    state @deltas = [
+        Position.new(-2, -1),
+        Position.new(-2, 1),
+        Position.new(-1, 2),
+        Position.new(1, 2),
+        Position.new(2, 1),
+        Position.new(2, -1),
+        Position.new(-1, -2),
+        Position.new(1, -2)
+    ];
+
+    my @moves;
+    for @deltas -> $delta {
+        my $move = tryMove($position, $delta);
+        if $move {
+            @moves.push($move);
+        }
+    }
+
+    @moves = @moves.sort({
+        estimatedCost($^a, $target) < estimatedCost($^b, $target);
+    });
+
+    return @moves;
+}
+
+sub search(Position $target, Position @path, Int $estimate) {
+    my $current = @path[*-1];
+    my $cost = @path.elems + estimatedCost($current, $target);
+
+    if $cost > $estimate {
+        return $cost;
+    }
+
+    if $current == $target {
+        return -∞;
+    }
+
+    my $min = ∞;
+
+    for possibleMoves($current, $target) -> $move {
+        if $move ⊄ @path {
+            @path.push($move);
+            my $t = search($target, @path, $estimate);
+
+            if $t == -∞ {
+                return -∞;
+            }
+
+            if $t < $min {
+                $min = $t;
+            }
+
+            @path.pop;
+        }
+    }
+
+    return $min;
+}
+
+sub makePath(Position $knight is rw, Position @targets) {
+    my @path = [ $knight ];
+
+    for @targets -> $target {
+        my Position @stage = [ $knight ];
+        my $estimate = estimatedCost($knight, $target);
+
+        loop {
+            my $t = search($target, @stage, $estimate);
+
+            if $t ~~ -∞ {
+                last;
+            }
+
+            # Can't solve; this shouldn't happen.
+            if $t ~~ ∞ {
+                last;
+            }
+
+            $estimate = $t;
+        }
+
+        @path.push(| @stage[1 .. *]);
+        @stage = [];
+        $knight = $target;
+    }
+
+    return @path;
+}
+
+sub MAIN() {
+
+    my Position @treasures = [
+        Position.new(2, 4),
+        Position.new(4, 2),
+        Position.new(5, 1),
+        Position.new(6, 0),
+        Position.new(6, 1),
+        Position.new(7, 1),
+    ];
+
+    my $shortest = ∞;
+    my @shortestPath;
+    for @treasures.permutations -> @perm {
+        my $knight = Position.new(0, 0);
+        my Position @p = @perm;
+
+        my @path = makePath($knight, @p);
+
+        if @path.elems < $shortest {
+            $shortest = @path.elems;
+            @shortestPath = @path;
+        }
+    }
+
+    @shortestPath.join(q{ }).say;
+}
\ No newline at end of file