# Python program for OEIS A358711
# Michael S. Branicky, Dec 02 2022 

# A358711 Autobiographical numbers: let the k-th digit count the k-th nonnegative integer (A001477(k)) (possibly overlapping) occurrences in the term.		0
data = [1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 53110100002, 62200010001, 541011000021, 6401101000310, 74011001003100, 840110001031000, 9321000001201000, 94201000012110000]

from time import time

from sympy import isprime
from itertools import count, islice
from sympy.utilities.iterables import partitions, multiset_permutations

time0 = time()
OVERLAPS = True # global switch

def count_overlaps(subs, s):
    c = i = 0
    while i != -1:
        i = s.find(subs, i)
        if i != -1: c += 1; i += 1
    return c

def count_subs(subs, s):
    global OVERLAPS
    if not OVERLAPS:
        return s.count(subs)
    return count_overlaps(subs, s)

def okstr(lst):
    M = len(lst)
    slst = "".join(lst)
    return all(count_subs(str(i), slst) == int(lst[i]) for i in range(M))

def partialokstr(lst):
    M = len(lst)
    slst = "".join(lst)
    partialok, s = True, ""
    for i in range(M):
        missing = int(lst[i]) - count_subs(str(i), slst)
        if missing < 0: return False, ""
        else: 
            if i < 10:
                s += missing*str(i)
    return True, s

def agen():
    for d in range(1, 101):
        okset = set()
        for p in partitions(d, k=9, m=10):
            sp = "".join(str(k)*v for k, v in p.items())
            missing_zeros = min(d, 10) - len(sp)
            if missing_zeros < 0 or missing_zeros > 9: continue
            s = sp + "0"*missing_zeros
            for m in multiset_permutations(s):
                if m[0] != "0":
                    passes, needs = partialokstr(m)
                    if passes:
                        if d <= 10:
                            if okstr(m):
                                okset.add(int("".join(m)))
                        else:
                            if needs != '':
                                if sum(map(int, needs)) <= sum(int(m[i]) for i in range(1, d//10+1)):
                                    for m2 in multiset_permutations(needs):
                                        if okstr(m+m2):
                                            print("FOUND", "".join(m), "".join(m2), "".join(m+m2))
                                            okset.add(int("".join(m+m2)))
        yield from sorted(okset)
        print("...", d, time()-time0)

alst = []
g = agen()
for n in range(1, 10001):
    an = next(g)
    alst.append(an)
    print(n, an, len(str(alst))-2, time()-time0)
    print("   ", alst)
    print("   ", data)
    with open('b358711.txt', 'a') as bfile:
        bfile.write(f"{n} {an}\n")