Merge pull request #3197 from pauloscustodio/007

Add Perl and Python solutions to challenge 007

6 files changed, 321 insertions, 0 deletions

diff --git a/challenge-007/paulo-custodio/README b/challenge-007/paulo-custodio/README
new file mode 100644
index 0000000000..87dc0b2fbd
--- /dev/null
+++ b/challenge-007/paulo-custodio/README
@@ -0,0 +1 @@
+Solution by Paulo Custodio
diff --git a/challenge-007/paulo-custodio/perl/ch-1.pl b/challenge-007/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..1f8017cb9f
--- /dev/null
+++ b/challenge-007/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,23 @@
+#!/usr/bin/perl
+
+# Challenge 007
+# 
+# Challenge #1
+# Print all the niven numbers from 0 to 50 inclusive, each on their own line. 
+# A niven number is a non-negative number that is divisible by the sum of its digits.
+
+use strict;
+use warnings;
+use 5.030;
+use List::Util 'sum';
+
+sub solve {
+	my($max) = @_;
+	for my $n (1..$max) {
+		my $sum = sum(split //, $n);
+		say $n if $n % $sum == 0;
+	}
+}
+
+my $max = shift || 50;
+solve($max);
diff --git a/challenge-007/paulo-custodio/perl/ch-2.pl b/challenge-007/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..758d0cf755
--- /dev/null
+++ b/challenge-007/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,110 @@
+#!/usr/bin/perl
+
+# Challenge 007
+# 
+# Challenge #2
+# Word Ladder
+# A word ladder is a sequence of words [w0, w1, …, wn] such that each word wi
+# in the sequence is obtained by changing a single character in the word wi-1. 
+# All words in the ladder must be valid English words.
+# 
+# Given two input words and a file that contains an ordered word list, implement 
+# a routine (e.g., find_shortest_ladder(word1, word2, wordlist)) that finds the 
+# shortest ladder between the two input words. For example, for the words cold 
+# and warm, the routine might return:
+# 
+# ("cold", "cord", "core", "care", "card", "ward", "warm")
+# However, there’s a shortest ladder: (“cold”, “cord”, “card”, “ward”, “warm”).
+# 
+# Givens:
+# All words in the list have the same length.
+# 
+# All words contain only lowercase alphabetical characters.
+# 
+# There are no duplicates in the word list.
+# 
+# The input words aren’t empty and aren’t equal but they have the same length 
+# as any word in the word list.
+# 
+# Requirements:
+# The routine must return a list of the words in the ladder if it exists. 
+# Otherwise, it returns an empty list.
+# 
+# If any of the input words is the wrong length (i.e., its length is different 
+# to a random from the word list) or isn’t in the word list, return an empty list.
+
+use strict;
+use warnings;
+use 5.030;
+
+# get arguments
+sub get_args {
+	@ARGV==2 or die "Usage: ch-2.pl word1 word2\n";
+	my($word1, $word2) = @ARGV;
+	length($word1)==length($word2) or die "words must have the same length\n";
+	$word1 ne $word2 or die "words must be different\n";
+	for ($word1, $word2) {
+		/^[a-z]+$/ or die "words must have lower case letters only\n";
+	}
+	return ($word1, $word2)
+}
+
+# read wordlist from dictionary
+sub read_words {
+	my($file, $length) = @_;
+	
+	my %wordlist;
+	open(my $fh, "<", $file) or die "open $file: $!\n";
+	while (<$fh>) {
+		chomp;
+		next unless length($_)==$length;
+		next unless /^[a-z]+$/;
+		$wordlist{$_} = 1;
+	}
+	return %wordlist;
+}
+
+# find shortest ladder
+sub find_shortest_ladder {
+	my($word1, $word2, %wordlist) = @_;
+	my @queue = [$word1, [$word1], {$word1=>1}];	# [node, path, visited]
+	while (@queue) {
+		my($word, $path, $visited) = @{shift @queue};
+		my @next = next_possible_words($word, \%wordlist, $visited);
+		for my $next (@next) {
+			return (@$path, $next) if $next eq $word2;	# found solution
+			push @queue, [$next, [@$path, $next], {%$visited, $next=>1}];
+		}			
+	}
+	return ();	# no solution found
+}
+
+# find possible next words from %wordlist and not yet %visited
+sub next_possible_words {
+	my($word, $wordlist, $visited) = @_;
+	my @next;
+	for (sort keys %$wordlist) {
+		push @next, $_ if $_ ne $word && !$visited->{$_} && word_diff($_, $word)==1;
+	}
+	return @next;
+}
+
+sub word_diff {
+	my($word1, $word2) = @_;
+	my $diff = 0;
+	for (0 .. length($word1)-1) {
+		$diff++ if substr($word1,$_,1) ne substr($word2,$_,1);
+	}
+	return $diff;
+}
+
+
+# main
+sub solve {
+	my($word1, $word2) = get_args();
+	my %wordlist = read_words("words.txt", length($word1));
+	my @ladder = find_shortest_ladder($word1, $word2, %wordlist);
+	say "(", join(", ", map {'"'.$_.'"'} @ladder), ")";
+}
+
+solve;
diff --git a/challenge-007/paulo-custodio/python/ch-1.py b/challenge-007/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..2029cb3fcd
--- /dev/null
+++ b/challenge-007/paulo-custodio/python/ch-1.py
@@ -0,0 +1,19 @@
+#!/usr/bin/env python
+
+# Challenge 007
+# 
+# Challenge #1
+# Print all the niven numbers from 0 to 50 inclusive, each on their own line. 
+# A niven number is a non-negative number that is divisible by the sum of its digits.
+
+import sys
+
+def solve(max):
+	for n in range(1, max+1):
+		digits = [int(char) for char in str(n)]
+		sum_digits = sum(digits)
+		if n % sum_digits == 0:
+			print(n) 
+
+max = int(sys.argv[1]) if len(sys.argv)==2 else 50
+solve(max)
diff --git a/challenge-007/paulo-custodio/python/ch-2.py b/challenge-007/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..32b273080e
--- /dev/null
+++ b/challenge-007/paulo-custodio/python/ch-2.py
@@ -0,0 +1,108 @@
+#!/usr/bin/env python
+
+# Challenge 007
+# 
+# Challenge #2
+# Word Ladder
+# A word ladder is a sequence of words [w0, w1, ..., wn] such that each word wi
+# in the sequence is obtained by changing a single character in the word wi-1. 
+# All words in the ladder must be valid English words.
+# 
+# Given two input words and a file that contains an ordered word list, implement 
+# a routine (e.g., find_shortest_ladder(word1, word2, wordlist)) that finds the 
+# shortest ladder between the two input words. For example, for the words cold 
+# and warm, the routine might return:
+# 
+# ("cold", "cord", "core", "care", "card", "ward", "warm")
+# However, there's a shortest ladder: ("cold", "cord", "card", "ward", "warm").
+# 
+# Givens:
+# All words in the list have the same length.
+# 
+# All words contain only lowercase alphabetical characters.
+# 
+# There are no duplicates in the word list.
+# 
+# The input words aren't empty and aren't equal but they have the same length 
+# as any word in the word list.
+# 
+# Requirements:
+# The routine must return a list of the words in the ladder if it exists. 
+# Otherwise, it returns an empty list.
+# 
+# If any of the input words is the wrong length (i.e., its length is different 
+# to a random from the word list) or isn't in the word list, return an empty list.
+
+from __future__ import print_function
+import sys
+import re
+import collections
+from collections import deque 
+
+def eprint(*args, **kwargs):
+    print(*args, file=sys.stderr, **kwargs)
+
+def get_args():
+	if len(sys.argv) != 3:
+		eprint("Usage: ch-2.py word1 word2")
+		sys.exit(1)
+	word1, word2 = sys.argv[1:]
+	if len(word1) != len(word2):
+		eprint("words must have the same length")
+		sys.exit(1)
+	if word1 == word2:
+		eprint("words must be different")
+		sys.exit(1)
+	for word in word1, word2:
+		if not re.match(r"^[a-z]+$", word):
+			eprint("words must have lower case letters only")
+			sys.exit(1)
+	return word1, word2
+
+def read_words(filename, length):
+	wordlist = set()
+	with open(filename, 'r') as f:
+		for line in f.readlines():
+			word = line.strip()
+			if len(word) == length and re.match(r"^[a-z]+$", word):
+				wordlist.add(word)
+	return wordlist
+
+def find_shortest_ladder(word1, word2, wordlist):
+	queue = deque()
+	queue.append((word1, [word1]))		# node, path
+	while queue:
+		word, path = queue.popleft()
+		for next in sorted(next_possible_words(word, wordlist - set(path))):
+			if next == word2:			# found solution
+				return path + [next]
+			else:
+				queue.append((next, path + [next]))
+	return []
+	
+def next_possible_words(word1, wordlist):
+	next = set()
+	for word in wordlist:
+		if word != word1 and word_diff(word, word1) == 1:
+			next.add(word)
+	return next
+	
+def word_diff(word1, word2):
+	diff = 0
+	list1 = list(word1)
+	list2 = list(word2)
+	for i in range(0, len(list1)):
+		if list1[i] != list2[i]:
+			diff = diff+1
+	return diff
+
+def print_list(list):
+	output = "(";
+	for word in list:
+		output += '"' + word + '", '
+	output = output[:-2] + ")"
+	print(output)
+
+word1, word2 = get_args()
+wordlist = read_words("words.txt", len(word1))
+print_list(find_shortest_ladder(word1, word2, wordlist))
diff --git a/challenge-007/paulo-custodio/test.pl b/challenge-007/paulo-custodio/test.pl
new file mode 100644
index 0000000000..cc5355723d
--- /dev/null
+++ b/challenge-007/paulo-custodio/test.pl
@@ -0,0 +1,60 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use Test::More;
+use 5.030;
+
+# build list of words for testing
+ok 0==system("aspell -d en dump master | aspell -l en expand > words.txt");
+
+
+for ([50, <<END]) {
+1
+2
+3
+4
+5
+6
+7
+8
+9
+10
+12
+18
+20
+21
+24
+27
+30
+36
+40
+42
+45
+48
+50
+END
+	my($in, $out) = @$_;
+	
+	is capture(    "perl perl/ch-1.pl $in"), $out;
+	is capture("python python/ch-1.py $in"), $out;
+}
+
+
+for (["cold warm", <<END]) {
+("cold", "cord", "card", "ward", "warm")
+END
+	my($in, $out) = @$_;
+	
+	is capture(    "perl perl/ch-2.pl $in"), $out;
+	is capture("python python/ch-2.py $in"), $out;
+}
+
+done_testing;
+
+sub capture {
+	my($cmd) = @_;
+	my $out = `$cmd`;
+	$out =~ s/[ \t\v\f\r]*\n/\n/g;
+	return $out;
+}