From 3ac4799328b78382bd071404cb508535c1118b9d Mon Sep 17 00:00:00 2001 From: "Gustavo L. de M. Chaves" Date: Wed, 8 May 2019 22:28:40 -0300 Subject: Add Gustavo Chaves's solutions to challenge 007 --- challenge-007/gustavo-chaves/perl5/ch-1.pl | 14 +++++ challenge-007/gustavo-chaves/perl5/ch-2.pl | 86 ++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+) create mode 100755 challenge-007/gustavo-chaves/perl5/ch-1.pl create mode 100755 challenge-007/gustavo-chaves/perl5/ch-2.pl diff --git a/challenge-007/gustavo-chaves/perl5/ch-1.pl b/challenge-007/gustavo-chaves/perl5/ch-1.pl new file mode 100755 index 0000000000..d54ace4779 --- /dev/null +++ b/challenge-007/gustavo-chaves/perl5/ch-1.pl @@ -0,0 +1,14 @@ +#!/usr/bin/env perl + +# 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 5.026; +use strict; +use warnings; +use List::Util 'sum'; + +for (1 .. 50) { + say unless $_ % sum split //; +} diff --git a/challenge-007/gustavo-chaves/perl5/ch-2.pl b/challenge-007/gustavo-chaves/perl5/ch-2.pl new file mode 100755 index 0000000000..ddb900251f --- /dev/null +++ b/challenge-007/gustavo-chaves/perl5/ch-2.pl @@ -0,0 +1,86 @@ +#!/usr/bin/env perl + +# 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. + +use 5.026; +use strict; +use autodie; +use warnings; +use List::Util qw(reduce uniq); +use Path::Tiny; + +# Implements Dijkstra's Algorith as described in +# https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode + +sub first_shortest_ladder { + my ($source, $target, $wordlist) = @_; + + # Build an adjacency graph from $wordlist + + my (%graph, %dist, %prev); + + my $length = length $source; + for my $i (0 .. @$wordlist-2) { + my $word_i = $wordlist->[$i]; + foreach my $word_j (@{$wordlist}[$i+1 .. @$wordlist-1]) { + my $distance = 0; + for (my $k = $length; $k >= 0; --$k) { + $distance += 1 if substr($word_i, $k, 1) ne substr($word_j, $k, 1); + } + if ($distance == 1) { + $graph{$word_i}{$word_j} = undef; + $graph{$word_j}{$word_i} = undef; + } + } + $dist{$word_i} = @$wordlist + 1; # infinity + $prev{$word_i} = undef; + } + + $dist{$source} = 0; + + while (%graph) { + my $u = reduce {$dist{$a} < $dist{$b} ? $a : $b} keys %graph; + + my $neighbors = delete $graph{$u}; + + last if $u eq $target; # found a shortest path to $target + + foreach my $v (grep {exists $graph{$_}} keys %$neighbors) { + my $alt = $dist{$u} + 1; + if ($alt < $dist{$v}) { + $dist{$v} = $alt; + $prev{$v} = $u; + } + } + } + + # Return an empty list if no path was found to $target + return if exists $graph{$target}; + + my @path = ($target); + + for (my $u = $target; $prev{$u}; $u = $prev{$u}) { + unshift @path, $prev{$u}; + } + + return @path; +} + +@ARGV == 2 or die "Usage: $0 FROM TO\n"; + +my ($source, $target) = map {lc} @ARGV; + +my $length = length $source; + +my @words = + uniq + sort + map {lc} + grep {length == $length} + path('/usr/share/dict/words')->lines({chomp => 1}); + +my @ladder = first_shortest_ladder($source, $target, \@words); + +say join "\n", @ladder; -- cgit From 0c04fc8ce603860f5faceb1764f5b379b93697ce Mon Sep 17 00:00:00 2001 From: "Gustavo L. de M. Chaves" Date: Wed, 8 May 2019 22:34:00 -0300 Subject: Optimize a hash into an array --- challenge-007/gustavo-chaves/perl5/ch-2.pl | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/challenge-007/gustavo-chaves/perl5/ch-2.pl b/challenge-007/gustavo-chaves/perl5/ch-2.pl index ddb900251f..5ced16a2d6 100755 --- a/challenge-007/gustavo-chaves/perl5/ch-2.pl +++ b/challenge-007/gustavo-chaves/perl5/ch-2.pl @@ -30,8 +30,8 @@ sub first_shortest_ladder { $distance += 1 if substr($word_i, $k, 1) ne substr($word_j, $k, 1); } if ($distance == 1) { - $graph{$word_i}{$word_j} = undef; - $graph{$word_j}{$word_i} = undef; + push @{$graph{$word_i}}, $word_j; + push @{$graph{$word_j}}, $word_i; } } $dist{$word_i} = @$wordlist + 1; # infinity @@ -47,7 +47,7 @@ sub first_shortest_ladder { last if $u eq $target; # found a shortest path to $target - foreach my $v (grep {exists $graph{$_}} keys %$neighbors) { + foreach my $v (grep {exists $graph{$_}} @$neighbors) { my $alt = $dist{$u} + 1; if ($alt < $dist{$v}) { $dist{$v} = $alt; -- cgit From 0aae50e6dc686fad8e6d51097768f97cf60638f0 Mon Sep 17 00:00:00 2001 From: "Gustavo L. de M. Chaves" Date: Wed, 8 May 2019 22:37:04 -0300 Subject: Optimize the calculation of a constant --- challenge-007/gustavo-chaves/perl5/ch-2.pl | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/challenge-007/gustavo-chaves/perl5/ch-2.pl b/challenge-007/gustavo-chaves/perl5/ch-2.pl index 5ced16a2d6..e9d757481a 100755 --- a/challenge-007/gustavo-chaves/perl5/ch-2.pl +++ b/challenge-007/gustavo-chaves/perl5/ch-2.pl @@ -21,7 +21,9 @@ sub first_shortest_ladder { my (%graph, %dist, %prev); - my $length = length $source; + my $length = length $source; + my $infinity = @$wordlist + 1; + for my $i (0 .. @$wordlist-2) { my $word_i = $wordlist->[$i]; foreach my $word_j (@{$wordlist}[$i+1 .. @$wordlist-1]) { @@ -34,7 +36,7 @@ sub first_shortest_ladder { push @{$graph{$word_j}}, $word_i; } } - $dist{$word_i} = @$wordlist + 1; # infinity + $dist{$word_i} = $infinity; $prev{$word_i} = undef; } -- cgit