72 lines
2.1 KiB
Python
72 lines
2.1 KiB
Python
"""Tests for lis.py."""
|
|
import unittest
|
|
import random
|
|
from lis import lis_length, lis, lis_indices, is_increasing
|
|
|
|
|
|
class TestLIS(unittest.TestCase):
|
|
def test_empty(self):
|
|
self.assertEqual(lis_length([]), 0)
|
|
self.assertEqual(lis([]), [])
|
|
self.assertEqual(lis_indices([]), [])
|
|
|
|
def test_single(self):
|
|
self.assertEqual(lis_length([5]), 1)
|
|
self.assertEqual(lis([5]), [5])
|
|
|
|
def test_sorted(self):
|
|
self.assertEqual(lis_length([1,2,3,4]), 4)
|
|
self.assertEqual(lis([1,2,3,4]), [1,2,3,4])
|
|
|
|
def test_reverse(self):
|
|
self.assertEqual(lis_length([4,3,2,1]), 1)
|
|
|
|
def test_duplicates_strict(self):
|
|
self.assertEqual(lis_length([1,1,1]), 1)
|
|
self.assertEqual(lis([2,2,1,1,3]), [1,3])
|
|
|
|
def test_known(self):
|
|
seq = [10, 9, 2, 5, 3, 7, 101, 18]
|
|
self.assertEqual(lis_length(seq), 4)
|
|
sub = lis(seq)
|
|
self.assertEqual(len(sub), 4)
|
|
self.assertTrue(is_increasing(sub))
|
|
|
|
def test_indices(self):
|
|
seq = [3, 1, 2]
|
|
idx = lis_indices(seq)
|
|
self.assertEqual([seq[i] for i in idx], lis(seq))
|
|
self.assertEqual(lis_length(seq), 2)
|
|
|
|
def test_brute_random(self):
|
|
def brute(seq):
|
|
n = len(seq)
|
|
if n == 0:
|
|
return 0
|
|
dp = [1]*n
|
|
for i in range(n):
|
|
for j in range(i):
|
|
if seq[j] < seq[i]:
|
|
dp[i] = max(dp[i], dp[j]+1)
|
|
return max(dp)
|
|
rng = random.Random(42)
|
|
for _ in range(300):
|
|
L = rng.randint(0, 14)
|
|
seq = [rng.randint(-6, 6) for _ in range(L)]
|
|
self.assertEqual(lis_length(seq), brute(seq))
|
|
sub = lis(seq)
|
|
self.assertEqual(len(sub), brute(seq))
|
|
self.assertTrue(is_increasing(sub))
|
|
idx = lis_indices(seq)
|
|
self.assertEqual([seq[i] for i in idx], sub)
|
|
|
|
def test_tuple_input(self):
|
|
self.assertEqual(lis_length((3,1,4,1,5)), 3)
|
|
sub = lis((3,1,4,1,5))
|
|
self.assertEqual(len(sub), 3)
|
|
self.assertTrue(is_increasing(sub))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|