How to Solve Van Eck's Sequence in Python

0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, …

This is the Van Eck’s Sequence.

Let’s go through it step by step.

Term 1: The first term is 0. Term 2: Since we haven’t seen 0 before, the second term is 0. Term 3: Since we had seen a 0 before, one step back, the third term is 1 Term 4: Since we haven’t seen a 1 before, the fourth term is 0 Term 5: Since we had seen a 0 before, two steps back, the fifth term is 2. And so on…

Your task is to find the n_th number in Van Eck’s Sequence. (1-based)

The Solution in Python

Option 1

from collections import Counter

c=Counter()
SEQ = [0]
for i in range(1000):
    n = SEQ[-1]
    if not c[n]: c[n]=i
    SEQ.append(i-c[n])
    c[n]=i
    
seq=SEQ.__getitem__

Option 2

def dist(arr):
    for i in range (1, len(arr)):
        if arr[-1-i] == arr[-1]:
            return i
    return 0

def seq(n):
    s = [0, 0]
    for _ in range (n):
        s.append(dist(s))
    return s[n-1]

Option 3

def seq(n):
    van, eck = [0], 0
    while n := n - 1:
        van.insert(0, eck := van.index(eck, 1) if eck in van[1:] else 0)
    return eck

Test cases to validate the solution

from solution import seq
import test

from random import randint

@test.describe("Sample tests:")
def tests():
    @test.it("Small numbers")
    def _():
        s = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6]
        for i in range (len(s)):
            test.assert_equals(seq(i+1), s[i])
    @test.it('Larger numbers')
    def __():
        s = [3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11,
             18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3,
             6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0,
             5, 37, 0, 3, 8, 8, 1, 46, 0, 6, 23, 0]
        for i in range (len(s)):
            test.assert_equals(seq(i+50), s[i])

@test.describe('Random tests:')
def r():

    def dist(arr):
        for i in range (1, len(arr)):
            if arr[-1-i] == arr[-1]:
                return i
        return 0

    def ref_sol(n):
        s = [0, 0]
        for _ in range (n):
            s.append(dist(s))
        return s[n-1]
    
    @test.it('200 random tests:')
    def _():
        for _ in range (200):
            a = randint(100, 1000)
            exp = ref_sol(a)
            test.assert_equals(seq(a), exp)