Mrówkowe szaleństwo

Natrafiłem niedawno w Wikipedii na Mrówkę Langdona. Pomysł jest w sumie prosty: na nieskończenie dużej planszy składającej się kwadratowych pól stoi sobie mrówka. I teraz tak: jeżeli stoi na białym polu, obraca się w lewo, a jeżeli na czarnym – w prawo. Następnie zmienia kolor pola na przeciwny (a więc z białego na czarny, lub z czarnego na biały) i przesuwa się o jedno pole do przodu. I tak do usranej śmierci.

Trochę się to kojarzy z Game of Life Johna Conwaya.

Pomyślałem sobie, że mogłoby to być całkiem niezłe ćwiczenie ogólne na posługiwanie się Pythonem.

No i się zaczęło…

Najpierw całkiem niewinna wersja minimalna:

import matplotlib.pyplot as plt
import numpy as np

dirs = {"N": [0, 1], "S": [0, -1], "W": [-1, 0], "E": [1, 0]}
L = {"N": "W", "W": "S", "S": "E", "E": "N"}
R = {"N": "E", "E": "S", "S": "W", "W": "N"}

xsize, ysize = 500,500
steps = 1000000
x, y = xsize//2, ysize//2
board = np.zeros(shape=(xsize, ysize), dtype=int)

turns = [L,R]
dir = "N"
for X in range(steps):
    dir = turns[(board[x, y])][dir]
    board[x, y] = 1-board[x, y]
    dx, dy = dirs[dir]
    x, y = (x + dx) % xsize, (y + dy) % ysize
plt.imshow(board)
plt.xticks([])
plt.yticks([])
plt.show()

Powyższy kod generuje trasę spaceru Mrówki Langdona z jedną różnicą względem oryginału: zamiast nieskończonej płaszczyzny używamy prostokąta “zawiniętego” wzdłuż i w poprzek (czyli mrówka wychodząc poza lewą krawędź pojawia się po prawej stronie i tak dalej).

Wynik:

A potem spróbowałem dodać więcej kolorów, więcej opcji zakręcania, czyli do “w lewo” i “w prawo” dołożyłem opcję “zawróć” oraz “idź dalej prosto” i na koniec zrobił mi się z tego generator losowych spacerów Mrówek Langdona, którego kod wygląda teraz tak:

import matplotlib.pyplot as plt
import numpy as np
from random import choice, randrange as rr

dirs = {"N": [0, 1], "S": [0, -1], "W": [-1, 0], "E": [1, 0]}

L = {"N": "W", "W": "S", "S": "E", "E": "N"} # left
R = {"N": "E", "E": "S", "S": "W", "W": "N"} # right
N = {"N": "N", "W": "W", "S": "S", "E": "E"} # none
B = {"N": "S", "W": "E", "S": "N", "E": "W"} # back

colormaps = plt.colormaps()

for mainloop in range(1000):

    xsize, ysize = 200 + rr(300), 200+rr(300)
    steps, colours = 1000000 + rr(4000000), 20+rr(65515)
    x, y = xsize//2, ysize//2
    board = np.zeros(shape=(xsize, ysize), dtype=int)

    turns = []
    tt = ""
    trnum = 2+rr(20)
    for i in range(trnum):
        t = choice(("L", "R", "N", "B"))
        tt += t
        turns.append({"L": L, "R": R, "N": N, "B": B}[t])

    dir = "N"
    for X in range(steps):
        dir = turns[(board[x, y]) % len(turns)][dir]
        board[x, y] = (board[x, y] + 1) % colours
        dx, dy = dirs[dir]
        x, y = (x + dx) % xsize, (y + dy) % ysize
    plt.imshow(board, cmap=choice(colormaps))
    plt.xticks([])
    plt.yticks([])
    xlab = "{}x{}|{}|C:{}|S:{}".format(xsize, ysize, tt, colours, steps)
    plt.xlabel(xlab)
    filename = "ants/langton-{}-{}-{}-{}-{}.png".format(
        xsize, ysize, tt, colours, steps)
    plt.savefig(filename)
    print(".", end="")
print()

Przed uruchomieniem skryptu należy się upewnić, że mamy lokalny folder o nazwie “ants”, do którego będą trafiać wygenerowane obrazki. Skrypt wygeneruje 1000 losowych spacerów i zapisze każdy z nich w osobnym pliku png. Obrazki mają losową rozdzielczość (od 200×200 do 500×500 pikseli), losową mapę i liczbę kolorów, losowe reguły zakręcania oraz liczbę iteracji (między 1M a 5M).

Mała próbka:

Większa próbka (kliknięcie w obrazek wyświetli go w powiększeniu):

Co dalej?

Jak czas i zdrowie pozwolą, spróbujemy pobawić się planszą heksagonalną…

Pasjansowy zegar czy zegarowy pasjans?

Solitaire znają wszyscy[citation needed]. Wykładały go nasze babcie i prababcie, był też dołączany przez Microsoft do większości wersji Windows.

Jest jednak wiele innych pasjansów. Jeden z nich – którego nauczyła mnie babcia – to Zegar.

Zegar jest – w odróżnieniu od Solitaire – pasjansem stuprocentowo deterministycznym. Innymi słowy wynik zależy wyłącznie od początkowego potasowania talii. Nie ma tu żadnego miejsca na myślenie, na decydowanie; po prostu robimy krok po kroku to, co każą nam karty. Mało twórcze, ale czasem człowiek potrzebuje[citation needed] mechanicznego, bezmyślnego przekładania kart. Taki reset.

