added this week's challenge solutions

4 files changed, 245 insertions, 19 deletions

diff --git a/challenge-049/duncan-c-white/README b/challenge-049/duncan-c-white/README
index bc2b8ce427..6895a656b2 100644
--- a/challenge-049/duncan-c-white/README
+++ b/challenge-049/duncan-c-white/README
@@ -1,29 +1,57 @@
-Task 1: "Roman Calculator
+Task 1: "Smallest Multiple:
 
-Write a script that accepts two roman numbers and operation. It should
-then perform the operation on the give roman numbers and print the result.
+Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.
 
-For example,
+For example:
+For given number 55, the smallest multiple is 110 consisting of digits 0 and 1.
+"
 
-perl ch-1.pl V + VI
+My notes: cute.
 
-should print
 
-XI
-"
+Task #2: "LRU Cache
+
+Write a script to demonstrate LRU Cache feature. It should support
+operations get and set. Accept the capacity of the LRU Cache as command
+line argument.
+
+Definition of LRU: An access to an item is defined as a get or a set
+operation of the item. "Least recently used" item is the one with the
+oldest access time.
+
+For example:
+
+capacity = 3
+set(1, 3)
+set(2, 5)
+set(3, 7)
+
+Cache at this point:
+[Least recently used] 1,2,3 [most recently used]
+
+get(2)      # returns 5
+
+Cache looks like now:
+[Least recently used] 1,3,2 [most recently used]
+
+get(1)      # returns 3
+
+Cache looks like now:
+[Least recently used] 3,2,1 [most recently used]
+
+get(4)      # returns -1
+
+Cache unchanged:
+[Least recently used] 3,2,1 [most recently used]
 
-My notes: cute, especially given that we did Roman->Int and Int->Roman in
-challenge 10:-).  So convert Roman->Int, Do Op, Int->Roman for the result.
-Added the ability for the user to specify the operands in EITHER Roman
-or Arabic.
+set(4, 9)
 
-Task #2: "Gapful Numbers
+Cache is full, so pushes out key = 3:
+[Least recently used] 2,1,4 [most recently used]
 
-Write a script to print first 20 Gapful Numbers greater than or equal
-to 100.  See https://oeis.org/A108343 for details.
-In summary, Gapful Numbers are those numbers >= 100 that are divisible
-by the number formed by their first and last digit.  Numbers up to 100
-trivially have this property and are excluded.  eg. 100 is, because 100%10==0
+get(3)      # returns -1
 "
 
