Code Test: Given an array of ints, return True if the sequence.. 1, 3, 4 .. appears in the array somewhere.

appears_in.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Given an array of int's, return True if the sequence.. 1, 3, 4 .. appears in
# the array somewhere.


# O(len(haystack)) || Ω(len(needle))
def appears_in(haystack: list, needle: list) -> bool:
    """ Return True if `needle` appears in `haystack`.

    :param haystack: Earth.
    :param needle: Waldo.
    :rtype: bool
    """

    if (not haystack) or (not needle):
        return False
    if len(needle) > len(haystack):
        return False

    h_index = 0  # haystack index
    n_index = 0  # needle index
    diff = len(haystack) - len(needle)

    while h_index < len(haystack):
        # Are we close to the E.N.D,
        if h_index > diff:
            # & still unsuccessful?
            if n_index == 0:
                return False  # bail

        # The above conditions can give a slight performance boost when wrapped
        # in the `while` condition (Py 3.6.2):
        # while (h_index < len(haystack)) \
        #     and not ((h_index > diff) and (n_index == 0)):

        num = haystack[h_index]

        # Can we match the needle?
        if num == needle[n_index]:
            n_index += 1
        # How about now!?
        elif num == needle[0]:
            n_index = 1
        # Fine, reset that needle!
        else:
            n_index = 0

        if n_index == len(needle):
            return True  # 𝔍ackpot

        h_index += 1

    return False  # ¯\_(ツ)_/¯


if __name__ == '__main__':
    haystack = [6, 2, 1, 1, 1, 3, 3, 1, 2, 5, 5, 1, 2, 1, 3, 1, 1, 3, 4, 4, 1]

    assert appears_in(haystack, [1, 3, 4])  # <- solution

    assert not appears_in(haystack, [1, 3, 4, 6])
    assert not appears_in(haystack, [0, 1, 3, 4])
    assert not appears_in(haystack, [])
    assert not appears_in([], [])  # ??