Redukujemy do absurdu, czyli żarcik programistyczny

Przeglądając blogosferę, natrafiłem niedawno na artykuł o liczbach pierwszych limerykowych. Są to pięciocyfrowe liczby pierwsze postaci AABBA gdzie A i B to dwie różne cyfry, A>0.

Liczb takich jest osiem: 11551, 33113, 33223, 33773, 77447, 77557, 99119, 99559.

Spróbowałem napisać program w Pythonie, który mi te liczby wyszuka. Temat jest banalny, dwie minuty później miałem już gotowca:

from sympy import isprime
results = []
for x in range(10):
    for y in range(10):
        n = 11001*x+110*y
        if(isprime(n)):
            results.append(n)
print(results)

Osiem linii kodu. Oczywiście natychmiast zadałem sobie pytanie czy można to jakoś skrócić. Na przykład, po co zapisywać wyniki pośrednie skoro można je na bieżąco wypisywać na ekran?

from sympy import isprime
for x in range(10):
    for y in range(10):
        n = 11001*x+110*y
        if(isprime(n)):
            print(n)

Co prawda wynik pojawia się teraz w odrobinę innym układzie (każda liczba w osobnej linijce), ale wynik to wynik.

Co by tu dalej... Można zastąpić dwie zagnieżdżone pętle for - jedną:

from sympy import isprime
for x, y in [[x, y] for x in range(10) for y in range(10)]:
    n = 11001*x+110*y
    if(isprime(n)):
        print(n)

Udało nam się zejść do pięciu linii kodu. Co prawda czytelność w linii numer 2 nieco spadła, ale nie ma tragedii. Kolejny pomysł: przełożyć wyliczenie zmiennej n do linii otwierającej pętlę:

from sympy import isprime
for n in [11001*x+110*y for x in range(10) for y in range(10)]:
    if(isprime(n)):
        print(n)

Już tylko cztery linie kodu, wyniki nadal poprawne. Czytelność... mogłaby być lepsza, ale da się to jeszcze w miarę zrozumieć. A co gdyby tak spróbować przefiltrować pod kątem pierwszości listę tworzoną w drugiej linii - w tej samej linii?

from sympy import isprime
for n in list(filter(lambda x: isprime(x), [11001*x+110*y for x in range(10) for y in range(10)])):
    print(n)

Udało nam się zejść do trzech linii kosztem znacznego pogorszenia czytelności. Ale wyniki nadal poprawne, więc kombinujemy dalej.

Hmmmm...

(pięć strzałów znikąd później...)

Hmmmm... Te liczby są raptem tylko pięciocyfrowe, nie potrzebujemy żadnego zaawansowanego algorytmu sprawdzania pierwszości, prawda? Wystarczy podzielić liczbę n przez każdą liczbę od 2 do pierwiastka z n zaokrąglonego w górę do pełnej całości - jeżeli nie dzieli się przez żadną z nich, to jest pierwsza.

Hmmmmmmm...

print(list(filter(lambda n: n>2 and len([i for i in range(2, int(n**0.5)+1) if n%i==0])==0, [11001*x+110*y for x in range(10) for y in range(10)])))

Krócej się już nie da 🙂

11 komentarzy

    1. Słuszna uwaga. Jednakowoż po zapisaniu na dysku plik z pierwszą wersją ma 177 bajtów a z ostatnią – 148:

      drwxr-xr-x  2 xpil xpil 4096 Jan 13 13:47 ./
      drwxr-xr-x 61 xpil xpil 4096 Jan 10 19:57 ../
      -rw-rw-r--  1 xpil xpil  148 Jan 13 15:08 limprim2.py
      -rw-rw-r--  1 xpil xpil  177 Jan 13 15:08 limprim1.py
      

      Tak że tego.

      1. Interesujące. Nie mam do czynienia z pythonem, więc lekko nie rozumiem, dlaczego jedna wersja nie zmieniła w ogóle długości, a inna powiększyła się aż o 39 bajtów, czyli o ponad 28%! Znaki końca wiersza mogą zajmować 7*2B=14B. Brakuje jeszcze 25B. Gdzie one są?

        1. Znaki końca wiersza zajmują 7 bajtów a nie 14, bo mam w tym pliku linuksowe (jednobajtowe: heksadecymalnie `0A`) znaki końca linii.

          Linie 1 – 8 mają następujące długości: 25, 12, 19, 23, 25, 23, 29, 14.
          Suma długości linii daje 170.
          170 plus 7 znaków końca linii daje łącznie 177. Wszystko się zgadza.

  1. Policzyłeś wiodące spacje linii! One są tylko polepszaczem optycznym dla programisty, nie są częścią wykonywanego kodu. Policz te prawdziwe znaki, jest ich 138+7=145. I pierwszy program nadal jest krótszy…

    1. Spacje wiodące są elementem składni Pythona. Po redukcji poczwórnych spacji do pojedynczych otrzymujemy:

      -rw-rw-r--  1 xpil xpil  150 Jan 13 20:08 limprim1.py
      -rw-rw-r--  1 xpil xpil  148 Jan 13 15:12 limprim2.py
      

      … czyli pojedyncza linia jest o 2 bajty krótsza od posiedmiorczej.

      1. P.S. “nie są częścią wykonywanego kodu.” jest prawdziwe dla wszystkich znaków obydwu wersji. Wykonuje się kod maszynowy skompilowany z pseudokodu skompilowanego z kodu źródłowego. Obstawiam, że w obydwu przypadkach ów kod maszynowy jest prawie taki sam (chociaż import biblioteki `sympy` może trochę namieszać…)

        1. Rzeczywiście, pobawiłem się chwilę na online-python – przedziwny to język z wiodącymi spacjami. Jestem w szoku! Zwracam honor.
          Zauważyłem, że dwukropek otwiera blok, a wcięcia spacjami oznaczają przynależność do tego bloku – takie mało ekonomiczne { } lub begin end. Ewidentnie Python został wymyślony po to, aby pisać “krótkie” programy jednowierszowe. 🙂

          1. Python z założenia powstał jako język, w którym nie da się napisać źle sformatowanego kodu, bo wcięcia są interpretowane. Jedni mówią, że to kiepski pomysł, innym się podoba. Mi się podoba, chociaż pisałem przedtem całkiem sporo w C / C++ i tameczne nawiasy klamrowe też mi się podobały. Bo ja mało awanturujący się klient jestem 🙂

            Przy okazji, jeżeli “wcięty” blok składa się tylko z jednej linii, można ją umieścić w tej samej linii co dwukropek, o czym dowiedziałem się całkiem niedawno:

            zamiast

            cośtam:
                plonk
            

            można:

            cośtam: plonk
            
  2. Nie wiem czy znasz zabawę zwaną Perl golf. Jeśli nie, to polecam wyszukanie. Dokładnie coś takiego wydajesz się uprawiać w Pythonie. Tylko nie masz precyzyjnych zasad. Znaczy nie wiadomo czy minimalizujesz ilość linii czy znaków.

    Swoją drogą, to IMO średni sposob na naukę języka programowania w ogóle, a Pythona w szczególności. Priorytetem jest przecież czytelność, prawda?

    1. Prawda. Ale liczy się też zabawa – redukowanie programu do jak najmniejszej liczby linii (znaków, instrukcji itd itd) ma dla mnie aspekt rozrywkowy.

      Podobno każdy program w C da się zapisać w postaci jednej pętli for 🙂

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]