Merge pull request #4494 from drbaggy/master

Solns to 121

4 files changed, 165 insertions, 298 deletions

diff --git a/challenge-121/james-smith/README.md b/challenge-121/james-smith/README.md
index 8891ff92d5..34633d404a 100644
--- a/challenge-121/james-smith/README.md
+++ b/challenge-121/james-smith/README.md
@@ -10,327 +10,99 @@ submit solutions in whichever language you feel comfortable with.
 
 You can find the solutions here on github at:
 
-https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-120/james-smith/perl
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-121/james-smith/perl
 
-# Task 1 - Swap bits
+# Task 1 - Invert Bit
 
-***You are given a positive integer `$N` less than or equal to `255`. Write a script to swap the odd positioned bit with even positioned bit and print the decimal equivalent of the new binary representation.***
+***You are given integers `0 <= $m <= 255` and `1 <= $n <= 8`. Write a script to invert `$n` bit from the end of the binary representation of `$m` and print the decimal representation of the new binary number.***
 
 ## The solution
 
-This is very similar to last weeks challenge - but instead of swapping bits 4-7 with bits 0-3 this time we are swapping even bits with odd bits - so the solution is similar...
-
-The even bits are found by bit-wise *and*ing the number with `0b01010101` 0r `0x55` (`85` decimal) and the odd bits are found by bit-wise anding with `0b10101010` or `0xaa` (`170` decimal). We then switch them by multiplying or dividing by 2 {which we do with the bit shift operators `<<` & `>>`}. We just have to add the two values together - as we know the bits don't overlap we can use `|` rather than `+`.
+To invert a particular bit we can **xor**(`^`) `2^($n-1)` with the number in question. We can simplify the `2^($n-1)` by rewriting as `1<<$n-1` this is using bit-shift operators. So the function simply becomes.
 
 ```perl
-sub switch_bits {
-  ($_[0]&0xaa)>>1 | ($_[0]&0x55)<<1;
+sub flip_bit {
+  return $_[0] ^ 1<<$_[1]-1;
 }
 ```
 
-# Task 2 - Clock Angle
-
-***You are given time `$T` in the format `hh:mm`. Write a script to find the smaller angle formed by the hands of an analog clock at a given time.***
-
-## The solution
-
-Given a time we can compute the position of the hour hand as `$hr*30+$min/2` and the minute hand as `$min*6`.
+# Task 2 - The Travelling Salesman
 
-We can then get the angle between the two as: `($hr*60+$min-$min*12)/2`
+***You are given a `NxN` matrix containing the distances between `N` cities. Write a script to find a round trip of minimum length visiting all `N` cities exactly once and returning to the start.***
 
-To make sure the angle is between `-360` and `360` we have to ensure that the hour is between `0` and `11`, by reducing it module 12. We then get the absolute value so we have a value between `0` and `360`
+## Solution.
 
-We need a number between `0` and `180`. To map the range `180` - `360` we can either use an IF OR we can note that if we
-do `abs(angle - 180)` we get the complementary angle. So we just subtract this from `180` giving the method below...
+This is very similar to the pre-computed distance "Adventure of Knight" solution from challenge 118, the only change we have to do is add the distance from the last node to the start node. The only change is when the list of "targets" left is of length 1. In that problem we were not expected to return to the start...
 
+The addition is this condition:
 ```perl
-sub clock_angle_1_liner {
-  180-abs(abs((substr$_[0],0,2)%12*30-5.5*substr$_[0],3)-180);
-}
+  if(@r=1) { 
+    $len = $dist_maps->[$start][$r[0]] + $dist_maps->[$r[0]][0];
+    $rt = chr(65+$r[0]).'A';
+  } else {
 ```
 
