Project Euler #51: Prime digit replacements

  • + 0 comments

    python code/-100points

    N = 7
    K = 3
    L = 7
    M = {}
    smPrime = 99999999
    
    def match(num, regex, dig, howOften, startPos):
        global smPrime
        asDig = str(dig)
        for i in range(startPos, N):
            if regex[i] != asDig:
                continue
            if i == 0 and asDig == '0':
                continue
            regex[i] = '.'
            if howOften == 1:
                addTo = M.setdefault("".join(regex), [])
                addTo.append(num)
                if len(addTo) >= L and addTo[0] < smPrime:
                    smPrime = addTo[0]
            else:
                match(num, regex, dig, howOften - 1, i + 1)
            regex[i] = asDig
    
    def main():
        global N, K, L, smPrime
        N, K, L = map(int, input().split())
    
        minNum = 1
        for i in range(1, N):
            minNum *= 10
        maxNum = minNum * 10 - 1
        primes = [True] * (maxNum + 1)
        primes[0], primes[1] = False, False
    
        for i in range(2, int(maxNum ** 0.5) + 1):
            if primes[i]:
                for j in range(2 * i, maxNum + 1, i):
                    primes[j] = False
    
        for i in range(minNum, maxNum + 1):
            if primes[i]:
                strNum = str(i)
                for dig in range(10):
                    match(i, list(strNum), dig, K, 0)
                if N == 7:
                    if K == 1 and i > 2 * 10 ** 6:
                        break
                    if K == 2 and i > 3 * 10 ** 6:
                        break
    
        mini = ""
        for key, values in M.items():
            if len(values) < L:
                continue
            if values[0] != smPrime:
                continue
            s = " ".join(map(str, values[:L]))
            if mini > s or not mini:
                mini = s
        print(mini)
    
    if __name__ == "__main__":
        main()