Merge pull request #1354 from saiftynet/branch-050

Challenge-050 solutions by saiftynet

2 files changed, 109 insertions, 0 deletions

diff --git a/challenge-050/saiftynet/perl/ch-1.pl b/challenge-050/saiftynet/perl/ch-1.pl
new file mode 100644
index 0000000000..8cc1af4ccd
--- /dev/null
+++ b/challenge-050/saiftynet/perl/ch-1.pl
@@ -0,0 +1,58 @@
+#!/usr/env/perl
+# Task 1 Challenge 050 Solution by saiftynet
+# Merge Intervals
+# Write a script to merge the given intervals where ever possible.
+# [2,7], [3,9], [10,12], [15,19], [18,22]
+# The script should merge [2, 7] and [3, 9] together to return [2, 
+# 9].
+# Similarly it should also merge [15, 19] and [18, 22] together 
+# to return [15, 22].
+# The final result should be something like below:
+# [2, 9], [10, 12], [15, 22]
+
+# 1st part generates random intervals. Intervals are pairs of numbers.
+# $start is smaller than the $end. Because these are random, they are
+# also unsorted unlike the example shown above
+my @list=();
+foreach (0..10){
+    my $start=int(80*rand());
+    my $end=$start+int(10*rand()+2);
+    push @list,[$start,$end];
+}
+
+print "Before Merging:-\n",printall(@list), "\n"; # Prints the the initial list
+@list=mergeIntervals(@list);                      # Merge the list
+print "After Merging:-\n",printall(@list),"\n\n"; # Print the list post merger
+
+# The mergeIntervals takes a list of intervals and merges where possible
+sub mergeIntervals{
+  my @toMerge=@_;
+  @toMerge=sort {$$a[0]<=>$$b[0]} @toMerge;     # sort intervals on the intervals' start
+    
+  my $merges=1;                                 # ensure loop executes at least once
+    while ($merges){                            # until no more merges
+      my $pointer=$merges=0;                    # reset pointer and merges
+      while ($pointer<@toMerge-1){              # check two adjacent intervals for merging
+         splice @toMerge,$pointer,2,merge($toMerge[$pointer],$toMerge[$pointer+1]);
+         $pointer++;                            # check next pair
+      }
+    }
+  return @toMerge;
+    
+  sub merge{          # for sorted pair, pair will merge if start of second is
+    my ($a,$b)=@_;    # less or equal to end of first. When a merge happens,
+		              # start is the start of first, and end is the largest
+		              # of either end
+    return ([$$a[0], $$a[1]>$$b[1]?$$a[1]:$$b[1]])
+         if  $$a[1]>=$$b[0] and $merges=1;   # a merge happens and is flagged
+    return ($a,$b);                          # if not merged, returns the pair
+  }
+}
+
+# printall prints the lists of intervals
+sub printall{
+  my $printOut="";
+  $printOut.="[".$$_[0].",".$$_[1]."]," foreach(@_);
+  return $printOut;
+}
+
diff --git a/challenge-050/saiftynet/perl/ch-2.pl b/challenge-050/saiftynet/perl/ch-2.pl
new file mode 100644
index 0000000000..e61b9123b3
--- /dev/null
+++ b/challenge-050/saiftynet/perl/ch-2.pl
@@ -0,0 +1,51 @@
+#!/usr/env/perl
+# Task 2 Challenge 050 Solution by saiftynet
+# Contributed by Ryan Thompson.Noble Integer
+# You are given a list, @L, of three or more random integers between 
+# 1 and 50. A Noble Integer is an integer N in @L, such that there 
+# are exactly N integers greater than N in @L. Output any Noble 
+# Integer found in @L, or an empty list if none were found.
+# An interesting question is whether or not there can be multiple 
+# Noble Integers in a list.
+# For example,
+# Suppose we have list of 4 integers [2, 6, 1, 3].
+# Here we have 2 in the above list, known as Noble Integer, since 
+# there are exactly 2 integers in the list i.e.3 and 6, which are 
+# greater than 2.
+# Therefore the script would print 2.
+
+# The first part of the solution generates random lists to test
+# The list generator is configurable with random sizes and contents
+# The number of tests to be performed can also be set below
+my $maxListLength   =  15 ;
+my $minListLength   =   3 ;
+my $minIntSize      =   1 ;
+my $maxIntSize      =  20 ;
+my $numberOfTests   =  15 ;
+
+foreach (0..$numberOfTests ){
+  @list=();
+  push @list,int(rand()*($maxIntSize-$minIntSize)+$minIntSize)
+  foreach (0..(rand()*($maxListLength-$minListLength)+$minListLength));
+  findNobel(@list);
+}
+
+# The findNobel function, as one might expect, finds the nobel number.
+# The answer to the question of whether there can be more than 1 nobel
+# number is "NO".  A list with a noble number N has N elements with
+# greater value than N.  Any of the numbers which are greater than N
+# will therefore have less than N numbers greater than themselves. As
+# a number can not be both greater and less than N at the same time,
+# only one possible nobel number can exist for any list.
+
+sub findNobel{
+  @l=sort{$a<=>$b} @_;	# sort the list first
+  $found=0;             # intialise $found to zero
+  foreach(0..$#l){      # look through elements
+    # when a nobel element is found, report, set $found and exit
+    print "Found Nobel Number $l[$_] " and $found=1 and last if $l[$_]==($#l-$_);
+  }
+  print "No Nobel numbers" unless $found;   # $found not set if not found
+  print   " in ".(join ",",@l),"\n";        # either way, print out the list
+}
+