-Compared to this (perhaps slightly more readable) method there is about a 85% performance gain [avoiding variables!]
-```perl
-sub clock_angle {
-  my($h,$m) = split /:/,shift;
-  my $t = abs($h%12*30-$m*5.5);
-  return $t > 180 ? 360-$t : $t;
-}
-```
-
-**Note** We can gain more speed (110% faster than "simple" method and about 15% faster than the 1-liner) by removing the first `substr` but to do so we need to disable `numeric` warnings - `no warnings qw(numeric)`.
+Giving us our walking algorithm.... {the calls count is just to see how efficient the caching is}
 
 ```perl
-sub clock_angle_fast {
-  180-abs(abs($_[0]%12*30-5.5*substr$_[0],3)-180);
+sub optimal_route {
+  $calls++;
+  my($start,@r) = @_;
+  my $key = "$start @{[ sort @r ]}";
+  return $CACHE{$key} if exists $CACHE{$key};
+  my $len = 1e99;
+  my $rt  = '';
+  if(@r==1) { 
+    $len = $dist_maps->[$start][$r[0]] + $dist_maps->[$r[0]][0];
+    $rt = chr(65+$r[0]).'A';
+  } else {
+    foreach(0..$#r) {
+      my $t = shift @r;
+      my $x = optimal_route($t,@r);
+      my $l = $dist_maps->[$start][$t] + $x->[0];
+      if( $l < $len ) {
+        $len = $l;
+        $rt  = (chr(65+$t)).$x->[1];
+      }
+      push @r,$t;
+    }
+  }
+  return $CACHE{$key} = [$len,$rt];
 }
 ```
 
-(Without disabling warnings this gives `Argument "04:00" isn't numeric in modulus (%) at ..` errors)
-
-# Solutions in CESIL
-
-OK - last weeks CESIL challenge was easier than this weeks....
-
-Due to not having bit wise operations or an easy convert between hex and binary we have to find an alternative solution.
-
-## Task 1
-
- * In this case we work through the pairs of bits flipping them round.
- * We compute the value of the bits by dividing though by 64 (then 16, 4, (and 1)) and taking the integer value.
- * If the value is 0 or 3 then we do nothing otherwise we map 1 to 2 and 2 to 1 respectively....
- * we repeat 4 times for each pair and keep a running sum which gives us our answer...
-
-```
-        LINE
-        LOAD  +0
-        STORE success
-        STORE tests
-Next    IN
-        JINEG End
-        STORE a
-        OUT
-        IN
-        STORE ans
-        LOAD +0
-        STORE res
-        LOAD +64
-Loop    STORE divisor
-        LOAD a
-        DIVIDE divisor
-        SUBTRACT 1
-        JIZERO j_1
-        SUBTRACT 1
-        JIZERO j_2
-        ADD 2
-        JUMP j
-j_1     LOAD   +2
-        JUMP j
-j_2     LOAD   +1
-j       MULTIPLY divisor
-        ADD res
-        STORE res
-        LOAD a
-        DIVIDE divisor
-        MULTIPLY divisor
-        MULTIPLY -1
-        ADD a
-        STORE a
-        LOAD divisor
-        DIVIDE +4
-        JIZERO EndL
-        JUMP Loop
-EndL    LOAD res
-        PRINT " => "
-        OUT
-(Now run the test!
-        PRINT " : "
-        SUBTRACT ans
-        JIZERO Ok
-        PRINT "-- should be "
-        LOAD ans
-        OUT
-        PRINT "?"
-        JUMP Line
-Ok      PRINT "OK"
-        LOAD success
-        ADD +1
-        STORE success
-Line    LINE
-        LOAD tests
-        ADD +1
-        STORE tests
-        JUMP Next
-End     LINE
-        PRINT "TESTS: "
-        LOAD success
-        OUT
-        PRINT " of "
-        LOAD tests
-        OUT
-        PRINT " passed"
-        LINE
-        LINE
-        HALT
-        %
-        101
-        154
-        18
-        33
-        154
-        101
-        33
-        18
-        -1
-```
-Output...
-```
-101 => 154 : OK
-18 => 33 : OK
-154 => 101 : OK
-33 => 18 : OK
-
-TESTS: 4 of 4 passed
-```
-
-## Task 2
+Running this for size 20 give us this output... {obv a randomised distance matrix}
 
