711 wyrazów o optymalizacji – część 3

Była część pierwsza i część druga, pora na kolejną, niezupełnie planowaną. Jak pamiętamy w części drugiej udało się ograniczyć sprawdzane liczby do 49 sztuk. To, co chodziło mi od czasu do czasu po głowie to pytanie, czy da się rozwiązać tę zagadkę „na piechotę”, bez użycia komputera?

Rozejrzałem się za możliwymi uproszczeniami i zauważyłem kolejne potencjalne pole do optymalizacji, czyli zmniejszenia liczby potrzebnych obliczeń. Jak wiadomo, 711 jest liczbą nieparzystą. Aby suma dwóch liczb była nieparzysta, jedna z nich musi być parzysta, druga nieparzysta. Z kolei aby suma dwóch liczb była parzysta, albo obie muszą być parzyste, albo nieparzyste. Tu mamy do czynienia z sumą czterech liczb, więc są dwa przypadki. Albo jedna z liczb jest nieparzysta, a trzy są parzyste, albo odwrotnie.

Z naszych 49 liczb, 37 jest parzystych, a 12 nieparzystych. Jak to wpływa na przestrzeń rozwiązań? Z 49^4, czyli ok. 5,8 mln przechodzimy na 12*37^3 + 37*12^3 czyli ok. 672 tys. Nadal trochę dużo jak na ręczne liczenie, ale jak to wpłynie na czas obliczeń? Nasz skrypt będzie miał postać:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(0, len(divs_even)-1):
    for b in range(a, len(divs_odd)-1):
        for c in range (0, len(divs_odd)-1):
            for d in range (c, len(divs_odd)-1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(0, len(divs_odd)-1):
    for b in range(0, len(divs_even)-1):
        for c in range (b, len(divs_even)-1):
            for d in range (c, len(divs_even)-1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Niezależnie od kolejności bloków (najpierw 1 liczba parzysta i 3 nieparzyste, co jest teoretycznie korzystniejszym wariantem, czy odwrotnie), potrzebować będziemy poniżej 95 tys. iteracji. Czas to 0,08 sekundy dla zwykłego interpretera Pythona lub 0,12 sekundy dla Pypy.

Możliwa jest też wersja „w dół”:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(len(divs_even)-1, 0, -1):
    for b in range(len(divs_odd)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(len(divs_odd)-1, 0, -1):
    for b in range(len(divs_even)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Ilość potrzebnych iteracji waha się od 18 do 28 tys. w zależności od kolejności bloków. Natomiast czas wykonania to 0,06 sekundy dla zwykłego interpretera Pythona i 0,1 sekundy dla Pypy.

Nadal nie jest to optymalizacja powodująca, że da się policzyć „na piechotę”, ale… coraz bliżej.