Szczegóły samego pasjansa dobrze objaśnia Łukasz z portalu Przystanek Planszówka (KLIK), skąd zresztą ukradłem obrazek do dzisiejszego wpisu. Jeżeli ktoś nie zna Zegara, może sobie tam poczytać. Tutaj natomiast pokażę jak zrobić symulację Zegara w Pythonie aby sprawdzić jak często wychodzi, a jak często – nie wychodzi.

Zanim zacznę, powiem jeszcze, że za dzieciaka wykładałem Zegar dość często. Nie pamiętam ile razy mi się udało “wygrać”, ale były to przypadki bardzo rzadkie.

OK, lecimy:

from random import sample
wygrane, ilosc_prob = 0, 100000

for proba in range(ilosc_prob):
    stos = sample(range(52), 52)  # tasujemy talię

    # zegar to lista list:
    # zewnętrzna lista ma 13 elementów (12 godzin plus stosik na środku)
    # każdy z 13 elementów jest listą 4-elementową (stos 4 kart)
    # przykładowo zegar[11][0] to pierwsza karta godziny 11
    zegar = []

    for i in range(13):  # rozkładamy zegar
        zegar.append(stos[i::13])

    krole = 0  # licznik króli (królów?)

    karta = 0  # startujemy od środka zegara
    while 1:  # gramy!
        karta = zegar[karta % 13].pop()  # bierzemy kolejną kartę
        if karta % 13 == 0:  # jeżeli trafiliśmy na króla
            krole += 1  # liczymy go
            if krole == 4:  # jeżeli to ostatni król
                break  # koniec pasjansa

    # jeżeli odkryliśmy wszystkie 12 godzin zegara, udało się
    if(sum(map(lambda x: x == [], zegar)) == 12):
        wygrane += 1

print(wygrane/ilosc_prob)

Przy liczbie prób 1M (lub więcej) wynik prawie zawsze wychodzi w okolicach 0.077. A więc 77 razy na 1000 pasjans wychodzi. Pozostałe 923 razy – nie wychodzi.

Najbardziej frustrujące jest, kiedy już prawie, prawie wyszedł, odkryliśmy 11 godzin, brakuje tylko jednej – i ostatni król pojawia się odrobinę za wcześnie.

No dobra. Skoro pasjans nie wychodzi za często, może spróbujmy policzyć ile średnio godzin uda się odkryć zanim pojawi się czwarty król?

from random import sample
wygrane, ilosc_prob, odkryte = 0, 100000, 0

for proba in range(ilosc_prob):
    stos = sample(range(52), 52)  # tasujemy talię

    # zegar to lista list:
    # zewnętrzna lista ma 13 elementów (12 godzin plus stosik na środku)
    # każdy z 13 elementów jest listą 4-elementową (stos 4 kart)
    # przykładowo zegar[11][0] to pierwsza karta godziny 11
    zegar = []

    for i in range(13):  # rozkładamy zegar
        zegar.append(stos[i::13])

    krole = 0  # licznik króli (królów?)

    karta = 0  # startujemy od środka zegara
    while 1:  # gramy!
        karta = zegar[karta % 13].pop()  # bierzemy kolejną kartę
        if karta % 13 == 0:  # jeżeli trafiliśmy na króla
            krole += 1  # liczymy go
            if krole == 4:  # jeżeli to ostatni król
                break  # koniec pasjansa

    # zliczamy ilość odkrytych godzin
    odkryte += sum(map(lambda x: x == [], zegar))

print(odkryte/ilosc_prob)

Modyfikacja jest niewielka: zamiast zliczać wygrane pasjanse, po każdym pasjansie zliczamy ilość odkrytych godzin.

Ile razy bym tego nie uruchamiał, zawsze wychodzi mi około 6.99. Czyli wykładając Zegar możemy się spodziewać, że odkryjemy siedem godzin zanim trafimy na ostatniego króla.

Wyjaśnienie sposobu liczenia odkrytych godzin:

Operator map działa tak, że wywołuje zadaną funkcję dla każdego elementu zadanej listy i zwraca listę wyników. W naszym przypadku listą jest zegar po zakończeniu pasjansa, a funkcją jest sprawdzenie, czy element listy jest sam w sobie pustą listą (x == []). Na końcu sumujemy wynik. Operator porównania zwraca True / False, które są traktowane przez sum jako 1 / 0.

Pchełki Python: plotka w totka

Natrafiłem gdzieś niedawno na informację, że w jednym z krajów w Afryce podobno doszło do przekrętu, bo w loterii padły liczby 5, 6, 7, 8, 9, 10.

Pomyślałem sobie, jakie jest prawdopodobieństwo wylosowania pięciu sąsiednich liczb spośród… no właśnie, spośród ilu? Przyjąłem roboczo, że spośród 49.

Pierwszą liczbę możemy wybrać na 49 sposobów. Drugą na 48, trzecią na 47 i tak dalej, aż do szóstej. Razem około dziesięciu miliardów kombinacji:

44 * 45 * 46 * 47 * 48 * 49 = 10 068 347 520

Ile spośród nich składa się z sześciu sąsiadujących liczb?

Sąsiadujące liczby ustawione w kolejności od najmniejszej do największej można uzyskać na 44 sposoby: począwszy od (1,2,3,4,5,6) aż do (44,45,46,47,48,49).