-**CAVEAT:**
- * Can't cope with "odd minutes" as this will lead to a fractional angle {and CESIL is integer only}
- * Can't handle non-integer input - so the times have to be put in without the : so `03:30` is put in as `0330`
-```
-( Compute the angle between the hour and minute hand
-( Input contains of pairs of hour.minute & answer so
-( can check calculations are OK!
-        LINE
-        LOAD  +0
-        STORE success
-        STORE tests
-Next    IN
-        JINEG End
-        STORE mn
-        DIVIDE 100
-        STORE hr
-        MULTIPLY -100
-        ADD mn
-        STORE mn
-        LOAD hr
-        SUBTRACT +10
-        JINEG bl1
-        JUMP bl1e
-bl1     PRINT "0"
-bl1e    ADD +10
-        OUT
-        PRINT ":"
-        LOAD mn
-        SUBTRACT +10
-        JINEG bl2
-        JUMP bl2e
-bl2     PRINT "0"
-bl2e    ADD +10
-        OUT
-        IN
-        STORE ans
-        LOAD mn
-        PRINT " => "
-        MULTIPLY -11
-        DIVIDE +2
-        STORE t
-        LOAD hr
-        SUBTRACT 12
-        JINEG lt12
-        JUMP gt12
-lt12    ADD +12
-gt12    MULTIPLY +30
-        ADD t
-        JINEG lt0
-        JUMP gt0
-lt0     MULTIPLY -1
-gt0     SUBTRACT +180
-        JINEG ltx0
-        MULTIPLY -1
-ltx0    ADD +80
-        JINEG lt100
-        JUMP gt100
-lt100   PRINT " "
-        ADD +90
-        JINEG lt10
-        JUMP gt10
-lt10    PRINT " "
-gt10    SUBTRACT +90
-gt100   ADD +100
-        OUT
-        PRINT " : "
-        SUBTRACT ans
-        JIZERO Ok
-        PRINT "-- should be "
-        LOAD ans
-        OUT
-        PRINT "?"
-        JUMP Line
-Ok      PRINT "OK"
-        LOAD success
-        ADD +1
-        STORE success
-Line    LINE
-        LOAD tests
-        ADD +1
-        STORE tests
-        JUMP Next
-End     LINE
-        PRINT "TESTS: "
-        LOAD success
-        OUT
-        PRINT " of "
-        LOAD tests
-        OUT
-        PRINT " passed"
-        LINE
-        LINE
-        HALT
-        %
-        0318
-        9
-        0420
-        10
-        0440
-        100
-        0310
-        35
-        0400
-        120
-        0800
-        120
-        1600
-        120
-        1800
-        180
-        2000
-        120
-        -1
 ```
