4 files changed, 236 insertions, 0 deletions
diff --git a/challenge-022/paulo-custodio/README b/challenge-022/paulo-custodio/README
new file mode 100644
index 0000000000..87dc0b2fbd
--- /dev/null
+++ b/challenge-022/paulo-custodio/README
@@ -0,0 +1 @@
+Solution by Paulo Custodio
diff --git a/challenge-022/paulo-custodio/perl/ch-1.pl b/challenge-022/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..d3522e00b9
--- /dev/null
+++ b/challenge-022/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/env perl
+
+# Challenge 022
+#
+# Task #1
+# Write a script to print first 10 Sexy Prime Pairs. Sexy primes are prime 
+# numbers that differ from each other by 6. For example, the numbers 5 and 11 
+# are both sexy primes, because 11 - 5 = 6. The term “sexy prime” is a pun
+# stemming from the Latin word for six: sex. For more information, please 
+# checkout wiki page.
+
+use strict;
+use warnings;
+use 5.030;
+
+# check if number is prime
+sub is_prime {
+	my($n) = @_;
+
+    return 0 if $n <= 1;
+    return 1 if $n <= 3;
+    
+    return 0 if ($n % 2)==0 || ($n % 3)==0;
+    
+    for (my $i = 5; $i*$i <= $n; $i += 6) {
+		return 0 if ($n % $i)==0 || ($n % ($i+2))==0;
+	}
+    
+    return 1;
+}
+
+# next prime
+sub next_prime {
+	my($n) = @_;
+	
+	return 2 if $n <= 1;
+	my $p = $n;
+	1 while !is_prime(++$p);
+	return $p;
+}
+
+# sexy primes
+sub sexy_primes_iter {
+	my $a = 1;
+	return sub {
+		while (1) {
+			$a = next_prime($a);
+			my $b = $a;
+			$b = next_prime($b) while $b < $a+6;
+			return ($a, $b) if $b == $a+6;
+		}
+	};
+}
+
+my $iter = sexy_primes_iter();
+for (1..10) {
+	my($a, $b) = $iter->();
+	say "($a, $b)";
+}
diff --git a/challenge-022/paulo-custodio/perl/ch-2.pl b/challenge-022/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..731e5b71b7
--- /dev/null
+++ b/challenge-022/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl
+
+# Challenge 022
+# 
+# Task #2
+# Write a script to implement Lempel–Ziv–Welch (LZW) compression algorithm. 
+# The script should have method to encode/decode algorithm. The wiki page 
+# explains the compression algorithm very nicely.
+
+use strict;
+use warnings;
+use 5.030;
+
+{ 
+	package Dict;
+	use constant EOM => "#";
+	use constant SYMBOLS => 'A'..'Z';
+	use Object::Tiny::RW qw( dict symbols );
+	
+	sub new {
+		my($class) = @_;
+		my $self = bless { dict => {}, symbols => [] }, $class;
+		for (EOM, SYMBOLS) {
+			$self->add($_);
+		}
+		return $self;
+	}
+	
+	sub last {
+		my($self) = @_;
+		return scalar(@{$self->symbols}) - 1;
+	}
+	
+	sub width {
+		my($self) = @_;
+		return length(sprintf("%b", $self->last));
+	}
+	
+	sub next_width {
+		my($self) = @_;
+		return length(sprintf("%b", $self->last+1));
+	}
+	
+	sub add {
+		my($self, $seq) = @_;
+		my $last = $self->last + 1;
+		$self->dict->{$seq} = $last;
+		$self->symbols->[$last] = $seq;
+	}
+		
+	sub longest_match {
+		my($self, $text) = @_;
+		
+		# find longest match
+		my $len = 0;
+		$len++ while $len < length($text) 
+				  && exists $self->dict->{substr($text, 0, $len+1)};
+		my $w = substr($text, 0, $len);
+		$text = substr($text, $len);
+		my $code = $self->dict->{$w};
+		my $old_width = $self->width;
+		
+		# store new prefix in the dictionary
+		if ($text ne '') {
+			my $next_prefix = $w.substr($text, 0, 1);
+			$self->add($next_prefix);
+		}
+		
+		# return code and new text
+		return (sprintf("%0*b", $old_width, $code), $text);
+	}
+}
+
+sub encode {
+	my($text) = @_;
+	$text .= Dict->EOM;
+	my $encoded = "";
+	my $dict = Dict->new();
+	
+	while ($text ne '') {
+		(my $code, $text) = $dict->longest_match($text);
+		$encoded .= $code;
+	}
+
+	return $encoded;
+}
+
+sub decode {
+	my($encoded) = @_;
+	my $text = "";
+	my $dict = Dict->new();
+
+	while ($encoded ne '') {
+		my $code = eval("0b".substr($encoded, 0, $dict->width));
+		$encoded = substr($encoded, $dict->width);
+		my $seq = $dict->symbols->[$code];
+		$text .= $seq;
+		if ($encoded ne '') {
+			my $next_width = $dict->next_width;
+			my $next_code = eval("0b".substr($encoded, 0, $next_width));
+			my $next_seq = $dict->symbols->[$next_code];
+			$dict->add($seq.substr($next_seq, 0, 1));
+		}
+		
+	}
+	
+	# remove end terminator
+	$text = substr($text, 0, length($text)-1);
+
+	return $text;
+}
+
+
+# main
+my($op, $arg) = @ARGV;
+if ($op =~ /^enc/i) {
+	say encode($arg);
+}
+elsif ($op =~ /^dec/i) {
+	say decode($arg);
+}
+else {
+	die "Usage: ch-2.pl encode|decode text\n";
+}
diff --git a/challenge-022/paulo-custodio/test.pl b/challenge-022/paulo-custodio/test.pl
new file mode 100644
index 0000000000..b184a05b8b
--- /dev/null
+++ b/challenge-022/paulo-custodio/test.pl
@@ -0,0 +1,52 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use 5.030;
+use Test::More;
+
+is capture("perl perl/ch-1.pl"), <<END;
+(5, 11)
+(7, 13)
+(11, 17)
+(13, 19)
+(17, 23)
+(23, 29)
+(31, 37)
+(37, 43)
+(41, 47)
+(47, 53)
+END
+
+my($text, $encoded) = ("TOBEORNOTTOBEORTOBEORNOT", join("", qw(
+					  10100	
+					  01111	
+					  00010	
+					  00101	
+					  01111	
+					  10010	
+					  001110	
+					  001111	
+					  010100	
+					  011011	
+					  011101	
+					  011111	
+					  100100	
+					  011110	
+					  100000	
+					  100010	
+					  000000	
+					  )));
+
+is capture("perl perl/ch-2.pl encode $text"), "$encoded\n", "$text -> $encoded";
+is capture("perl perl/ch-2.pl decode $encoded"), "$text\n", "$encoded -> $text";
+
+done_testing;
+
+
+sub capture {
+	my($cmd) = @_;
+	my $out = `$cmd`;
+	$out =~ s/[ \t\v\f\r]*\n/\n/g;
+	return $out;
+}