Pomysł na wprowadzenie do programowania w Pythonie pojawił się po meetupie - Od humanisty do programisty. Załóżmy, że już trochę wiesz o programowaniu. Przydałoby się jakieś ciekawe zadanie... Tak się składa, że mam coś. Na pierwszy rzut oka bardzo trudne, ale jak się dobrze przyjrzeć - do zrobienia.
Kiedyś, w telewizji były popularne teleturnieje, gdzie uczestnik wygrywał, jeżeli prawidłowo wybrał jedną, z 3 bramek. Co ciekawe, po pierwszym wyborze prowadzący odsłaniał jedną z niewybranych bramek i pozwalał zmienić początkowy wybór... Zadanie, o którym mówię polega na znalezieniu odpowiedzi - czy opłaca się zmienić, czy trwać przy początkowym wyborze?
Jak podejść do problemu?¶
Takie zadanie brzmi dość abstrakcyjnie. Być może trzeba użyć jakiejś zaawansowanej biblioteki do liczenia prawdopodobieństwa. Co gorsze - rozwiązywanie problemów, przy pomocy komputera jest dość specyficzne.
Oczywiście można policzyć, ale to wymaga znajomości probabilistyki i trzeba też umiejętnie zdefiniować problem.
Na szczęście komputer liczy szybko i można przeprowadzić na przykład 1000 eksperymentów. Średnio połowa będzie zawierała zmianę bramki, a przy takiej próbce wynik powinien być dość jednoznaczny. Tak duża ilość prób pokaże wzorzec i szybko zorientujemy się jaka jest odpowiedź. A może wynik będzie pokaże równe szanse w obu przypadkach?
Z polskiego na nasze¶
Zawsze są 3 bramki. Tylko jedna bramka skrywa wygraną. Nie ma podglądania.
Kroki do wykonania:
- Losujemy, gdzie jest wygrana. Czyli wybieramy bramkę 1,2, lub 3 - jako wygrywającą.
- Pierwszy wybór uczestnika: losujemy jedną z 3 bramek.
- Prowadzący odsłania bramkę. Tu są dwie opcie:
- jeżeli uczestnik wybrał bramkę, która wygrywa to odsłaniamy losową z pozostałych,
- w innym wypadku - jest jedna pusta do odsłonięcia.
- Losujemy decyzję o zmianie.
- Sprawdzamy wynik.
Krok 3 można zrobić tak, że losujemy jedną z bramek, których użytkownik nie wybrał - jeżeli jest pusta to pokazujemy, jeżeli nie to pokazujemy drugą bramkę.
Narzędzia¶
Zanim przejdę do kodu chciałbym zwrócić uwagę narzędzia. W zasadzie - są cztery:
- Edytor tekstu.
- ipython3 - i od interactive.
- www.pythontutor.com.
- jupyter.
Edytor tekstu - może to być notatnik - chodzi o, wygodę wpisania tego, co chcemy i co jest nam potrzebne. Być może środowisko programistyczne, które użyje kolorów do poprawy czytelności wpisanego kodu, albo też podpowie to i owo jest lepsze, ale na początek - notatnik w zupełności wystarczy.
ipython3 - można użyć też samego python3. Osobiście wolę ipython3 - jest to narzędzie przygotowane do wykonywania pojedynczych poleceń, w trybie interaktywnym, czyli z założenia, z człowiekiem. Zawiera więc szereg prostych udogodnień - np. TAB podpowiada, strzałka w górę przenosi do poprzedniego polecenia, Ctrl-r pozwala szukać w wykonanych poleceniach - jeżeli strzałka w górę wymaga przeklikania się przez długą listę, używa koloru do poprawienia czytelności - słowem są plusy. Z drugiej strony - oba narzędzia służą do tego samego - można wykonywać kod.
Python - za równo ipython3, jak i python3 ma w sobie, zawsze dostępny system pomocy. Do poruszania się po nim służą dwa polecenia dir(), help(). Konkretnie - zróbmy zmienną a, zawierającą pusty ciąg znaków. Na pytanie, jakie metody ma tak utworzony ciąg znaków dostarczy nam dir. Druga funkcja, help() pokaże pomoc dla danej metody. Dla przykładu, żeby sprawdzić co robi funkcja find() - można wpisać: help(a.find). Poniżej przykładowe wykonanie tego, co opisałem:
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
Type "copyright", "credits" or "license" for more information.
IPython 5.5.0 -- An enhanced Interactive Python.
? -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help -> Python's own help system.
object? -> Details about 'object', use 'object??' for extra details.
In [1]: a=''
In [2]: dir(a)
Out[2]:
['__add__',
'__class__',
'__contains__',
'__delattr__',
'__dir__',
'__doc__',
'__eq__',
[.................]
In [3]: help(a.find)
Help on built-in function find:
find(...) method of builtins.str instance
S.find(sub[, start[, end]]) -> int
Return the lowest index in S where substring sub is found,
such that sub is contained within S[start:end]. Optional
arguments start and end are interpreted as in slice notation.
Return -1 on failure.
Trzecie narzędzie, jak łatwo wywnioskować pozwala na programowanie w przeglądarce. Program jest wykonywany w krokach, a działanie każdego kroku jest przedstawiane w formie wizualnej. Chyba trzeba zobaczyć, żeby zrozumieć. To bywa bardzo pomocne, szczególnie, gdy program działa inaczej niż zamierzyliśmy, a szukanie błedu w kodzie nie przynosi zamierzonych rezultatów...
Elementy składowe¶
Przymierzając się do pisania programu dobrze jest określić z czego program będzie korzystał, jakie są kroki do wykonania, co może pójść źle - trochę jak w życiu.
Program będzie potrzebował listy 3 bramek. Bramkom można im przypisać różne cechy. I to jest informacja, którą musimy gdzieś zapisać, żeby się nie okazało, że pokazaliśmy bramkę wygrywającą... Cechy bramki: - wygrywająca, - odsłonięta przez prowadzącego, - wybrana za pierwszym razem, - wybrana za drugim razem. Można powiedzieć, że niektóre z tych cech się wykluczają, ale pamiętanie wszystkich pozwoli łatwiej wychwycić błędy.
Potrzebujemy listy z 3 elementami, każdy z nich to lista tego co działo się z bramką. Nawet jak lista list brzmi zawile - nie jest to takie straszne.
Idąc dalej - napotykamy problem losowania. Po angielsku "losowy" to "random". W Google więc wpisujemy "python random". U mnie pierwszy link prowadzi do dokumentacji, strona: https://docs.python.org/3/library/random.html Po przejrzeniu pasują dwie funkcje randint() i choice(). Pierwsza wylosuje liczbę całkowitą z zadanego przedziału. Druga - wybierze losowy element z zadanej sekwencji np. listy bramek. Pytanie, czy to zadziała?
Random to standardowy moduł Pythona, co oznacza, że nie trzeba doinstalowywać dodatkowych bibliotek. Niemniej, aby z niego skorzystać, należy go wpierw zaimportować. Do importowania modułów do naszego programu służy polecenie import. Wpisujemy: import random do naszego interpretera - ipython3 / python3. Po tym poleceniu mamy dostęp do wszystkiego, co oferuje ta biblioteka. Co zatem można zrobić? Proponuję użycie poleceń dir(random), help(random), help(random.choice), no i oczywiście, przydałoby się wykonać losowanie: random.randint(0,100) - dla pewności, można je wywołać kilka razy. Poniższy kod zawiera import i losowanie liczby z zadanego przedziału:
import random
a = random.randint(0, 100)
a
Ostatnia linijka jest tylko po to, żeby coś się pokazało na ekranie. Jeżeli nie rozumiesz co znaczy a = ..... - przeczytaj o zmiennych
Losowanie bramki wygrywającej¶
Można użyć funkcji choice(), a następnie, w wybranym elemencie, dopisać do listy informację, że bramka wygrywa:
import random
gates = [[], [], []] # 3 puste bramki
winning = random.choice(gates)
winning.append('winning')
Tu jednak pojawiają się dwa problemy. Pierwszy dość prozaiczny: fajnie byłoby coś jednak zobaczyć. Drugi jest taki, że to jest jedno losowanie, a ma być 1000.
Z jednym i drugim poradzimy sobie funkcjami.
Funkcja to taki podprogram, czyli teraz trzeba się zastanowić nad mniejszymi częściami - dokładnie tak jak się cały czas zastanawiamy nad całością.
Potrzebujemy funkcji, która weźmie gates i wypisze wartości. Do powyższego dopiszmy:
def printout():
print(gates)
A czy można wypisać używając samego: print(gates)? Można, oczywiście - sprawdzi się równie dobrze. Czasem jednak chciałoby się coś więcej wypisać i wtedy lepiej mieć jedno miejsce z wypisywaniem.
Druga funkcja lottery() będzie zawierać pojedynczą grę, żeby można ją było wykonać wiele razy:
def lottery():
winning = random.choice(gates)
winning.append('winning')
printout()
Wywołajmy zatem funcję lottery() 10 razy. Cały "program" wygląda wówczas tak:
import random
gates = [[], [], []] # 3 puste bramki
def printout():
print(gates)
def lottery():
clean()
winning = random.choice(gates)
winning.append('winning')
printout()
for i in range(10):
lottery()
No, prawie. Na plus, że zadziałało, coś wypisało, ale... jakieś to dziwne jeszcze jest. W pierwszym kroku jest jeden napis winning, w drugim dwa, potem trzy... Aaa, no tak... nie ma czyszczenia stanu gry! Nie nadpisujemy wyniku poprzedniej gry, więc widać, że kolejne wykonania tylko się dopisują. O pętli for możesz przeczytać tu.
Wracając do zadania - dodajmy czyszczenie zmiennej gates:
import random
gates = [[], [], []]
def clean():
gates = [[], [], []]
def printout():
print(gates)
def lottery():
clean()
winning = random.choice(gates)
winning.append('winning')
printout()
for i in range(10):
lottery()
I co? I jak? U Was też nie działa? Spokojnie - to normalne; gates można używać, zmieniać, ale ze środka funkcji, tak po prostu nie da się zmienić wskazania na zmienną. Dokładniej w funkcji clean przypisanie powoduje, że zostanie utworzona nowa zmienna gates, która zniknie po zakończeniu tej funkcji, a globalna zmienna gates - pozostaje niezmieniona. Można rozwiązać problem na dwa sposoby - dodać global gates, albo wyczyścić i dodać puste listy. Tu jest kod, który dodaje global gates - u mnie działa:
import random
gates = [[], [], []]
def clean():
global gates
gates = [[], [], []]
def printout():
print(gates)
def lottery():
clean()
winning = random.choice(gates)
winning.append('winning')
printout()
for i in range(10):
lottery()
Program zaczyna nabierać kształtu. Może wiele nie robi, ale szkielet rozwiązania - jest.
Pierwszy wybór uczestnika¶
Skoro jest szkielet to trzeba wypełnić brakujące miejsca. Kolejnym krokiem po wyborze wygrwywającej bramki ma być "pierwszy wybór uczestnika".
Wylosujmy więc wybór uczestnikowi:
import random
gates = [[], [], []]
def clean():
global gates
gates = [[], [], []]
def printout():
print(gates)
def lottery():
clean()
winning = random.choice(gates)
winning.append('winning')
first_choice = random.choice(gates)
first_choice.append('first_choice')
printout()
for i in range(10):
lottery()
Sprawdzenie wyniku¶
Jak sprawdzić, czy uczestnik wygrał? W końcu to gra... Trzeba znać numer bramki wygrywającej i sprawdzić czy wybór gracza się z nim pokrywa. Brzmi jak kolejna funkcja. Przekażemy nazwę tego, czego szukamy, a funkcja odda indeks - czyli numer bramki, pod którym ona znajduje się na liście gates.
def get_index(label):
for i in range(len(gates)):
if label in gates[i]:
return i
return -1
Funkcja len zwraca długość - np. listy. range zwraca generator, listę kolejnych liczb, od zera do zadanej wartości -1. for i in .... przechodzi po liście, przypisuje kolejne wartości do i i wykonuje kolejny blok, gdzie i jest dostępne. gates[i] zwraca element z listy. a in [1,2,3] - zwraca True jeżeli wartość zmiennej a jest na liście. Skoro tak to zgodnie z tym, co wcześniej napisałem - zwracamy i. O for piszę w tym poście. Jeżeli if, True i całe sprawdzanie brzmi dziwnie - też można o tym poczytać.
Prosta symulacja¶
Pozostaje jeszcze dodać licznik, żeby wiedzieć ile jest wygranych, bez konieczności przeglądania 1000 wpisów. Oto kod:
import random
gates = [[], [], []]
count = 0
def clean():
global gates
gates = [[], [], []]
def printout():
print(gates)
def get_index(label):
for i in range(len(gates)):
if label in gates[i]:
return i
return -1
def lottery():
global count
clean()
winning = random.choice(gates)
winning.append('winning')
first_choice = random.choice(gates)
first_choice.append('first_choice')
printout()
if get_index('first_choice') == get_index('winning'):
count += 1
for i in range(1000):
lottery()
print(count / 1000)
Prawdopodobieństwo wylosowania jednej z trzech wartości to 1/3. Czyli działa.
Prowadzący odsłania wolną bramkę¶
Kolejny krok w procesie to zadanie prowadzącego, który odsłania jedną z pozostałych bramek. Z opisu wynikało, że to najbardziej skomplikowany krok. Trochę sprawdzania, ale z drugiej strony - szkielet jest.
Po kolei - jak ma wyglądać odsłanianie. Jeżeli uczestnik w pierwszym kroku wybrał bramkę z nagrodą - to można odsłonić którąkolwiek, z dwóch pozostałych. W innym wypadku... Skoro wiadomo, że wszystkich bramek jest trzy, jedna wybrana, jenda z nagrodą - to nie ma wątpliwości, że trzeba pokazać tę ostatnią.
Jest tylko jeden problem - jak stwierdzić, która bramka jest która, skoro za każdym razem wszystko jest losowane? Posłużymy się metodą remove(), która jest dostępna dla listy. Innymi słowy mogę przekazać element i zostanie on z listy usunięty. Tworzę więc listę dostpęnych opcji i usuwam indeksy tych bramek, które są do odrzucenia.
Kod, dla obu przypadków:
if get_index('first_choice') == get_index('winning'):
indices = [0, 1, 2]
indices.remove(get_index('winning'))
showed = random.choice(indices)
showed.append('showed')
else:
for i in range(len(gates)):
if [] == gates[i]:
gates[i].append('showed')
Mała uwaga. To, że zmienna indices ma numery bramek zaczynające się od zera. Jest jak najbardziej zamierzone. Wszystkie listy mają indeksy zaczynające się od zera. Czyli pierwszy element to tak na prawdę element zerowy.
Trudna decyzja¶
Prowadzący właśnie odsłonił, teraz kolej na uczestnika. Zmienia, czy nie? Do tej pory wszystkie decyzje losowaliśmy - nie inaczej będzie tym razem. Trzeba wylosować, czy uczestnik zmiana pierwotny wybór. Jeżeli tak to mamy jedną bramkę z pierwszego wyboru, drugą, odsłoniętą i trzecią do wybrania. Trick z listą i remove() ponownie się przyda:
indices = [0, 1, 2]
indices.remove(get_index('showed'))
indices.remove(get_index('first_choice'))
second_choice = gates[indices[0]]
second_choice.append('second_choice')
if get_index('second_choice') == get_index('winning'):
win_counters[change] += 1
Jeżeli zmiany nie ma, należy sprawdzić, czy pierwszy wybór okazał się wygrywający, ale to już znamy.
Trzeba jeszcze zapamiętać cztery liczniki. Daczego aż cztery? Całkowita liczba prób i liczba wygranych - dla dwóch opcji - ze zmianą i bez. Dwa razy dwa - razem cztery.
Ostatecznie skrypt, program wygląda tak:
import random
gates = [[], [], []]
total_counters = [0, 0]
win_counters = [0, 0]
def clean():
global gates
gates = [[], [], []]
def printout():
print(gates)
def get_index(label):
for i in range(len(gates)):
if label in gates[i]:
return i
return -1
def lottery():
clean()
winning = random.choice(gates)
winning.append('winning')
first_choice = random.choice(gates)
first_choice.append('first_choice')
if get_index('first_choice') == get_index('winning'):
indices = [0, 1, 2]
indices.remove(get_index('first_choice'))
showed = random.choice(indices)
gates[showed].append('showed')
else:
for i in range(len(gates)):
if not gates[i]:
gates[i].append('showed')
if random.randint(0, 1) == 1:
# zmiana!
change = 1
indices = [0, 1, 2]
indices.remove(get_index('showed'))
indices.remove(get_index('first_choice'))
second_choice = gates[indices[0]]
second_choice.append('second_choice')
if get_index('second_choice') == get_index('winning'):
win_counters[change] += 1
else:
# jednak bez zmiany
change = 0
if get_index('first_choice') == get_index('winning'):
win_counters[change] += 1
total_counters[change] += 1
printout()
for i in range(5000):
lottery()
print(win_counters[0] / total_counters[0])
print(win_counters[1] / total_counters[1])
Z przytoczonych na początku narzędzi nie opisałem ostatniego - Jupytera. Zabieg celowy. Ponieważ nawet jeśli ktoś nie ma zainstalowanego Pythona, to wciąż jet nadzieja! Można użyć właśnie Jupytera wybieramy "Try Jupyter with Python". Czekamy chwilę aż załaduje się repozytorium. "Welcome to Jupyter!" oznacza, że nasz arkusz online jest gotów. Z menu File wybieramy New Notebook, następnie Python3, wklejamy powyższy skrypt, klikamy przycisk Run - i sprawa jasna. Jeszcze tylko trochę trzeba przewinąć i odcyfrować - który wynik jest dla którego przypadku.
Warto też użyć wymienionego pythontutora. Można wykonać każdy krok programu - osobno przyglądając się co się zmienia.
Wytłumaczenie wyniku - wikiepedia - Monty Hall problem.