Merge pull request #2760 from hstejas/heads/refs/c86

The Weekly Challenge - 086

5 files changed, 397 insertions, 0 deletions

diff --git a/challenge-086/hstejas/README b/challenge-086/hstejas/README
new file mode 100644
index 0000000000..969c5c0569
--- /dev/null
+++ b/challenge-086/hstejas/README
@@ -0,0 +1 @@
+Solution by Tejas
diff --git a/challenge-086/hstejas/cpp/c1.cpp b/challenge-086/hstejas/cpp/c1.cpp
new file mode 100644
index 0000000000..79fa9a55bc
--- /dev/null
+++ b/challenge-086/hstejas/cpp/c1.cpp
@@ -0,0 +1,43 @@
+#include <iostream>
+#include <algorithm>
+#include <vector>
+
+// g++ --std=c++17 c1.cpp && ./a.out
+
+void pair_diff(unsigned int reference, std::vector<int> nums)
+{
+    std::sort(nums.begin(), nums.end(), std::greater<int>());
+    auto start = nums.begin();
+    auto curr = start;
+    while(start != nums.end() && curr != nums.end())
+    {
+        ++curr;
+        int diff = std::abs(*start - *curr);
+        if(diff == reference)
+        {
+            std::cout << "1 as " << *start << " - " << *curr << " = " << diff << std::endl;
+            return;
+        }
+        else if (diff > reference)
+        {
+            ++start;
+            curr = start;
+        }
+    }
+    std::cout << "0" << std::endl;
+}
+
+int main()
+{
+    std::vector<std::pair< int, std::vector<int>>> tests { 
+        {7, {50, 8, 12, 15, 5} },
+        {6, {1, 5, 2, 9, 7} },
+        {15, {10, 30, 20, 50, 40} },
+        {15, {-15, -5, -30, 20, 50, 40} }
+    };
+
+    for (auto test : tests)
+    {
+        pair_diff(test.first, test.second);
+    }
+}
\ No newline at end of file
diff --git a/challenge-086/hstejas/cpp/c2.cpp b/challenge-086/hstejas/cpp/c2.cpp
new file mode 100644
index 0000000000..534a5f036b
--- /dev/null
+++ b/challenge-086/hstejas/cpp/c2.cpp
@@ -0,0 +1,210 @@
+#include <array>
+#include <vector>
+#include <set>
+#include <iostream>
+#include <utility>
+
+// https://raw.githubusercontent.com/agauniyal/rang/master/include/rang.hpp
+#include "rang.hpp"
+
+// g++ --std=c++17 c2.cpp -O2 && ./a.out
+
+namespace std
+{
+    std::string to_string(bool in)
+    {
+        return in ? "true" : "false";
+    }
+} // namespace std
+
+class Board
+{
+public:
+
+    Board(const std::array<std::array<int, 9>, 9>& in)
+    :mBoard(in) { }
+
+    void fill(int* in)
+    {
+        for(size_t row = 0; row < mBoard.size(); row++)
+        {
+            for(size_t col = 0; col < mBoard.size(); col++)
+            {
+                *(in + (mBoard.size() * row) + col) = mBoard[row][col];
+            }
+        }
+    }
+
+    void checkPrint(const std::array<std::array<int, 9>, 9>& ref)
+    {
+        for(size_t row=0; row < mBoard.size(); row++)
+        {
+            for(size_t col=0; col < mBoard.size(); col++)
+            {
+                if(mBoard[row][col] == ref[row][col])
+                {
+                    std::cout << mBoard[row][col] << " ";
+                }
+                else
+                {
+                    std::cout << rang::fg::red << mBoard[row][col] << rang::fg::reset << " ";
+                }
+            }
+            std::cout << std::endl;
+        }
+    }
+
+    void print()
+    {
+        for(size_t row=0; row < mBoard.size(); row++)
+        {
+            for(size_t col=0; col < mBoard.size(); col++)
+            {
+                if(mBoard[row][col] != 0)
+                {
+                    std::cout << mBoard[row][col] << " ";
+                }
+                else
+                {
+                    std::cout << rang::fg::red << mBoard[row][col] << rang::fg::reset << " ";
+                }
+            }
+            std::cout << std::endl;
+        }
+    }
+
+    bool solve()
+    {
+        bool result = solveNext(0, 0);
+        std::cout << "Solved? " << std::to_string(result) << std::endl;
+        return result;
+    }
+
+protected:
+
+    bool validRow(int num, size_t row)
+    {
+        return std::find(mBoard[row].begin(), mBoard[row].end(), num) == mBoard[row].end();
+    }
+
+    bool validCol(int num, size_t col)
+    {
+        // entire col
+        for(size_t irow = 0; irow < mBoard.size(); irow++)
+        {
+            if(mBoard[irow][col] == num)
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool validBox(int num, size_t row, size_t col)
+    {
+        size_t oRow = 3 * (row / 3);
+        size_t oCol = 3 * (col / 3);
+        // entire box
+        for(size_t irow = oRow; irow < oRow+3; irow++)
+        {
+            if(std::find(mBoard[irow].begin() + oCol, mBoard[irow].begin() + oCol + 3, num) 
+                != (mBoard[irow].begin() + oCol + 3))
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool isValid(int num, size_t row, size_t col)
+    {
+        return validRow(num, row) && validCol(num, col) && validBox(num, row, col);
+    }
+
+    bool solveNext(size_t row, size_t col)
+    {
+        if(mBoard[row][col] == 0)
+        {
+            for(int num = 1; num <=9; num++)
+            {
+                if(isValid(num, row, col))
+                {
+                    mBoard[row][col] = num;
+                    size_t nextCol = col == 8 ? 0 : col+1;
+                    size_t nextRow = col == 8 ? row + 1 : row;
+                    if(nextRow == 9 || solveNext(nextRow, nextCol))
+                    {
+                        return true;
+                    }
+                    mBoard[row][col] = 0;
+                }
+            }
+        }
+        else
+        {
+            size_t nextCol = col == 8 ? 0 : col + 1;
+            size_t nextRow = col == 8 ? row + 1 : row;
+            if(nextRow == 9 || solveNext(nextRow, nextCol))
+            {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    std::array<std::array<int, 9>, 9> mBoard;
+};
+
+#ifdef BUILD_SHARED
+extern "C" {
+    bool solve(int *data)
+    {
+        std::array< std::array<int, 9>, 9> input;
+        for(size_t row = 0; row < input.size(); row++)
+        {
+            for(size_t col = 0; col < input.size(); col++)
+            {
+                input[row][col] = *(data + (row * input.size()) + col);
+            }
+        }
+
+        Board board(input);
+        board.print();
+        bool ret = board.solve();
+        board.print();
+        board.fill(data);
+        return ret;
+    }
+}
+#else
+int main()
+{
+    std::array< std::array<int, 9>, 9> solved {{
+        { 4, 3, 5, 2, 6, 9, 7, 8, 1 },
+        { 6, 8, 2, 5, 7, 1, 4, 9, 3 },
+        { 1, 9, 7, 8, 3, 4, 5, 6, 2 },
+        { 8, 2, 6, 1, 9, 5, 3, 4, 7 },
+        { 3, 7, 4, 6, 8, 2, 9, 1, 5 },
+        { 9, 5, 1, 7, 4, 3, 6, 2, 8 },
+        { 5, 1, 9, 3, 2, 6, 8, 7, 4 },
+        { 2, 4, 8, 9, 5, 7, 1, 3, 6 },
+        { 7, 6, 3, 4, 1, 8, 2, 5, 9 },
+    }};
+
+    std::array< std::array<int, 9>, 9> input {{
+        { 0, 0, 0, 2, 6, 0, 7, 0, 1 },
+        { 6, 8, 0, 0, 7, 0, 0, 9, 0 },
+        { 1, 9, 0, 0, 0, 4, 5, 0, 0 },
+        { 8, 2, 0, 1, 0, 0, 0, 4, 0 },
+        { 0, 0, 4, 6, 0, 2, 9, 0, 0 },
+        { 0, 5, 0, 0, 0, 3, 0, 2, 8 },
+        { 0, 0, 9, 3, 0, 0, 0, 7, 4 },
+        { 0, 4, 0, 0, 5, 0, 0, 3, 6 },
+        { 7, 0, 3, 0, 1, 8, 0, 0, 0 },
+    }};
+
+    Board board(input);
+    board.solve();
+    board.print();
+}
+#endif // BUILD_SHARED
\ No newline at end of file
diff --git a/challenge-086/hstejas/perl/c1.pl b/challenge-086/hstejas/perl/c1.pl
new file mode 100755
index 0000000000..8c1e81a7ba
--- /dev/null
+++ b/challenge-086/hstejas/perl/c1.pl
@@ -0,0 +1,38 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use v5.30;
+
+sub pair_diff {
+    my $ref = abs(shift);
+    my @nums = sort { $b <=> $a } @{ shift @_ };
+
+    while(@nums) {
+        my $num = shift @nums;
+        foreach(@nums) {
+            my $diff = abs($num - $_);
+            if($diff == $ref) {
+                say "1 as $num - $_ = $ref";
+                return;
+            }
+            elsif($diff > $ref) {
+                last;
+            }
+        }
+    }
+    say '0';
+}
+
+my $tests = {
+    'Test1' => { 'ref' => 7, 'arr' => [10, 8, 12, 15, 5] },
+    'Test2' => { 'ref' => 6, 'arr' => [1, 5, 2, 9, 7] },
+    'Test3' => { 'ref' => 15, 'arr' => [10, 30, 20, 50, 40] },
+    'Test4' => { 'ref' => 15, 'arr' => [-15, -5, -30, 20, 50, 40] },
+    'Test5' => { 'ref' => -15, 'arr' => [-15, -5, -30, 20, 50, 40] },
+    'Test6' => { 'ref' => 1, 'arr' => [9, map { $_ * 10 } 1..900000 ] },
+};
+
+foreach(sort keys %{$tests}) {
+    my $test = $tests->{$_};
+    pair_diff($test->{'ref'}, $test->{'arr'});
+}
\ No newline at end of file
diff --git a/challenge-086/hstejas/perl/c2.pl b/challenge-086/hstejas/perl/c2.pl
new file mode 100755
index 0000000000..a72ffa21ea
--- /dev/null
+++ b/challenge-086/hstejas/perl/c2.pl
@@ -0,0 +1,105 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use v5.30;
+
+# g++ --std=c++17 -DBUILD_SHARED ../cpp/c2.cpp -O2 -fPIC -shared -o sudoku.so
+use FFI::Platypus;
+
+# sudo apt install libgtk3-perl 
+use Gtk3 -init;
+
+use Data::Dumper;
+
+
+my $ffi = FFI::Platypus->new( api => 1 );
+$ffi->lib('./sudoku.so');
+
+$ffi->attach( 'solve' => ['int[]']  => 'bool' );
+
+my @puzzle = ( '', '', '',  2,  6, '',  7, '',  1,
+                6,  8, '', '',  7, '', '',  9, '',
+                1,  9, '', '', '',  4,  5, '', '',
+                8,  2, '',  1, '', '', '',  4, '',
+               '', '',  4,  6, '',  2,  9, '', '',
+               '',  5, '', '', '',  3, '',  2,  8,
+               '', '',  9,  3, '', '', '',  7,  4,
+               '',  4, '', '',  5, '', '',  3,  6,
+                7, '',  3, '',  1,  8, '', '', '',);
+
+my $window = Gtk3::Window->new ('toplevel');
+$window->signal_connect (delete_event => sub { Gtk3->main_quit });
+$window->set_title("Sudoku Solver");
+$window->set_border_width(5);
+
+my $provider = Gtk3::CssProvider->new();
+my $screen = Gtk3::Gdk::Screen::get_default;
+Gtk3::StyleContext::add_provider_for_screen($screen, $provider, 600);
+$provider->load_from_data('#boxsep { margin: 5px;} #boardsep { margin: 8px; }');
+
+my @input_boxes;
+
+my $vbox = Gtk3::Box->new( 'vertical', 5 );
+$window->add($vbox);
+
+for my $row (0..8) {
+    if($row == 3 or $row == 6) {
+        my $sep = Gtk3::HSeparator->new;
+        $sep->set_name('boxsep');
+        $vbox->add($sep);
+    }
+
+    my $hbox = Gtk3::Box->new( 'horizontal', 5 );
+    $vbox->add($hbox);
+
+    for my $col (0..8) {
+        if($col == 3 or $col == 6) {
+            my $sep = Gtk3::VSeparator->new();
+            $sep->set_name('boxsep');
+            $hbox->add($sep);
+        }
+        my $cell = new Gtk3::Entry->new;
+        $cell->set_width_chars(2);
+        $cell->set_text($puzzle[$row*9 + $col]);
+        push @input_boxes, $cell;
+        $hbox->add($cell)
+    }
+}
+my $board_sep = Gtk3::HSeparator->new;
+$board_sep->set_name('boardsep');
+$vbox->add($board_sep);
+
+my $solve_btn = Gtk3::Button->new('Solve');
+$solve_btn->signal_connect (clicked => sub { 
+        my @input_nums;
+        foreach(@input_boxes) {
+            my $text = $_->get_text();
+            push @input_nums,  ($text ? $text : 0);
+        }
+        my $result = solve(\@input_nums);
+        if($result) {
+            for(my $i = 0; $i <= $#input_nums; $i++) {
+                $input_boxes[$i]->set_text($input_nums[$i]);
+            }
+        }
+        else {
+            my $error_dialog = Gtk3::MessageDialog->new($window, 'destroy-with-parent', 'error', 'ok', 'Error solving Sudoku');
+            $error_dialog->present();
+            $error_dialog->signal_connect( response => sub { $error_dialog->destroy() } );
+        }
+    });
+
+my $clear_btn = Gtk3::Button->new('Clear');
+$clear_btn->signal_connect (clicked => sub {
+        for(@input_boxes) {
+            $_->set_text('');
+        }
+    });
+
+my $buttons = Gtk3::HBox->new;
+$buttons->add($solve_btn);
+$buttons->add($clear_btn);
+$vbox->add($buttons);
+
+$window->show_all;
+Gtk3::main;