Każdy z tych 44 sposobów ma dodatkowo 6! = 720 permutacji (przestawień). A więc łącznie mamy 44 * 720 = 31 680 układów liczb sąsiadujących ze sobą. Szansa trafienia na jeden z nich wynosi:

31 680 / 10 068 347 520 = 0.000000314649449

Mniej więcej trzy dziesięciomilionowe. Jeżeli zagramy w totka dziesięć milionów razy, natrafimy na układ sześciu kolejnych liczb mniej więcej trzy razy.

Jak długo trzeba grać, żeby trafić chociaż raz?

Oczywiście, nie wiadomo. Szansa za każdym razem jest taka sama: około trzy na dziesięć milionów. Wiadomo jednak, że przy odpowiednio długim graniu prędzej czy później trafimy na jeden z tych 31680 układów.

Ile to jest “odpowiednio długo”?

Nie da się uzyskać gwarancji, że po N próbach trafimy. Ale można spróbować policzyć ile tych prób powinno być, żeby szansa trafienia była, dajmy na to, 99%. Jak to zrobić? Jeżeli szansa nie trafienia w jednej próbie wynosi (1 – 31680/10068347520) czyli około 0.99999685350550951185, to przy dwóch próbach będzie to (1 – 31680/10068347520)2 czyli około 0.99999370702091945128. Różnica niewielka. Ale nie wolno nie doceniać potęgowania: przy odpowiednio dużej liczbie prób uzyskamy wreszcie prawdopodobieństwo nie trafienia mniejsze niż 0.01.

Metodą prób i błędów (chociaż pewnie dałoby się prościej, logarytmem) sprawdziłem, że:

(1 – 31680/10068347520)1463586 = 0.009999976555193245

natomiast

(1 – 31680/10068347520)1463585 = 0.010000008020163384

Tak więc grając 1463586 razy mamy 99% szans na to, że gdzieś tam trafimy pięć sąsiednich liczb.

Na koniec spróbujemy sobie to zasymulować w Pythonie:

from random import sample
data = [x for x in range(1, 50)]
while 1 == 1:
    c = 0
    minr = 48
    while minr > 5:
        c += 1
        s = sample(data, 6)
        mr = max(s) - min(s)
        if mr < minr:
            minr = mr
    print(c, end=" ")

Uruchomienie powyższego kodu na kilkanaście godzin (ponad 32000 wykonań dużej pętli) dało mi na wyjściu trochę liczb, podstawowe statystyki:

  • W ekstremalnych przypadkach udało się uzyskać trafienie po 35 losowaniach (minimum) oraz po 3 999 695 losowaniach (maksimum).
  • Średnio trafienie następowało po 318K losowań
  • Mediana w okolicy 221K losowań

Wnioskuję stąd, że gdyby w owym afrykańskim kraju loteria odbywałaby się codziennie, to trzeba by czekać na uzyskanie takiego wyniku gdzieś między 650 a 1000 lat. Zakładając rzecz jasna, że losujemy spośród 49 liczb, a nie, dajmy na to, 20 albo 100.

Wniosek?

Brak 😉 Może był tam jakiś przekręt, może nie… Z prawdopodobieństwem tak już jest.

Pchełki Python: 15999

Bierzemy liczbę naturalną, następnie każdą jej cyfrę podnosimy do kwadratu, kwadraty sumujemy, wynik sumowania poddajemy tej samej operacji i tak do oporu. Co wyjdzie na końcu? I w ogóle to na jakim “końcu”, przecież może się toto rozjedzie w nieskończoność? Czemu taki dziwny tytuł wpisu jest? O sssso chozzzi?

Okazuje się, że od jakiej liczby byśmy nie zaczęli (mogą nawet być lemowe centygigaheptatrybilionardy), zawsze zejdziemy albo do jedynki, albo do czwórki. Przy czym jedynka się zapętla sama na sobie, a czwórka daje pętlę ośmioelementową 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4

Wygląda znajomo?

No bo już kiedyś o tym pisałem 😉 Tylko że wtedy podany kod był napisany w Powershell, a dziś pokażę jak to samo uzyskać w Pythonie:

def suma_kwadratow_cyfr(n):
    return sum(int(cyfra)**2 for cyfra in str(n))


def iteracje(n):
    i = 0
    while(not n in (1, 4)):
        i += 1
        n = suma_kwadratow_cyfr(n)
    return(i)


maksiter = -1
for n in range(1, 1000000):
    iter = iteracje(n)
    if(iter > maksiter):
        print(n, iter)
        maksiter = iter

Wynik:

1 0
2 1
3 11
6 13
88 14
269 15
15999 16

Dzisiejszy temat (w tym również część kodu w Pythonie) zerżnąłem bezwstydnie od jednego z moich ulubionych blogerów: https://www.johndcook.com/blog/2020/02/28/sum-of-squared-digits/ – w wolnym czasie zapraszam do zapoznania się z innymi jego materiałami, facet pisze całkiem ciekawie i bardzo, bardzo konkretnie.

Pchełki Python: zabawa w gematrię

Gematria, wynalazek pochodzący z czasów starożytnej Babilonii, spopularyzowała się głównie za sprawą Żydów. Oni bowiem zaczęli kombinować nad znaczeniem wartości liczbowych poszczególnych słów i zdań w Biblii wyliczonych jako suma wartości pojedynczych liter.

