Python | Way23

Алгоритм Flood fill на Python

Алгоритм Flood fill возвращает замкнутую область внутри массива. Кроме областей связанных с графикой, алгоритм может применяется для поиска замкнутых областей в игре Го и для сходных задач.

Алгоритм основан на рекурсии. Проверяется заданный элемент массива, затем процедура вызывается для всех соседних элементов:

Flood_fill(node)
  Если node не подходит по условиям то завершить функцию

  Обработать node

  Вызывать Flood_fill для всех соседних с node элементов

Flood_fill(node)

Если node не подходит по условиям то завершить функцию

Обработать node

Вызывать Flood_fill для всех соседних с node элементов

Реализация на Python:

F_SPACE = 0
F_WALL = 1

field = [
    [0, 1, 1, 1],
    [1, 0, 0, 0],
    [0, 0, 1, 1],
    [0, 1, 0, 0]
]

def flood_fill(field, x, y, w, h,  res):
    if x < 0 or y < 0 or x >= w or y >= h:
        return

    if field[y][x] == F_WALL:
        return

    if (x, y) in res:
        return

    res.add((x, y))

    flood_fill(field, x - 1, y, w, h, res)
    flood_fill(field, x + 1, y, w, h, res)
    flood_fill(field, x, y + 1, w, h, res)
    flood_fill(field, x, y - 1, w, h, res)

res = set()

res.clear()
flood_fill(field, 0, 0, 4, 4, res)
print(res) # {(0, 0)}

res.clear()
flood_fill(field, 1, 0, 4, 4, res)
print(res) # set()

res.clear()
flood_fill(field, 1, 1, 4, 4, res)
print(res) # {(1, 2), (3, 1), (2, 1), (1, 1), (0, 3), (0, 2)}

F_SPACE = 0

F_WALL = 1

field = [

[0, 1, 1, 1],

[1, 0, 0, 0],

[0, 0, 1, 1],

[0, 1, 0, 0]

]

def flood_fill(field, x, y, w, h, res):

if x < 0 or y < 0 or x >= w or y >= h:

return

if field[y][x] == F_WALL:

return

if (x, y) in res:

return

res.add((x, y))

flood_fill(field, x - 1, y, w, h, res)

flood_fill(field, x + 1, y, w, h, res)

flood_fill(field, x, y + 1, w, h, res)

flood_fill(field, x, y - 1, w, h, res)

res = set()

res.clear()

flood_fill(field, 0, 0, 4, 4, res)

print(res) # {(0, 0)}

res.clear()

flood_fill(field, 1, 0, 4, 4, res)

print(res) # set()

res.clear()

flood_fill(field, 1, 1, 4, 4, res)

print(res) # {(1, 2), (3, 1), (2, 1), (1, 1), (0, 3), (0, 2)}

Алгоритм легко модифицируется для случая с трёхмерным массивом или если нужно учитывать соседние элементы по диагоналям.

Примеры использования JSONPath в Python

Перевод статьи Python JSONPath Examples.

Что такое JSONPath?

JSONPath это язык запросов к JSON. Он очень похож на язык запросов XPath для XML. Вы формируете строку запроса и получаете нужное значение. Такое подход экономит память, так как необходимости разбазарить JSON полностью.

Библиотеки Python для JSONPath

Существует много JSONPath-библиотек для Python.

jsonpath: это портированая из Perl и JavaScript версия JSONPath.

jsonpath-rw: полностью Python-реализация JSONPath. Объект выражения JSONPath это объект первого класса, простой для анализа, преобразования, обработки, печати и расширения. Модуль jsonpath-rw-ext расширяет функционал библиотеки.

jsonpath-ng: окончательная реализация JSONPath цель которой соответствие стандарту, включая арифметические и бинарные сравнения. Эта библиотека соединяет модули jsonpath-rw и jsonpath-rw-ext и расширяет их.

Какую библиотеку использовать?

