diff options
| -rwxr-xr-x | challenge-121/roger-bell-west/perl/ch-1.pl | 14 | ||||
| -rwxr-xr-x | challenge-121/roger-bell-west/perl/ch-2.pl | 95 | ||||
| -rw-r--r-- | challenge-121/roger-bell-west/postscript/ch-1.ps | 37 | ||||
| -rwxr-xr-x | challenge-121/roger-bell-west/python/ch-1.py | 17 | ||||
| -rwxr-xr-x | challenge-121/roger-bell-west/raku/ch-1.p6 | 12 | ||||
| -rwxr-xr-x | challenge-121/roger-bell-west/ruby/ch-1.rb | 19 | ||||
| -rwxr-xr-x | challenge-121/roger-bell-west/rust/ch-1.rs | 16 | ||||
| -rw-r--r-- | challenge-121/roger-bell-west/rust/ch-2.rs | 89 |
8 files changed, 299 insertions, 0 deletions
diff --git a/challenge-121/roger-bell-west/perl/ch-1.pl b/challenge-121/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..1fab3458fc --- /dev/null +++ b/challenge-121/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,14 @@ +#! /usr/bin/perl + +use strict; +use warnings; + +use Test::More tests => 2; + +is(ib(12,3),8,'example 1'); +is(ib(18,4),26,'example 2'); + +sub ib { + my ($m,$n)=@_; + return $m ^ (1 << ($n-1)); +} diff --git a/challenge-121/roger-bell-west/perl/ch-2.pl b/challenge-121/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..6d4878d398 --- /dev/null +++ b/challenge-121/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,95 @@ +#! /usr/bin/perl + +use strict; +use warnings; + +use Test::More tests => 2; + +is_deeply(tsp([ + [0, 2, 9, 10], + [1, 0, 6, 4], + [15, 7, 0, 8], + [6, 3, 12, 0], + ]),[21,[0,2,3,1,0]],'example 1'); + +is_deeply(tsp([ + [0, 5, 2, 7], + [5, 0, 5, 3], + [3, 1, 0, 6], + [4, 5, 4, 0], + ]),[10,[0,2,1,3,0]],'example 2'); + +use YAML::XS; +print Dump(tsp(mkmatrix(10))); + +use Algorithm::Permute; +use List::Util qw(min); + +sub tsp { + my ($d)=shift; + my $n=scalar @{$d}; + my $n1=$n-1; + my %c; + foreach my $k (1..$n1) { + $c{1<<$k}{$k}=[$d->[0][$k],0]; + } + foreach my $ss (2..$n1) { + my $p=Algorithm::Permute->new([1..$n1],$ss); + while (my @s = $p->next) { + my $bits=0; + foreach my $bit (@s) { + $bits |= 1 << $bit; + } + foreach my $k (@s) { + my $prev=$bits & ~(1<<$k); + my @res; + foreach my $m (@s) { + if ($m==0 || $m==$k) { + next; + } + push @res,[$c{$prev}{$m}[0]+$d->[$m][$k],$m]; + } + my @r=map {$_->[0]} @res; + my %r=map {$r[$_] => $_} (0..$#r); + $c{$bits}{$k}=$res[$r{min(@r)}]; + } + } + } + my $bits=(1<<$n)-1 & ~1; + my @res; + foreach my $k (1..$n1) { + push @res,[$c{$bits}{$k}[0]+$d->[$k][0],$k]; + } + my @r=map {$_->[0]} @res; + my %r=map {$r[$_] => $_} (0..$#r); + my ($opt,$parent)=@{$res[$r{min(@r)}]}; + my @path; + foreach my $i (0..$n1-1) { + push @path,$parent; + my $nb=$bits & ~(1 << $parent); + $parent=$c{$bits}{$parent}[1]; + $bits=$nb; + } + push @path,0; + @path=reverse @path; + push @path,0; + return [$opt,\@path]; +} + +sub mkmatrix { + my $n=shift; + my $n1=$n-1; + my @r; + foreach my $x (0..$n1) { + my @a; + foreach my $y (0..$n1) { + if ($x==$y) { + push @a,0; + } else { + push @a,int(rand()*10)+1; + } + } + push @r,\@a; + } + return \@r; +} diff --git a/challenge-121/roger-bell-west/postscript/ch-1.ps b/challenge-121/roger-bell-west/postscript/ch-1.ps new file mode 100644 index 0000000000..7b8922a591 --- /dev/null +++ b/challenge-121/roger-bell-west/postscript/ch-1.ps @@ -0,0 +1,37 @@ +%! Not DSC compliant + +/ib { + exch + 1 exch 1 sub bitshift + xor +} def + +/str 50 string def +/fs 12 def +/Helvetica findfont +fs scalefont setfont +20 750 translate +/line 0 def +/testnum 1 def + +/disptest { + 0 line moveto testnum str cvs show (.) show + dup + 50 line moveto str cvs show + exch + dup + 100 line moveto str cvs show + exch + ib + dup + 150 line moveto str cvs show + eq { (Pass) } { (FAIL) } ifelse + 200 line moveto show + /line line fs 2 mul sub def + /testnum testnum 1 add def +} def + +8 3 12 disptest +26 4 18 disptest + +showpage diff --git a/challenge-121/roger-bell-west/python/ch-1.py b/challenge-121/roger-bell-west/python/ch-1.py new file mode 100755 index 0000000000..2d4c2f745f --- /dev/null +++ b/challenge-121/roger-bell-west/python/ch-1.py @@ -0,0 +1,17 @@ +#! /usr/bin/python3 + +import unittest +import re + +def ib(m,n): + return m ^ (1 << (n-1)) + +class TestIb(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(ib(12,3),8,'example 1') + + def test_ex2(self): + self.assertEqual(ib(18,4),26,'example 2') + +unittest.main() diff --git a/challenge-121/roger-bell-west/raku/ch-1.p6 b/challenge-121/roger-bell-west/raku/ch-1.p6 new file mode 100755 index 0000000000..ae5eb0b566 --- /dev/null +++ b/challenge-121/roger-bell-west/raku/ch-1.p6 @@ -0,0 +1,12 @@ +#! /usr/bin/perl6 + +use Test; + +plan 2; + +is(ib(12,3),8,'example 1'); +is(ib(18,4),26,'example 2'); + +sub ib($m,$n) { + return $m +^ (1 +< ($n-1)); +} diff --git a/challenge-121/roger-bell-west/ruby/ch-1.rb b/challenge-121/roger-bell-west/ruby/ch-1.rb new file mode 100755 index 0000000000..7ea06b0478 --- /dev/null +++ b/challenge-121/roger-bell-west/ruby/ch-1.rb @@ -0,0 +1,19 @@ +#! /usr/bin/ruby + +def ib(m,n) + return m ^ (1 << (n-1)) +end + +require 'test/unit' + +class TestIb < Test::Unit::TestCase + + def test_ex1 + assert_equal(8,ib(12,3)) + end + + def test_ex2 + assert_equal(26,ib(18,4)) + end + +end diff --git a/challenge-121/roger-bell-west/rust/ch-1.rs b/challenge-121/roger-bell-west/rust/ch-1.rs new file mode 100755 index 0000000000..2939e1ec85 --- /dev/null +++ b/challenge-121/roger-bell-west/rust/ch-1.rs @@ -0,0 +1,16 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit + +#[test] +fn test_ex1() { + assert_eq!(ib(12,3),8); +} + +#[test] +fn test_ex2() { + assert_eq!(ib(18,4),26); +} + +fn ib (m: u8,n: u8) -> u8 { + return m ^ (1 << (n-1)) +} diff --git a/challenge-121/roger-bell-west/rust/ch-2.rs b/challenge-121/roger-bell-west/rust/ch-2.rs new file mode 100644 index 0000000000..c28b8fc3ba --- /dev/null +++ b/challenge-121/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,89 @@ +use std::collections::HashMap; +use permutator::{Permutation,Combination}; +use rand::prelude::*; +use std::time::Instant; + +#[test] +fn test_ex1() { + assert_eq!(tsp(vec![ + vec![0, 2, 9, 10], + vec![1, 0, 6, 4], + vec![15, 7, 0, 8], + vec![6, 3, 12, 0] + ]),(21,vec![0,2,3,1,0])); +} + +#[test] +fn test_ex2() { + assert_eq!(tsp(vec![ + vec![0, 5, 2, 7], + vec![5, 0, 5, 3], + vec![3, 1, 0, 6], + vec![4, 5, 4, 0], + ]),(10,vec![0,2,1,3,0])); +} + +fn main() { + for size in 4..=11 { + let m=genmatrix(size); + let start=Instant::now(); + let _o=tsp(m); + let duration=start.elapsed(); + println!("| {} | {:?} |",size,duration); + } +} + +fn genmatrix(n: usize) -> Vec<Vec<usize>> { + let mut m=vec![vec![0;n];n]; + for x in 0..n { + for y in 0..n { + if x != y { + m[x][y]=thread_rng().gen::<u16>() as usize; + } + } + } + return m; +} + +fn tsp (d: Vec<Vec<usize>>) -> (usize, Vec<usize>) { + let n=d.len(); + let mut c: HashMap<(usize,usize),(usize,usize)>=HashMap::new(); + for k in 1..n { + c.insert((1<<k,k),(d[0][k],0)); + } + for ss in 2..n { + let sb=(1..n).collect::<Vec<usize>>(); + sb.combination(ss).for_each(|mut sbb| { + sbb.permutation().for_each(|s| { + let mut bits: usize=0; + s.iter().for_each(|bit| {bits += 1<<**bit}); + for k in &s { + let prev=bits & !(1<<**k); + let mut res: Vec<(usize,usize)>=vec![]; + for m in &s { + if **m==0 || **m==**k { + continue; + } + res.push((c.get(&(prev,**m)).unwrap().0+d[**m][**k],**m)); + } + c.insert((bits,**k),*res.iter().min().unwrap()); + } + }); + }); + } + let mut bitmask=(1<<n)-1 & !1; + let opp=(1..n).collect::<Vec<usize>>().iter().map(|k| (c.get(&(bitmask,*k)).unwrap().0+d[*k][0],*k)).min().unwrap(); + let opt=opp.0; + let mut parent=opp.1; + let mut path: Vec<usize>=vec![]; + for _i in 0..n-1 { + path.push(parent); + let nb=bitmask & !(1 << parent); + parent=c.get(&(bitmask,parent)).unwrap().1; + bitmask=nb; + } + path.push(0); + path.reverse(); + path.push(0); + return (opt,path); +} |