Challenge 111 done

6 files changed, 209 insertions, 0 deletions

diff --git a/challenge-111/dms061/perl/ch-1-example.txt b/challenge-111/dms061/perl/ch-1-example.txt
new file mode 100644
index 0000000000..d8eb05bc99
--- /dev/null
+++ b/challenge-111/dms061/perl/ch-1-example.txt
@@ -0,0 +1,33 @@
+Run with:
+$ perl ch-1.pl
+
+Example output:
+
+[1 2 3 4 5]
+[6 7 8 9 10]
+[11 12 13 14 15]
+[16 17 18 19 20]
+[21 22 23 24 25]
+Enter a number to search for: 20
+20 is in the matrix
+
+-------------------------------------------
+
+[1 2 3 4 5]
+[6 7 8 9 10]
+[11 12 13 14 15]
+[16 17 18 19 20]
+[21 22 23 24 25]
+Enter a number to search for: 30
+30 is not in the matrix
+
+-------------------------------------------
+
+[1 2 3 4 5]
+[6 7 8 9 10]
+[11 12 13 14 15]
+[16 17 18 19 20]
+[21 22 23 24 25]
+Enter a number to search for: 8
+8 is in the matrix
+
diff --git a/challenge-111/dms061/perl/ch-1.pl b/challenge-111/dms061/perl/ch-1.pl
new file mode 100644
index 0000000000..967ba6a335
--- /dev/null
+++ b/challenge-111/dms061/perl/ch-1.pl
@@ -0,0 +1,90 @@
+use strict;
+use warnings;
+
+# Question 1: You are given 5x5 matrix filled with integers such that
+# each row is sorted from left to right and the first integer of each row
+# is greater than the last integer of the previous row
+# Write a script to find a given integer in the matrix using an efficient search algorithm
+
+# Solution: 2d binary search. Elements are sorted, so binary search is a good algorithm to use
+# 1st search for the array the element is in -- our "equality" check is an in range check X0 <= X <= Xn
+# 2nd seach is standard binary search on the array the element is in
+
+sub binary_search {
+	# need integer division for index calcs
+	# this says to use int div lexically (SCOPED)
+	use integer;
+	# 2 args, 1 scalar and an array
+	# however, perl puts them all into 1 array, @_
+	# so we shift the value param off
+	# and treat @_ as the array
+	#my $val = shift;
+	# TODO add optimization?
+	# Change this to be a helper that assumes
+	# we are working on an array w/ elts (del 1st line after comments)
+	# and that $val is in it
+	# Add a top level binary_search that checks if
+	# @arr has elements and $val is in @arr
+	# this would be done so those checks occur only once
+	my ($val, @arr) = @_;
+	return 0 if @arr == 0;
+	if(@arr == 1){
+		return 1 if $arr[0] == $val;
+		return 0; 
+	}
+	my $mid = $#arr/2;
+	# Can I replace the equality / comparison ops with custom operators or functions?
+	# This way, we can implement 2d_binary_search by using the regular binary search
+	# and a custom comparator.
+	return binary_search ($val, @arr[0..$mid-1]) if $val < $arr[$mid];
+	return binary_search ($val, @arr[$mid+1..$#arr]) if $val > $arr[$mid];
+	# $val == $_[$mid]
+	return 1;
+}
+
+sub binary_search_2d {
+	use integer;
+	# 2 args, val to search for and array of refs
+	my ($val, @arrs) = @_;
+
+	# no empty array? Value can't be present
+	return 0 if @arrs == 0;
+
+	#find the middle array (will work if there is only 1 array present)	
+	my $mid = $#arrs/2;
+	#extract the array for easier usage
+	my @mid_arr = @{$arrs[$mid]};
+	# no elts in middle array, ret 0
+	return 0 if @mid_arr == 0;
+	# check if $val is out of range, we can't binary search if it isn't there
+	if($val < $mid_arr[0]){
+		return binary_search_2d($val, @arrs[0..$mid-1]);
+	}elsif($val > $mid_arr[$#mid_arr]){
+		return binary_search_2d($val, @arrs[$mid+1..$#arrs]);
+	}
+	# $val may be in array, so we can search for it now
+	return binary_search $val, @mid_arr;
+}
+
+my @matrix = ( 
+	[1, 2, 3, 4, 5],
+	[6, 7, 8, 9, 10],
+	[11, 12, 13, 14, 15],
+	[16, 17, 18, 19, 20], 
+	[21, 22, 23, 24, 25]);
+
+# print out the matrix
+foreach my $ref (@matrix){
+	print "[@$ref]\n";
+}
+
+# Get a number to search for
+print "Enter a number to search for: ";
+my $val = <STDIN>;
+chomp $val; #remove trailing whitespace 
+
+if (binary_search_2d $val, @matrix){
+	print "$val is in the matrix\n";	
+}else{
+	print "$val is not in the matrix\n";
+}
diff --git a/challenge-111/dms061/perl/ch-2-example.txt b/challenge-111/dms061/perl/ch-2-example.txt
new file mode 100644
index 0000000000..ff7c284ac6
--- /dev/null
+++ b/challenge-111/dms061/perl/ch-2-example.txt
@@ -0,0 +1,3 @@
+Question 2:
+Longest presorted word(s) in American English is/are 7 letters long.
+Word(s): billowy
diff --git a/challenge-111/dms061/perl/ch-2.pl b/challenge-111/dms061/perl/ch-2.pl
new file mode 100644
index 0000000000..a488fac712
--- /dev/null
+++ b/challenge-111/dms061/perl/ch-2.pl
@@ -0,0 +1,50 @@
+use strict;
+use warnings;
+
+# Question 2: Given a word, you can sort its letters alphabetically (case insensitive). 
+# For example, “beekeeper” becomes “beeeeekpr” and “dictionary” becomes “acdiinorty”.
+
+# Write a script to find the longest English words that don’t change when their letters are sorted.
+
+# The question is trying to be misleading. If the word doesn't change when it is sorted, then 
+# all we have to check is if the word is sorted (no need to reverse it)
+
+open(my $dict, "<", "american-english") or die "Couldn't open dict file\n";
+
+my @chars;
+my $len = 0;
+my @words;
+WORD: while (<$dict>) {
+	# Remove whitespace (chomp), convert to lowercase ('A' != 'a') and split word into an array of characters 
+	chomp;
+	$_ = lc;
+	# Implementation is based off the idea that the string need only be iterated over once
+	# Because we have to split it, we really iterate over it twice
+	# A more efficient implementation would just access characters in the string directly
+	@chars = split "";
+	# Optimization, only search for words of increasing size
+	next WORD if @chars < $len;
+	# Check if the word is sorted
+	for(my $i = 0; $i < $#chars; $i++){
+		# like a weird mix of break and goto
+		# immediately goes to the next iteration of the label
+		# no other code is executed
+		next WORD unless $chars[$i] le $chars[$i+1];
+	}
+	#print "$_\n";
+	if ($len == @chars){
+		#equal length, add to a list
+		push @words, $_;
+	}else{
+		# new largest (remember we skip smaller words)
+		#reset the list and update the length
+		@words = ($_);
+		$len = @chars;
+	}
+}
+
+print "Question 2:\nLongest presorted word(s) in American English is/are $len letters long.\nWord(s): @words\n";
+
+#open(my $dict, "<", "/usr/share/dict/american-english");
+close $dict;
+
diff --git a/challenge-111/dms061/python3/ch-2.py b/challenge-111/dms061/python3/ch-2.py
new file mode 100644
index 0000000000..e38ce33ef8
--- /dev/null
+++ b/challenge-111/dms061/python3/ch-2.py
@@ -0,0 +1,24 @@
+def sorted(arr):
+    for i in range(0, len(arr)-1, 1):
+        if(arr[i] > arr[i+1]):
+            return False
+    return True
+
+if __name__ == "__main__":
+    length = 0
+    words = []
+    with open("../perl/american-english", "r") as f:
+        for word in f.readlines():
+            word = word.lower().strip()
+            #no need to scan for smaller words ;>
+            #I'm not sure that this saves any [noticable] amount of time
+            if(length < len(word) and sorted(word)):
+                if(len(word) > length):
+                    length = len(word)
+                    words = [word]
+                elif(len(word) == length):
+                    words.append(word)
+                #else: we discard
+    print("Longest presorted word(s) is/are", length, "letters long")
+    print("Word(s):", words)
+    
diff --git a/challenge-111/dms061/readme b/challenge-111/dms061/readme
new file mode 100644
index 0000000000..5b4521ecae
--- /dev/null
+++ b/challenge-111/dms061/readme
@@ -0,0 +1,9 @@
+Solutions by David Schwartz
+5/9/2021
+
+Contains:
+	Solutions for questions 1 and 2 in perl.
+	Solution for question 2 in python (3).
+
+The folders also contain examples of output generated from running the program.
+Note, I am new to programming in perl--sorry if the solutions are sloppy!