My się dziś Biblią bawić nie będziemy, ale pomysł z ponumerowaniem liter jest całkiem niezły – spróbujemy sobie dziś znaleźć liczbę, która reprezentuje samą siebie.

Zaczniemy od początku:

  1. Bierzemy alfabet polski (czyli ze wszystkimi ogonkami, ale za to bez q, v i x) – razem 32 litery
  2. Każdej literze przypisujemy wartość będącą numerem kolejnym danej litery w alfabecie. Czyli A=1, Ą=2, B=3 i tak dalej aż do Ż=32
  3. Bierzemy liczbę 1, zapisujemy ją słownie: JEDEN.
  4. Liczymy: J + E + D + E + N = 13 + 7 + 6 + 7 + 18 = 51
  5. Bierzemy następną liczbę: DWA
  6. D + W + A = 6 + 28 + 1 = 35

I tak dalej. Czy trafimy w końcu na liczbę, której suma wartości liter będzie się równać tej właśnie liczbie? Jeżeli tak, co to za liczba?

A czy jest liczba, której suma liter jest dwukrotnie większa od niej samej? A trzykrotnie? A dziesięciokrotnie?

Zaczniemy od przypadku trywialnego, czyli poszukamy liczby, której litery sumują się [1] do niej samej.

[1] Powinienem napisać “której wartości liter sumują się”, ale jestem za leniwy.

Żeby nie wynajdować koła, skorzystamy z gotowej biblioteki przekształcającej liczbę na tekst. Biblioteka autorstwa Jakuba Wilka, instalujemy za pomocą PIP:

Teraz już możemy przystąpić do zabawy właściwej:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"

for i in range(1000):
    s = slownie(i)
    if(sum([litery.index(litera) for litera in s]) == i):
        print(s)

Objaśnienie dla spostrzegawczych: alfabet zacząłem od spacji, co daje nam podwójną korzyść: po pierwsze spacja ma wartość zero, a po drugie litera “A” ma wartość jeden, czyli dokładnie tak, jak powinno być.

Powyższy kod wyrzuci nam na ekran tylko jedną linijkę:

dwieście dziewięć

Faktycznie:

D + W + I + E + Ś + C + I + E + D + Z + I + E + W + I + Ę + Ć = 6 + 28 + 12 + 7 + 25 + 4 + 12 + 7 + 6 + 30 + 12 + 7 + 28 + 12 + 8 + 5 = 209

Spróbujmy sobie teraz skomplikować życie i poszukajmy liczb, których litery zapisu słownego sumują się do ich wielokrotności. W tym celu wprowadzimy sobie mnożnik od 1 do 200 i posprawdzamy:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"

for i in range(100000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    for mnoznik in range(1, 201):
        if(suma * mnoznik == i):
            print(s, "=", suma, "*", mnoznik)

Tu już program wypluje nam całkiem sporo bo aż 153 trafienia:

dwieście dziewięć = 209 * 1
tysiąc pięćset trzydzieści dziewięć = 513 * 3
dwa tysiące pięćset dwa = 278 * 9
dwa tysiące dziewięćset czterdzieści = 490 * 6
trzy tysiące sto sześćdziesiąt dwa = 527 * 6
trzy tysiące dwieście osiemdziesiąt dwa = 547 * 6
trzy tysiące sześćset = 360 * 10
cztery tysiące sześćset dziewięćdziesiąt siedem = 671 * 7
pięć tysięcy dwieście osiemdziesiąt trzy = 587 * 9
pięć tysięcy czterysta dwanaście = 451 * 12
(bla, bla, bla...)
dziewięćdziesiąt trzy tysiące pięćset siedemdziesiąt trzy = 843 * 111
dziewięćdziesiąt trzy tysiące osiemset osiem = 656 * 143
dziewięćdziesiąt trzy tysiące dziewięćset pięćdziesiąt pięć = 817 * 115
dziewięćdziesiąt pięć tysięcy trzysta czterdzieści dziewięć = 859 * 111
dziewięćdziesiąt pięć tysięcy pięćset osiemdziesiąt dziewięć = 817 * 117
dziewięćdziesiąt sześć tysięcy sześćset czterdzieści dwa = 819 * 118
dziewięćdziesiąt siedem tysięcy dziewięćset dwadzieścia dziewięć = 837 * 117
dziewięćdziesiąt osiem tysięcy sto trzy = 617 * 159
dziewięćdziesiąt osiem tysięcy pięćset trzydzieści dwa = 782 * 126

A co jeżeli przypiszemy literom wartości w odwrotnej kolejności? Czyli od Ż = 1 do A = 32?

from slownie import slownie

litery = "aąbcćdeęfghijklłmnńoóprsśtuwyzźż "[::-1]

for i in range(10000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    if(suma == i):
        print(s)

Okazuje się, że tu są dwa trafienia:

czterysta dwadzieścia dwa
czterysta dziewięćdziesiąt dwa

Oczywiście możliwości są nieskończone. Można na przykład przypisać kolejnym literom wartości odpowiadające kolejnym liczbom pierwszym, a więc A=2, Ą=3, B=5, C=7, Ć=11 i tak dalej aż do Ż=137:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"
pierwsze = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137]

for i in range(50000):
    s = slownie(i)
    suma = sum([pierwsze[litery.index(litera)] for litera in s])
    if(suma == i):
        print(s)

(zero na początku listy ma tu takie samo działanie jak spacja na początku alfabetu – patrz objaśnienie powyżej)

Wynik:

tysiąc pięćdziesiąt jeden
tysiąc sześćset siedemdziesiąt jeden

Jeżeli odwrócimy alfabet (A=137, Ą=131, B=127 aż do Ż=2), dostaniemy:

from slownie import slownie

litery = "aąbcćdeęfghijklłmnńoóprsśtuwyzźż "[::-1]
pierwsze = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137]

