Project Euler #51: Prime digit replacements

Sort by

recency

|

22 Discussions

|

  • + 0 comments

    100% python3

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    import math
    from collections import deque
    
    n, k, l = map(int, input().split())
    
    last_d  = ['1', '3', '7', '9']
    
    primes = [ 0 for i in range(2, 1+10**n) ]
    
    for i in range(2, int(math.sqrt(10**n))):
        if primes[i]:
           continue
        for j in range(i*2, len(primes), i):
            primes[j] = 1
    
    def main():
        if k == n:
            #solutions can only be 1*, 3*, 7* and 9* and not l > 4
            print(11)
        else:
            soln, soln_space = [], deque( map(lambda x: '0'*(n-len(x))+x, [bin(i)[2:]
                            for i in range(2**n-1, -1, -1) if bin(i).count('1') == k ]) )
            T, minval = 1, 10**7
            while soln_space:
                N = soln_space.popleft() if T%2 == 1 else soln_space.pop()
                T += 1
                if (N[0] == '1' and N[-1] == '1') or N[-1] == '1':
                    v = last_d
                elif N[0] == '1':
                    v = range(1, 10)
                else:
                    v = range(10)
                N = N.replace('1', '-')
                c, end_val = [ 0 for _ in range(n)], 1
                for _ in range(n):
                    if N[_] == '0':
                        if _ == 0:
                            c[_], end_val = deque(range(1,10)), end_val*9
                        elif _ == n-1:
                            c[_], end_val = deque(last_d), end_val*4
                        else:
                            c[_], end_val = deque(range(10)), end_val*10
                    else:
                        c[_] = N[_]
                z_c = 0
                #print(N)
                while z_c < end_val:
                    r_c, N = 1, ''
                    for _ in range(len(c)-1, -1, -1):
                        if not c[_] == '-':
                            if  r_c == 1 and z_c != 0 :
                                c[_].rotate(-1)
                            elif z_c > 0 and  z_c % r_c == 0:
                                c[_].rotate(-1)
                            N = str(c[_][0])+N
                            r_c *= len(c[_])
                        else:
                            N = '-'+N
                    z_c += 1
                    if int(N.replace('-', str(v[0]))) > minval:
                        break
                    tmp, ll = [], len(v)
                    if len(v) < l:
                        break
                    for j in range(ll):
                        val = N.replace('-', str(v[j]))
                        if (j == 0 and int(val) > minval):
                            break
                        if  primes[int(val)] == 0:
                            tmp.append(val)
                        if len(tmp) >=  l:
                            if minval > int(tmp[0]):
                                minval = int(tmp[0])
                            soln.append(tmp)
                            break
                        if len(tmp)+ll-(j+1) < l:
                             break
            #print(soln)
            soln.sort()
            print(*soln[0][:l])
    
    
    if __name__ == '__main__':
        main()
    
  • + 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()
    
  • + 0 comments

    JAva code

    import java.io.*;
    import java.util.*;
    
    public class Solution {
    
       static int N = 7;
        static int K = 3;
        static int L = 7;
        static Map<String, List<Integer>> M = new HashMap<>();
        static int smPrime = 99999999;
    
        static void match(int num, StringBuilder regex, int dig, int howOften, int startPos) {
            char asDig = (char) (dig + '0');
            for (int i = startPos; i < N; i++) {
                if (regex.charAt(i) != asDig) {
                    continue;
                }
                if (i == 0 && asDig == '0') {
                    continue;
                }
                regex.setCharAt(i, '.');
                if (howOften == 1) {
                    List<Integer> addTo = M.computeIfAbsent(regex.toString(), k -> new ArrayList<>());
                    addTo.add(num);
                    if (addTo.size() >= L && addTo.get(0) < smPrime) {
                        smPrime = addTo.get(0);
                    }
                } else {
                    match(num, regex, dig, howOften - 1, i + 1);
                }
                regex.setCharAt(i, asDig);
            }
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            N = scanner.nextInt();
            K = scanner.nextInt();
            L = scanner.nextInt();
    
            int minNum = 1;
            for (int i = 1; i < N; i++) {
                minNum *= 10;
            }
            int maxNum = minNum * 10 - 1;
            boolean[] primes = new boolean[maxNum + 1];
            Arrays.fill(primes, true);
            primes[0] = primes[1] = false;
    
            for (int i = 2; i * i <= maxNum; i++) {
                if (primes[i]) {
                    for (int j = 2 * i; j <= maxNum; j += i) {
                        primes[j] = false;
                    }
                }
            }
    
            for (int i = minNum; i <= maxNum; i++) {
                if (primes[i]) {
                    String strNum = Integer.toString(i);
                    for (int dig = 0; dig <= 9; dig++) {
                        match(i, new StringBuilder(strNum), dig, K, 0);
                    }
                    if (N == 7) {
                        if (K == 1 && i > 2 * Math.pow(10, 6)) {
                            break;
                        }
                        if (K == 2 && i > 3 * Math.pow(10, 6)) {
                            break;
                        }
                    }
                }
            }
    
            String mini = "";
            for (Map.Entry<String, List<Integer>> entry : M.entrySet()) {
                List<Integer> values = entry.getValue();
                if (values.size() < L) {
                    continue;
                }
                if (!values.get(0).equals(smPrime)) {
                    continue;
                }
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < L; i++) {
                    s.append(values.get(i)).append(" ");
                }
                if (mini.compareTo(s.toString()) > 0 || mini.isEmpty()) {
                    mini = s.toString();
                }
            }
            System.out.println(mini);
        }
    }
    
  • + 0 comments

    100points/- python 3
    Some points-
    1) L prime family means a family where a single fixed set of indices when replaced by numbers has Atleast L primes.
    2) The problem demands that you produce the smallest Family in lexicographical order for a given n,k,l, not the one which is produced by smallest prime number with n digits whose family is L . If you are using primes in sorted order or even only those primes where k digits repeat, it can happen that for a smaller number you get a family with larger initials than the next bigger prime, so check it.
    3) Timing is Important.

  • + 3 comments

    WA #3, #13, #15, #17.. not sure why