14.05.2021 07:24
sukhe 127 21900 Источник

Мой друг Алексей ищет работу и ходит на собеседования. После которых интересуется, как бы я ответил на некоторые из заданных вопросов.

Отвечая на один такой вопрос, я слегка увлёкся, и материала набралось на целую статью. Впрочем, небольшую и несерьёзную - пятничного формата.

Хотите немного развлечься? Вопрос лёгкий. Надеюсь, вы попытаетесь ответить на него самостоятельно, прежде чем читать дальше. Итак:

"Сложить два целых числа (от 1 до 99) без использования оператора 'плюс'. Дайте пять разных ответов"

Ну как? Придумали пять ответов? Давайте сравним. Если будет что-то такое, до чего я не додумался - добавляйте в комментарии.

Дальше - художественно обработанная "стенограмма" моего общения с другом.

Первое, что приходит в голову - "минус на минус даёт плюс":

plus1 = lambda a,b: a - (-b)

>>> plus1(22,6)
28

Видишь ошибку? Она здесь есть. И на интервью её заметят. Но не будем пока отвлекаться - в конце объясню.

Второй вариант, думаю, очевиден:

import math
plus2  = lambda a,b: int(math.log10(10**a * 10**b))
Пояснение для читателей

Используется равенство an+m = an * am

Соответственно, логарифм от an+m равен n+m

С помощью модуля operator:

import operator
plus3 = lambda a,b: operator.add(a,b)

Но можно и напрямую, без этого модуля:

plus4 = lambda a,b: a.__add__(b)

Впрочем, есть готовая встроенная функция:

plus5 = lambda a,b: sum([a,b])

И даже вот так можно:

plus6 = lambda a,b: list(range(a, 200, b))[1]

Или через длину строки:

plus7 = lambda a,b: len(''.join([a*'#', b*'*']))

Python вообще богат на варианты:

plus8 = lambda a,b: eval('a + b')

Тут мой товарищ возмутился, что видит плюс, а плюс использовать нельзя. Спорный вопрос. В условии говорится про оператор '+', а здесь он просто символ. Хотя eval его, конечно, исполняет как оператор.

Впрочем, не буду спорить с другом:

plus9 = lambda a,b: eval('a \N{PLUS SIGN} b')
Пояснение для читателей

Используется символ плюса через его название в Unicode

Друг: "Мне кажется, меня тут пытаются обмануть. Что это ещё за PLUS SIGN?"

Ладно! Сейчас не будет никаких плюсов:

plus10 = lambda a,b: eval("".join(map(chr, [97, 32, 43, 32, 98])))
Пояснение для читателей

С помощью join из отдельных символов собирается строка 'a + b'

"Так! Никаких больше eval!"

Хорошо. Кстати, я тут придумал ещё пару вариантов. Правда, с плюсом, но Python даже не будет этот плюс исполнять. Вариант первый:

import sqlite3
conn = sqlite3.connect(':memory:')
cursor = conn.cursor()
plus11 = lambda a,b: cursor.execute('select ? + ?', (a,b)).fetchone()[0]

Вариант второй (для Linux, FreeBSD и т.п.):

import os
plus12 = lambda a,b: int(os.popen(f'expr {a} + {b}').read().strip())

"Э-э-э, нет... Давай вот без этого. Только встроенными средствами Питона. А то так можно в каком-нибудь онлайн-калькуляторе два числа сложить, а потом распарсить ответ"

Эх... А я только собирался предложить что-нибудь эдакое. Что-ж... Придётся вспомнить детство. Складываем "в столбик" двоичные представления чисел:

def plus13(aa,bb):
    a = f'{aa:0>8b}'
    b = f'{bb:0>8b}'
    result = ['0'] * 8
    carry_bit = '0'
    for i in range(7, -1, -1):
        if a[i]=='1' and b[i]=='1':
            result[i] = carry_bit
            carry_bit = '1'
        elif (a[i]=='1' and b[i]=='0') or (a[i]=='0' and b[i]=='1'):
            if carry_bit == '0':
                result[i] = '1'
        else:
            if carry_bit == '1':
                result[i] = '1'
                carry_bit = '0'
    return int(''.join(result),2)
Пояснение на примере

22 + 6 = 10110 + 00110 (считаем справа налево, всего пять шагов) 

  1    |    2    |    3    |    4    |    5
       |    Ў1   |   Ў1    |         | 