for i in range(50000):
    s = slownie(i)
    suma = sum([pierwsze[litery.index(litera)] for litera in s])
    if(suma == i):
        print(s)

Wynik: brak!

Można też całkiem od czapy ponadawać kolejnym literom wartości odpowiadające kolejnym cyfrom liczby Pi:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"
pi = [0,3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5]

for i in range(50000):
    s = slownie(i)
    suma = sum([pi[litery.index(litera)] for litera in s])
    if(suma == i):
        print(s)

Wynik:

dziewięćdziesiąt

… albo zastąpić Pi podstawą logarytmu naturalnego:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"
e = [0,2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,6,0,2,8,7,4,7,1,3,5,2,6]

for i in range(50000):
    s = slownie(i)
    suma = sum([e[litery.index(litera)] for litera in s])
    if(suma == i):
        print(s)

Wynik:

osiemdziesiąt siedem

… albo policzyć sumę kwadratów…

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"

for i in range(100000):
    s = slownie(i)
    suma = sum([litery.index(litera)**2 for litera in s])
    if(suma == i):
        print(s)

Wynik:

jedenaście tysięcy osiemset siedemdziesiąt dwa

… albo kwadrat sumy…

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"

for i in range(500000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    if(suma**2 == i):
        print(s)

Wynik:

dwieście pięćdziesiąt jeden tysięcy jeden

… albo poustawiać litery tak, że najpierw idą wszystkie samogłoski a dopiero potem spółgłoski…

from slownie import slownie

litery = " aąeęioóuybcćdfghjklłmnńprsśtwzźż"

for i in range(100000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    if(suma == i):
        print(s)

Wynik:

sto pięć
trzysta siedemdziesiąt pięć
czterysta sześćdziesiąt trzy

… albo na odwrót…

from slownie import slownie

litery = " bcćdfghjklłmnńprsśtwzźżaąeęioóuy"

for i in range(100000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    if(suma == i):
        print(s)

Wynik: brak 🙂

… albo brać liczby parami i sprawdzać czy suma liter w parze jest równa sumie pary:

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"

for i in range(1000):
    for j in range(i, 1000):
        s1 = slownie(i)
        s2 = slownie(j)
        s = s1 + " " + s2
        suma = sum([litery.index(litera) for litera in s])
        if(suma == i + j):
            print(s1, ",", s2)

Wynik:

zero , czterysta sześćdziesiąt
dwa , dwieście siedem
dwa , czterysta dwadzieścia sześć
cztery , czterysta cztery
[...]
czterysta trzydzieści dziewięć , czterysta dziewięćdziesiąt jeden
czterysta czterdzieści trzy , czterysta dziewięćdziesiąt osiem
czterysta czterdzieści osiem , czterysta dziewięćdziesiąt trzy
czterysta czterdzieści dziewięć , czterysta pięćdziesiąt dziewięć
czterysta osiemdziesiąt trzy , czterysta dziewięćdziesiąt dziewięć
czterysta osiemdziesiąt dziewięć , czterysta dziewięćdziesiąt trzy

(łącznie 341 kombinacji)

Ciekawe która z liczb mniejszych od sumy własnych liter jest największa…

from slownie import slownie

litery = " aąbcćdeęfghijklłmnńoóprsśtuwyzźż"
maxsuma, maxi = 0, 0
for i in range(100000):
    s = slownie(i)
    suma = sum([litery.index(litera) for litera in s])
    if(i > maxi and i < suma):
        maxsuma, maxi = suma, i
print(maxi, maxsuma)

Wynik:

499 505

499 czyli “czterysta dziewięćdziesiąt dziewięć” po zsumowaniu wartości liter daje 505 i to jest największa liczba mniejsza od sumy swoich liter. Fascynujące, prawda?

W zasadzie mógłbym ten wpis ciągnąć jeszcze przez dobre trzy godziny (liczby można przedstawiać w różnych językach!), ale mi się już znudziło 🙂

A więc – kończymy.

Albo nie, jeszcze jedno: jaka jest najmniejsza dodatnia liczba, której suma wartości liter daje aktualny numer roku (2020)?

Mi się udało znaleźć 13269499994 (trzynaście miliardów dwieście sześćdziesiąt dziewięć milionów czterysta dziewięćdziesiąt dziewięć tysięcy dziewięćset dziewięćdziesiąt cztery) – ale pewnie przy odrobinie sprytu dałoby się znaleźć mniejszą…

Pomysły?

Pchełki Python: opowieść o najsłynniejszym żuku dwudziestego wieku

Miałem cztery lata, kiedy matematycy po raz pierwszy podali definicję tego zbioru. Dwa lata później udało się zaprząc komputery do wykonania wizualizacji zbioru, a po kolejnych dwóch latach zbiorowi nadano oficjalnie nazwę “zbiór Mandelbrota”, na cześć Benoit Mandelbrota, francusko-amerykańskiego matematyka (urodzonego, ciekawostka, w Polsce!). Benoit zajmował się fraktalami i opublikował na ich temat całkiem sporo fachowej literatury.

Z większej odległości zbiór Mandelbrota może się kojarzyć z żukiem. Ma duży tułów (z dwoma półokrągłymi półdupkami), mniejszą głowę oraz mnóstwo nóżek ze wszystkich stron. Trzeba oczywiście przymknąć oko na dodatkowe, coraz mniejsze głowy wystające tu i ówdzie, ale ogólnie podobieństwo do żuka jakieś tam jest.

Od strony matematycznej Żuk reprezentuje obszar stabilności pewnego całkiem prostego przekształcenia zespolonego.

Tak, wiem, ja sam na widok słowa “zespolony” przeważnie uciekam na drugi koniec, nigdy tak do końca nie przetrawiłem tego kawałka matematyki. Ale tu jest naprawdę prosto.

Otóż tak: bierzemy dowolną liczbę zespoloną P.

Następnie bierzemy liczbę zespoloną Z równą 0 (a konkretnie 0 + 0i)

I teraz tak: podnosimy Z do kwadratu, do wyniku dodajemy P i to co wyjdzie zapisujemy jako, uwaga, Z.

Po czym powyższy krok powtarzamy w nieskończoność.

Jeżeli po wykonaniu nieskończonej liczby kroków wyjdzie nam w wyniku jakaś konkretna liczba, to uznajemy punkt P za stabilny.

Punkt? Jaki, kurdę, punkt? Przecież P to liczba jest!

Liczba, owszem, ale zespolona, czyli składająca się z rzeczywistego iksa oraz urojonego igreka. A jak jest iks i igrek to już mamy dwie współrzędne, czyli punkt na płaszczyźnie.

Jeżeli natomiast po wykonaniu nieskończonej liczby kroków dostaniemy w wyniku nieskończoność (dodatnią bądź ujemną, bez znaczenia), uznajemy punkt P za niestabilny.

I teraz tak: jeżeli punkt P jest stabilny, rysujemy go na czarno, a jeżeli nie – na kolorowo. Kolor uzależniamy od stopnia niestabilności, czyli tego, jak szybko (w ilu krokach) dany punkt dotarł do nieskończoności.

Następnie bierzemy kolejny punkt P (jakiś inny) i powtarzamy cały proces od zera (dosłownie!). Czyli ustawiamy Z na 0 + 0i i zaczynamy wyliczać Z^2+P, a to co wyjdzie podstawiamy do Z i zapętlamy do nieskończoności. Powtarzamy powyższe dla wszystkich punktów na płaszczyźnie.

Czujny Czytelnik powinien teraz zakrzyknąć w myślach: “ten gość bredzi!”

Proszę bardzo, krzyczymy: “ten gość bredzi!”

Nie martwcie się. Nie obrażam się za takie coś, zresztą przywykłem już 😉

Po pierwsze, nie da się policzyć nieskończonej ilości punktów. Skończy nam się ilość pamięci w komputerze, potem Słońce zgaśnie i Wogle. No nie da się.

Po drugie nawet dla pojedynczego punktu nie da się wykonać nieskończonej ilości kroków. Czas się skończy, pamięć, Kosmos, takie tam…

Po trzecie, jak to “w ilu krokach punkt dotarł do nieskończoności”?!? No przecież że po nieskończonej, c’nie? Więc jak to jest z tym kolorem?

Skoro nie radzimy sobie za bardzo z nieskończonościami, zamiast tego musimy proces uprościć. Zbudować model.

Jak powiedział kiedyś jeden mądry facet:

Żaden model nie jest dokładny. Niektóre modele są użyteczne.

No dobra. Czyli tak: zamiast dla każdego punktu wyliczać nieskończenie wiele kroków, wyliczymy ich tylko pięćdziesiąt.

Czemu akurat tyle?

Bo jeżeli weźmiemy mniej niż pięćdziesiąt, przybliżenie będzie raczej niedokładne, a jeżeli weźmiemy dużo więcej, będziemy musieli długo czekać na wyniki. Pięćdziesiąt to dobry kompromis między jednym a drugim. Jeżeli ktoś ma szybki komputer (albo dużo czasu), może poeksperymentować z większymi wartościami.

Problem z nieskończoną ilością iteracji mamy załatwiony.

Drugi problem to jak po pięćdziesięciu krokach stwierdzić, czy dany punkt doszedł do nieskończoności czy nie?

Tu w sukurs przychodzi nam całkiem zaawansowana matematyka, której nie będę prezentował w szczegółach, bo sam jej do końca nie rozumiem, ale która mówi, że jeżeli po którymś z kroków |Z^2+P| przekroczy 2, to już będzie rosło w nieskończoność.

A więc zamiast sprawdzać, czy dotarliśmy do nieskończoności, wystarczy sprawdzić czy przekroczyliśmy dwójkę. Jeżeli tak, punkt jest z całą pewnością niestabilny. Jeżeli nie… No cóż. Jeżeli nie, to *raczej* jest stabilny, ale tak naprawdę to nie wiadomo. Czym więcej iteracji, czym większa dokładność, jednak stuprocentowej pewności nigdy mieć nie będziemy. Ale nie szkodzi. To tylko model. Przybliżenie w zupełności wystarczy.

Ostatni, trzeci problem to jak policzyć to draństwo dla wszystkich punktów na płaszczyźnie? Przecież jest ich całkiem sporo (nieskończenie wiele!), w dodatku są cholernie gęsto upakowane (nieskończenie gęsto!). Hmmm.

Rozwiązaniem tego problemu jest (a) wziąć pod uwagę tylko niektóre punkty (jeden piksel na ekranie to jeden piksel, gęściej nie narysujemy) oraz (b) wybrać sobie tylko fragment płaszczyzny. Ten najbardziej interesujący rozciąga się w poziomie od -2 do 0.8 oraz w pionie od -1.3 do 1.3.

Jeżeli do tego założymy, że nasz obrazek ma mieć rozdzielczość, dajmy na to, 600×600 pikseli, to będziemy musieli wykonać obliczenia dla 360 tysięcy pikseli, dla każdego z nich maksymalnie 50 iteracji, co daje razem… niecałe 18 milionów operacji.

Na papierze, z ołówkiem byłoby to raczej kłopotliwe. Ale komputery radzą sobie z takimi liczbami całkiem sprawnie.

Czas na kod:

from PIL import Image, ImageDraw
LimitIteracji = 50

# wymiary obrazka w pikselach
PikselePoziomo = 600
PikselePionowo = 558

# współrzędne kartezjańskie - granice obszaru
xStart = -2
xKoniec = 0.8
yStart = -1.3
yKoniec = 1.3


def mandelbrot(punkt):
    z, kroki = 0, 0
    while abs(z) < = 2 and kroki < LimitIteracji:
        z = z*z + punkt
        kroki += 1

    return kroki


# wybieramy HSV zamiast RGB żeby łatwiej było sterować kolorem
# # (w HSV o kolorze decyduje wyłącznie H,
# natomiast S i V mówią jak bardzo kolor jest nasycony i jasny)
obrazek = Image.new('HSV', (PikselePoziomo, PikselePionowo), (0, 0, 0))
kredka = ImageDraw.Draw(obrazek)

for x in range(0, PikselePoziomo):
    for y in range(0, PikselePionowo):
        # Skalujemy współrzędne pikseli ekranowych do współrzędnych rzeczywistych
        # oraz zamieniamy współrzędne rzeczywiste na liczbę zespoloną
        c = complex(xStart + (x / PikselePoziomo) * (xKoniec - xStart),
                    yStart + (y / PikselePionowo) * (yKoniec - yStart))
        # Wyliczamy liczbę iteracji
        m = mandelbrot(c)
        # kolor piksela zależy od liczby iteracji
        odcien = int(255 * m / LimitIteracji)
        # nasycenie ustawiamy na stałe na maksa
        nasycenie = 255
        # jasność maksymalna jeżeli piksel niestabilny, w przeciwnym razie zero (czarny)
        jasnosc = 255 if m < LimitIteracji else 0
        # stawiamy kropkę
        kredka.point([x, y], (odcien, nasycenie, jasnosc))

# po narysowaniu wszystkich pikseli, zapisujemy obrazek na dysk
obrazek.convert('RGB').save('output.png', 'PNG')

Powyższy kod uruchamiamy (może zajść potrzeba uprzedniego zainstalowania biblioteki Pillow – po szczegóły odsyłam do Google) a następnie zaglądamy do folderu ze skryptem – powinien tam pojawić się plik o nazwie output.png, z takim oto obrazkiem:

Piękny Żuk, prawda?

Po zwiększeniu limitu iteracji do 100 oraz podwojeniu wymiarów w pionie i w poziomie czeka się ciut dłużej, ale efekt jest jeszcze piękniejszy:

(najlepiej widać to na dużym monitorze – trzeba kliknąć prawym myszem w obrazek i otworzyć go w nowym okienku)

Przy 500 iteracjach oraz kolejnych zwiększeniu wymiarów 2x w każdym wymiarze efekt jest taki:

Z bliska wygląda to tak:

Można teraz, manipulując współrzędnymi oraz ilością iteracji, robić sobie dowolne zbliżenia – efekty są całkiem interesujące, ale o tym może już kiedy indziej.

Czytasz dalej?

Kolejna ciekawostka dotycząca Żuka jest taka, że są w nim “zakodowane” dwie bardzo słynne stałe matematyczne: Pi oraz Fi.

Pi zakodowana jest w sposób dość niezwykły: otóż jeżeli ustawimy się w punkcie (-3/4, 0) oraz zrobimy “zoom” o powiększeniu 10^x – krotnym (dajmy na to, dziesięć milionów razy, czyli 10^7), żeby narysować każdy piksel w tym powiększeniu, będziemy musieli wykonać Pi * 10^x iteracji (w tym przypadku: 31415928 iteracji).

Jeśli natomiast chodzi o Fi (złoty podział, te sprawy), to okazuje się, że sumy częściowe ilości “antenek” na okrągłych “głowach” Żuka kolejnych poziomów układają się w ciąg Fibonacciego.

Na koniec kilka obrazków z naprawdę dużym zoomem (pobrane z Wikipedii, a wygenerowane przez Wolfganga Beyera za pomocą programu UltraFractal 3):

Disklajmer: kod do dzisiejszej Pchełki ukradłem stąd. Trochę go spolszczyłem dla czytelności.

Dopisane półtora roku później: Żuk Mandelbrota jest też głównym tematem hipotezy MLC (skrót od Mandelbrot Locally Connected) mówiącej, że jest on lokalnie spójny (na nasze, w uproszeniu, że nie jest porozrywany na mniejsze kawałki, czyli z każdego miejsca na Żuku da się dotrzeć w każde inne miejsce bez opuszczania Żuka).

2019: rozwiązanie zagadki

Niedawno pojawiła się tu zagadka o liczbie 2019.

Zadanie polegało na podaniu pewnej właściwości tej liczby, której nie mają liczby od niej mniejsze (aż do okolic 1775) oraz większe (aż do okolic 2275).

Zamiast udzielić odpowiedzi cywilizowanej, podaję kod:

from itertools import product

liczby = set()
for podstawa, wykladnik in product(range(1, 16), range(2, 8)):
    if(podstawa**wykladnik <= 243):
        liczby.add(podstawa**wykladnik)
liczby = list(liczby)
liczby.sort()
print(' + '.join(str(x) for x in liczby), end=' = ')
print(sum(liczby))

Kliknij tutaj aby zobaczyć powyższy kod w akcji

(na smartfonie najlepiej obrócić ekran do poziomu, ale najlepiej jednak oglądać na dużym ekranie)

Pchełki Python: zaprzeczenie pętli

Pythona używam rzadko. Prawdę powiedziawszy nigdy jeszcze nie miałem okazji napisać linijki kodu w tym języku dla któregokolwiek z moich pracodawców. Czasem zerknę w jakiś kod źródłowy, żeby “być na bieżąco”. Czasem dla hecy napiszę parę prościutkich linijek. Póki co więcej mi nie potrzeba.

Python jest zwarty, elegancki, niezwykle popularny, wymusza poprawne formatowanie kodu (wcięcia!) oraz – co najważniejsze – jest aktywnie rozwijany. Ma też oczywiście wady: jest wysokopoziomowy (a więc względnie wolny), mało popularny na platformach mobilnych (Android, IOS), jest późno typowany (typy zmienych i wyrażeń są ustalane na etapie wykonania programu, a nie kompilacji) przez to uczy początkujących programistów złych nawyków, a także ułatwia popełnianie błędów związanych z rzutowaniem typów.

Jednak lubię ten język i od czasu do czasu przeglądam sobie różne materiały on-line, z czystej ciekawości.

Niedawno trafiłem na perełkę, która wprawiła mój mózguł (nie łudzę się, że mam więcej niż jeden) w lekkie zdziwienie.

Otóż okazuje się, że operatora ELSE można w Pythonie używać nie tylko jako uzupełnienia bloku IF, ale także jako dodatku do pętli FOR.

Żeby było śmieszniej (ale nie jest), działanie tego operatora w przypadku pętli FOR jest zgoła przeciwne do tego, co podpowiada nam intuicja. O ile bowiem – i jest to prawdą nie tylko w Pythonie, ale w większości języków programowania implementujących ten paradygmat – blok IF-ELSE oznacza “Wykonaj ten kawałek kodu pod takim to a takim warunkiem, w przeciwnym razie wykonaj tamten kawałek”, o tyle w Pythonie blok FOR-ELSE oznacza: “Wykonaj pętlę FOR, a potem, o ile pętla zakończyła się bez używania operatora BREAK – wykonaj również ten kawałek po ELSE”.

Innymi słowy – zamieszanie.

Jednak użyteczność tej konstrukcji, chociaż jej składnia może nieco razić, jest niezaprzeczalna. Weźmy taki przykład:

from math import sqrt, ceil


def is_prime(n: int):
    if(n < 3):
        return(n == 2)

    if(n % 2 == 0):
        return(False)
    else:
        for d in range(3, ceil(sqrt(n)), 2):
            if(n % d == 0):
                break
        else:
            return(True)
    return(False)
Funkcja is_prime to naiwna implementacja algorytmu sprawdzającego pierwszość liczby. Najpierw “obsługuje” przypadki szczególne (0, 1, 2), potem parzystość, a na koniec zabiera się za sprawdzanie, czy liczba dzieli się przez którąkolwiek z liczb nieparzystych począwszy od trójki aż do pierwiastka ze sprawdzanej liczby (zaokrąglonego w górę do pełnej całości).

Przy okazji: tutaj opisałem algorytm o wiele potężniejszy.

Najbardziej interesujący jest tutaj ten kawałek:

        for d in range(3, ceil(sqrt(n)), 2):
            if(n % d == 0):
                break
        else:
            return(True)
    return(False)
Pętla for wykonuje się dopóty, dopóki nieparzysta liczba d (dzielnik) nie przekroczy pierwiastka z liczby sprawdzanej (zaokrąglonego w górę), chyba że natrafimy na podzielnik – wtedy kończymy pętlę for za pomocą break. Blok else natomiast wykona się *wyłącznie* wtedy, jeżeli zakończenie pętli for nastąpiło w sposób “naturalny” (a więc jeżeli zostały wykorzystane wszystkie dostępne wartości zmiennej d i nie natrafiono na operator break).

Gdybyśmy nie mieli do dyspozycji owego else (bądź czegoś analogicznego), wówczas musielibyśmy uciekać się do tworzenia flagi (dodatkowej zmiennej), która mówiłaby nam, czy wyjście z pętli nastąpiło w wyniku znalezienia podzielnika, czy wyczerpania wiaderka z podzielnikami.

Nudne, prawda?