eval.in

Paste #554365

Python — CPython 3.4.1, pasted 2 years ago (json)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def vampireFangs(vampire):
    def recurse(vampire, prevA, prevB, counts, divider):
        if divider < 1: # end of recursion
            # Product of fangs must equal original number and fangs must not
            # both end with a 0.
            if prevA * prevB == vampire and prevA % 10 + prevB % 10 > 0:
                # Solution found
                return [prevA, prevB]
            # It's not a solution
            return False
        # Get left-most digits (multiple of 2) of potential vampire number
        v = vampire//divider
        
        # Shift decimal digits of partial fangs to the left to make room for 
        # the next digits
        prevA *= 10
        prevB *= 10
        # Calculate the min/max A digit that can potentially contribute to a 
        # solution
        minDigA = v // (prevB + 10) - prevA
        maxDigA = 9 if prevB == 0 else (v + 1) // prevB - prevA
        if maxDigA > 9: maxDigA = 9
        for digA in range(minDigA, maxDigA+1):
            if not counts[digA]: continue # this digit is not available
            fangA = prevA + digA
            counts[digA] -= 1
            # Calculate the min/max B digit that can potentially contribute
            # to a solution
            minDigB = v // (fangA + 1) - prevB
            maxDigB = 9 if fangA == 0 else (v + 1) // fangA - prevB
            # Don't search mirrored A-B digits when both fangs are equal 
            # until now.
            if prevA == prevB and digA > minDigB: minDigB = digA
            if maxDigB > 9: maxDigB = 9
            for digB in range(minDigB, maxDigB+1):
                if not counts[digB]: continue # this digit is not available
                fangB = prevB + digB
                counts[digB] -= 1
                # Recurse by considering the next two digits of the potential 
                # vampire number, for finding the next digits to append to 
                # both partial fangs.
                result = recurse(vampire, fangA, fangB, counts, divider // 100);
                # When solution is found: stop searching & exit search tree.
                if result: return result # solution found
                # Restore counts
                counts[digB] += 1
            counts[digA] += 1
        return False

    digits = str(vampire)
    if vampire < 0 or len(digits) % 2: return False
    counts = [0,0,0,0,0,0,0,0,0,0]
    for d in map(int, digits): counts[d] += 1
    return recurse(vampire, 0, 0, counts, 10**(len(digits)-2))

vampire = int(input("Enter number: "))
print(vampire)
result = vampireFangs(vampire)
print(result)

Program Output

Enter number: 67094221760561813454
[7654411206, 8765432109]

OK (0.236 sec real, 0.249 sec wall, 8 MB, 30 syscalls)

Fork