From 3b7fa3819a985c034f0d1ad497b488a19bcdbea7 Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 5 Jun 2023 10:31:25 +0100 Subject: RogerBW solutions for challenge no. 220 --- challenge-220/roger-bell-west/javascript/ch-1.js | 68 +++++ challenge-220/roger-bell-west/javascript/ch-2.js | 134 ++++++++++ challenge-220/roger-bell-west/kotlin/ch-1.kt | 36 +++ challenge-220/roger-bell-west/kotlin/ch-2.kt | 82 ++++++ challenge-220/roger-bell-west/lua/ch-1.lua | 76 ++++++ challenge-220/roger-bell-west/lua/ch-2.lua | 155 +++++++++++ challenge-220/roger-bell-west/perl/ch-1.pl | 27 ++ challenge-220/roger-bell-west/perl/ch-2.pl | 63 +++++ challenge-220/roger-bell-west/postscript/ch-1.ps | 253 ++++++++++++++++++ challenge-220/roger-bell-west/postscript/ch-2.ps | 323 +++++++++++++++++++++++ challenge-220/roger-bell-west/python/ch-1.py | 26 ++ challenge-220/roger-bell-west/python/ch-2.py | 51 ++++ challenge-220/roger-bell-west/raku/ch-1.p6 | 20 ++ challenge-220/roger-bell-west/raku/ch-2.p6 | 56 ++++ challenge-220/roger-bell-west/ruby/ch-1.rb | 29 ++ challenge-220/roger-bell-west/ruby/ch-2.rb | 45 ++++ challenge-220/roger-bell-west/rust/ch-1.rs | 35 +++ challenge-220/roger-bell-west/rust/ch-2.rs | 48 ++++ challenge-220/roger-bell-west/tests.yaml | 39 +++ 19 files changed, 1566 insertions(+) create mode 100755 challenge-220/roger-bell-west/javascript/ch-1.js create mode 100755 challenge-220/roger-bell-west/javascript/ch-2.js create mode 100644 challenge-220/roger-bell-west/kotlin/ch-1.kt create mode 100644 challenge-220/roger-bell-west/kotlin/ch-2.kt create mode 100755 challenge-220/roger-bell-west/lua/ch-1.lua create mode 100755 challenge-220/roger-bell-west/lua/ch-2.lua create mode 100755 challenge-220/roger-bell-west/perl/ch-1.pl create mode 100755 challenge-220/roger-bell-west/perl/ch-2.pl create mode 100644 challenge-220/roger-bell-west/postscript/ch-1.ps create mode 100644 challenge-220/roger-bell-west/postscript/ch-2.ps create mode 100755 challenge-220/roger-bell-west/python/ch-1.py create mode 100755 challenge-220/roger-bell-west/python/ch-2.py create mode 100755 challenge-220/roger-bell-west/raku/ch-1.p6 create mode 100755 challenge-220/roger-bell-west/raku/ch-2.p6 create mode 100755 challenge-220/roger-bell-west/ruby/ch-1.rb create mode 100755 challenge-220/roger-bell-west/ruby/ch-2.rb create mode 100755 challenge-220/roger-bell-west/rust/ch-1.rs create mode 100755 challenge-220/roger-bell-west/rust/ch-2.rs create mode 100644 challenge-220/roger-bell-west/tests.yaml diff --git a/challenge-220/roger-bell-west/javascript/ch-1.js b/challenge-220/roger-bell-west/javascript/ch-1.js new file mode 100755 index 0000000000..fa14df573c --- /dev/null +++ b/challenge-220/roger-bell-west/javascript/ch-1.js @@ -0,0 +1,68 @@ +#! /usr/bin/node + +"use strict" + +// by Frank Tan +// https://stackoverflow.com/questions/38400594/javascript-deep-comparison +function deepEqual(a,b) +{ + if( (typeof a == 'object' && a != null) && + (typeof b == 'object' && b != null) ) + { + var count = [0,0]; + for( var key in a) count[0]++; + for( var key in b) count[1]++; + if( count[0]-count[1] != 0) {return false;} + for( var key in a) + { + if(!(key in b) || !deepEqual(a[key],b[key])) {return false;} + } + for( var key in b) + { + if(!(key in a) || !deepEqual(b[key],a[key])) {return false;} + } + return true; + } + else + { + return a === b; + } +} + +function word2set(word) { + let r = new Set(); + for (let c of word.toLowerCase()) { + if (c >= 'a' && c <= 'z') { + r.add(c); + } + } + return r +} + +function commoncharacters(lst) { + let c = word2set(lst[0]); + for (let w of lst.slice(1)) { + const d = word2set(w); + for (let l of c) { + if (!d.has(l)) { + c.delete(l); + } + } + } + let s = Array.from(c); + s.sort(); + return s; +} + +if (deepEqual(commoncharacters(['Perl', 'Rust', 'Raku']), ['r'])) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write(" "); +if (deepEqual(commoncharacters(['love', 'live', 'leave']), ['e', 'l', 'v'])) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write("\n"); diff --git a/challenge-220/roger-bell-west/javascript/ch-2.js b/challenge-220/roger-bell-west/javascript/ch-2.js new file mode 100755 index 0000000000..8937d6f67a --- /dev/null +++ b/challenge-220/roger-bell-west/javascript/ch-2.js @@ -0,0 +1,134 @@ +#! /usr/bin/node + +"use strict" + +// by Frank Tan +// https://stackoverflow.com/questions/38400594/javascript-deep-comparison +function deepEqual(a,b) +{ + if( (typeof a == 'object' && a != null) && + (typeof b == 'object' && b != null) ) + { + var count = [0,0]; + for( var key in a) count[0]++; + for( var key in b) count[1]++; + if( count[0]-count[1] != 0) {return false;} + for( var key in a) + { + if(!(key in b) || !deepEqual(a[key],b[key])) {return false;} + } + for( var key in b) + { + if(!(key in a) || !deepEqual(b[key],a[key])) {return false;} + } + return true; + } + else + { + return a === b; + } +} + +function permute(a) { + let out = []; + let n=a.length; + let c=[]; + for (let i = 0; i < n; i++) { + c.push(0); + } + out.push([...a]); + let i=0; + while (true) { + if (i >= n) { + break; + } + if (c[i] < i) { + if (i % 2 == 0) { + [a[0],a[i]] = [a[i],a[0]]; + } else { + [a[c[i]],a[i]] = [a[i],a[c[i]]]; + } + out.push([...a]); + c[i]++; + i=0; + } else { + c[i]=0; + i++; + } + } + return out; +} + +// by VLAZ +// https://stackoverflow.com/a/59322890 +function toWindows(inputArray, size) { + return Array.from( + {length: inputArray.length - (size - 1)}, //get the appropriate length + (_, index) => inputArray.slice(index, index+size) //create the windows + ) +} + +function squared(a) { + return a * a; +} + +function decode(a0, base) { + let eq = []; + let a = a0; + while (a > 0) { + eq.unshift(a % base); + a = Math.trunc(a / base); + } + return eq; +} + +function encode(sq, base) { + let a = 0; + for (let v of sq) { + a *= base; + a += v; + } + return a; +} + +function squareful(lst) { + let results = new Set(); + let squares = new Set(); + const base = Math.max(...lst) + 1; + for (let la of permute(lst)) { + let squareful = true; + for (let a of toWindows(la, 2)) { + const cs = a[0] + a[1]; + let mx = squared(squares.size); + while (cs > mx) { + mx = squared(squares.size + 1); + squares.add(mx); + } + if (!squares.has(cs)) { + squareful = false; + break; + } + } + if (squareful) { + results.add(encode(la, base)); + } + } + let s = Array.from(results); + s.sort(function(a,b) { + return a-b; + }); + return s.map(x => decode(x, base)); +} + +if (deepEqual(squareful([1, 17, 8]), [[1, 8, 17], [17, 8, 1]])) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write(" "); +if (deepEqual(squareful([2, 2, 2]), [[2, 2, 2]])) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write("\n"); diff --git a/challenge-220/roger-bell-west/kotlin/ch-1.kt b/challenge-220/roger-bell-west/kotlin/ch-1.kt new file mode 100644 index 0000000000..dcddd560c5 --- /dev/null +++ b/challenge-220/roger-bell-west/kotlin/ch-1.kt @@ -0,0 +1,36 @@ +fun word2set(word: String): MutableSet { + var r = mutableSetOf() + for (c in word.lowercase()) { + if (c >= 'a' && c <= 'z') { + r.add(c) + } + } + return r +} + +fun commoncharacters(lst: List): List { + var c = word2set(lst[0]) + for (w in lst.drop(1)) { + c = c.intersect(word2set(w)).toMutableSet() + } + var s = ArrayList(c) + s.sort() + return s.toList() +} + +fun main() { + + if (commoncharacters(listOf("Perl", "Rust", "Raku")) == listOf('r')) { + print("Pass") + } else { + print("Fail") + } + print(" ") + if (commoncharacters(listOf("love", "live", "leave")) == listOf('e', 'l', 'v')) { + print("Pass") + } else { + print("Fail") + } + println("") + +} diff --git a/challenge-220/roger-bell-west/kotlin/ch-2.kt b/challenge-220/roger-bell-west/kotlin/ch-2.kt new file mode 100644 index 0000000000..02832eb560 --- /dev/null +++ b/challenge-220/roger-bell-west/kotlin/ch-2.kt @@ -0,0 +1,82 @@ +fun permute(aa: List): ArrayList> { + var a = ArrayList() + for (i in aa) { + a.add(i) + } + var out = ArrayList>() + val n = a.size + var c = ArrayList(); + for (i in 0..n-1) { + c.add(0) + } + out.add(a.toList()) + var i = 0 + while (true) { + if (i >= n) { + break + } + if (c[i] < i) { + if (i % 2 == 0) { + val tmp = a[0] + a[0] = a[i] + a[i] = tmp + } else { + val tmp = a[c[i]] + a[c[i]] = a[i] + a[i] = tmp + } + out.add(a.toList()) + c[i] += 1 + i = 0 + } else { + c[i] = 0 + i += 1 + } + } + return out +} + +fun squared(a: Int): Int { + return a * a +} + +fun squareful(lst: List): List> { + var results = mutableSetOf>() + var squares = mutableSetOf() + for (la in permute(lst)) { + var squareful = true + for (a in la.windowed(size = 2)) { + val cs = a[0] + a[1] + var mx = squared(squares.size) + while (cs > mx) { + mx = squared(squares.size + 1) + squares.add(mx) + } + if (!squares.contains(cs)) { + squareful = false + break + } + } + if (squareful) { + results.add(la) + } + } + return results.toList() +} + +fun main() { + + if (squareful(listOf(1, 17, 8)) == listOf(listOf(1, 8, 17), listOf(17, 8, 1))) { + print("Pass") + } else { + print("Fail") + } + print(" ") + if (squareful(listOf(2, 2, 2)) == listOf(listOf(2, 2, 2))) { + print("Pass") + } else { + print("Fail") + } + println("") + +} diff --git a/challenge-220/roger-bell-west/lua/ch-1.lua b/challenge-220/roger-bell-west/lua/ch-1.lua new file mode 100755 index 0000000000..74624b0e7e --- /dev/null +++ b/challenge-220/roger-bell-west/lua/ch-1.lua @@ -0,0 +1,76 @@ +#! /usr/bin/lua + +-- by Michael Anderson at +-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua +-- modified by Roger +function recursive_compare(t1,t2) + -- Use usual comparison first. + if t1==t2 then return true end + -- We only support non-default behavior for tables + if (type(t1)~="table") then return false end + -- They better have the same metatables + local mt1 = getmetatable(t1) + local mt2 = getmetatable(t2) + if( not recursive_compare(mt1,mt2) ) then return false end + -- Build list of all keys + local kk = {} + for k1, _ in pairs(t1) do + kk[k1] = true + end + for k2, _ in pairs(t2) do + kk[k2] = true + end + -- Check each key that exists in at least one table + for _, k in ipairs(kk) do + if (not recursive_compare(t1[k], t2[k])) then + return false + end + end + return true +end + +function keys(t) + local a = {} + for k, v in pairs(t) do + table.insert(a, k) + end + return a +end + +function word2set(word) + local s = {} + for c in string.gmatch(string.lower(word), "%a") do + s[c] = true + end + return s +end + +function commoncharacters(lst) + local c = word2set(lst[1]) + for i = 2, #lst do + local d = word2set(lst[i]) + for k, _ in pairs(c) do + if d[k] == nil then + c[k] = nil + end + end + end + local o = keys(c) + table.sort(o) + return o +end + +if recursive_compare(commoncharacters({"Perl", "Rust", "Raku"}), {"r"}) then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if recursive_compare(commoncharacters({"love", "live", "leave"}), {"e", "l", "v"}) then + io.write("Pass") +else + io.write("FAIL") +end +print("") + diff --git a/challenge-220/roger-bell-west/lua/ch-2.lua b/challenge-220/roger-bell-west/lua/ch-2.lua new file mode 100755 index 0000000000..57254c3a40 --- /dev/null +++ b/challenge-220/roger-bell-west/lua/ch-2.lua @@ -0,0 +1,155 @@ +#! /usr/bin/lua + +-- by Michael Anderson at +-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua +-- modified by Roger +function recursive_compare(t1,t2) + -- Use usual comparison first. + if t1==t2 then return true end + -- We only support non-default behavior for tables + if (type(t1)~="table") then return false end + -- They better have the same metatables + local mt1 = getmetatable(t1) + local mt2 = getmetatable(t2) + if( not recursive_compare(mt1,mt2) ) then return false end + -- Build list of all keys + local kk = {} + for k1, _ in pairs(t1) do + kk[k1] = true + end + for k2, _ in pairs(t2) do + kk[k2] = true + end + -- Check each key that exists in at least one table + for k, _ in pairs(kk) do + if (not recursive_compare(t1[k], t2[k])) then + return false + end + end + return true +end + +function keys(t) + local a = {} + for k, v in pairs(t) do + table.insert(a, k) + end + return a +end + +function deepcopy(src) + local dst = {} + for k, v in pairs(src) do + if type(v) == "table" then + v = deepcopy(v) + end + dst[k] = v + end + return dst +end + +function permute(a) + local out = {} + local n = #a + local c = {} + for i = 1,n do + table.insert(c, 1) + end + table.insert(out, deepcopy(a)) + local i=1 + while true do + if i > n then + break + end + if c[i] < i then + if i % 2 == 1 then + a[1],a[i] = a[i],a[1] + else + a[c[i]],a[i] = a[i],a[c[i]] + end + table.insert(out, deepcopy(a)) + c[i] = c[i]+1 + i = 1 + else + c[i] = 1 + i = i+1 + end + end + return out +end + +function propersize(t) + local l=0 + for k,v in pairs(t) do + l = l + 1 + end + return l +end + +function squared(a) + return a * a +end + +function encode(sq, base) + local a = 0 + for _, v in ipairs(sq) do + a = a * base + a = a + v + end + return a +end + +function decode(a, base) + local eq = {} + while a > 0 do + table.insert(eq, 1, a % base) + a = a // base + end + return eq +end + +function squareful(lst) + local results = {} + local squares = {} + local base = math.max(table.unpack(lst)) + 1 + for _, la in ipairs(permute(lst)) do + local squareful = true + for i = 1, #la-1 do + local cs = la[i] + la[i + 1] + local mx = squared(propersize(squares)) + while cs > mx do + mx = squared(propersize(squares) + 1) + squares[mx] = true + end + if squares[cs] == nil then + squareful = false + break + end + end + if squareful then + results[encode(la, base)] = true + end + end + local o = keys(results) + table.sort(o) + local out = {} + for _, v in ipairs(o) do + table.insert(out, decode(v, base)) + end + return out +end + +if recursive_compare(squareful({1, 17, 8}), {{1, 8, 17}, {17, 8, 1}}) then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if recursive_compare(squareful({2, 2, 2}), {{2, 2, 2}}) then + io.write("Pass") +else + io.write("FAIL") +end +print("") + diff --git a/challenge-220/roger-bell-west/perl/ch-1.pl b/challenge-220/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..9370a80063 --- /dev/null +++ b/challenge-220/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,27 @@ +#! /usr/bin/perl + +use strict; +use warnings; +use experimental 'signatures'; + +use Test::More tests => 2; + +is_deeply(commoncharacters(['Perl', 'Rust', 'Raku']), ['r'], 'example 1'); +is_deeply(commoncharacters(['love', 'live', 'leave']), ['e', 'l', 'v'], 'example 2'); + +sub word2set($word) { + return {map {$_ => 1} grep /[a-z]/, split '', lc($word)}; +} + +sub commoncharacters($lst) { + my $c = word2set($lst->[0]); + foreach my $si (1 .. $#{$lst}) { + my $d = word2set($lst->[$si]); + foreach my $l (keys %{$c}) { + unless (exists $d->{$l}) { + delete $c->{$l}; + } + } + } + return [sort keys %{$c}]; +} diff --git a/challenge-220/roger-bell-west/perl/ch-2.pl b/challenge-220/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..4785f189c4 --- /dev/null +++ b/challenge-220/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,63 @@ +#! /usr/bin/perl + +use strict; +use warnings; +use experimental 'signatures'; + +use Algorithm::Permute; +use List::Util qw(max); + +use Test::More tests => 2; + +is_deeply(squareful([1, 17, 8]), [[1, 8, 17], [17, 8, 1]], 'example 1'); +is_deeply(squareful([2, 2, 2]), [[2, 2, 2]], 'example 2'); + + +sub squared($a) { + return $a * $a; +} + +sub decode($a0, $base) { + my @eq; + my $a = $a0; + while ($a > 0) { + unshift @eq, $a % $base; + $a = int($a / $base); + } + return \@eq; +} + +sub encode($sq, $base) { + my $a = 0; + foreach my $v (@{$sq}) { + $a *= $base; + $a += $v; + } + return $a; +} + +sub squareful($lst) { + my %results; + my %squares; + my $base = max(@{$lst}) + 1; + my $p = Algorithm::Permute->new($lst); + while (my @la = $p->next) { + my $squareful = 1; + foreach my $i (0 .. $#la - 1) { + my $cs = $la[$i] + $la[$i + 1]; + my $mx = squared(scalar keys %squares); + while ($cs > $mx) { + $mx = squared((scalar keys %squares) + 1); + $squares{$mx} = 1; + } + unless (exists $squares{$cs}) { + $squareful = 0; + last; + } + } + if ($squareful) { + $results{encode(\@la, $base)} = 1; + } + } + return [map {decode($_, $base)} sort {$a <=> $b} keys %results]; +} diff --git a/challenge-220/roger-bell-west/postscript/ch-1.ps b/challenge-220/roger-bell-west/postscript/ch-1.ps new file mode 100644 index 0000000000..d46e25cd53 --- /dev/null +++ b/challenge-220/roger-bell-west/postscript/ch-1.ps @@ -0,0 +1,253 @@ +%!PS + +% begin included library code +% see https://codeberg.org/Firedrake/postscript-libraries/ +/map { % array proc -> array + 2 dict begin + /p exch def + [ exch + { + p + } forall + ] + end +} bind def + +/s2a { + [ exch { } forall ] +} bind def + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + +/quicksort.with_comparator { % [ a c b ] { comparator } -> [ a b c ] + 2 dict begin + /cmp exch def + /arr exch def + arr length 0 gt { + 0 arr length 1 sub quicksort.main + } if + arr + end +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot cmp 0 ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot cmp 0 le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/deepeq { + 2 dict begin + /a exch def + /b exch def + a type b type eq { + a type /dicttype eq { + a length b length eq { + << + a { + pop + true + } forall + b { + pop + true + } forall + >> + true exch + { + pop + dup a exch known { + dup b exch known { + dup a exch get exch b exch get deepeq not { + pop false + } if + } { + false + } ifelse + } { + false + } ifelse + } forall + } { + false + } ifelse + } { + a type dup /arraytype eq exch /stringtype eq or { + a length b length eq { + true + 0 1 a length 1 sub { + dup a exch get exch b exch get deepeq not { + pop false + exit + } if + } for + } { + false + } ifelse + } { + a b eq + } ifelse + } ifelse + } { + false + } ifelse + end +} bind def + +/toset { % array -> dict of (value, true) + << exch + { + true + } forall + >> +} bind def + +/quicksort.cmp { + 2 copy + lt { + pop pop -1 + } { + gt { + 1 + } { + 0 + } ifelse + } ifelse +} bind def + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cvs print + (/) print + test.count (...) cvs print + ( \() print + test.pass 100 mul test.count idiv (...) cvs print + (%\)) print + (\r\n) print + } if +} bind def + +/quicksort { + { quicksort.cmp } quicksort.with_comparator +} bind def + +/keys { % dict -> array of dict keys + [ exch + { + pop + } forall + ] +} bind def + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + + +% end included library code + +/word2set { + 1 dict begin + [ exch + s2a { + /ch exch def + ch 65 ge ch 90 le and { + ch 32 add + } { + ch 97 ge ch 122 le and { + ch + } if + } ifelse + } forall + ] toset + end +} bind def + +/commoncharacters { + 4 dict begin + /lst exch def + /c lst 0 get word2set def + 1 1 lst length 1 sub { + lst exch get word2set /d exch def + c keys { + /k exch def + d k known not { + c k undef + } if + } forall + } for + c keys quicksort { 1 string dup 0 4 -1 roll put } map + end +} bind def + +(commoncharacters) test.start +[(Perl) (Rust) (Raku)] commoncharacters [(r)] deepeq test +[(love) (live) (leave)] commoncharacters [(e) (l) (v)] deepeq test +test.end diff --git a/challenge-220/roger-bell-west/postscript/ch-2.ps b/challenge-220/roger-bell-west/postscript/ch-2.ps new file mode 100644 index 0000000000..b47b145c36 --- /dev/null +++ b/challenge-220/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,323 @@ +%!PS + +% begin included library code +% see https://codeberg.org/Firedrake/postscript-libraries/ +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cvs print + (/) print + test.count (...) cvs print + ( \() print + test.pass 100 mul test.count idiv (...) cvs print + (%\)) print + (\r\n) print + } if +} bind def + +/reverse { + 1 dict begin + dup length /l exch def + [ exch + aload pop + 2 1 l { + -1 roll + } for + ] + end +} bind def + +/listmax { + { max } reduce +} bind def + +/keys { % dict -> array of dict keys + [ exch + { + pop + } forall + ] +} bind def + +/quicksort.with_comparator { % [ a c b ] { comparator } -> [ a b c ] + 2 dict begin + /cmp exch def + /arr exch def + arr length 0 gt { + 0 arr length 1 sub quicksort.main + } if + arr + end +} bind def + +/permute { % [array] {proc} permute runs proc on each permutation of array + 7 dict begin + /permute.subproc exch def + /permute.a exch def + /permute.n permute.a length def + /permute.c [ permute.n { 0 } repeat ] def + permute.a permute.subproc + /permute.i 0 def + { + permute.i permute.n ge { + exit + } if + permute.c permute.i get permute.i lt { + permute.i 2 mod 0 eq { + 0 permute.i permute.swap + } { + permute.c permute.i get permute.i permute.swap + } ifelse + permute.a permute.subproc + permute.c permute.i get 1 add permute.c exch permute.i exch put + /permute.i 0 def + } { + permute.c permute.i 0 put + /permute.i permute.i 1 add def + } ifelse + } loop + end +} bind def + +/permute.swap { + /permute.bi exch def + /permute.ai exch def + permute.a permute.ai get + permute.a permute.bi get + permute.a exch permute.ai exch put + permute.a exch permute.bi exch put +} bind def + +/quicksort.cmp { + 2 copy + lt { + pop pop -1 + } { + gt { + 1 + } { + 0 + } ifelse + } ifelse +} bind def + +/quicksort { + { quicksort.cmp } quicksort.with_comparator +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/toset { % array -> dict of (value, true) + << exch + { + true + } forall + >> +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot cmp 0 ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot cmp 0 le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/reduce { % array proc -> value + 2 dict begin + /p exch def + /a exch def + a 0 get + 1 1 a length 1 sub { + a exch get + p + } for + end +} bind def + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + +/deepeq { + 2 dict begin + /a exch def + /b exch def + a type b type eq { + a type /dicttype eq { + a length b length eq { + << + a { + pop + true + } forall + b { + pop + true + } forall + >> + true exch + { + pop + dup a exch known { + dup b exch known { + dup a exch get exch b exch get deepeq not { + pop false + } if + } { + false + } ifelse + } { + false + } ifelse + } forall + } { + false + } ifelse + } { + a type dup /arraytype eq exch /stringtype eq or { + a length b length eq { + true + 0 1 a length 1 sub { + dup a exch get exch b exch get deepeq not { + pop false + exit + } if + } for + } { + false + } ifelse + } { + a b eq + } ifelse + } ifelse + } { + false + } ifelse + end +} bind def + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + + +% end included library code + +/squareful { + 0 dict begin + /lst exch def + /squares 0 dict def + /results [ + lst { + /la exch def + /squareful true def + 0 1 la length 2 sub { + dup + 1 add la exch get + exch + la exch get + add + /cs exch def + /mx squares length dup mul def + { + cs mx le { + exit + } if + /mx squares length 1 add dup mul def + squares mx true put + } loop + squares cs known not { + /squareful false def + exit + } if + } for + squareful { + [ la aload pop ] + } if + } permute + ] def + /base lst listmax 1 add def + [ + [ + results { + { exch base mul add } reduce + } forall + ] toset keys quicksort { + [ exch + { + dup 0 eq { + pop exit + } if + dup base mod exch base idiv + } loop + ] reverse + } forall + ] + end +} bind def + +(squareful) test.start +[1 17 8] squareful [[1 8 17] [17 8 1]] deepeq test +[2 2 2] squareful [[2 2 2]] deepeq test +test.end diff --git a/challenge-220/roger-bell-west/python/ch-1.py b/challenge-220/roger-bell-west/python/ch-1.py new file mode 100755 index 0000000000..a9f0d23e3b --- /dev/null +++ b/challenge-220/roger-bell-west/python/ch-1.py @@ -0,0 +1,26 @@ +#! /usr/bin/python3 + +def word2set(word): + r = set() + for c in word.lower(): + if c >= 'a' and c <= 'z': + r.add(c) + return r + +def commoncharacters(lst): + c = word2set(lst[0]) + for w in lst[1:]: + c = c.intersection(word2set(w)) + return sorted(list(c)) + +import unittest + +class TestCommoncharacters(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(commoncharacters(["Perl", "Rust", "Raku"]), ["r"], 'example 1') + + def test_ex2(self): + self.assertEqual(commoncharacters(["love", "live", "leave"]), ["e", "l", "v"], 'example 2') + +unittest.main() diff --git a/challenge-220/roger-bell-west/python/ch-2.py b/challenge-220/roger-bell-west/python/ch-2.py new file mode 100755 index 0000000000..b9fc7f9c51 --- /dev/null +++ b/challenge-220/roger-bell-west/python/ch-2.py @@ -0,0 +1,51 @@ +#! /usr/bin/python3 + +import collections +from itertools import permutations, islice + +# https://docs.python.org/3/library/itertools.html +def sliding_window(iterable, n): + # sliding_window('ABCDEFG', 4) --> ABCD BCDE CDEF DEFG + it = iter(iterable) + window = collections.deque(islice(it, n), maxlen=n) + if len(window) == n: + yield tuple(window) + for x in it: + window.append(x) + yield tuple(window) + +def squared(a): + return a * a + +def squareful(lst): + results = set() + squares = set() + for la in permutations(lst): + squareful = True + for a in sliding_window(la, 2): + cs = a[0] + a[1] + mx = squared(len(squares)) + while cs > mx: + mx = squared(len(squares) + 1) + squares.add(mx) + if cs not in squares: + squareful = False + break + if squareful: + results.add(tuple(la)) + o = list(results) + o.sort() + return [ list(x) for x in o ] + + +import unittest + +class TestSquareful(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(squareful([1, 17, 8]), [[1, 8, 17], [17, 8, 1]], 'example 1') + + def test_ex2(self): + self.assertEqual(squareful([2, 2, 2]), [[2, 2, 2]], 'example 2') + +unittest.main() diff --git a/challenge-220/roger-bell-west/raku/ch-1.p6 b/challenge-220/roger-bell-west/raku/ch-1.p6 new file mode 100755 index 0000000000..cc9f09f8a6 --- /dev/null +++ b/challenge-220/roger-bell-west/raku/ch-1.p6 @@ -0,0 +1,20 @@ +#! /usr/bin/raku + +use Test; + +plan 2; + +is-deeply(commoncharacters(['Perl', 'Rust', 'Raku']), ['r'], 'example 1'); +is-deeply(commoncharacters(['love', 'live', 'leave']), ['e', 'l', 'v'], 'example 2'); + +sub word2set($word) { + return SetHash($word.lc.comb.grep(/<[a..z]>/)); +} + +sub commoncharacters(@lst) { + my $c = word2set(@lst[0]); + for @lst.skip(1) -> $w { + $c (&)= word2set($w); + } + return $c.keys.sort.Array; +} diff --git a/challenge-220/roger-bell-west/raku/ch-2.p6 b/challenge-220/roger-bell-west/raku/ch-2.p6 new file mode 100755 index 0000000000..aae0b4e697 --- /dev/null +++ b/challenge-220/roger-bell-west/raku/ch-2.p6 @@ -0,0 +1,56 @@ +#! /usr/bin/raku + +use Test; + +plan 2; + +is-deeply(squareful([1, 17, 8]), [[1, 8, 17], [17, 8, 1]], 'example 1'); +is-deeply(squareful([2, 2, 2]), [[2, 2, 2],], 'example 2'); + +sub squared($a) { + return $a * $a; +} + +sub decode($a0, $base) { + my @eq; + my $a = $a0; + while ($a > 0) { + @eq.unshift($a % $base); + $a div= $base; + } + return @eq; +} + +sub encode(@sq, $base) { + my $a = 0; + for @sq -> $v { + $a *= $base; + $a += $v; + } + return $a; +} + +sub squareful(@lst) { + my $results = SetHash.new; + my $squares = SetHash.new; + my $base = max(@lst) + 1; + for @lst.permutations -> @la { + my $squareful = True; + for @la.rotor(2 => -1) -> @a { + my $cs = @a[0] + @a[1]; + my $mx = squared($squares.elems); + while ($cs > $mx) { + $mx = squared($squares.elems + 1); + $squares{$mx}++; + } + unless ($squares{$cs}:exists) { + $squareful = False; + last; + } + } + if ($squareful) { + $results{encode(@la, $base)}++; + } + } + return $results.keys.sort({$^a <=> $^b}).map({decode($_, $base)}).Array; +} diff --git a/challenge-220/roger-bell-west/ruby/ch-1.rb b/challenge-220/roger-bell-west/ruby/ch-1.rb new file mode 100755 index 0000000000..54ae5ca678 --- /dev/null +++ b/challenge-220/roger-bell-west/ruby/ch-1.rb @@ -0,0 +1,29 @@ +#! /usr/bin/ruby + +require 'set' + +def word2set(word) + return Set.new(word.downcase.chars.find_all {|i| i >= 'a' && i <= 'z'}) +end + +def commoncharacters(lst) + c = word2set(lst[0]) + lst.drop(1).each do |w| + c = c & word2set(w) + end + return c.to_a.sort +end + +require 'test/unit' + +class TestCommoncharacters < Test::Unit::TestCase + + def test_ex1 + assert_equal(['r'], commoncharacters(['Perl', 'Rust', 'Raku'])) + end + + def test_ex2 + assert_equal(['e', 'l', 'v'], commoncharacters(['love', 'live', 'leave'])) + end + +end diff --git a/challenge-220/roger-bell-west/ruby/ch-2.rb b/challenge-220/roger-bell-west/ruby/ch-2.rb new file mode 100755 index 0000000000..65679c8e9d --- /dev/null +++ b/challenge-220/roger-bell-west/ruby/ch-2.rb @@ -0,0 +1,45 @@ +#! /usr/bin/ruby + +require 'set' + +def squared(a) + return a * a +end + +def squareful(lst) + results = Set.new + squares = Set.new + lst.permutation do |la| + squareful = true + la.each_cons(2) do |a| + cs = a[0] + a[1] + mx = squared(squares.length) + while cs > mx do + mx = squared(squares.length + 1) + squares.add(mx) + end + if !squares.include?(cs) then + squareful = false + break + end + end + if squareful then + results.add(la) + end + end + return results.to_a.sort +end + +require 'test/unit' + +class TestSquareful < Test::Unit::TestCase + + def test_ex1 + assert_equal([[1, 8, 17], [17, 8, 1]], squareful([1, 17, 8])) + end + + def test_ex2 + assert_equal([[2, 2, 2]], squareful([2, 2, 2])) + end + +end diff --git a/challenge-220/roger-bell-west/rust/ch-1.rs b/challenge-220/roger-bell-west/rust/ch-1.rs new file mode 100755 index 0000000000..eee4197e66 --- /dev/null +++ b/challenge-220/roger-bell-west/rust/ch-1.rs @@ -0,0 +1,35 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit + +use std::collections::HashSet; + +#[test] +fn test_ex1() { + assert_eq!(commoncharacters(vec!["Perl", "Rust", "Raku"]), vec!['r']); +} + +#[test] +fn test_ex2() { + assert_eq!( + commoncharacters(vec!["love", "live", "leave"]), + vec!['e', 'l', 'v'] + ); +} + +fn word2set(word: &str) -> HashSet { + let mut s: HashSet = HashSet::new(); + for c in word.to_ascii_lowercase().chars() { + s.insert(c); + } + s +} + +fn commoncharacters(lst: Vec<&str>) -> Vec { + let mut c = word2set(lst[0]); + for w in lst.iter().skip(1) { + c = c.intersection(&word2set(w)).cloned().collect::>(); + } + let mut s = c.into_iter().collect::>(); + s.sort(); + s +} diff --git a/challenge-220/roger-bell-west/rust/ch-2.rs b/challenge-220/roger-bell-west/rust/ch-2.rs new file mode 100755 index 0000000000..3d8284d43b --- /dev/null +++ b/challenge-220/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,48 @@ +// [dependencies] +// itertools = "0.10.5" + +use itertools::Itertools; +use std::collections::HashSet; + +#[test] +fn test_ex1() { + assert_eq!(squareful(vec![1, 17, 8]), vec![vec![1, 8, 17], vec![17, 8, 1]]); +} + +#[test] +fn test_ex2() { + assert_eq!(squareful(vec![2, 2, 2]), vec![vec![2, 2, 2]]); +} + +fn squared(a: u32) -> u32 { + a * a +} + +fn squareful(lst: Vec) -> Vec> { + let mut results: HashSet> = HashSet::new(); + let mut squares: HashSet = HashSet::new(); + for la in lst.iter().permutations(lst.len()) { + let mut squareful = true; + for a in la.windows(2) { + let cs = a[0] + a[1]; + let mut mx = squared(squares.len() as u32); + while cs > mx { + mx = squared(squares.len() as u32 + 1); + squares.insert(mx); + } + if !squares.contains(&cs) { + squareful = false; + break; + } + } + if squareful { + results.insert(la.into_iter().map(|i| *i).collect::>()); + } + } + let mut out = Vec::new(); + for a in results { + out.push(a); + } + out.sort(); + out +} diff --git a/challenge-220/roger-bell-west/tests.yaml b/challenge-220/roger-bell-west/tests.yaml new file mode 100644 index 0000000000..da885eadaf --- /dev/null +++ b/challenge-220/roger-bell-west/tests.yaml @@ -0,0 +1,39 @@ +--- +ch-1: + - function: commoncharacters + arguments: + - Perl + - Rust + - Raku + result: + - r + - arguments: + - love + - live + - leave + result: + - e + - l + - v +ch-2: + - function: squareful + arguments: + - 1 + - 17 + - 8 + result: + - - 1 + - 8 + - 17 + - - 17 + - 8 + - 1 + - arguments: + - 2 + - 2 + - 2 + result: + - - 2 + - 2 + - 2 + -- cgit