10110  |  10110  |  10110  |  10110  |  10110
00110  |  00110  |  00110  |  00110  |  00110
-----  |  -----  |  -----  |  -----  |  -----
    0  |     00  |    100  |   1100  |  11100 = 28

Шаг 2) 1 + 1 = 10. Что не вмещается в двоичный разряд. Поэтому 0 пишем, а не вместившийся бит (бит переноса, carry bit) переходит в следующий разряд.

Шаг 3) 1 + 1 = 10 плюс бит переноса = 11. Пишем один и один переносим.

А собственно... Что это я в бирюльки играюсь? Можно обрабатывать все разряды одновременно:

def plus14(a, b):
    while b != 0:
        carry_bits = a & b
        a = a ^ b
        b = carry_bits << 1
    return a
Пояснение для читателей

Сначала используем битовое И (&). Так мы узнаем разряды, в которых появится переполнение. Соответственно, на разряд левее нужно будет добавить биты переноса. Для этого сдвигаем полученное число на бит влево (00110 << 1 = 01100). И получаем первое слагаемое для следующего цикла. Или выходим из цикла, если битов переноса нет (одно из слагаемых стало равно нулю, значит вычисление завершено).

10110
00110
----- &
00110 << 1 = 01100

С помощью исключающего ИЛИ (^) устанавливаем в 0 переполненные разряды и оставляем неизменными непереполненные. Это будет второе слагаемое для следующего цикла или конечный результат, если вычисления завершены.

10110
00110
----- ^
10000

Можно даже сделать рекурсивный вариант:

def plus15(a, b):
    if b == 0:
        return a
    else:
        return plus15(a ^ b, (a & b) << 1)

А теперь - внимание! Барабанная дробь... Смертельный номер! Закат Солнца вручную:

import types
co = types.CodeType(2, 0, 0, 2, 0, 0, b'|\x00|\x01\x17\x00S\x00', (), (),
                    ('a','b'), '', '', 1, b'')
plus16 = types.FunctionType(co, globals())

"Так... Секундочку... Что это сейчас было?"

Ты-же в курсе, что внутри функции есть CodeObject, который состоит из байт-кода Питона и нескольких параметров (определение переменных, размер стека и т.п.). Этот объект можно сгенерировать вручную и получить из него работающую функцию.

"Ну да. Ты ещё скажи, что в голове питоновские программы в байт-код компилируешь :)"

Нет, конечно. Просто я это пару дней назад смотрел и пока ещё помню.

На самом деле там несложно
>>> import dis
>>> dis.dis(co)
  1           0 LOAD_FAST                0 (a)
              2 LOAD_FAST                1 (b)
              4 BINARY_ADD
              6 RETURN_VALUE

То есть, это обычное сложение через стек.

Вообще, к байткоду функции легко добраться:

>>> bytecode = plus16.__code__.co_code
>>> bytecode
b'|\x00|\x01\x17\x00S\x00'

>>> list(bytecode)
[124, 0, 124, 1, 23, 0, 83, 0]

Видно, что операции в байткоде состоят из кодов команд (opcode) и аргументов (oparg). Вот команды:

124 - LOAD_FAST    # |
23 - BINARY_ADD    # \x17
83 - RETURN_VALUE  # S

С помощью dis.opmap и dis.opname их можно преобразовывать туда-сюда:

>>> dis.opname[124]
'LOAD_FAST'

>>> dis.opmap('LOAD_CONST')
100

Аргумент операции - это номер в списке переменных. В нашем случае список состоит из двух переменных a и b, которые загоняются в стек и складываются.

Примечание: если Питон версии ниже 3.8, то там перед байт-кодом пять параметров, а не шесть (в 3.8 добавились "только позиционные аргументы").

Кстати, без модуля types можно обойтись. Переменные типа "функция" и "объект кода" можно клонировать из других объектов: 

f = lambda: ...
function = type(f)
code = type(f.__code__)
co = code(2, 0, 0, 2, 0, 0, b'|\x00|\x01\x17\x00S\x00', (), (), 
          ('a','b'), '', '', 1, b'')
plus17 = function(co, globals() )

"Три точки в первой строке - это Ellipsis?"

Да. Объект-заполнитель, который здесь используется вместо pass. Появился в последних версиях.

