about summary refs log tree commit diff
path: root/scratch/deepmind/part_two/find-duplicate-optimize-for-space-beast-mode.py
blob: c9edc32c8856000e541494263ba6580415d91735 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import unittest


################################################################################
# InterviewCake's solution
################################################################################
def cycle_len(xs, i):
    """
    Returns the length of a cycle that contains no duplicate items.
    """
    result = 1
    checkpt = i
    current = xs[checkpt - 1]

    while current != checkpt:
        current = xs[current - 1]
        result += 1

    return result


def theirs(xs):
    """
    This is InterviewCake's solution.
    """
    i = xs[-1]
    for _ in range(len(xs) - 1):
        i = xs[i - 1]

    cycle_length = cycle_len(xs, i)

    p0 = xs[-1]
    p1 = xs[-1]
    for _ in range(cycle_length):
        p1 = xs[p1 - 1]

    while p0 != p1:
        p0 = xs[p0 - 1]
        p1 = xs[p1 - 1]

    print(p0, p1)

    return p0


################################################################################
# My solution
################################################################################
def mine(xs):
    """
    This is the solution that I came up with, which differs from InterviewCake's
    solution.
    """
    i = xs[-1]
    offset = 1 if len(xs) % 2 == 0 else 2

    for _ in range(len(xs) - offset):
        i = xs[i - 1]

    return i


use_mine = True
find_duplicate = mine if use_mine else theirs


# Tests
class Test(unittest.TestCase):
    def test_just_the_repeated_number(self):
        # len(xs) even
        actual = find_duplicate([1, 1])
        expected = 1
        self.assertEqual(actual, expected)

    def test_short_list(self):
        # len(xs) even
        actual = find_duplicate([1, 2, 3, 2])
        expected = 2
        self.assertEqual(actual, expected)

    def test_medium_list(self):
        # len(xs) even
        actual = find_duplicate([1, 2, 5, 5, 5, 5])
        expected = 5
        self.assertEqual(actual, expected)

    def test_long_list(self):
        # len(xs) odd
        actual = find_duplicate([4, 1, 4, 8, 3, 2, 7, 6, 5])
        expected = 4
        self.assertEqual(actual, expected)

    ############################################################################
    # Additional examples from InterviewCake.com
    ############################################################################
    def test_example_a(self):
        # len(xs) even
        actual = find_duplicate([3, 4, 2, 3, 1, 5])
        expected = 3
        self.assertTrue(actual, expected)

    def test_example_b(self):
        # len(xs) even
        actual = find_duplicate([3, 1, 2, 2])
        expected = 2
        self.assertEqual(actual, expected)

    def test_example_c(self):
        # len(xs) odd BUT multiple duplicates
        actual = find_duplicate([4, 3, 1, 1, 4])
        self.assertTrue(actual in {1, 4})


unittest.main(verbosity=2)