Модуль jsonpath-ng самый развитый и написан на чистом Python. Он поддерживает Python 2 и Python 3. Мы будем использовать этот модуль для примеров.

Установка модуля:

pip3.7 install jsonpath-ng

1	pip3.7 install jsonpath-ng

Читать далее Примеры использования JSONPath в Python

Области видимости в Python

Перевод статьи Understanding Python scope.

Рассмотрим функцию Python и модульный тест для неё. Что в ней неверно?

import unittest

def method_under_test(callback, value):
    """Call callback with value."""
    callback(value)

class MyTestCase(unittest.TestCase):
    def test_function_calls_callback(self):
        callback_called = False
        def callback(actual):
            callback_called = True
            if actual != 42:
                raise AssertionError('wrong value!')

        method_under_test(callback, 42)
        self.assertTrue(callback_called)

if __name__ == '__main__':
    unittest.main()

import unittest

def method_under_test(callback, value):

"""Call callback with value."""

callback(value)

class MyTestCase(unittest.TestCase):

def test_function_calls_callback(self):

callback_called = False

def callback(actual):

callback_called = True

if actual != 42:

raise AssertionError('wrong value!')

method_under_test(callback, 42)

self.assertTrue(callback_called)

if __name__ == '__main__':

unittest.main()

Запустим тест:

$ python test.py
F
======================================================================
FAIL: test_function_calls_callback (__main__.MyTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "x.py", line 16, in test_function_calls_callback
    self.assertTrue(callback_called)
AssertionError: False is not true

----------------------------------------------------------------------
Ran 1 test in 0.000s

FAILED (failures=1)
$

$ python test.py

======================================================================

FAIL: test_function_calls_callback (__main__.MyTestCase)

----------------------------------------------------------------------

Traceback (most recent call last):

File "x.py", line 16, in test_function_calls_callback

self.assertTrue(callback_called)

AssertionError: False is not true

----------------------------------------------------------------------

Ran 1 test in 0.000s

FAILED (failures=1)

Выглядит так как будто функция callback не вызвана. Проверим это: если изменить аргумент для callback передаваемый в method_under_test(), вы увидите что проверка в функции callback срабатывает.

Разберёмся почему так происходит.

Читать далее Области видимости в Python

Поверхностное и глубокое копирование в Python

Перевод статьи Python Shallow Copy and Deep Copy.

Копирование объектов в Python

Оператор присваивания = не создаёт копию объекта. Присваивание создаёт новую переменную которая дублирует ссылку на исходный объект.

Рассмотрим пример

old_list = [[1, 2, 3], [4, 5, 6], [7, 8, 'a']]
new_list = old_list

new_list[2][2] = 9

print('Old List:', old_list)
print('ID of Old List:', id(old_list))

print('New List:', new_list)
print('ID of New List:', id(new_list))

old_list = [[1, 2, 3], [4, 5, 6], [7, 8, 'a']]

new_list = old_list

new_list[2][2] = 9

print('Old List:', old_list)

print('ID of Old List:', id(old_list))

print('New List:', new_list)

print('ID of New List:', id(new_list))

После запуска программа выдаст следующее:

Old List: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
ID of Old List: 140673303268168

New List: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
ID of New List: 140673303268168

Old List: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

ID of Old List: 140673303268168

New List: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

ID of New List: 140673303268168

Обе переменные ссылаются на один объект, это подтверждает одинаковый идентификатор объекта 140673303268168. Так что при изменении значений в переменных new_list и old_list, изменение будет видно в обоих переменных.

Иногда нужно оставить исходное значение без изменений и модифицировать только новое. В Python, есть два способа сделать копию: поверхностное копирование и глубокое копирование.

Читать далее Поверхностное и глубокое копирование в Python

Изменяемые и неизменяемые объекты в Python

Перевод статьи Mutable vs Immutable Objects in Python.

Все значения в Python это объекты. Объекты делятся на изменяемые и неизменяемые.

Каждая переменная ссылается на экземпляр объекта. При создании, объекту присваивается уникальный идентификатор (object id) и тип объекта. Тип объекта не меняется после создания, но может изменится состояние объекта. Изменяемые объекты меняют своё состояние после создания, а неизменяемые сохраняются в том виде в котором были созданы.

Встроенные неизменяемые типы: int, float, bool, str, tuple, unicode. Встроенные изменяемые типы list, set, dict. Пользовательские классы обычно изменяемы. Для имитирования неизменяемости переопределите методы изменения и удаления значений чтобы они возвращали исключение.

Чтобы узнать ссылается ли переменная на изменяемый или неизменяемый рассмотрим подробнее функции id() и type().

Читать далее Изменяемые и неизменяемые объекты в Python

Python. Свойства

Перевод статьи Python @property.

Python поддерживает концепцию свойств упрощающих объектно ориентированное программирование. Прежде чем погрузится глубже в детали свойств, рассмотрим зачем могут быть нужны свойства.

Начальный пример

Представим что вы решили сделать класс хранящий температуру в градусах Цельсия. Он также должен реализовывать метод для конвертации температуры в градусы Фаренгейта. Реазуем класс так:

class Celsius:
    def __init__(self, temperature = 0):
        self.temperature = temperature

    def to_fahrenheit(self):
        return (self.temperature * 1.8) + 32

class Celsius:

def __init__(self, temperature = 0):

self.temperature = temperature

def to_fahrenheit(self):

return (self.temperature * 1.8) + 32

Затем создаём объект этого класса и меняем значение температуры как пожелаем:

>>> # создание нового объекта
>>> man = Celsius()
>>> # установка темпиратуры
>>> man.temperature = 37
>>> # получение значения темпиратуры
>>> man.temperature
37
>>> # конвертация в градусы Фаренгейта
>>> man.to_fahrenheit()
98.60000000000001

>>> # создание нового объекта

>>> man = Celsius()

>>> # установка темпиратуры

>>> man.temperature = 37

>>> # получение значения темпиратуры

>>> man.temperature

>>> # конвертация в градусы Фаренгейта

>>> man.to_fahrenheit()

98.60000000000001

Дополнительные десятичные разряды при конвертации в градусы Фаренгейта происходят из-за арифметической ошибки с плавающей запятой (попробуйте сложить 1.1 + 2.2 в интерпретаторе).

Когда мы присваиваем или извлекаем атрибут объекта, такой как temperature, Python ищет его в словаре объекта __dict__.

>>> man.__dict__
{'temperature': 37}

1 2	>>> man.__dict__ {'temperature': 37}

Внутри интерпретатора man.temperature становится man.__dict__['temperature'].

Читать далее Python. Свойства

Python. Функция property()

Перевод статьи Python | property() function.

Функция property() создаёт новое свойство. Свойство — это атрибут класса с которым связаны функции чтения и записи.

property(fget, fset, fdel, doc)

1	property(fget, fset, fdel, doc)

Параметры:

fget() – используется для получения значения атрибута
fset() – используется для установки значения атрибута
fdel() – используется для удаления атрибута
doc() – строка с документацией (docstring) для атрибута

Функция property() возвращает свойство с данными геттером, сеттером и deleter.

Вызванная без аргументов функция property() возвращает свойство без геттера, сеттера и deleter.

Читать далее Python. Функция property()

Python. Структуры данных: список, кортеж, множество, словарь

Перевод параграфа 3.6 Data Structures из книги Intermediate Python.

Python содержит встроенные типы данных: списки, кортежи, словари.

Списки

Чтобы создать список используйте квадратные скобки или функцию list():

my_list1 = [] # Пустой список
my_list2 = list() # Пустой список

1 2	my_list1 = [] # Пустой список my_list2 = list() # Пустой список

Список сохраняет порядок элементов с которым создаётся или в котором элементы добавляются. Списки являются последовательностями и поддерживают доступ к элементам по индексу, другие свойства последовательностей будут описаны в следующих главах.

Первый элемент списка находится под индексом 0, последний — на единицу меньше длины списка.

>>> name = ["obi", "ike", "nwosu"]
>>> name[0]
'obi'
>>> name[1]
'ike'
>>> name[2]
'nwosu'

>>> name = ["obi", "ike", "nwosu"]

>>> name[0]

'obi'

>>> name[1]

'ike'

>>> name[2]

'nwosu'

Метод append() добавляет элемент в список.

>>> name = ["obi", "ike", "nwosu"]
>>> name.append("nkem")
>>> names
["obi", "ike", "nwosu", "nkem"]

>>> name = ["obi", "ike", "nwosu"]

>>> name.append("nkem")

>>> names

["obi", "ike", "nwosu", "nkem"]

Читать далее Python. Структуры данных: список, кортеж, множество, словарь

Задача Pythagorean Triplet

Условие

Дано число $N$. Найти все пифагоровы тройки такие что $a + b + c = N$. Пифагоровы тройки удовлетворяют условиям $a^2 + b^2 = c^2$ и $a \lt b \lt c$.

Решение

Простейшее решение перебором даёт сложность $O(n^2)$:

for a in range(n):
  for b in range(a + 1, n):
    c = N - a - b
    if is_triplet(a, b, c):
      add_result(a, b, c)

for a in range(n):

for b in range(a + 1, n):

c = N - a - b

if is_triplet(a, b, c):

add_result(a, b, c)

Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.

Эту же задачу можно решить за $O(n)$. Из условий задачи следуют два уравнения:

$a + b + c = N$
$a^2 + b^2 = c^2$

$N$ является константой. Примем так же за константу $a$. Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

$c = N - a - b$ (1)
$c^2 - b^2 = a^2$
$(c - b)(c + b) = a^2$ (2)
$(n - a - b - b)(n - a - b + b) = a^2$ (подставляем 1 в 2)
$(n - a - 2b)(n - a) = a^2$
$n^2 - an - 2nb - an + a^2 + 2ab = a^2$
$n^2 - 2an - 2nb + 2ab = 0$
$(2a - 2n)b = 2an - n^2$
$b = \frac{2an - n^2}{2a - 2n}$
$c = N - a - b$

Используя формулы для вычисления $b$ и $c$ в цикле по $a$ находим все пифагоровы тройки.

def triplets_with_sum(number):
    res = []
    n = number
    for a in range(1, number):
        b = (2 * a * n - n ** 2) / (2 * a - 2 * n)
        c = n - b - a

        if round(b) == b and a < b < c:
            res.append([a, b, c])

    return res

def triplets_with_sum(number):

res = []

n = number

for a in range(1, number):

b = (2 * a * n - n ** 2) / (2 * a - 2 * n)

c = n - b - a

if round(b) == b and a < b < c:

res.append([a, b, c])

return res

Проверка xml по xsd на Python через lxml

В библиотеке lxml содержаться функции для проверки xml по xsd. Пример кода:

from lxml import etree

# Загрузка xsd схемы
xsd_file_name = r'schema.xsd'
schema_root = etree.parse(xsd_file_name)
schema = etree.XMLSchema(schema_root)

# Загрузка xml

xml_filename = 'file.xml'
xml = etree.parse(xml_filename)

# Проверка

if not schema.validate(xml):
    print(schema.error_log)

from lxml import etree

# Загрузка xsd схемы

xsd_file_name = r'schema.xsd'

schema_root = etree.parse(xsd_file_name)

schema = etree.XMLSchema(schema_root)

# Загрузка xml

xml_filename = 'file.xml'

xml = etree.parse(xml_filename)

# Проверка

if not schema.validate(xml):

print(schema.error_log)

Метод validate возвращает False если xml не проходит проверку по схеме. Свойство error_log содержит список несоответствий xml схеме из xsd.

Пн	Вт	Ср	Чт	Пт	Сб	Вс
« Фев
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31