Merge pull request #1767 from sangeetkar/ch62

Ch62

15 files changed, 219 insertions, 0 deletions

diff --git a/challenge-062/sangeet-kar/perl/ch-1.1.sh b/challenge-062/sangeet-kar/perl/ch-1.1.sh
new file mode 100644
index 0000000000..77decb0596
--- /dev/null
+++ b/challenge-062/sangeet-kar/perl/ch-1.1.sh
@@ -0,0 +1 @@
+perl -F@ -alnE 'push @mails,[@F]; END {say join "@", @$_ for sort {fc(@$a[1]).@$a[0] cmp fc(@$b[1]).@$b[0]} @mails}' mails.txt 
diff --git a/challenge-062/sangeet-kar/perl/mails.txt b/challenge-062/sangeet-kar/perl/mails.txt
new file mode 100644
index 0000000000..5dc3f2ceb0
--- /dev/null
+++ b/challenge-062/sangeet-kar/perl/mails.txt
@@ -0,0 +1,5 @@
+name@example.org
+rjt@cpan.org
+Name@example.org
+rjt@CPAN.org
+user@alpha.example.org
diff --git a/challenge-062/sangeet-kar/perl/mails2.txt b/challenge-062/sangeet-kar/perl/mails2.txt
new file mode 100644
index 0000000000..10ec915529
--- /dev/null
+++ b/challenge-062/sangeet-kar/perl/mails2.txt
@@ -0,0 +1 @@
+ssk@gmail.com
diff --git a/challenge-062/sangeet-kar/python/ch-1.py b/challenge-062/sangeet-kar/python/ch-1.py
new file mode 100755
index 0000000000..3ac4b37683
--- /dev/null
+++ b/challenge-062/sangeet-kar/python/ch-1.py
@@ -0,0 +1,21 @@
+import sys
+
+unique = len(sys.argv) > 1 and sys.argv[1] == '-u'
+files = sys.argv[2:] if unique else sys.argv[1:]
+
+mails = []
+if files:
+    for f in files:
+        mails.extend(open(f).read().splitlines())
+else:
+    mails.extend(sys.stdin.read().splitlines())
+
+mails = [mail.split("@") for mail in mails]
+
+if unique:
+    mails = {(name, domain.lower()) for name, domain in mails}
+
+mails = sorted(mails,key=lambda pair: (pair[1].lower(), pair[0]))
+
+print("\n".join(f"{name}@{domain}" for name, domain in mails))
+
diff --git a/challenge-062/sangeet-kar/python/ch-2.py b/challenge-062/sangeet-kar/python/ch-2.py
new file mode 100755
index 0000000000..e243087412
--- /dev/null
+++ b/challenge-062/sangeet-kar/python/ch-2.py
@@ -0,0 +1,27 @@
+#!/usr/bin/env python
+
+import sys
+
+def n_queens_3d (n = 2):
+    solutions = []
+    place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], [], solutions)
+    return indices_to_array(max(solutions, key=len), n);
+
+def place_queen (indices, queens, solutions):
+    if not indices: solutions.append(queens)
+    for pos in indices:
+        place_queen ([index for index in indices if is_available(pos, index)], [*queens, pos], solutions)
+
+def is_available(ref, pos):
+    diff = {abs(i - j) for i, j in zip (ref, pos)}
+    return not ( len(diff) < 2 or (len(diff) == 2 and 0 in diff))
+
+def indices_to_array (indices, n):
+    array = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
+    for i, j, k in indices:
+        array[i][j][k] = 1
+    return array
+
+n = int(sys.argv[1]) if len(sys.argv) > 1 else 2
+print(n_queens_3d (n))
+
diff --git a/challenge-062/sangeet-kar/python/ch-2a.py b/challenge-062/sangeet-kar/python/ch-2a.py
new file mode 100755
index 0000000000..21ed5b6898
--- /dev/null
+++ b/challenge-062/sangeet-kar/python/ch-2a.py
@@ -0,0 +1,50 @@
+#!/usr/bin/env python
+
+import sys
+import heapq
+
+# 1. n_queens_3d finds the solution using beam search
+# 2. the higher the beam_width, the better is the solution. 
+# 3. with beam_width=1, it's very fast but the solution may not be optimal maximising the number of queens.
+# 4. with beam-width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n
+# 5. I think one can find the best solution with beam-width 2-3 for n-values less than 8
+
+
+def n_queens_3d (n = 2, beam_width = 2):
+    solutions = []
+    place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], 
+                 [], 
+                 solutions, 
+                 beam_width=beam_width)
+    best = max(solutions, key=len)
+    print(f"queens: {len(best)}")
+    return indices_to_array( best, n)
+
+def place_queen (indices, queens, solutions, beam_width=2):
+    if not indices: 
+        solutions.append(queens)
+        return
+    if beam_width == -1:
+        best = ((index, [i for i in indices if is_available(index, i)]) for index in indices)
+    else:
+        best = heapq.nlargest(beam_width, 
+                              ((index, [i for i in indices if is_available(index, i)]) for index in indices), 
+                              key=lambda pair: len(pair[1]))
+    for pos, available in best:
+        place_queen (available, [*queens, pos], solutions, beam_width=beam_width)
+
+def is_available(ref, pos):
+    diff = {abs(i - j) for i, j in zip (ref, pos)}
+    return not ( len(diff) < 2 or (len(diff) == 2 and 0 in diff))
+
+def indices_to_array (indices, n):
+    array = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
+    for i, j, k in indices:
+        array[i][j][k] = 1
+    return array
+
+n = int(sys.argv[1]) if len(sys.argv) > 1 else 2
+beam_width = int(sys.argv[2]) if len(sys.argv) > 2 else 2
+
+print(n_queens_3d (n, beam_width))
+
diff --git a/challenge-062/sangeet-kar/python/mails.txt b/challenge-062/sangeet-kar/python/mails.txt
new file mode 100644
index 0000000000..5dc3f2ceb0
--- /dev/null
+++ b/challenge-062/sangeet-kar/python/mails.txt
@@ -0,0 +1,5 @@
+name@example.org
+rjt@cpan.org
+Name@example.org
+rjt@CPAN.org
+user@alpha.example.org
diff --git a/challenge-062/sangeet-kar/python/mails2.txt b/challenge-062/sangeet-kar/python/mails2.txt
new file mode 100644
index 0000000000..10ec915529
--- /dev/null
+++ b/challenge-062/sangeet-kar/python/mails2.txt
@@ -0,0 +1 @@
+ssk@gmail.com
diff --git a/challenge-062/sangeet-kar/raku/ch-1.1.sh b/challenge-062/sangeet-kar/raku/ch-1.1.sh
new file mode 100644
index 0000000000..fd94c10be9
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/ch-1.1.sh
@@ -0,0 +1 @@
+raku -e 'lines>>.split("@").sort({.[1].lc ~ .[0]})>>.join("@")>>.say' mails.txt mails2.txt
diff --git a/challenge-062/sangeet-kar/raku/ch-1.2.sh b/challenge-062/sangeet-kar/raku/ch-1.2.sh
new file mode 100644
index 0000000000..c5975bcb52
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/ch-1.2.sh
@@ -0,0 +1 @@
+raku -e 'lines>>.split("@").unique(as=>{.[0] ~ .[1].lc}).sort({.[1].lc ~ .[0]})>>.join("@")>>.say' mails.txt
diff --git a/challenge-062/sangeet-kar/raku/ch-1.raku b/challenge-062/sangeet-kar/raku/ch-1.raku
new file mode 100755
index 0000000000..bf5c4afd00
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/ch-1.raku
@@ -0,0 +1,7 @@
+#!/usr/bin/env raku
+
+sub MAIN(Bool :$u=False, *@files){
+        my @mails = @files ?? @files.flatmap(*.IO.lines) 
+                           !! $*IN.lines;
+        @mails».split("@").&{$u ?? .unique(as => {$^a[0] ~ $^a[1].lc}) !! .self}.sort({.[1].lc ~ .[0]})».join("@")».say;
+}
diff --git a/challenge-062/sangeet-kar/raku/ch-2.raku b/challenge-062/sangeet-kar/raku/ch-2.raku
new file mode 100755
index 0000000000..3d973dab62
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/ch-2.raku
@@ -0,0 +1,35 @@
+#!/usr/bin/env raku
+
+sub n-queens-threeD($n = 2) {
+        my @solutions = [];
+        place-queen [^$n X ^$n X ^$n], [], @solutions;
+        return indices-to-array @solutions.max(+*), $n;
+}
+
+
+sub place-queen(@indices, @queens, @solutions) {
+       @solutions.push([@queens]) if not @indices;
+       for @indices -> $pos {
+               place-queen(@indices.grep({is-available($pos, $_)}), (|@queens, $pos), @solutions);
+       }
+}
+
+
+sub is-available($ref, $pos) {
+        my $diff = ($ref »-« $pos)».abs.Set;
+        not (+$diff == 1 || (+$diff == 2 && 0 ∈ $diff))
+}
+
+
+sub indices-to-array(@indices, $n) {
+    my @array = [[[ 0 xx $n] xx $n] xx $n];
+    for @indices -> ($x, $y, $z) {
+            @array[$x; $y; $z] = 1;
+    }
+    return @array;
+}
+
+
+sub MAIN (Int :$n=2) {
+        say n-queens-threeD $n;
+}
diff --git a/challenge-062/sangeet-kar/raku/ch-2a.raku b/challenge-062/sangeet-kar/raku/ch-2a.raku
new file mode 100755
index 0000000000..a1a9e78560
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/ch-2a.raku
@@ -0,0 +1,58 @@
+#!/usr/bin/env raku
+
+# 1. n-queens-d3 finds the solution using beam search
+# 2. the higher the beamr-width, the better is the solution. 
+# 3. with beam-width=1, it's very fast but the solution may not be optimal maximising the number of queens.
+# 4. with beam-width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n
+# 5. I think one can find the best solution with beam-width 2-3 for n-values less than 8
+
+sub n-queens-d3($n = 2, $beam-width=2) {
+        my @solutions = [];
+        place-queen [^$n X ^$n X ^$n], [], @solutions, $beam-width;
+        my $best = @solutions.max(+*);
+        say "Queens placed : ", +$best;
+        return indices-to-array $best, $n;
+}
+
+
+sub place-queen(@indices, @queens, @solutions, $beam-width=2) {
+       if not @indices {
+               @solutions.push(@queens);
+               return;
+       }
+       my @best = (for @indices -> $pos {($pos, @indices.grep({is-available($pos, $_)}))});
+       if $beam-width ≠ -1 {
+               @best = find-best($beam-width, @best, {+$^b[1] cmp +$^a[1]}); 
+       }
+       for @best -> ($pos, @available) {
+               place-queen(@available, (|@queens, $pos), @solutions, $beam-width);
+       }
+}
+
+
+sub is-available($ref, $pos) {
+        my $diff = ($ref »-« $pos)».abs.Set;
+        not (+$diff == 1 || (+$diff == 2 && 0 ∈ $diff))
+}
+
+
+sub indices-to-array(@indices, $n) {
+    my @array = [[[ 0 xx $n] xx $n] xx $n];
+    for @indices -> ($x, $y, $z) {
+            @array[$x; $y; $z] = 1;
+    }
+    return @array;
+}
+
+
+#| ideally this routine should use a priority queue for better efficiency
+sub find-best($n, @elems, &key){
+        my @sorted = @elems.sort(&key);
+        return @sorted[^$n] if +@sorted > $n;
+        return @sorted;
+}
+
+
+sub MAIN (Int :$n=2, Int :$beam=2) {
+        say n-queens-d3 $n, $beam;
+}
diff --git a/challenge-062/sangeet-kar/raku/mails.txt b/challenge-062/sangeet-kar/raku/mails.txt
new file mode 100644
index 0000000000..5dc3f2ceb0
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/mails.txt
@@ -0,0 +1,5 @@
+name@example.org
+rjt@cpan.org
+Name@example.org
+rjt@CPAN.org
+user@alpha.example.org
diff --git a/challenge-062/sangeet-kar/raku/mails2.txt b/challenge-062/sangeet-kar/raku/mails2.txt
new file mode 100644
index 0000000000..10ec915529
--- /dev/null
+++ b/challenge-062/sangeet-kar/raku/mails2.txt
@@ -0,0 +1 @@
+ssk@gmail.com