Optymalizacje, optymalizacje, ciągłe optymalizacje


(enedil) #1

Witajcie.
Ćwiczę się w algorytmice, wobec tego rozwiązuję przeszłe zadanie z Google Code Jam. Niestety, to co zakodziłem jest nazbyt wolne, by dać w ogóle wynik. Dlatego proszę o pomoc w ulepszeniu mojego rozwiązania (tzn. nie pragnę całkiem odmiennego podejścia, ciekawi mnie czy liczę coś w nadmiernych ilościach).

Zadanie - https://code.google.com/codejam/contest/6254486/dashboard#s=p2
Moje polskie skrótowe tłumaczenie:

Poprawnym ciągiem znaków jest ten, który spełnia poniższe warunki:

  • każdy znak jest zerem lub jedynką
  • pierwszy i ostatni znak jest jedynką
  • dla liczb całkowitych 2 <= b <= 10 jeśli zinterpretujemy ciąg jako liczbę w systemie o podstawie b, to powstała liczba nie będzie pierwsza
    Znajdź j ciągów znaków zadanej długości n, jako dowód poprawności dla każdej podstawy b podaj właściwy dzielnik

Są dwa przypadki testowe, n, j = 16, 50 oraz n, j = 32, 500. Mniejszy przechodzi bez większego problemu. Za to większy, cóż. Właśnie z nim mam problem. Mój kod wygląda tak:

#!/usr/bin/env python3

import sympy as sp # http://sympy.org
from sys import stderr

def nextnum(l):
    '''
    Generuje kolejne potencjalne ciągi
    '''
    for i in range(2**(l-2)):
        yield '1' + bin(i)[2:].zfill(l-2) + '1'

primes = sp.primerange(2, 10**4)
def get_factor(s, b):
    n = int(s, b)
    # najpierw odsiej małe liczby pierwsze z dzielników
    for x in primes:
        if n%x == 0:
            return x

    # potem spróbuj efektywniejszej metody (dla większych liczb)
    f = sp.pollard_rho(n)
    if f != 1 and f != n:
        return f

    # jeśli się nie powiedzie, kontynuuj
    for x in range(10**4, int(n**0.5)+1):
        if n%x == 0:
            return x

def main():
    # liczba przypadków testowych
    t = int(input())
    for i in range(t):
        n, j = [int(c) for c in input().split()]
        print("Case #{}:".format(i+1))
        g = nextnum(n)
        while j:
            s = next(g)
            print(s, file=stderr) # dla oglądania postępu            
            n_in_b = [int(s, b) for b in range(2, 11)]
            if all(not sp.primetest.isprime(n) for n in n_in_b):
                # jeśli wszystkie są złożone,
                # to znajdź najmiejszy dzielnik właściwy
                l = [str(get_factor(s, b)) for b in range(2, 11)]
                print(' '.join([s] + l))
                j -= 1

if __name__ == '__main__':
    main()