Имеются три разработчика: бэкенд (А), фронтенд (В) и фулстек (С). Первый всегда говорит правду, второй всегда лжёт, а третий всегда отвечает случайным образом, то есть может как соврать, так и сказать правду. Нужно за три вопроса выяснить, кто из них кто.
Ограничения и условия:
- программисты отвечают только фразами «Надо подумать» и «Зависит от ситуации». Одна из этих фраз означает «да», другая — «нет», но мы заранее не знаем, какая где;
- один и тот же вопрос двум разработчикам задавать нельзя (но задать два вопроса одному разработчику — можно);
- не обязательно задавать вопросы каждому разработчику, можно все три вопроса задать одному;
- вы сами решаете, кому и в каком порядке задавать вопросы;
- нельзя задавать философские вопросы, на которые нельзя ответить однозначно «Да» или «Нет»;
- нельзя задавать такие вопросы, на которые невозможно ответить.
Наша задача — однозначно определить бэкенда и фронтенда, чтобы методом исключения найти фулстека.
Самый высокий небоскреб в мире | Гигантские стройки | Discovery
Сложность задачи в том, что мы не знаем, что означают их ответы. Если мы что-то спросим и нам ответят «Надо подумать», то как мы поймём, это «Да» или «Нет»? Получается, что нам нужно задавать такие вопросы, чтобы уже с первого ответа понять, что на самом деле означает их «Зависит от ситуации» или «Надо подумать».
Но тратить один вопрос из трёх только чтобы выяснить это — глупо. Надо ещё получить какую-то информацию о том, кто перед нами (или кого перед нами точно нет). Значит, первый вопрос должен состоять из двух частей — дать нам новую информацию о разработчике и одновременно с этим установить, что у них означает «Зависит от ситуации» и «Надо подумать».
Например, сформулируем вопрос так «Если я спрошу у тебя „Программист В — это фулстек?“, ты ответишь мне „Зависит от ситуации“?»
Общая схема составления подобных вопросов такая: мы формулируем какой-то вопрос про другого программиста и спрашиваем, если бы ответ был верным, ты бы ответил вот так-то? Такие вопросы помогут понять, что за программист стоит перед нами, и, что самое важное, даст нам дополнительную информацию про второго программиста.
Чтобы понять, как работают такие вопросы и почему их нужно использовать, давайте разберём, как на них отвечают бэкенд и фронтенд. Фулстека пока разбирать смысла нет — он отвечает абсолютно рандомно, и как трактовать его ответы, расскажем позже.
Например, вот вопрос: «Если я спрошу у тебя „Разработчик В — это фулстек“, ты ответишь мне „Зависит от ситуации“?»
Если правильный ответ на заданный нами вопрос — «Да», то нам ответят «Зависит от ситуации», а если правильный ответ — «Нет», то нам ответят «Надо подумать».
Автор задачи понимал, что это утверждение нужно чем-то доказать, поэтому он сразу после текста задачи привёл доказательства своей правоты. Следите внимательно за логикой ответов.
1. Допустим, что «Зависит от ситуации» означает «Да», а «Надо подумать» означает «Нет»:
Виктория | Экстремальная экономия | TLC
- Мы спрашивали у бэкенда, и он ответил «Зависит от ситуации». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Зависит от ситуации», он означает «Да».
- Мы спрашивали у бэкенда, и он ответил «Надо подумать». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Надо подумать», то он означает «Нет».
- Мы спрашивали у фронтенда, и он ответил «Зависит от ситуации». Поскольку он всегда лжёт, то на наш вопрос он ответит «Надо подумать». Получается, что правильный ответ на вопрос — «Зависит от ситуации», который означает «Да».
- Мы спрашивали у фронтенда, и он ответил «Надо подумать». Так как он всегда лжёт, то на наш вопрос он ответит «Зависит от ситуации». Получается, правильный ответ на вопрос — «Надо подумать», который означает «Нет».
2. Представим обратное: «Зависит от ситуации» означает «Нет», а «Надо подумать» означает «Да»:
- Мы спрашивали у бэкенда, и он ответил «Зависит от ситуации». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Надо подумать», то его ответ означает «Да».
- Мы спрашивали у бэкенда, и он ответил «Надо подумать». Поскольку он всегда говорит правду и верный ответ на наш вопрос будет «Зависит от ситуации», то его ответ означает «Нет».
- Мы спрашивали у фронтенда, и он ответил «Зависит от ситуации». Так как он всегда лжёт, получается, что верный ответ на наш вопрос — «Надо подумать», и его ответ означает «Да».
- Мы спрашивали у фронтенда, и он ответил «Надо подумать». Поскольку он всегда лжёт, то верный ответ на наш вопрос — «Зависит от ситуации», и получается, что его ответ означает «Нет».
Это безумно сложное на первый взгляд доказательство математически верное. Мы к нему ещё вернёмся, когда будем рассказывать про математическую логику и про то, как она работает в жизни.
Если вы три раза прочитали это, но так ничего и не поняли — это нормально, тогда просто поверьте, что доказательство верное
Теперь мы можем это использовать для того, чтобы выяснить, кто из них кто.
1. Сначала зададим второму разработчику вопрос: «Если я спрошу у тебя „Первый разработчик — это фулстек?“, ты ответишь мне „Зависит от ситуации“?»
Если второй разработчик отвечает «Зависит от ситуации», значит, либо он фулстек и отвечает абсолютно рандомно, либо он не фулстек, а на самом деле первый разработчик — фулстек. В любом варианте, третий оставшийся разработчик — это не фулстек.
Если же второй отвечает «Надо подумать», то либо он фулстек и отвечает случайным образом, либо он не фулстек, а это означает, что первый разработчик — тоже не фулстек. В любом варианте, первый разработчик — это не фулстек.
2. По первому вопросу нам стало понятно, кто из них НЕ фулстек. Спросим у него: «Если я спрошу у тебя: „Ты — фронтенд?“, ты ответишь мне „Зависит от ситуации“?» Поскольку он не фулстек, ответ «Надо подумать» означает, что он бэкенд, а ответ «Зависит от ситуации» означает, что он фронтенд.
3. Спросим у этого же разработчика «Если я у тебя спрошу: „Программист, которому я задавал свой первый вопрос — фулстек?“, ответишь ли ты „Зависит от ситуации“?» Если ответят «Зависит от ситуации» — то первый, у кого мы спрашивали, будет фулстеком, а если нам ответят «Надо подумать», то фулстеком будет программист, с которым ещё не говорили.
Последний разработчик определяется методом исключения.
Если вы прочитали решение и всё поняли с первого раза — снимаем шляпу.
Источник: thecode.media
Русские Блоги
LeetCode-128. Самый длинный последовательный код Python3 последовательности + идеи решения проблем
0. Оригинальное название:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Перевод: Найти непрерывную последовательность значений элементов в заданном несортированном массиве целочисленных элементов и вывести наибольшую длину последовательности. Требование О (nСложность
1. Код:
class Solution: def longestConsecutive(self, nums): «»» :type nums: List[int] :rtype: int «»» list_length = len(nums) if(not list_length): return 0 counters = [] while(list_length): archor = nums.pop() counter = 1 #look forward target = archor — 1 while(target in nums): counter = counter + 1 nums.remove(target) target = target — 1 #look backward target = archor + 1 while(target in nums): counter = counter + 1 nums.remove(target) target = target + 1 counters.append(counter) list_length = list_length — counter return max(counters)
2. Мышление:
(1) Сначала вам нужно определить, является ли список пустым.
Этот шаг необходим, иначе Функция max () сообщит об ошибке при оценке пустого списка , Кроме того, поскольку длина списка чисел используется как в суждении if, так и в цикле while, для записи этого значения устанавливается параметр, то есть list_length = len (nums).
Обратите внимание, что не следует повторно вычислять длину списка чисел в цикле while, то есть while (len (nums)), это увеличит объем вычислений, и программа в итоге не сможет пройти из-за тайм-аута.
(2) Прочитайте элемент и определите количество соседних элементов в числах.
step1：Получить значение из чисел и записать его как якорь;
step2：Непрерывно ожидайте непрерывных значений, то есть, существуют ли якорь-1, якорь-2, якорь-3 и т. Д., Найдите одно, счетчик +1, пока не будет найдено непрерывное значение;
step3：Найти последовательные значения в обратном направлении и выполнить счетчик + 1 операцию. Наконец, запишите значение счетчика.
В процессе поиска, чтобы уменьшить количество повторяющихся операций, искомое значение должно быть удалено из числа во времени.
(3) Найти длину самой длинной непрерывной последовательности
Поскольку значение счетчика каждого шага записывается в счетчиках, до тех пор, пока max (счетчики) решены, можно получить окончательное решение.
Результаты 3.LeetCode
Источник: russianblogs.com
Величайшая программа из когда-либо написанных
Как вы думаете, какую из существующих программ можно назвать самой великой? Можете ли вы сказать про одну из своих программ, что она круче всех остальных? Есть мнение и, прямо скажем, далеко не безосновательное, что такую программу написал Дэвид Хорн в 1983 году: шахматы в один килобайт для ZX81.
Дэвид Хорн — это не какая-нибудь байка. Он достиг того, что многие из нас вообще сочли бы невозможным. Он написал шахматы с искусственным интеллектом (!) для плохо документированной и полной багов машины, содержащей всего один килобайт памяти. Мы говорим о Sinclar ZX81.
Задумайтесь на секунду об этом количестве памяти. Один килобайт. 1024 байта. Вы могли бы хотя бы записать правила шахмат менее, чем за тысячу символов? Это сама по себе нетривиальная задача.
Запустите свой любимый компилятор и соберите минимальное приложение, которое только возможно. Скорее всего оно уже будет занимать больше одного килобайта, хотя не делает вообще ничего полезного.
Так, подождите-ка. Один килобайт — это же общий объём памяти. Сколько из этого было доступно программисту? Ответ есть по ссылке в конце статьи, пользоваться можно было всего 672 байтами! Даже эта короткая статья занимает больше.
И в этих шахматах был ИИ. Не то чтобы это был очень умный ИИ, но тем не менее он был. То есть программа могла не только показывать доску, проверять правильность ходов, определять победителя (или ничью), но еще и выбирать ходы для себя и разыгрывать их.
Было еще кое-что. Дэвид не только продумал и реализовал идею шахмат в столь малом объеме памяти. Он еще опубликовал их полный исходный код с подробным объяснением того, как именно всё было сделано, в феврале 1983 года в журнале «Your Computer». Эта статья прямо таки погружает нас в захватывающую 8-битную атмосферу тех времён, когда существенные ограничения заставляли программистов писать по настоящему компактный и эффективный код.
Итак, Дэвид Хорн, эта статья посвящается вам.
Тому, кто создал величайшую программу из когда-либо написанных.
Источник: tproger.ru