adding challenge 1

1 files changed, 58 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..99e2b30dcc
--- /dev/null
+++ b/challenge-049/ianrifkin/perl/ch-1.pl
@@ -0,0 +1,58 @@
+#!/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;
+
+my $i = 2;
+my $output = undef;
+
+
+# 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.
+
+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++;
+}
+
+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.