Solution to Prob #38

The problem statement is here. I spent some time thinking the best way to exit the brute force loop. I still don’t claim to have gotten it right, but this one is atleast not too slow and gets the right answer.

def list_to_number(l) :
    r = 0
    for i in l :
        r *= 10
        r += i
    return r

def number_to_list(n) :
    r = []
    while n :
        r.insert(0, n%10)
        n /= 10
    return r

def is_1to9_pandigital(l) :
    if len(l)  9 :
        return False
    for i in range(1, 10) :
        if i not in l :
            return False
    return True

def get_next_seed(s) :

    seed = s + 1
    while seed  9999 :
        return -1

    return seed

if __name__ == '__main__' :

    seed = 1
    pans = 0
    while True :
        pandigital = []
        n = 1
        while True :
            p = seed * n
            pl = number_to_list(p)
            fail = False
            for l in pl :
                if l in pandigital :
                    fail = True
                    break
            if fail :
                break
            pandigital.extend(pl)
            if is_1to9_pandigital(pandigital) :
                pd = list_to_number(pandigital)
                if pd >= pans :
                    pans = pd
                    print "Current Pandigital is ", pd
                    print seed, n

                fail = True
                break
            n += 1
            digits_left = []
            for i in range(1, 10) :
                if i not in pandigital :
                    digits_left.append(i)
            digits_left.sort(reverse=True)
            if n*seed > list_to_number(digits_left) :
                break
        seed = get_next_seed(seed)
        if seed == -1 :
            break
    print "Exhausted!"

I will upload this into the bitbucket repo real soon

Advertisement