diff options
| -rw-r--r-- | challenge-018/paulo-custodio/Makefile | 2 | ||||
| -rw-r--r-- | challenge-018/paulo-custodio/python/ch-1.py | 39 | ||||
| -rw-r--r-- | challenge-018/paulo-custodio/python/ch-2.py | 115 | ||||
| -rw-r--r-- | challenge-018/paulo-custodio/t/test-1.yaml | 10 | ||||
| -rw-r--r-- | challenge-018/paulo-custodio/t/test-2.yaml | 24 | ||||
| -rw-r--r-- | challenge-018/paulo-custodio/test.pl | 23 |
6 files changed, 190 insertions, 23 deletions
diff --git a/challenge-018/paulo-custodio/Makefile b/challenge-018/paulo-custodio/Makefile new file mode 100644 index 0000000000..c3c762d746 --- /dev/null +++ b/challenge-018/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-018/paulo-custodio/python/ch-1.py b/challenge-018/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..2227f647ee --- /dev/null +++ b/challenge-018/paulo-custodio/python/ch-1.py @@ -0,0 +1,39 @@ +#!/usr/bin/python3 + +# Challenge 018 +# +# Task #1 +# 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". Please check +# this wiki page for details. + +import sys +import re + +def longest_substr(strs): + def matches_all(substr, strs): + for s in strs: + if not re.search(substr, s): + return False + return True + + longest_len = -1 + longest = set() + + for s in strs: + for start in range(0, len(s)): + for end in range(start+1, len(s)+1): + if end-start >= longest_len: + substr = s[start:end] + if substr not in longest: + if matches_all(substr, strs): + if end-start == longest_len: + longest.add(substr) + else: + longest = set([substr]) + longest_len = end-start + return sorted(list(longest)) + +print("("+", ".join(['"'+x+'"' for x in longest_substr(sys.argv[1:])])+")") diff --git a/challenge-018/paulo-custodio/python/ch-2.py b/challenge-018/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..fa8adf18c9 --- /dev/null +++ b/challenge-018/paulo-custodio/python/ch-2.py @@ -0,0 +1,115 @@ +#!/usr/bin/python3 + +# Challenge 018 +# +# Task #2 +# 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. +# Please check this wiki page for more informations. It should serve the +# following operations: +# +# is_empty: check whether the queue has no elements. +# insert_with_priority: add an element to the queue with an associated priority. +# pull_highest_priority_element: remove the element from the queue that has the +# highest priority, and return it. If two elements have the same priority, +# then return element added first. + +# priority queue +class PQueue(): + def __init__(self): + self.q = [] + + def is_empty(self): + return len(self.q)==0 + + def insert(self, pri, elem): + if self.is_empty(): + self.q.append([pri, [elem]]) + elif pri < self.q[0][0]: + self.q.insert(0, [pri, [elem]]) + elif pri > self.q[-1][0]: + self.q.append([pri, [elem]]) + else: + for i in range(0, len(self.q)): + if self.q[i][0] == pri: + self.q[i][1].append(elem) + return + elif self.q[i][0] > pri: + self.q.insert(i, [pri, [elem]]) + return + + def pull(self): + if self.is_empty(): + return None + else: + elem = self.q[-1][1].pop(0) + if len(self.q[-1][1]) == 0: + self.q.pop(-1) + return elem + +# tests +test_num = 0 + +def ok(f, title): + global test_num + test_num += 1 + if f: + print(f"ok {test_num} - {title}") + else: + print(f"nok {test_num} - {title}") + +def eq(a, b, title): + ok(a==b, title) + if a!=b: + print("#", a, "!=", b) + +def done_testing(): + print(f"1..{test_num}") + + +# run tests +q = PQueue() + +ok(q.is_empty(), "is empty") +ok(q.pull() is None, "pull from empty queue") + +# insert same priority +q.insert(1, 123) +ok(not q.is_empty(), "is not empty") + +q.insert(1, 456) +ok(not q.is_empty(), "is not empty") + +q.insert(1, 789) +ok(not q.is_empty(), "is not empty") + +# pull +eq(q.pull(), 123, "got element") +ok(not q.is_empty(), "is not empty") + +eq(q.pull(), 456, "got element") +ok(not q.is_empty(), "is not empty") + +eq(q.pull(), 789, "got element") +ok(q.is_empty(), "is empty") + +# insert higher priority +q.insert(1, 123) +q.insert(1, 456) +q.insert(2, 23) +q.insert(3, 4) + +# insert lower priority +q.insert(0, 999) +q.insert(0, 998) + +eq(q.pull(), 4, "got element") +eq(q.pull(), 23, "got element") +eq(q.pull(), 123, "got element") +eq(q.pull(), 456, "got element") +eq(q.pull(), 999, "got element") +eq(q.pull(), 998, "got element") +ok(q.is_empty(), "is empty") + +done_testing() diff --git a/challenge-018/paulo-custodio/t/test-1.yaml b/challenge-018/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..041df7a1ad --- /dev/null +++ b/challenge-018/paulo-custodio/t/test-1.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: ABABC BABCA ABCBA + input: + output: ("ABC") +- setup: + cleanup: + args: ABABCBA BABCACBA ABCBCBA + input: + output: ("ABC", "CBA") diff --git a/challenge-018/paulo-custodio/t/test-2.yaml b/challenge-018/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..e99c9f130a --- /dev/null +++ b/challenge-018/paulo-custodio/t/test-2.yaml @@ -0,0 +1,24 @@ +- setup: + cleanup: + args: + input: + output: | + ok 1 - is empty + ok 2 - pull from empty queue + ok 3 - is not empty + ok 4 - is not empty + ok 5 - is not empty + ok 6 - got element + ok 7 - is not empty + ok 8 - got element + ok 9 - is not empty + ok 10 - got element + ok 11 - is empty + ok 12 - got element + ok 13 - got element + ok 14 - got element + ok 15 - got element + ok 16 - got element + ok 17 - got element + ok 18 - is empty + 1..18 diff --git a/challenge-018/paulo-custodio/test.pl b/challenge-018/paulo-custodio/test.pl deleted file mode 100644 index a60d3559d3..0000000000 --- a/challenge-018/paulo-custodio/test.pl +++ /dev/null @@ -1,23 +0,0 @@ -#!/usr/bin/perl - -use Modern::Perl; -use Test::More; - -is capture("perl perl/ch-1.pl ABABC BABCA ABCBA"), <<END; -("ABC") -END - -is capture("perl perl/ch-1.pl ABABCBA BABCACBA ABCBCBA"), <<END; -("ABC", "CBA") -END - -ok 0==system("perl perl/ch-2.pl"); - -done_testing; - -sub capture { - my($cmd) = @_; - my $out = `$cmd`; - $out =~ s/[ \t\v\f\r]*\n/\n/g; - return $out; -} |