diff options
author | Vincent Ambo <mail@tazj.in> | 2021-12-13T22·51+0300 |
---|---|---|
committer | Vincent Ambo <mail@tazj.in> | 2021-12-13T23·15+0300 |
commit | 019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch) | |
tree | 76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py | |
parent | 464bbcb15c09813172c79820bcf526bb10cf4208 (diff) | |
parent | 6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff) |
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208 git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py')
-rw-r--r-- | users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py new file mode 100644 index 000000000000..5df12ebabdc7 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py @@ -0,0 +1,181 @@ +from collections import deque +import unittest + +################################################################################ +# Solution +################################################################################ + + +def rev(xs, i, j): + """Reverse xs in place from [i, j]""" + while i < j: + xs[i], xs[j] = xs[j], xs[i] + i += 1 + j -= 1 + + +def rotate(xs, n, i=None, j=None): + """Mutably rotates list, xs, n times. Positive n values rotate right while + negative n values rotate left. Rotate within window [i, j].""" + i = i or 0 + j = j or len(xs) - 1 + ct = j - i + + if n < 0: + n = abs(n) + p = i + n - 1 + rev(xs, i, p) + rev(xs, p + 1, j) + rev(xs, i, j) + else: + p = j - (n - 1) + rev(xs, p, j) + rev(xs, i, p - 1) + rev(xs, i, j) + return xs + + +def rev_words(xs, i, j): + if j + 1 == len(xs): + return 0 + + while j + 1 < len(xs): + while j + 1 < len(xs) and xs[j + 1] != ' ': + j += 1 + + rev(xs, i, j) + j += 2 + i = j + + return 0 + + +def reverse_words(xs): + # first reverse everything + rev(xs, 0, len(xs) - 1) + return rev_words(xs, 0, 0) + + +def reverse_words_bak(xs, i=None, j=None): + i = i or 0 + j = j or len(xs) - 1 + w0, w1 = [], [] + + if i >= j: + return 0 + + pi = i + while pi < len(xs) and xs[pi] != ' ': + w0.append(xs[pi]) + pi += 1 + + if pi == len(xs): + return 0 + + pj = j + while xs[pj] != ' ': + w1.append(xs[pj]) + pj -= 1 + + d = len(w0) - len(w1) + + rotate(xs, -1 * d, i, j) + + for k in range(len(w1)): + xs[i + k] = w1[len(w1) - 1 - k] + + for k in range(len(w0)): + xs[j - k] = w0[len(w0) - 1 - k] + + while i != j and xs[i] != ' ' and xs[j] != ' ': + i += 1 + j -= 1 + + if i == j: + return 0 + + elif xs[i] == ' ': + while j > 0 and xs[j] != ' ': + j -= 1 + if j == 0: + return 0 + elif xs[j] == ' ': + while i < len(xs) and xs[i] != ' ': + i += 1 + if i == len(xs): + return 0 + return reverse_words(xs, i + 1, j - 1) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_rev(self): + xs = [1, 2, 3, 4, 5] + rev(xs, 0, len(xs) - 1) + self.assertEqual(xs, [5, 4, 3, 2, 1]) + + def test_rotate(self): + ys = [1, 2, 3, 4, 5] + xs = ys[:] + self.assertEqual(rotate(xs, 1, 1, 3), [1, 4, 2, 3, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, -1, 1, 3), [1, 3, 4, 2, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 1), [5, 1, 2, 3, 4]) + xs = ys[:] + self.assertEqual(rotate(xs, -1), [2, 3, 4, 5, 1]) + xs = ys[:] + self.assertEqual(rotate(xs, -2), [3, 4, 5, 1, 2]) + xs = ys[:] + self.assertEqual(rotate(xs, -5), [1, 2, 3, 4, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 5), [1, 2, 3, 4, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 3), [3, 4, 5, 1, 2]) + + def test_one_word(self): + message = list('vault') + reverse_words(message) + expected = list('vault') + self.assertEqual(message, expected) + + def test_two_words(self): + message = list('thief cake') + reverse_words(message) + expected = list('cake thief') + self.assertEqual(message, expected) + + def test_three_words(self): + message = list('one another get') + reverse_words(message) + expected = list('get another one') + self.assertEqual(message, expected) + + def test_multiple_words_same_length(self): + message = list('rat the ate cat the') + reverse_words(message) + expected = list('the cat ate the rat') + self.assertEqual(message, expected) + + def test_multiple_words_different_lengths(self): + message = list('at rat house') + reverse_words(message) + expected = list('house rat at') + self.assertEqual(message, expected) + + def test_multiple_words_different_lengths(self): + message = list('yummy is cake bundt chocolate') + reverse_words(message) + expected = list('chocolate bundt cake is yummy') + self.assertEqual(message, expected) + + def test_empty_string(self): + message = list('') + reverse_words(message) + expected = list('') + self.assertEqual(message, expected) + + +unittest.main(verbosity=2) |