Может кто-нибудь, пожалуйста, объясните XOR (для контрольной суммы) в Python 3
Я работаю над упражнением для foo.bar, и основная идея состоит в том, чтобы взять список целых чисел и сделать с ним некоторые вещи, чтобы получить определенное подмножество этого списка, а затем XOR (для контрольной суммы) этих значений с помощью этого:
result2 = 17^18^19^20^21^22^23^25^26^29 Я не совсем уверен, что здесь происходит и как достигаются эти значения (2, 14).
Актуальное описание проблемы от Foo.Bar
> Очередь, чтобы сделать
Вы почти готовы сделать шаг, чтобы уничтожить устройство LAMBCHOP конца света, но контрольные точки безопасности, которые охраняют базовые системы LAMBCHOP, будут проблемой. Вы смогли снять его, не отключив ни одной тревоги, и это здорово! За исключением того, что, будучи помощником коммандера Лямбды, вы узнали, что контрольно-пропускные пункты скоро будут подвергнуты автоматическому анализу, а это значит, что ваш саботаж будет обнаружен и ваше укрытие взорвано — если вы не сможете обмануть автоматизированную систему обзора.
Чтобы обмануть систему, вам нужно написать программу, которая будет возвращать ту же контрольную сумму безопасности, что и у охранников после того, как они проверят всех рабочих. К счастью, стремление коммандера Лямбды к эффективности не позволяет использовать многочасовые очереди, поэтому охранники контрольно-пропускных пунктов нашли способы ускорить пропускную способность. Вместо того, чтобы проверять каждого проходящего работника, охранники вместо этого просматривают всех в очереди, отмечая их идентификаторы безопасности, а затем позволяют линии заполниться. После того, как они это сделали, они снова перешли черту, на этот раз оставив последнего работника. Они продолжают это делать, каждый раз оставляя по очереди еще одного работника, но записывая идентификаторы безопасности тех, кого они проверяют, до тех пор, пока они не пропустят всю строку, после чего они XOR идентифицируют идентификаторы всех работников, которых они отметили, в контрольную сумму и затем сними на обед. К счастью, упорядоченный характер рабочих заставляет их всегда выстраиваться в числовом порядке без каких-либо пробелов.
Например, если первый рабочий в строке имеет идентификатор 0, а строка контрольной точки безопасности содержит трех рабочих, процесс будет выглядеть следующим образом:
где контрольная сумма XOR (^) охранников равна 0^1^2^3^4^6 == 2.
Аналогично, если первый работник имеет ID 17, а контрольная точка содержит четырех работников, процесс будет выглядеть следующим образом:
который производит контрольную сумму 17^18^19^20^21^22^23^25^26^29 == 14.
Все идентификаторы работника (включая первого работника) находятся в диапазоне от 0 до 2000000000 включительно, и длина строки контрольной точки всегда будет не менее 1 работника.
Получив эту информацию, напишите ответ функции (начало, длина), который покроет пропущенную контрольную точку безопасности путем вывода той же контрольной суммы, которую охранники обычно отправляют до обеда. У вас достаточно времени, чтобы узнать идентификатор первого проверяемого работника (начало) и длину строки (длина) до автоматического просмотра, поэтому ваша программа должна сгенерировать правильную контрольную сумму только с этими двумя значениями.
Контрольные примеры
(int) start = 0 (int) length = 3 (int) start = 17 (int) length = 4 Как выполнить xor строки?
Есть список значений различных типов. По условию необходимо «вычислить как логическая операция «исключающее ИЛИ» всех байтов» значение контрольной суммы.
b0 = 1 b1 = 1 b2 = 4 b3 = 'ной' csum = b0^b1^b2^b3Оценить 12 комментариев
abcd0x00: b3 — один из параметров необходимых передать устройству, соответственно он участвует в вычислении контрольной суммы пакета
Nahs: по сути имелось ввиду: привести к массиву байтов, просто разница между строкой и массивом байт — довольно зыбкая(если это не третий питон конечно). собственно в отмеченном вами решении так и делается, я просто поленился его читать перед тем, как оставить комментарий.
b3 — один из параметров необходимых передать устройству, соответственно он участвует в вычислении контрольной суммы пакета
Конкретизируй, как он участвует.
abcd0x00: Есть устройство, получающий пакет данных и выводящее переданный в пакете текст.
Пакет представляет из себя байтовую строку в виде:
1. префикс пакета (str)
2. управляющая команда пакета (byte)
3. префикс строки (str)
4. адрес вывода строки (int)
5. адрес вывода строки (int)
6. тип вывода строки (int)
7. строка для вывода (str)
8. код окончания строки (byte)
9. контрольная сумма (int)
10. код окончания пакета (byte)
Контрольная сумма вычисляется как xor всех байтов с 4 по 7.
То есть, если мы имеем, следующие значения 4-7: 114ной, то мы побайтно вычисляем xor
1^1^4^н^о^й
nirvimel как раз указал отличный способ решения моей задачи.
Неясно с кодировкой. Буквы кириллицы могут быть закодированы двумя байтами.
>>> b0 = 1 >>> b1 = 1 >>> b2 = 4 >>> b3 = 'abc' >>> >>> def xorit(seq): . n = 0 . for i in seq: . if isinstance(i, int): . n ^= i . elif isinstance(i, str): . n ^= xorit(map(ord, i)) . return n . >>> n = xorit([b0, b1, b2, b3]) >>> n 100 >>>Ну, я что-то не особо был рад увидеть эту to_bytes(). Во-первых, её наличие — под вопросом, а во-вторых, если она и нужна, то делается она гораздо короче и яснее.
def xor_bytes(data): accumulator=0 if isinstance(data, int): string = data.to_bytes(1, byteorder='big') accumulator ^= (ord(string) & 0xff) elif isinstance(data, str): data = data.encode('cp1251') for char in data: accumulator ^= (ord(char.to_bytes(1, byteorder='big')) & 0xff) else: raise Exception('Invalid type') return accumulatorВыше написал. Там не нужно ни 0xff, ни эндианство. Потому что в сети эндианство всегда big-endian, а раз это однобайтовый xor, то и усечение до одного байта не нужно.
Боюсь что универсального решения для любых типов данных достичь не получится хотя бы потому что внутреннее представление различных типов зависит от интерпретатора и платформы, и в общем случае непостоянно.
Но для str и int могу предложить такое решение:
def xor_bytes(data): accumulator = 0 for item in data: if isinstance(item, int): string = to_bytes(item) elif isinstance(item, str): string = item else: raise Exception('Invalid item type') for char in string: accumulator ^= (ord(char) & 0xff) return accumulatordef to_bytes(n, length=8, endianess='big'): h = '%x' % n s = ('0'*(len(h) % 2) + h).zfill(length*2).decode('hex') return s if endianess == 'big' else s[::-1]Способ эффективного вычисления контрольной суммы XOR(^) на основе списка идентификаторов
При поиске информации о понимании списков Python мне предложили задание Google foobar, над которым я потихоньку работал последние несколько дней. Последний вызов:
эффективно вызывает создание списка идентификаторов, игнорируя увеличивающееся число с каждой новой строки, пока не останется один идентификатор. Затем вы должны XOR(^) идентификаторы для создания контрольной суммы. Я создал рабочую программу, которая выводит правильный ответ, однако он недостаточно эффективен, чтобы пройти все тестовые случаи (проходит 6/10) за отведенное время. Длина 50000 должна дать результат менее чем за 20 секунд, но это займет 320.
Может ли кто-нибудь направить меня в правильном направлении, но, пожалуйста, не делайте этого для меня, я с удовольствием провожу себя этим вызовом. Возможно, есть структура данных или алгоритм, который я могу реализовать, чтобы ускорить время вычислений?
- Во-первых, начальный идентификатор и длина взяты в
- Создается список идентификаторов, игнорирующий все большее число идентификаторов из каждой новой строки, начиная с игнорирования 0 в первой строке.
- XORs все числа в списке IDS, используя цикл for
- Ответ возвращается как int
import timeit def answer(start,length): x = start lengthmodified = length answerlist = [] for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length". prestringresult = 0 templist = [] for y in range (x,x + length): #Fills list with ids for new line templist.append(y) for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first answerlist.append(templist[d]) lengthmodified -= 1 x += length for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult prestringresult ^= n stringresult = str(prestringresult) answerlist = [] #Emptys list answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list #print(answerlist[0]) #Print statement allows value that's being returned to be checked, just uncomment it return (answerlist[0]) #Returns Answer #start = timeit.default_timer() answer(17,4) #stop = timeit.default_timer() #print (stop - start) 4 ответа
Вам, вероятно, понадобится другой подход, а не только незначительные улучшения, как у Джона. Я только что написал решение, которое может сделать answer(0, 50000) примерно через 2 секунды на моем ПК. Я все еще делаю это строка за строкой, но вместо того, чтобы сохранять все числа в диапазоне строк, я делаю это постепенно. Сколько чисел в строке имеет 1-битный набор? [*] Нечетное количество чисел? Затем я переворачиваю 1 бит моего ответа. И затем то же самое для 2-битных, 4-битных, 8-битных и т. Д. До 2 30 -битных. Таким образом, для каждой строки это всего лишь 31 маленький расчет (вместо того, чтобы фактически хорировать десятки тысяч чисел).
[*] Может быть быстро вычислено в постоянное время, начиная с начала / остановки диапазона.Изменить: так как вы попросили другую подсказку, вот, как вычислить, как часто 1-бит установлен в некотором диапазоне (a, b). Вычислите, как часто он установлен в диапазоне (0, a) и вычтите его из того, как часто он установлен в диапазоне (0, b). Проще, если диапазон начинается с нуля. Как часто устанавливается 1-бит в некотором диапазоне (0, c)? Легко: c//2 раз. Итак, как часто устанавливается 1-бит в некотором диапазоне (a, b)? Просто b//2 — a//2 раз. Старшие биты похожи, только немного сложнее.
Редактировать 2: Ой, подождите, я только что вспомнил. есть простой способ вычислить xor всех чисел в некотором диапазоне (a, b). Снова разделите работу на выполнение диапазона (0, a) и диапазона (0, b). Xor всех чисел в некотором диапазоне (0, c) легко, потому что есть хороший образец (вы увидите это, если вы сделаете это для всех c от 0 до, скажем, 30). Используя это, я теперь решаю answer(0, 50000) примерно за 0,04 секунды.
Большинству людей будет превышено ограничение по времени в этом вопросе. Я сделал! Этот вопрос можно заключить следующим образом: «Найти XOR всех чисел, которые лежат между определенным диапазоном в постоянное время». Да, постоянное время!
Таким образом, с 3-6, ответ должен быть 3^4^5^6 = 4 в O(1) времени.
Решение: XOR носит ассоциативный характер. Таким образом, A ^ B ^ C можно записать как B ^ A ^ C. Также мы знаем, что XOR означает: «И», когда одни и те же биты приводят к Истине, т. Е. 1, а разные биты — к 2.
Исходя из этих двух свойств, мы можем написать: XOR между всеми числами из 3-6 можно записать как:
3^4^5^6 = (0^1^2)^(0^1^2) ^ (3^4^5^6) = (0^1^2^3^4^5^6) ^ (0^1^2) (this comes from the associative nature of xor) = XOR betn all the numbers from (0-6) ^ XOR betn all the numbers from (0-2). eq(1) Так что теперь, если мы сможем найти XOR всех чисел от 0 до определенного целого числа за постоянное время, мы получим наш ответ.
К счастью, существует шаблон для нас:
(0-1): 0 ^ 1 = 1 (1) (0-2): 0 ^ 1 ^ 2 = 3 (2+1) (0-3): 0 ^ 1 ^ 2 ^ 3 = 0 (0) (0-4): 0 ^ 1 ^ 2 ^ 3 ^ 4 = 4 (4) (0-5): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1 (1) (0-6): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 (6+1) (0-7): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0 (0) (0-8): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 = 8 (8) So the pattern for finding the xor between all the integers between 0 to n is: if n%4 == 1 then, answer = 1 if n%4 == 2 then, answer = n+1 if n%4 == 3 then, answer = 0 if n%4 == 0 then answer = n Therefore, XOR(0-6) becomes 7 (since 6%4 ==2) and XOR(0-2) becomes 3 (since 2%4 ==2) Therefore, the eq(1) now becomes: 3^4^5^6 = 7 ^ 3 = 4 Теперь вопрос довольно прост, большинство из нас застревают из-за ошибки превышения лимита времени, потому что мы пытаемся xor в каждом цикле, который был бы огромным, если количество входов / итераций увеличивается. Вот мое рабочее решение в Python, для которого все тестовые примеры были пройдены Google:
#Main Program def answer(start, length): checkSum = 0 for l in range(length, 0, -1): checkSum = checkSum ^ (getXor(start + l-1) ^ getXor(start-1)) start = start + length return checkSum def getXor(x): result = [x, 1, x+1, 0] return result[x % 4]