Кодировки, исключения и генераторы

Долги за прошлую лекцию:

• Что такое «передача параметров по соиспользованию»?
• Защита от «побочного эффекта»:

   1 def fn():
   2   c = b
   3   b = 1
   4 
   5 b=3
   6 fn()

• ⇒ предварительный разбор лексем, выделение и классификация идентификаторов. Доказательство: dis.dis(fn) vs. функция без b = 1.

• Рекурсия. Оценка необходимости рекурсии. Гвидо и хвостовая рекурсия.

• random.shuffle(), random.choice() и random.sample()

Пример исходного кода

Генератор «красивого» лабиринта.

Идея 1

Только половина ячеек лабиринта случайна, из остальных половина заранее проходима, а половина — нет:

.?.?.?.?.…
?#?#?#?#?…
.?.?.?.?.…
?#?#?#?#?…
…

Идея 2

Алгоритм.

• Изначально все «?» непроходимы, а все «.» недостижимы.
• Выбираем любую «.», делаем её достижимой и добавляем в план разведки.
• Цикл, пока план разведки не пуст:
  • Выбираем случайную ячейку из плана
  • Если у неё есть неразведанный сосед (через одну ячейку)
    • Добавляем её обратно в план
    • Делаем соседа достижимым и добавляем его в план
    • Делаем стену между этой ячейкой и этим соседом проходимой

Идея 3

Если поместить в план разведки и вход, и выход, получится непроходимый лабиринт

   1 import random
   2 
   3 N = 15
   4 D = (-2,0), (0,2), (2,0), (0,-2)
   5 Map = {(i,j):2-(i%2|j%2) for i in xrange(N) for j in xrange(N)}
   6 Todo = [(N/2&-2,N/2&-2)] if random.randrange(2) else [(0,0),(N-1,N-1)]
   7 for x,y in Todo:
   8     Map[x,y]=0
   9 
  10 while Todo:
  11     x,y = Todo.pop(random.randrange(len(Todo)))
  12     Check = [(dx,dy) for dx,dy in D if 0<=x+dx<N and 0<=y+dy<N and Map[x+dx,y+dy]]
  13     if Check:
  14         dx,dy = random.choice(Check)
  15         Todo.extend([(x,y),(x+dx,y+dy)])
  16         Map[x+dx,y+dy]=Map[x+dx/2,y+dy/2]=0
  17 
  18 for i in xrange(N):
  19     print "".join(".#"[Map[i,j]] for j in xrange(N))

И результат:

...#.#.#.#.....
.###.#.#.#.#.##
...#.#...#.#.#.
##.#.#.###.###.
.........#.#.#.
.###.#####.#.#.
.#.............
####.#.#.###.##
.....#.#...#...
####.#.#.#.###.
.....#.#.#...#.
.#.#.###.###.##
.#.#.#.....#...
.#######.###.#.
.#.........#.#.

Кодировка, строки, u-строки и их преобразование

• однобайтовый UTF в Python2

• chr()/ord()

• unicode() (нужна кодировка), обратное (используется LOCALE)

• # coding: UTF в файле

Пример:

   1 # coding: utf
   2 a="Ку!"
   3 b=bytearray(a)
   4 u=unicode(a,"UTF")            # что будет без "UTF"?
   5 print "|".join(map(hex, b)) 
   6 print "|".join(a)
   7 print "|".join(u)
   8 print a,b,u

Исключения

• JT: Ошибки выполнения в интерпретируемых ЯП

• Ошибки Python — объекты

  • raise

  • Иерархия (например, ArithmeticError ⊃ ZeroDivisionError)

• try: … except:

  • Обработка всех или заданных исключений

  • Клаузы else: и finally:

  • Параметры исключений (у разных разные)

• raise Exception("QQ", "QKRQ", …)

Генераторы

• Объекты-итераторы iter() из коллекции (.__iter__()) или из последовательности (.__getitem__())

  • .next() и StopIteration

  • Работа цикла for

• Выражения-генераторы: для цикла лучше списков, но «одноразовые, что твои спорт-байкеры»

• Генераторы: функции с yield вместо return

  • Параметрические: .send(par) вместо .next() ( ⇒ par = yield)

  • Управление: .close() и .throw(исключение)

⇒ JT: Отложенные вычисления и… «побочный эффект»

Д/З

• Прочитать:

  • Про random в документации

  • Про исключения в учебнике (errors.html) и в документации

  • Про генераторы в учебнике, pep-0255, pep-0342

• (GenMinMax) Найти минимум и максимум произвольной функции на целочисленном отрезке

  Ввести строку — произвольное выражение Python, в котором могут дополнительно встречаться функции из модуля math и переменная x. На следующей строке ввести через запятую целые числа A и B (выражение должно быть определено как минимум на A или на B). Вывести через пробел минимальное и максимальное значение выражения на всех допустимых целых x, принадлежащих отрезку [A,B]. Точностью вычислений не управлять.

  Input:

  (x**5+1)/(factorial(x)-720)
  -10,10

  Output:

  -6 3

• (RandomGen) Найти число в псевдослучайной последовательности

  Ввести через запятую натуральные числа X₀, a, c и m (c также может быть равно 0); на следующей строке ввести натуральное число Y. Использовать генератор последовательности псевдослучайных чисел линейным конгруэнтным методом и проверить, встречается ли Y в последовательности X_n+1 = (aX_n + c) mod m (это и есть упомянутый метод ). Вывести YES, если встречается и NO, если нет.

  Input:

  7,7,7,10
  6

  Output:

  YES

• (DoPolIZ) Вычислить выражение в польской инверсной записи

  Ввести целочисленное выражение в польской инверсной записи, в котором могут содержаться разделённые пробелом целые числа и 4 знака арифметики: "+", "-", "*" и "/". Если выражение можно вычислить, вывести результат. В противном случае (синтаксическая ошибка, в стеке остался не один элемент, и т. п.) вывести ERROR.

  Input:

  234 345 456 + + 5 /

  Output:

  207

• (PaidStairs) Классическая задача динамического программирования «Платная лестница»

  Наступить на k-ю ступень лестницы A стоит A_k монет. Ввести через запятую «цены» ступеней A, и на следующей строке — ширину шага S (все числа натуральные) и вывести минимальную стоимость пути с земли до последней ступени (на которую наступать обязательно), при условии, что идти можно только вверх и перешагивать можно не более, чем через S-1 ступень.

  Input:

  5, 3, 6, 1, 1, 2, 3, 4, 7, 5, 5, 7, 1, 1, 4, 6, 3, 4, 7, 4, 2
  4

  Output:

  14