-My notes: cute.  Easy.  Was so easy that I did it in Postscript as well.
+My notes: ok, so an array of keys in most-recently-used
+order, and a hash to store the (no more than $capacity)
+key, value pairs.
diff --git a/challenge-049/duncan-c-white/perl/cache-input b/challenge-049/duncan-c-white/perl/cache-input
new file mode 100755
index 0000000000..58af7724b0
--- /dev/null
+++ b/challenge-049/duncan-c-white/perl/cache-input
@@ -0,0 +1,8 @@
+set 1 3
+set 2 5
+set 3 7
+get 2
+get 1
+get 4
+set 4 9
+get 3
diff --git a/challenge-049/duncan-c-white/perl/ch-1.pl b/challenge-049/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..93ca16578e
--- /dev/null
+++ b/challenge-049/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,60 @@
+#!/usr/bin/perl
+#
+# Task 1: "Smallest Multiple:
+# 
+# Write a script to accept a positive number as command line argument and
+# print the smallest multiple of the given number consists of digits 0
+# and 1.
+# 
+# For example:
+# For given number 55, the smallest multiple is 110 consisting of digits 0 and 1.
+# "
+# 
+# My notes: cute, sounds easy.
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+use Function::Parameters;
+use Getopt::Long;
+#use Data::Dumper;
+
+my $tabulate = 0;
+my $result = GetOptions( "tabulate" => \$tabulate );
+die "Usage: smallestmultiple [--tabulate] [MAX]\n" if $result && @ARGV>1;
+
+my $max = shift // 50;
+
+if( $tabulate )
+{
+	foreach my $n (1..$max)
+	{
+		my $x = smallest_binary_multiple( $n );
+		my $f = $x/$n;
+		say "smallest multiple of $n ($n x $f) consisting of only 1s and 0s: $x";
+	}
+}
+else
+{
+	my $x = smallest_binary_multiple( $max );
+	my $f = $x/$max;
+	say "smallest multiple of $max ($max x $f) consisting of only 1s and 0s: $x";
+}
+
+
+#
+# my $x = smallest_binary_multiple( $n );
+#	Find the smallest multiple of $n whose decimal representations
+#	consist only of digits 0 and 1.  Return that smallest multiple.
+#
+fun smallest_binary_multiple( $n )
+{
+	my $mult = $n;
+	do {
+		$mult += $n;
+	} while( $mult =~ /[2-9]/ );
+	return $mult;
+}
+
+
diff --git a/challenge-049/duncan-c-white/perl/ch-2.pl b/challenge-049/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..c490b19980
--- /dev/null
+++ b/challenge-049/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,130 @@
+#!/usr/bin/perl
+#
+# Task #2: "LRU Cache
+#
+# Write a script to demonstrate LRU Cache feature. It should support
+# operations get and set. Accept the capacity of the LRU Cache as command
+# line argument.
+#
+# Definition of LRU: An access to an item is defined as a get or a set
+# operation of the item. "Least recently used" item is the one with the
+# oldest access time.
+#
+# For example:
+#
+# capacity = 3
+# set(1, 3)
+# set(2, 5)
+# set(3, 7)
+#
+# Cache at this point:
+# [Least recently used] 1,2,3 [most recently used]
+#
+# get(2)      # returns 5
+#
+# Cache looks like now:
+# [Least recently used] 1,3,2 [most recently used]
+#
+# get(1)      # returns 3
+#
+# Cache looks like now:
+# [Least recently used] 3,2,1 [most recently used]
+#
+# get(4)      # returns -1
+#
+# Cache unchanged:
+# [Least recently used] 3,2,1 [most recently used]
+#
+# set(4, 9)
+#
+# Cache is full, so pushes out key = 3:
+# [Least recently used] 2,1,4 [most recently used]
+#
+# get(3)      # returns -1
+#"
+#
+# My notes: ok, so an array of keys in most-recently-used
+# order, and a hash to store the (no more than $capacity)
+# key, value pairs.
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+use Function::Parameters;
+
+die "Usage: ch-2 CAPACITY\n" unless @ARGV==1;
+my $capacity = shift;
+
+# represent the LRU cache as an array of keys in use order
+# and a hash containing $capacity key,value pairs.
+
+my @keysused;		# most recently used at front, last at end
+my %cache;		# no more than $capacity key,value pairs
+
+#
+# my $result = get( $key );
+#	If $key is present in the cache, promote $key to the most recently
+#	used entry, and return the corresponding value from the cache;
+#	or return -1 if $key is not present in the cache.
+#
+fun get( $key )
+{
+	return -1 unless exists $cache{$key};
+	my $x = $cache{$key};
+	@keysused = grep { $_ != $key } @keysused;
+	unshift @keysused, $key;
+	say "debug: keysused = ", join(',',@keysused);
+	return $x;
+}
+
+
+#
+# set( $key, $value );
+#	Set $key to $value in the cache.  May need to remove another
+#	key, value pair if the cache is at capacity and the key is NOT
+#	already present.
+#
+fun set( $key, $value )
+{
+	@keysused = grep { $_ != $key } @keysused;
+	unshift @keysused, $key;
+	$cache{$key} = $value;
+	if( @keysused > $capacity )
+	{
+		my $leastusedkey = pop @keysused;
+		delete $cache{$leastusedkey};
+	}
+	say "debug: keysused = ", join(',',@keysused);
+}
+
+
+while( <STDIN> )
+{
+	chomp;
+	# format: 'get x' or 'set x y'
+	my @x = split(/\s+/);
+	if( $x[0] eq "get" )
+	{
+		if( @x == 2 )
+		{
+			say "doing get($x[1])";
+			my $result = get( $x[1] );
+			say "get($x[1]): result $result";
+		} else
+		{
+			warn "get needs one arg\n";
+		}
+	}
+	elsif( $x[0] eq "set" )
+	{
+		if( @x == 3 )
+		{
+			say "doing set($x[1],$x[2])";
+			set( $x[1], $x[2] );
+		} else
+		{
+			warn "set needs two args\n";
+		}
+	}
+}