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/cafe-order-checker.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/cafe-order-checker.py')
-rw-r--r-- | users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py b/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py new file mode 100644 index 000000000000..e34a2b136ab6 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py @@ -0,0 +1,91 @@ +import unittest + + +################################################################################ +# Implementation +################################################################################ +def is_first_come_first_served(to, di, xs): + # All the guards, assertions we should need. + if to == di == xs == []: + return True + elif to == di == []: + return False + elif to == []: + return di == xs + elif to == []: + return di == xs + elif di == []: + return to == xs + elif xs == []: + return False + elif len(xs) != (len(to) + len(di)): + return False + + fst, snd = to, di + + if xs[0] == to[0]: + fst, snd = to, di + elif xs[0] == di[0]: + fst, snd = di, to + else: + return False + + fst_done, snd_done = False, False + fi, si = 1, 0 + + for i in range(1, len(xs)): + # Short-circuit and avoid index-out-of-bounds without introducing overly + # defensive, sloppy code. + if fst_done: + return snd[si:] == xs[i:] + elif snd_done: + return fst[fi:] == xs[i:] + + if fst[fi] == xs[i]: + fi += 1 + elif snd[si] == xs[i]: + si += 1 + else: + return False + + fst_done, snd_done = fi == len(fst), si == len(snd) + + return True + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_both_registers_have_same_number_of_orders(self): + result = is_first_come_first_served([1, 4, 5], [2, 3, 6], + [1, 2, 3, 4, 5, 6]) + self.assertTrue(result) + + def test_registers_have_different_lengths(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 2, 6, 3, 5]) + self.assertFalse(result) + + def test_one_register_is_empty(self): + result = is_first_come_first_served([], [2, 3, 6], [2, 3, 6]) + self.assertTrue(result) + + def test_served_orders_is_missing_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 6, 3, 5]) + self.assertFalse(result) + + def test_served_orders_has_extra_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], + [1, 2, 3, 5, 6, 8]) + self.assertFalse(result) + + def test_one_register_has_extra_orders(self): + result = is_first_come_first_served([1, 9], [7, 8], [1, 7, 8]) + self.assertFalse(result) + + def test_one_register_has_unserved_orders(self): + result = is_first_come_first_served([55, 9], [7, 8], [1, 7, 8, 9]) + self.assertFalse(result) + + +unittest.main(verbosity=2) |