From 9b5f294fd7feb46c546f0fa2b51ff4d12eb8ffe5 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Tue, 30 Nov 2021 11:22:40 +0000 Subject: Add Python solution to challenge 22 --- challenge-022/paulo-custodio/Makefile | 2 + challenge-022/paulo-custodio/perl/ch-1.pl | 2 +- challenge-022/paulo-custodio/perl/ch-2.pl | 2 +- challenge-022/paulo-custodio/python/ch-1.py | 39 +++++++++++ challenge-022/paulo-custodio/python/ch-2.py | 100 ++++++++++++++++++++++++++++ challenge-022/paulo-custodio/t/test-1.yaml | 15 +++++ challenge-022/paulo-custodio/t/test-2.yaml | 10 +++ challenge-022/paulo-custodio/test.pl | 50 -------------- 8 files changed, 168 insertions(+), 52 deletions(-) create mode 100644 challenge-022/paulo-custodio/Makefile create mode 100644 challenge-022/paulo-custodio/python/ch-1.py create mode 100644 challenge-022/paulo-custodio/python/ch-2.py create mode 100644 challenge-022/paulo-custodio/t/test-1.yaml create mode 100644 challenge-022/paulo-custodio/t/test-2.yaml delete mode 100644 challenge-022/paulo-custodio/test.pl diff --git a/challenge-022/paulo-custodio/Makefile b/challenge-022/paulo-custodio/Makefile new file mode 100644 index 0000000000..c3c762d746 --- /dev/null +++ b/challenge-022/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-022/paulo-custodio/perl/ch-1.pl b/challenge-022/paulo-custodio/perl/ch-1.pl index 68e05cd91b..34225c0078 100644 --- a/challenge-022/paulo-custodio/perl/ch-1.pl +++ b/challenge-022/paulo-custodio/perl/ch-1.pl @@ -5,7 +5,7 @@ # 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 +# 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. diff --git a/challenge-022/paulo-custodio/perl/ch-2.pl b/challenge-022/paulo-custodio/perl/ch-2.pl index 878d0162b9..27fd92c867 100644 --- a/challenge-022/paulo-custodio/perl/ch-2.pl +++ b/challenge-022/paulo-custodio/perl/ch-2.pl @@ -3,7 +3,7 @@ # Challenge 022 # # Task #2 -# Write a script to implement Lempel–Ziv–Welch (LZW) compression algorithm. +# 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. diff --git a/challenge-022/paulo-custodio/python/ch-1.py b/challenge-022/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..346c160fb4 --- /dev/null +++ b/challenge-022/paulo-custodio/python/ch-1.py @@ -0,0 +1,39 @@ +#!/usr/bin/python3 + +# 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. + +import sys +from primePy import primes + +def next_prime(n): + if n <= 1: + return 2 + else: + n += 1 + while not primes.check(n): + n += 1 + return n + +def sexy_primes_iter(): + a = 1 + while True: + a = next_prime(a) + b = a + while b < a+6: + b = next_prime(b) + if b == a+6: + yield (a, b) + +count = 0 +for a, b in sexy_primes_iter(): + print(f"({a}, {b})") + count += 1 + if count >= 10: + break diff --git a/challenge-022/paulo-custodio/python/ch-2.py b/challenge-022/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..8900cf37cd --- /dev/null +++ b/challenge-022/paulo-custodio/python/ch-2.py @@ -0,0 +1,100 @@ +#!/usr/bin/python3 + +# 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. + +import sys + +class Dict(): + EOM = '#' + SYMBOLS = ['A','B','C','D','E','F','G','H','I','J','K','L','M', + 'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'] + + def __init__(self): + self.dict = {} + self.symbols = [] + for sym in [Dict.EOM, *Dict.SYMBOLS]: + self.add(sym) + + def __str__(self): + return "dict="+str(self.dict)+",symbols="+str(self.symbols) + + def last(self): + return len(self.symbols)-1 + + def width(self): + return len("{:b}".format(self.last())) + + def next_width(self): + return len("{:b}".format(self.last()+1)) + + def add(self, seq): + seq = seq.upper() + + id = self.last()+1 + self.dict[seq] = id + self.symbols.append(seq) + + def longest_match(self, text): + text = text.upper() + + # find longest match + match_len = 0 + while match_len < len(text) and \ + text[:match_len+1] in self.dict: + match_len += 1 + w = text[:match_len] + text = text[match_len:] + code = self.dict[w] + old_width = self.width() + + # store new prefix in the dictionary + if text != "": + next_prefix = w+text[0] + self.add(next_prefix) + + # return code and new text + return ("{:0"+str(old_width)+"b}").format(code), text + +def encode(text): + text = text.upper()+Dict.EOM + encoded = "" + dict = Dict() + + while text != "": + code, text = dict.longest_match(text) + encoded += code + + return encoded + +def decode(encoded): + text = "" + dict = Dict() + + while encoded != "": + width = dict.width() + code = int(encoded[:width], 2) + encoded = encoded[width:] + seq = dict.symbols[code] + text += seq + + if encoded != "": + next_width = dict.next_width() + next_code = int(encoded[:next_width], 2) + next_seq = dict.symbols[next_code] + dict.add(seq + next_seq[0]) + + # remove end terminator + text = text[:-1] + return text + +if sys.argv[1] == "encode": + print(encode(sys.argv[2])) +elif sys.argv[1] == "decode": + print(decode(sys.argv[2])) +else: + print("Usage: ch-2.py encode|decode text") diff --git a/challenge-022/paulo-custodio/t/test-1.yaml b/challenge-022/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..f5b7fc6388 --- /dev/null +++ b/challenge-022/paulo-custodio/t/test-1.yaml @@ -0,0 +1,15 @@ +- setup: + cleanup: + args: + input: + output: | + (5, 11) + (7, 13) + (11, 17) + (13, 19) + (17, 23) + (23, 29) + (31, 37) + (37, 43) + (41, 47) + (47, 53) diff --git a/challenge-022/paulo-custodio/t/test-2.yaml b/challenge-022/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..06a3467c73 --- /dev/null +++ b/challenge-022/paulo-custodio/t/test-2.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: encode TOBEORNOTTOBEORTOBEORNOT + input: + output: 101000111100010001010111110010001110001111010100011011011101011111100100011110100000100010000000 +- setup: + cleanup: + args: decode 101000111100010001010111110010001110001111010100011011011101011111100100011110100000100010000000 + input: + output: TOBEORNOTTOBEORTOBEORNOT diff --git a/challenge-022/paulo-custodio/test.pl b/challenge-022/paulo-custodio/test.pl deleted file mode 100644 index 4fb163a066..0000000000 --- a/challenge-022/paulo-custodio/test.pl +++ /dev/null @@ -1,50 +0,0 @@ -#!/usr/bin/perl - -use Modern::Perl; -use Test::More; - -is capture("perl perl/ch-1.pl"), < $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; -} -- cgit