"""
Problem 38: https://projecteuler.net/problem=38

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call
192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5,
giving the pandigital, 918273645, which is the concatenated product of 9 and
(1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the
concatenated product of an integer with (1,2, ... , n) where n > 1?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/13
'''


def isConcatenated(m: int) -> bool:
    '''
    see solution() following
    '''

    ms = str(m)
    if '0' in ms:
        return False

    max_n = 9 // len(ms)
    for i in range(2, max_n+1):  # 2 < i <= 9/dm
        ms += str(m*i)
        if '0' in ms:
            return False
        if len(ms) == 9 and set(ms) == set('123456789'):
            return int(ms), m, i
        if len(ms) > 9:
            return False

    return False


def solution() -> int:
    '''
        m * 1
        m * 2
        m * 3
        ...
        m * n

    m * i has no less than dm digits, i = 1,2,...,n
    so, dm * n <= 9, such as, m = 192, dm = 3, n = 3
    for, n > 1, max(dm) = 4

    '''
    res = 123456789
    for i in range(1, 9999):
        tmp = isConcatenated(i)
        if tmp:
            print(tmp)
            res = tmp[0] if tmp[0] > res else res

    return res


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 932718654

    '''
    (123456789, 1,    9)
    (918273645, 9,    5)
    (192384576, 192,  3)
    (219438657, 219,  3)
    (273546819, 273,  3)
    (327654981, 327,  3)
    (672913458, 6729, 2)
    (679213584, 6792, 2)
    (692713854, 6927, 2)
    (726914538, 7269, 2)
    (729314586, 7293, 2)
    (732914658, 7329, 2)
    (769215384, 7692, 2)
    (792315846, 7923, 2)
    (793215864, 7932, 2)
    (926718534, 9267, 2)
    (927318546, 9273, 2)
    (932718654, 9327, 2)
    '''