-Output:
+Distance matrix:
+      0    8    7   18    3   14    5   18   16   10    0   18    8    0   12    5    0    0    3    7
+      3    0    7    0    3   17    8    5    0    7    6   19    8   13   14   18   19   15   11    7
+      7   12    0   14   14    4   11   11   11    6    5   15   11    1    8   12   19    6   14   12
+     19    1    5    0    5    7   11    3    7   17    8   14    8   12    4   18   17   15   19    7
+     14    3    8   12    0    1   18    2    4   12    5   10    7    2   11   11   19    1    6    1
+     10   17    6   14    4    0    9   12   13    7   19   14   16    1   12   13    3   18    9    7
+     17    5    5    4   10    3    0   19    1   15   10    2   18    3    3    4   18   11   18    9
+     15   12   12   15    5    6    5    0    0    5    6    6    0    2   16   10   10    4    9   18
+      3   17    4    3    0    5   14   14    0   15   12    8   12    8   10    3    6   18    9   17
+      6   13    5    2   12   15    5    5   13    0   12   16   12   18    8    6   12    3    9   18
+     15   15   19    2    2   14    0   11   13   13    0   16   17   17    9    3   12    2   13    1
+      4   18    5   18    9   10    9   13   16    2   15    0    0    8    1   19    5   18    5    6
+      7   17    5    6   18    5   19   13    8   15   10    6    0    1    3    5   17    5    8    3
+      5   19    3   16    6    5   16    3   16   18   17   18   10    0   17   18    8    4    4    8
+      6   16   18    4   16    6    6    7    0   15   18    2    3   16    0   10   16    1   12    0
+      9    3   17   18   12    5   12   10    1    3   17   19    3   13   16    0   13    9    8   11
+     13    6   12   17    2    2    0   12    9    2   16    1   19   15   11    3    0   17    7    6
+     13   12    9   13    3   17   16   10   10    7    7    1    7   11   14   10   12    0    4    7
+     18   18   14   10   14    1    5   17    4    9    0   11   13    8   14   11   17   19    0    7
+     14   14   17   13    2    5    6   12    8   11   12    6   19   18   16   10    1    5   11    0
+Routes: 121,645,100,408,832,000
+Calls:               44,826,302 { 1 :  2,713,699,212 }
+Cache:                4,980,718 { 1 : 24,423,205,732 }
+Length: 32
+Route:  A R L O T Q G I E H M C F N S K P J D B A
+Time:   181.083702 seconds
 ```
-03:18 =>   9 : OK
-04:20 =>  10 : OK
-04:40 => 100 : OK
-03:10 =>  35 : OK
-04:00 => 120 : OK
-08:00 => 120 : OK
-16:00 => 120 : OK
-18:00 => 180 : OK
-20:00 => 120 : OK
 
-TESTS: 9 of 9 passed
-```
-
-## Aside CESIL interpreter v2
-
-I do have an uncompressed version of this - but this was a challenge to get the
-CESIL interpreter into 1K of Perl - partly as we are harking back to the days of
-very small memory computers {about the time that I was programming a ZX81 with 1K
-RAM and a 4K ROM}...
-
-This fixes a few of the shortcomings in the interpreter last week {e.g. adds the
-ability to add "comments" and handles both specs of positive constants}
-
-```perl
-#!/bin/perl
-use strict;use warnings;my($M,$p,$r,@i,%m,@c,%q)=(1e6,0,0);
-my@t=('PROGRAM REQUIRES MORE DATA','UNKNOWN VARIABLE ',
-'DIVISION BY ZERO ','UNKNOWN LABEL ');
-sub _e{die sprintf "\n*** %s%s *** %s \@ %d\n",$t[$_[0]],@{$c[$p]}[1,0],1+$p}
-sub _j{exists$q{$_}?($p=$q{$_}-1):_e 3}
-sub _v{/^[-+]?\d+$/?(0+$_):exists$m{$_}?$m{$_}:_e 1}
-my%c=('LINE',sub{print"\n"},'OUT',sub{print$r},'STORE',sub{$m{$_}=$r},
-'PRINT',sub{print s/^"//r=~s/"$//r},'IN',sub{@i?($r=shift@i):_e 0},
-'JINEG',sub{_j if$r<0},'SUBTRACT',sub{$r-=_v},'MULTIPLY',sub{$r*=_v},
-'ADD',sub{$r+=_v},'DIVIDE',sub{$_=_v;$r=$_?int($r/$_):_e 2},
-'LOAD',sub{$r=_v},'JIZERO',sub{_j if!$r},'JUMP',sub{_j},'HALT',sub{exit});
-while(<>){next if/^ *\(/;((@i=map{/^\s+[-+]?\d+\s*$/?0+$_:()}<>),last)if/^ *%/;
-($q{$1},$_)=(0+@c,$2)if/^(\S{1,6})\s+(.*)/;
-my($x,$y)=split/\s+/,s/^\s+//r=~s/\s+$//r,2;next unless $x;
-die"\n# Unk cmd [$x \@ ",1+@c,"]\n"if!exists$c{$x};push@c,[$x,$y//''];}
-($c{$c[$p][0]}($_=$c[$p][1]),$p++)while--$M&&$p<@c;
-die"\n*** No HALT ***\n"
-```
+As you can see from the output the filtering is very efficient in this case quickly reducing the number
+of routes investigated from 121 quadrillion to a handful of millions. The algorithm is "limited" by
+memory as the cache grows rapidly as `$N` increases.
diff --git a/challenge-121/james-smith/blog.txt b/challenge-121/james-smith/blog.txt
new file mode 100644
index 0000000000..7108dd639d
--- /dev/null
+++ b/challenge-121/james-smith/blog.txt
@@ -0,0 +1 @@
+https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-121/james-smith
diff --git a/challenge-121/james-smith/perl/ch-1.pl b/challenge-121/james-smith/perl/ch-1.pl
new file mode 100644
index 0000000000..1929dc1409
--- /dev/null
+++ b/challenge-121/james-smith/perl/ch-1.pl
@@ -0,0 +1,24 @@
+#!/usr/local/bin/perl
+
+use strict;
+
+use warnings;
+use feature qw(say);
+use Test::More;
+use Benchmark qw(cmpthese timethis);
+use Data::Dumper qw(Dumper);
+
+my @TESTS = (
+  [ 12, 3, 8 ],
+  [ 18, 4, 26 ],
+);
+
+is( flip_bit($_->[0],$_->[1]), $_->[2] ) foreach @TESTS;
+is( flip_bit($_->[2],$_->[1]), $_->[0] ) foreach @TESTS;
+
+done_testing();
+
+sub flip_bit {
+  return $_[0] ^ 1<<$_[1]-1;
+}
+
diff --git a/challenge-121/james-smith/perl/ch-2.pl b/challenge-121/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..6b67d6d78a
--- /dev/null
+++ b/challenge-121/james-smith/perl/ch-2.pl
@@ -0,0 +1,70 @@
+#!/usr/local/bin/perl
+
+use strict;
+
+use warnings;
+use feature qw(say);
+use Time::HiRes qw(time);
+use Data::Dumper qw(Dumper);
+
+my $start = time;
+my %CACHE;
+my $calls=0;
+my $N = 4;
+my $dist_maps = [
+  [0, 5, 2, 7],
+  [5, 0, 5, 3],
+  [3, 1, 0, 6],
+  [4, 5, 4, 0],
+];
+
+my $comb = 1;
+if(@ARGV) {
+  $N = shift @ARGV;
+  $dist_maps = [];
+  foreach my $r (0..$N-1) {
+    $dist_maps->[$r][$_] = $r == $_ ? 0 : int rand(20) foreach 0..$N-1;
+  }
+}
+$comb*=$_ foreach 2..($N-1);
+
+say '';
+say 'Disance matrix:';
+say join '  ', '','',map{ sprintf '%3d', $_ } @{$_} foreach @{$dist_maps};
+
+my $res = optimal_route(0,1..($N-1));
+
+say 'Routes: ',$comb;
+say 'Calls:  ',$calls;
+say 'Cache:  ',scalar keys %CACHE;
+say 'Length: ',$res->[0];
+say 'Route:  A ',join q( ), split m{}, $res->[1];
+say 'Time:   ',sprintf '%10.6f seconds', time-$start;
+
+
+sub optimal_route {
+  $calls++;
+  my($start,@r) = @_;
+  my $key = "$start @{[ sort @r ]}";
+  return $CACHE{$key} if exists $CACHE{$key};
+  my $len = 1e99;
+  my $rt  = '';
+  if(@r==1) { ## Last node to visit... distance is from start to node to "0"
+    $len = $dist_maps->[$start][$r[0]] + $dist_maps->[$r[0]][0];
+    $rt = chr(65+$r[0]).'A';
+  } else {
+    foreach(0..$#r) {
+      my $t = shift @r;
+      my $x = optimal_route($t,@r);
+      my $l = $dist_maps->[$start][$t] + $x->[0];
+      if( $l < $len ) {
+        $len = $l;
+        $rt  = (chr(65+$t)).$x->[1];
+      }
+      push @r,$t;
+    }
+  }
+  return $CACHE{$key} = [$len,$rt];
+}
+
+exit;