środa, 23 listopada 2016

Curling! Nareszcie

Nareszcie znalazłem jakąś grę curlingową, z rozsądną fizyką i grywalnością (multiplayer!).

http://www.playcurling.com/pl/

czwartek, 17 listopada 2016

Zbiór zadań Alkuina

Podczas czwartkowych wykładów dla przyszłych studentów na MIM UW pojawił się temat zagadek ze zbioru zadań mnicha Alkuina. Zbiór odnalazłem i do znalezienia tu: http://www-history.mcs.st-and.ac.uk/PrintHT/Alcuin_book.html

niedziela, 13 listopada 2016

Project Euler - problem 83

Zadanie 83 jest uogólnieniem zadania 82. Rozwiązanie z zadania 82 było na tyle ogólne, że jego mała modyfikacja pozwoliła rozwiązać zadanie 83.

Rozwiązanie (od razu z kolorowaniem i  żółwikiem):

# encoding=utf-8
from heapq import heappop, heappush, heapify
import turtle
import time
f = open("p082_matrix.txt")
lines = f.readlines()
matrix = [map(int, line.strip().split(",")) for line in lines]
N = len(matrix)  # matrix is square, [0..N-1] x [0..N-1] 
queue = [(matrix[0][0], 0, 0, None)]
heapify(queue)
dist = {}
# Ustawienia malowania
turtle.hideturtle()
turtle.penup()
turtle.tracer(0, 0)
turtle.colormode(255)
def nice_colors():
  step = 7
  x = y = z = 0
  while True:
    yield x, y, z
    if x >= 170 and y >= 255 and z >= 255:
      x = y = z = 0
    elif y == 255 and z == 255:
      y = z = 0
      x = min(x + 3 * step, 255)
    elif z == 255:
      z = 0
      y = min(y + 7 * step, 255)
    else:
      z = min(z + step, 255)    
color_generator = nice_colors()
def draw(wait, (row, col), color=None):
  if not color:
    color = next(color_generator)
  time.sleep(wait)
  turtle.setpos((col * 5 - 200, row * 5 - 200))
  turtle.dot(None, *color)
  turtle.update()
# Wyliczanie odległości i malowanie grafu przeszukiwania.
parent = {}
while queue:
  cost, row, col, prev = heappop(queue)
  curr = row, col
  if curr in dist:
    continue
  parent[curr] = prev
  dist[curr] = cost
  if row == N - 1 and col == N - 1:
    break
  if col < N - 1:
    heappush(queue, (cost + matrix[row][col + 1], row, col + 1, curr))
  if col > 0:
    heappush(queue, (cost + matrix[row][col - 1], row, col - 1, curr))
  if row > 0:
    heappush(queue, (cost + matrix[row - 1][col], row - 1, col, curr))
  if row < N - 1:
    heappush(queue, (cost + matrix[row + 1][col], row + 1, col, curr))
  draw(0.001, curr)

print dist[N - 1, N - 1]

# Malowanie najlepszej ścieżki.
while curr:
  draw(0.2, curr, (255, 0, 0))
  curr = parent[curr]

turtle.exitonclick()

Wizualizacja:


Inkscape ma pętle!


gimpresultZacząłem poszukiwać ciekawych tutoriali z GIMPa. Jeden z nich używał kombinacji narzędzi Inkscape+GIMP. Efektem (po 10 minutach) jest bardzo ładny zbiór kółeczek. Cały tutorial tutaj.

sobota, 12 listopada 2016

Warsztaty matematyczne - Czerwińsk nad Wisłą vol. 2

Tego lata razem z moją narzeczoną zorganizowaliśmy warsztaty z matematyki rekreacyjnej na  Campo Bosko. To już nasz drugi taki wyczyn.

Fragment opisu ze strony opisującej wszystkie warsztaty:
"Nie można, oczywiście, całej matematyki sprowadzać do zagadek i rozrywki..." Ale my to właśnie zrobimy!
Dodatkowo możesz nauczyć się sztuczek, którymi będziesz mógł zaimponować w towarzystwie, nauczycielom w szkole, a na pewno ubogacisz nimi swoją łamigłówkową duszę!
Wymagania wstępne? Prawie żadne! Wystarczy ciekawość do świata, duch podróżnika (po krainie matematycznych rozrywek) w sercu i umiejętność dodawania małych liczb.
Limit miejsc: 30

Problemy jakie trzeba było rozwiązać były następujące:
  1. Zorganizować warsztaty matematyczne w warunkach polowych.

  2. Dostosować warsztaty do dużej liczby osób, zaprojektować zadania, które można wykonywać w grupach.

  3. Zadania dobrać tak, żeby dało się łatwo wytłumaczyć o co w nich chodzi + były robialne w akceptowalnym czasie + były pewnym wyzwaniem.
 Oznaczenie miejsca warsztatów.
Czymś co spełniało powyższe kryteria, to na przykład zespołowe sudoku.
Zespołowe sudoku w grupie późniejszej.
Zespołowe sudoku w grupie wcześniejszej.
I zespołowe układanie tangramu.

Próba ułożenia łódeczki z tangramu. Warto zauważyć, że na stole jest plakat wydany na dwusetlecie Uniwersytetu Warszawskiego.
 Zaangażowanie uczestników było spore! A na deser była zabawa w bańkową stereometrię.

Michał Lorenc - Taniec Eleny

Jedna z lepszych nutek tego miesiąca :)


piątek, 11 listopada 2016

Project Euler - problem 82