О! Насчёт последних версий. Если у тебя Python версии 3.8+, там есть замена кодового объекта:

def plus18(a,b): ...
plus18.__code__ = plus18.__code__.replace(
  co_code=b'|\x00|\x01\x17\x00S\x00')

Видал, какая чёрная магия? Весь "обвес" остаётся от исходной функции, а меняется только нужная часть (в этом примере - байт-код).

Вообще, там не обязательно должен быть байткод в явном виде. Можно не заморачиваться с преобразованием и писать вот так: 

plus18.__code__ = plus18.__code__.replace(
  co_code=(lambda a,b: a + b).__code__.co_code)

И, раз уж я полез во внутренности, можно задействовать подсчёт ссылок:

def plus19(a,b):
    lst = []
    value = 0
    before = sys.getrefcount(value)
    for i in range(a):
        lst.append(value)
    for i in range(b):
        lst.append(value)
    return sys.getrefcount(value) - before

Вот, как-то так...

. . .

{прошло несколько минут}

. . .

"Что молчишь? Нет больше вариантов?"

Один ещё есть. Только я формулу забыл. Пришлось в интернете посмотреть. Через разложение косинуса суммы углов:

from math import cos, sin, acos
def plus20(a,b):
    a = a / 200
    b = b / 200
    result = acos(cos(a)*cos(b) - sin(a)*sin(b)) * 200
    return int(round(result, 0))
Пояснение для читателей

Используется формула cos(a+b) = cos(a)*cos(b) - sin(a)*sin(b)

Максимально возможная сумма в этой задаче - 198. А тригонометрия считается в радианах. Чтобы исключить неоднозначность и гарантированно остаться в пределах четверти круга (около полутора радиан) - я просто делю и умножаю на 200.

А пока я мысленно представлял транспортир, вспомнилась ещё и функция enumerate, которая нумерует элементы:

plus21 = lambda a,b: list(enumerate([*range(-1,a), *range(b)]))[-1][0]

Вот на этом, пожалуй, всё... Сходу больше ничего в голову не приходит. Разве что на регулярных выражениях выкрутить. Но это ты уже сам сделай в качестве домашнего задания. А мне пока выдай ещё какой-нибудь каверзный вопрос.

"Вопрос я выдам. Не вопрос. Что там с первым ответом? Где ошибка?"

Ошибка в том, что по PEP 8 не рекомендуется присваивать лямбды. Надо использовать обычное определение функции через def, т.к. это "more useful for tracebacks and string representations".

То есть, неправильно писать 

fun1 = lambda a: a**2

надо использовать так:

def fun2(a): return a**2

Потому что лямбды делались именно для того, чтобы оставаться безымянными и никуда не присваиваться. Смотри:

>>> fun1
<function <lambda> at 0x0000024FEE36F1F0>	

>>> fun3 = lambda a: 2 * a
>>> fun3
<function <lambda> at 0x000001A7571BA550>

>>> fun2
<function fun2 at 0x0000024FEE36F3A0>

Видишь? У всех лямбд одинаковое имя - <lambda>. Когда я тебе однострочные примеры пишу - это неважно. А на собеседовании лучше делать так, как рекомендуют.

"А можно лямбде имя присвоить?"

Да без проблем!

>>> fun1.__qualname__ = 'fun1'
>>> fun1
<function fun1 at 0x0000024FEE36F1F0>

Только зачем такие сложности, если можно сразу через def объявить. Кроме того, всё ещё видно, что это лямбда:

>>> fun1.__code__.co_name
'<lambda>'

В отличие от

>>> fun2.__code__.co_name
'fun2'

При этом параметр co_name - readonly, т.е. напрямую имя не поменять. Надо использовать __code__.replace (но это только в Python 3.8+): 

>>> fun1.__code__ = fun1.__code__.replace(co_name='fun1')

И ещё в одном месте:

>>> fun1.__name__ = 'fun1'

Теперь она не отличается от обычной функции:

>>> fun1.__code__.co_name
'fun1'
>>> fun1.__qualname__
'fun1'
>>> fun1.__name__
'fun1'
>>> fun1
<function fun1 at 0x0000024FEE36F1F0>

Реально проще использовать def.

И я всё ещё жду новый вопрос...

Впрочем... Забавно у вас там на собеседованиях. Самому, что-ли, сходить? Ни разу не был.