Merge pull request #1340 from ianrifkin/branch-for-challenge-049

Branch for challenge 049

2 files changed, 144 insertions, 0 deletions

diff --git a/challenge-049/ianrifkin/perl/ch-1.pl b/challenge-049/ianrifkin/perl/ch-1.pl
new file mode 100644
index 0000000000..67d764a4a5
--- /dev/null
+++ b/challenge-049/ianrifkin/perl/ch-1.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/perl
+use strict;
+use Scalar::Util::Numeric qw(isint);
+use Math::BigInt;
+use Math::BigFloat;
+
+####  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.
+####  Solution by ianrifkin
+
+####  Assumption 1: the smallest multiple will ONLY have digits 0 and 1
+####  Assumption 2: Multiples are at least double the input (e.g. the multiple of 100 is 1000 and not 100)
+
+my $input = $ARGV[0];
+
+die("Input must be a positive number") unless $input > 0;
+
+
+# You could loop through every number and check if it's correct
+# For smaller answers like when $input = 2, or 5, or 100 it's quick
+# But when $input is 9 you can see how this starts to take too long to find the answer
+# and input = 99 is way too long to wait.
+
+# Instead b/c of assumption #1 we know that the answer will be 
+# only 0's and 1's we can do math using only binary numbers
+
+# subroutine taken from Perl Cookbook to convert decimals to binaries
+sub dec2bin {
+    my $str = unpack("B32", pack("N", shift));
+    $str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
+    return $str;
+}
+
+# for example when input = 9 in the first commented out method
+# it would take 1011111110 loops to get to 1011111111
+# But in this method it only takes 766 loops.
+
+my $i = 2;
+my $output = undef;
+while ($output == undef) {
+    my $bin_i = dec2bin($i);
+    $i++ and next unless $bin_i =~ /^1[1]*[0]+[0-1]*$/;
+    my $test = Math::BigFloat->new($bin_i);
+    $test->bdiv($input);
+    $output = $bin_i if $test == $test->as_int() and $input != $bin_i;
+    $i++;
+    #Consider if there needs to be an emergency exit after too many iterations
+    #without finding an answer
+}
+
+print "\n\nThe smallest multiple of $input with only digits 0 and 1 is: $output\n\n";
+
+# Note on BigFloat
+# My first attempt was to Scalar::Util::Numeric (or INT, POSIX or ROUND) to check 
+# if binary/input is an int  e.g. check $test == isint($test)
+# But this would return incorrect results when inputting a number like 99 because 
+# it was incorrectly rounding $test (too many digits?)
+# Using Math::BigFloat instead solves this problem but it's a major performance hit.
diff --git a/challenge-049/ianrifkin/perl/ch-2.pl b/challenge-049/ianrifkin/perl/ch-2.pl
new file mode 100644
index 0000000000..1f0333688f
--- /dev/null
+++ b/challenge-049/ianrifkin/perl/ch-2.pl
@@ -0,0 +1,85 @@
+#!/usr/bin/perl
+use strict;
+use Term::Prompt;
+use feature qw( say );
+use Data::Dumper;
+
+####  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.
+####  Solution by ianrifkin
+
+####  Notes: At first I was trying to have a %lru_map 
+####  not contain contents by refs to content, but I'm not sure why
+####  And the 'next' and 'prev' were orginally hash refs but I got confused
+####  how to delete from the cache
+
+####  Originally was going to organize code better using subs but alas
+####  here we are!
+
+### Globals
+my $max_cap = $ARGV[0];
+die("Input must be a positive number") unless $max_cap > 0;
+my @lru_cache = [];
+my %lru_map = {};
+my $head = undef;
+my $tail = undef;
+
+say "Welcome to the LRU Cache.";
+
+while(1) {
+    my $action = &prompt('x', "Choose: [get,set,quit]",'');
+
+    if ($action eq 'get') {
+	my $item_key = &prompt('x', "Input item key to get", '');
+	if (defined $lru_map{$item_key}) {
+	    say "Data from cache for key $item_key:";
+	    say $lru_map{$item_key}{'data'};
+	    $lru_map{$head}{'prev'} = $item_key; #set outgoing first item's prev to new first item
+	    $lru_map{$item_key}{'next'} = $head; #set new item's 'next' to outgoing head
+	    $head = $item_key; #Update head to current item key
+	    $lru_map{$item_key}{'prev'} = undef; #no prev since first in cache	    
+
+	    if ($tail eq $head) { #if the new head was the old tail
+		$tail = $lru_map{$tail}{'next'}; #set tail to new last item
+	    }
+	}
+	else {
+	    say "Item $item_key not currently in cache. Maybe you want to set it?";
+	}
+
+    }
+    elsif ($action eq 'set') {
+	my $item_key = &prompt('x', "Input key of new item to add to the cache", '');
+	my $item_data = &prompt('x', "Input item to add to cache", '');
+
+	$lru_map{$item_key} = {};
+	if ($head) { 
+	    $lru_map{$head}{'prev'} = $item_key; #set outgoing head's prev to current item
+	    $lru_map{$item_key}{'next'} = $head; #set new item's 'next' to outgoing head
+	}
+
+	$head = $item_key; #set new item as head
+	$tail = $item_key unless $tail; #set tail if no tail yet AKA 1st in cache
+
+	my $size = keys %lru_map; 
+	$size--; #don't count item being currently added
+	if ($size > $max_cap) { #if this new item can't fit in cache
+	    $tail = $lru_map{$tail}{'prev'}; #set new tail
+	    delete $lru_map{$lru_map{$tail}{'next'}}; #delete last item in cache
+	    delete $lru_map{$tail}{'next'}; #delete new last item's next since it's now last
+	}
+
+	$lru_map{$item_key}{'data'} = $item_data; #load actual cache
+	$lru_map{$item_key}{'prev'} = undef; #no prev since first in cache
+
+	next;
+    }
+    elsif ($action eq 'quit') {
+	say "Action is $action";
+	die("Thank you for trying the LRU Cache!");
+    }
+    else {
+	say "Invalid option selected. Please try again.";
+	next;
+    }
+}