Zadanie 82 polega na znalezieniu drogi z lewej kolumny do prawej kolumny, która będzie przechodzić po polach dających najmniejszą możliwą sumę. Zadanie można sprowadzić do poszukiwania najkrótszej ścieżki w grafie, dla odpowiednio skonstruowanego grafu (takie zadanie można już np. rozwiązać algorytmem Dijkstry).

Zastosowałem małą modyfikację tego algorytmu, ponieważ oryginalny algorytm służy do szukania najkrótszej ścieżki w grafie, w którym wagi przejść mają krawędzie. W tym zadaniu wagi mają wierzchołki, ale pomysł pozostał ten sam.

Rozwiązanie:

from heapq import heappop, heappush, heapify

f = open("p082_matrix.txt")
lines = f.readlines()
matrix = [map(int, line.strip().split(",")) for line in lines]
N = len(matrix)  # matrix is square, [0..N-1] x [0..N-1] 

queue = [(matrix[row][0] + matrix[row][1], row, 1) for row in range(N)]
dist = {(row, 0): matrix[row][0] for row in range(N)}
heapify(queue)

while queue:
  cost, row, col = heappop(queue)
  if col == N - 1:
    print cost, row, col
    break
  if (row, col) in dist:
    continue
  dist[(row, col)] = cost
  heappush(queue, (cost + matrix[row][col + 1], row, col + 1))
  if row > 0:
    heappush(queue, (cost + matrix[row - 1][col], row - 1, col))
  if row < N - 1:
    heappush(queue, (cost + matrix[row + 1][col], row + 1, col))

Pomyślałem, że można nieco rozwinąć to rozwiązanie i spróbować je namalować. Z biblioteką turtle jest to w miarę możliwe. Oto efekty:


Dla ciekawych, kod:


# encoding=utf-8
from heapq import heappop, heappush, heapify
import turtle
import time

f = open("p082_matrix.txt")
lines = f.readlines()
matrix = [map(int, line.strip().split(",")) for line in lines]
N = len(matrix)  # matrix is square, [0..N-1] x [0..N-1] 

queue = [(matrix[row][0] + matrix[row][1], row, 1, None) for row in range(N)]
heapify(queue)
dist = {(row, 0): matrix[row][0] for row in range(N)}

# Ustawienia malowania

turtle.hideturtle()
turtle.penup()
turtle.tracer(0, 0)
turtle.colormode(255)

def nice_colors():
  step = 7
  x = y = z = 0
  while True:
    yield x, y, z
    if x >= 170 and y >= 255 and z >= 255:
      x = y = z = 0
    elif y == 255 and z == 255:
      y = z = 0
      x = min(x + 3 * step, 255)
    elif z == 255:
      z = 0
      y = min(y + 7 * step, 255)
    else:
      z = min(z + step, 255)  
color_generator = nice_colors()

def draw(wait, (row, col), color=None):
  if not color:
    color = next(color_generator)
  time.sleep(wait)
  turtle.setpos((col * 5 - 200, row * 5 - 200))
  turtle.dot(None, *color)
  turtle.update()

# Wyliczanie odległości i malowanie grafu przeszukiwania.

parent = {}
while queue:
  cost, row, col, prev = heappop(queue)
  curr = row, col
  if col == N - 1:
    parent[curr] = prev
    break
  if curr in dist:
    continue
  parent[curr] = prev
  dist[curr] = cost
  heappush(queue, (cost + matrix[row][col + 1], row, col + 1, curr))
  if row > 0:
    heappush(queue, (cost + matrix[row - 1][col], row - 1, col, curr))
  if row < N - 1:
    heappush(queue, (cost + matrix[row + 1][col], row + 1, col, curr))
  draw(0.001, curr)

# Malowanie najlepszej ścieżki.

while curr:
  draw(0.2, curr, (255, 0, 0))
  curr = parent[curr]

turtle.exitonclick()

czwartek, 10 listopada 2016

Liczby o dowolnej precyzji w Pythonie

Dzięki bibliotece bigfloat udało mi się szybko rozwiązać zadanie 80 na Project Euler. Rozwiązywanie w taki sposób jest nieco nieładne, ale umożliwiło spojrzenie na rozwiązanie innych użytkowników, co jest już bardzo pouczające :)

niedziela, 6 listopada 2016

ChessNetwork




Polecam polecony mi niegdyś przez Piotrka Zielińskiego kanał na YouTube - ChessNetwork. Znajdują się na nim filmiki nagrane przez mistrza kraju, a konkretnie USA. Są tam umieszczane materiały szkoleniowe, poradniki jak i same gry Jerrego, bo tak autor ma na imię. Najciekawiej ogląda się gry, w których limit czasu na całą partię to jedna minuta. Jerry pomimo tego, że gra, z reguły wygrywa, to jeszcze na spokojnie komentuje posunięcia swoje i przeciwnika. Czasami jednak zdarza się mu zagapić i dostać szewskiego mata w 4 ruchach. I ma potem z siebie niezłą bekę.


Większość filmów to jednak nagrania z turniejów, w których Jerry brał udział lub z pojedynczej gry. Typowy turniej Jerrego:


Jednak to co najbardziej cieszy, to seria Beginner to Chess Master, w której przekazywana jest intuicja szachowa i strategiczna strona szachów. Wiele z tych pomysłów aplikuję do własnej gry, czasami do przesady.

Najbardziej zdumiewający dla mnie był odcinek #13, o dziurach w pozycji:
Jeśli choć trochę lubisz szachy, to warto żebyś spojrzał(a) na filmy tego gracza!