Merge pull request #2185 from Firedrake/rogerbw-challenge-076

Solution for challenge #76.

5 files changed, 287 insertions, 0 deletions

diff --git a/challenge-076/roger-bell-west/perl/ch-1.pl b/challenge-076/roger-bell-west/perl/ch-1.pl
new file mode 100755
index 0000000000..63a23ef8dd
--- /dev/null
+++ b/challenge-076/roger-bell-west/perl/ch-1.pl
@@ -0,0 +1,40 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::Util qw(sum);
+
+use Test::More tests => 1;
+
+is(psum(9),2,"example");
+
+sub psum {
+  my $n=shift;
+  my %pr=map {$_ => 1} (2..$n);
+  foreach my $m (2..$n) {
+    foreach my $mi (2..$n) {
+      delete $pr{$m*$mi};
+    }
+  }
+  my @p=sort {$b <=> $a} keys %pr;
+  my %pi=map {$p[$_] => $_} (0..$#p);
+  my @c=([]);
+  my @o;
+  while (my $r=shift @c) {
+    my $s=$n;
+    if (@{$r}) {
+      $s-=sum(map {$p[$_]} @{$r});
+    }
+    if ($s>0) {
+      my %ru=map {$_ => 1} @{$r};
+      foreach my $ci (grep {!exists $ru{$_}} map {$pi{$_}} grep {$_ <= $s} @p) {
+        push @c,[@{$r},$ci];
+      }
+    } elsif ($s==0) {
+      @o=map {$p[$_]} @{$r};
+      last;
+    }
+  }
+  return scalar @o;
+}
diff --git a/challenge-076/roger-bell-west/perl/ch-2.pl b/challenge-076/roger-bell-west/perl/ch-2.pl
new file mode 100755
index 0000000000..949c6a5723
--- /dev/null
+++ b/challenge-076/roger-bell-west/perl/ch-2.pl
@@ -0,0 +1,76 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::Util qw(max);
+
+my $minlen=5;
+
+my $y;
+my @grid;
+my @searchspaces;
+open I,'<',$ARGV[0] or die "Can't open puzzle file\n";
+while (<I>) {
+  chomp;
+  s/ +//g;
+  $_=lc($_);
+  if (defined $y) {
+    if ($y != length($_)) {
+      die "Not a rectangular grid\n";
+    }
+  } else {
+    $y = length($_);
+  }
+  push @searchspaces,$_; # horizontal forward
+  push @grid,[split '',$_];
+  push @searchspaces,join('',reverse(@{$grid[-1]})); # horizontal backward
+}
+close I;
+my $x=scalar @grid;
+
+foreach my $i (0..$y-1) {
+  my @q=map {$grid[$_][$i]} (0..$x-1);
+  push @searchspaces,join('',@q); # vertical forward
+  push @searchspaces,join('',reverse @q); # vertical backward
+}
+
+{
+  # +x +y diagonals
+  my $mxy=max($x,$y)-1;
+  foreach my $xi (-$y+$minlen-1..$x-$minlen+1) {
+    my @seq=map {[$xi+$_,$_]} grep {$xi+$_>=0 && $xi+$_<$x && $_<$y} (0..$mxy);
+    if (scalar @seq >= $minlen) {
+      my @q=map {$grid[$_->[0]][$_->[1]]} @seq;
+      push @searchspaces,join('',@q);
+      push @searchspaces,join('',reverse @q);
+    }
+  }
+  # -x +y diagonals
+  foreach my $xi (-$y+$minlen-1..$x-$minlen+1) {
+    my @seq=map {[$xi+$_,$y-$_]} grep {$xi+$_>=0 && $y-$_>=0 && $xi+$_<$x} (1..$mxy);
+    if (scalar @seq >= $minlen) {
+      my @q=map {$grid[$_->[0]][$_->[1]]} @seq;
+      push @searchspaces,join('',@q);
+      push @searchspaces,join('',reverse @q);
+    }
+  }
+}
+
+my @found;
+open I,'<',$ARGV[1] or die "Can't open wordlist file\n";
+while (<I>) {
+  chomp;
+  if (length($_) >= $minlen) {
+    my $w=lc($_);
+    foreach my $ss (@searchspaces) {
+      if (index($ss,$w) > -1) {
+        push @found,$w;
+        last;
+      }
+    }
+  }
+}
+close I;
+
+print join(', ',sort @found),"\n";
diff --git a/challenge-076/roger-bell-west/python/ch-1.py b/challenge-076/roger-bell-west/python/ch-1.py
new file mode 100755
index 0000000000..4d20a171d9
--- /dev/null
+++ b/challenge-076/roger-bell-west/python/ch-1.py
@@ -0,0 +1,42 @@
+#! /usr/bin/python3
+
+import unittest
+from collections import deque
+
+def psum(n):
+    pr=set(range(2,n+1))
+    for m in range(2,n+1):
+        for mi in range(2,n+1):
+            pr.discard(m*mi)
+    p=list(pr)
+    p.sort(reverse=True)
+    pi=dict()
+    for i in range(0,len(p)):
+        pi[p[i]]=i
+    c=deque()
+    o=list()
+    while True:
+        r=list()
+        s=n
+        if len(c)>0:
+            r=c.popleft()
+            s-=sum(p[i] for i in r)
+        if (s>0):
+            ru=set(r)
+            ca=set(pi[i] for i in p if i<=s)
+            ca-=ru
+            for i in ca:
+                q=r.copy()
+                q.append(i)
+                c.append(q)
+        elif (s==0):
+            o=[p[i] for i in r]
+            break
+    return len(o)
+
+class TestMajority(unittest.TestCase):
+
+    def test_ex(self):
+        self.assertEqual(psum(9),2,'example')
+
+unittest.main()
diff --git a/challenge-076/roger-bell-west/python/ch-2.py b/challenge-076/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..3a280ea191
--- /dev/null
+++ b/challenge-076/roger-bell-west/python/ch-2.py
@@ -0,0 +1,60 @@
+#! /usr/bin/python3
+
+import argparse
+import sys
+
+minlen=5
+grid=list()
+searchspaces=list()
+y=0
+
+parser = argparse.ArgumentParser(description='Process some integers.')
+parser.add_argument('puzzle', type=argparse.FileType('r'),
+                    help='the puzzle file')
+parser.add_argument('wordlist', type=argparse.FileType('r'),
+                    help='the wordlist file')
+args = parser.parse_args()
+
+for lino, line in enumerate(args.puzzle, start=1):
+    q=line.rstrip().lower().split()
+    if (y>0):
+        if (y != len(q)):
+            sys.exit("Not a rectangular grid")
+    else:
+        y=len(q)
+    grid.append(q)
+    searchspaces.append(''.join(q))
+    searchspaces.append(''.join(reversed(q)))
+x=len(grid)
+
+for i in range(0,y):
+    q=[grid[j][i] for j in range(0,x)]
+    searchspaces.append(''.join(q))
+    searchspaces.append(''.join(reversed(q)))
+
+mxy=max(x,y)
+for xi in range(-y+minlen-1,x-minlen+1):
+    seq=[[xi+i,i] for i in range(0,mxy) if xi+i>=0 and xi+i<x and i<y]
+    if (len(seq) >= minlen):
+        q=[grid[i[0]][i[1]] for i in seq]
+        searchspaces.append(''.join(q))
+        searchspaces.append(''.join(reversed(q)))
+for xi in range(-y+minlen-1,x-minlen+1):
+    seq=[[xi+i,y-i] for i in range(1,mxy) if xi+i>=0 and y-i>=0 and xi+i<x]
+    if (len(seq) >= minlen):
+        q=[grid[i[0]][i[1]] for i in seq]
+        searchspaces.append(''.join(q))
+        searchspaces.append(''.join(reversed(q)))
+
+found=list()
+
+for lino, line in enumerate(args.wordlist, start=1):
+    w=line.rstrip().lower()
+    if (len(w) >= minlen):
+        for ss in searchspaces:
+            if (w in ss):
+                found.append(w)
+                break
+
+found.sort()
+print(', '.join(found))
diff --git a/challenge-076/roger-bell-west/raku/ch-2.p6 b/challenge-076/roger-bell-west/raku/ch-2.p6
new file mode 100755
index 0000000000..d304c41fd7
--- /dev/null
+++ b/challenge-076/roger-bell-west/raku/ch-2.p6
@@ -0,0 +1,69 @@
+#! /usr/bin/perl6
+
+my $minlen=5;
+
+my $y;
+my @grid;
+my @searchspaces;
+my $fh=open :r,@*ARGS[0] or die "Can't open puzzle file\n";
+for $fh.lines {
+  .chomp;
+  (my $line=$_) ~~ s:global/\s+//;
+  $line=lc($line);
+  if (defined $y) {
+    if ($y != chars($line)) {
+      die "Not a rectangular grid\n";
+    }
+  } else {
+    $y = chars($line);
+  }
+  push @searchspaces,$line; # horizontal forward
+  push @grid,$line.comb;
+  push @searchspaces,join('',reverse(@grid[@grid.end])); # horizontal backward
+}
+close $fh;
+my $x=@grid.elems;
+
+for (0..$y-1) -> $i {
+  my @q=map {@grid[$_][$i]}, (0..$x-1);
+  push @searchspaces,join('',@q); # vertical forward
+  push @searchspaces,join('',reverse @q); # vertical backward
+}
+
+{
+  # +x +y diagonals
+  my $mxy=max($x,$y)-1;
+  for (-$y+$minlen-1..$x-$minlen+1) -> $xi {
+    my @seq=map {($xi+$_,$_)}, grep {$xi+$_ >= 0 && $xi+$_ < $x && $_ < $y}, (1..$mxy);
+    if (@seq.elems >= $minlen) {
+      my @q=map {@grid[$_.[0]][$_.[1]]}, @seq;
+      push @searchspaces,join('',@q);
+      push @searchspaces,join('',reverse @q);
+    }
+  }
+  # -x +y diagonals
+  for (-$y+$minlen-1..$x-$minlen+1) -> $xi {
+    my @seq=map {[$xi+$_,$y-$_]}, grep {$xi+$_ >= 0 && $y-$_ >= 0 && $xi+$_ < $x}, (1..$mxy);
+    if (@seq.elems >= $minlen) {
+      my @q=map {@grid[$_.[0]][$_.[1]]}, @seq;
+      push @searchspaces,join('',@q);
+      push @searchspaces,join('',reverse @q);
+    }
+  }
+}
+
+my @found;
+$fh=open :r,@*ARGS[1] or die "Can't open wordlist file\n";
+for $fh.lines {
+  .chomp;
+  if (chars($_) >= $minlen) {
+    my $w=lc($_);
+    for (@searchspaces) -> $ss {
+      with index($ss,$w) -> $ix {
+        push @found,$w;
+        last;
+      }
+    }
+  }
+}
+say join(', ',sort @found);