diff options
Diffstat (limited to 'challenge-018')
| -rw-r--r-- | challenge-018/duane-powell/perl5/ch-1.pl | 123 | ||||
| -rw-r--r-- | challenge-018/duane-powell/perl5/ch-2.pl | 203 |
2 files changed, 326 insertions, 0 deletions
diff --git a/challenge-018/duane-powell/perl5/ch-1.pl b/challenge-018/duane-powell/perl5/ch-1.pl new file mode 100644 index 0000000000..ed4443dd1b --- /dev/null +++ b/challenge-018/duane-powell/perl5/ch-1.pl @@ -0,0 +1,123 @@ +#!/usr/bin/perl +use Modern::Perl; + +# Write a script that takes 2 or more strings as command line parameters and print the longest common substring. +# For example, the longest common substring of the strings “ABABC”, “BABCA” and “ABCBA” is string “ABC” of length 3. +# Other common substrings are “A”, “AB”, “B”, “BA”, “BC” and “C” + +sub common_substr_find { + my @str = @_; + # The plan is to chunk our strings from largest to smallest + # for example: hello,hell,ello,hel,ell,llo,he,el,ll,lo,h,e,l,l,o + # Then use the chunks as hash keys to count occurances. + # We stop looking at smaller chunks if a bigger match is found. + + my $out = ""; + my %count; + my %chunk; + my $longest_match = 0; + foreach my $str (@str) { + my $i = 0; + my $len = length($str); + my $offset = $len; + while ($offset > 0) { + while (($i + $offset) <= $len and ($i + $offset) >= $longest_match) { + my $chunk = substr($str,$i,$offset); + unless (defined $chunk{$str}{$chunk}) { + # don't match chunks within the same str + $chunk{$str}{$chunk} = 1; + $count{$chunk}++; + } + $longest_match = length($chunk) if ($count{$chunk} > 1 and length($chunk) > $longest_match); + $i++; + } + $i = 0; + $offset--; + } + } + + foreach (keys %count) { + if ($count{$_} > 1) { + $out .= "$_\n" if (length($_) == $longest_match); + } + } + + say "strings are: " . join(",",@str); + if ($out) { + $out = "longest matching substrings are:\n" . $out; + } else { + $out = "no substrings match\n"; + } + say $out; +} + +if (@ARGV) { + common_substr_find(@ARGV); + exit; +} + +my %testdata = ( + 1 => "hello world", + 2 => "polar bears love snow", + 3 => "goodbye goodyear goody", + 4 => "abc xzy", + 5 => "duane powell xxxxduanexxxpowellxxx", + 6 => "abba bbaa aaaa bbbb baba abab", + 7 => "ALL ENGLISH WORDS ... words.txt", +); + +foreach my $data (sort(keys %testdata)) { + my @str; + if ($data < 7) { + @str = split(" ",$testdata{$data}); + common_substr_find(@str); + } else { + open(my $fh, "<", "words.txt") or die "Can't open < words.txt: $!"; + while (my $word = <$fh>) { + chomp $word; + push @str, $word; + } + common_substr_find(@str); + } +} + +__END__ + +./ch1.pl foo bar fubar +strings are: foo,bar,fubar +longest matching substrings are: +bar + +./ch1.pl +strings are: hello,world +longest matching substrings are: +o +l + +strings are: polar,bears,love,snow +longest matching substrings are: +ar + +strings are: goodbye,goodyear,goody +longest matching substrings are: +goody + +strings are: abc,xzy +no substrings match + +strings are: duane,powell,xxxxduanexxxpowellxxx +longest matching substrings are: +powell + +strings are: abba,bbaa,aaaa,bbbb,baba,abab +longest matching substrings are: +bba +aba +bab + +strings are: ... ALL ENGLISH WORDS ... +longest matching substrings are: +electroencephalographical +antidisestablishmentarian +microspectrophotometrical + diff --git a/challenge-018/duane-powell/perl5/ch-2.pl b/challenge-018/duane-powell/perl5/ch-2.pl new file mode 100644 index 0000000000..9eb7d0cf3f --- /dev/null +++ b/challenge-018/duane-powell/perl5/ch-2.pl @@ -0,0 +1,203 @@ +#!/usr/bin/perl +use Modern::Perl; + +# Write a script to implement Priority Queue. It is like regular queue except each element has a priority associated with it. +# In a priority queue, an element with high priority is served before an element with low priority. + +my $p = PriorityQueue->new(); +$p->pull_highest_priority_element(); +$p->insert_with_priority(200,"milkshake!"); +$p->insert_with_priority(300,"pizza?"); +$p->insert_with_priority(500,"cheeseburgers!"); +sleep 1; # sleep a second so nodes have different date values +$p->insert_with_priority(250,"steak and eggs!"); +$p->queue_print(); +$p->pull_highest_priority_element(); +$p->insert_with_priority(350,"hotdogs?"); +$p->insert_with_priority(550,"pancakces and syrup!"); +$p->insert_with_priority(650,"donuts!"); +$p->insert_with_priority(600,"cookies!"); +$p->queue_print(); +$p->pull_highest_priority_element(); +$p->queue_print(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +sleep 1; # sleep a second so nodes have different date values +$p->insert_with_priority(200,"dr peppers!"); +$p->insert_with_priority(300,"pizza?"); +$p->insert_with_priority(500,"cheeseburgers!"); +$p->insert_with_priority(250,"steak and eggs!"); +$p->insert_with_priority(350,"hotdogs?"); +$p->insert_with_priority(550,"pancakces and syrup!"); +$p->queue_print(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->queue_print(); +sleep 1; # sleep a second so nodes have different date values +$p->insert_with_priority(350,"hotdogs?"); +$p->insert_with_priority(550,"pancakces and syrup!"); +$p->queue_print(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->pull_highest_priority_element(); +$p->queue_print(); +exit; + +package PriorityQueue; +sub new { + my $class = shift; + # Simple class to represent a priority queue. + # The queue is made of nested hash refs, linked by _next + # _next=>{ ..., _next=>{ ..., _next=>undef}} + my $self = { + _next => undef, # undef signals empty queue + }; + return bless $self, $class; +} + +sub is_empty { + my $self = shift; + return not defined $self->{_next}; +} + +sub insert_with_priority { + my $self = shift; + + # init new node + my $priority = shift; + my $data = shift; + my $i = { + priority => $priority || 100, + data => $data, + date => time, + _next => undef, # undef signals end of queue + }; + + # empty queue, insert first node and return + if ($self->is_empty()) { + $self->{_next} = $i; + return; + } + + # iterate over queue nodes and insert $i where it belongs + my $here = $self; + my $n = $self->{_next}; + while ($n) { + if ($n->{priority} >= $i->{priority}) { + if (defined $n->{_next}) { + # iterate + $here = $n; + $n = $n->{_next}; + } else { + # we're at the end of queue + $n->{_next} = $i; + return; + } + } else { + # insert $i here + $i->{_next} = $here->{_next}; + $here->{_next} = $i; + return; + } + } +} + +sub pull_highest_priority_element { + my $self = shift; + if ($self->is_empty()) { + say "nothing to pop, queue is empty."; + return; + } else { + my $n = $self->{_next}; + $self->{_next} = $n->{_next}; + say "popping $n->{priority} $n->{date} $n->{data}"; + return $n; + } +} + +sub queue_print { + my $self = shift; + my $n = $self->{_next}; + my $depth = 0; + say "queue print:"; + while ($n) { + my $space = (' ' x $depth); + say "$space $n->{priority} $n->{date} $n->{data}"; + $n = $n->{_next}; + $depth++; + } +} + + +1; + +__END__ + +./ch2.pl +nothing to pop, queue is empty. +queue print: + 500 1563884736 cheeseburgers! + 300 1563884736 pizza? + 250 1563884737 steak and eggs! + 200 1563884736 milkshake! +popping 500 1563884736 cheeseburgers! +queue print: + 650 1563884737 donuts! + 600 1563884737 cookies! + 550 1563884737 pancakces and syrup! + 350 1563884737 hotdogs? + 300 1563884736 pizza? + 250 1563884737 steak and eggs! + 200 1563884736 milkshake! +popping 650 1563884737 donuts! +queue print: + 600 1563884737 cookies! + 550 1563884737 pancakces and syrup! + 350 1563884737 hotdogs? + 300 1563884736 pizza? + 250 1563884737 steak and eggs! + 200 1563884736 milkshake! +popping 600 1563884737 cookies! +popping 550 1563884737 pancakces and syrup! +queue print: + 550 1563884738 pancakces and syrup! + 500 1563884738 cheeseburgers! + 350 1563884737 hotdogs? + 350 1563884738 hotdogs? + 300 1563884736 pizza? + 300 1563884738 pizza? + 250 1563884737 steak and eggs! + 250 1563884738 steak and eggs! + 200 1563884736 milkshake! + 200 1563884738 dr peppers! +popping 550 1563884738 pancakces and syrup! +popping 500 1563884738 cheeseburgers! +popping 350 1563884737 hotdogs? +popping 350 1563884738 hotdogs? +popping 300 1563884736 pizza? +popping 300 1563884738 pizza? +popping 250 1563884737 steak and eggs! +popping 250 1563884738 steak and eggs! +queue print: + 200 1563884736 milkshake! + 200 1563884738 dr peppers! +queue print: + 550 1563884739 pancakces and syrup! + 350 1563884739 hotdogs? + 200 1563884736 milkshake! + 200 1563884738 dr peppers! +popping 550 1563884739 pancakces and syrup! +popping 350 1563884739 hotdogs? +popping 200 1563884736 milkshake! +popping 200 1563884738 dr peppers! +nothing to pop, queue is empty. +queue print: + |