Рассказ на одну остановку яндекс дзен

Написание однострочников в python всегда было довольно интересным для меня, и однажды я заинтересовался - а любой ли алгоритм возможно

Написание однострочников в Python всегда было довольно интересным для меня, и однажды я заинтересовался — а любой ли алгоритм возможно реализовать всего в одну строчку Python кода ?

Оказалось — да!

Немного теории

Исполнитель называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию, и наоборот. То есть, чтобы доказать что в одну строку на Python можно написать какой угодно код, необходимо доказать Тьюринг-полноту однострочных программ на python. Как это сделать ?

Довольно простой способ, который я и выбрал — имитировать другую исполнительную систему, для которой уже доказано, что она обладает полнотой по Тьюрингу. Например, я мог бы написать интерпретатор языка PHP, который, естественно, является Тьюринг-полным, как и почти все существующие языки программирования. В этом, однако, нет никакой необходимости, ведь есть гораздо более простые системы, полные по Тьюрингу. Например, клеточный автомат, под названием Правило 110.

Чёткие правила данного автомата изложены в Википедии по ссылке здесь.

Вкратце, мы имеем бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния (0 и 1), будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей и рассчитывается по определённому несложному алгоритму.

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

Реализация

Сразу уточню, что символ «;» я считал началом новой строки, чем он по сути и является, иначе задача превращается в тривиальную.

Итак, опредилившись с тем что же именно я собираюсь написать, я, недолго думая, запустил VSCode и… И завис. Потому что неясно было что писать. Ясно было, что нужен цикл while, ввод начального состояния, которое нужно как-то обработать, действия над ним в цикле, Кроме того, цикл надо ещё как-то остановливать, если состояние системы стабилизировалось и больше не меняется.

Как это всё уместить в одну строчку, было не очень понятно. Например даже результат вызова input() нельзя никак занести в обычную в переменную и потом работать с ним дальше одной строкой.

# А не работает так!
while (a=int(input()) or a!=0):print(a)

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

#Объявление
globals().update({"a":0})
#Получение значения
globals().get("a")
# Простейший цикл while
while (globals().update({"a":int(input())}) or globals().get("a")!=0):print(globals().get("a"))

В этом примере мы также пользуемся тем, что исполняемая функция globals.update() возвращает None, а условие (None or value) почти всегда вернёт value, кроме некоторых случаев. То есть, по факту, условный оператор or можно использовать, чтобы встраивать любой исполняемый код в условие. Разумеется, можно написать сколько угодно … or … or … подряд, так что задача существенно упрощается.

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

https://github.com/Thane784/rule_110

Куда же тыкать ?

Основной файл — code.py Там, правда есть некоторые проблемы с выводом — для человека он не очень читаем. Можно запустить файл show.py , там цикл искусственно ограничен 25 итерациями и всё видно нагляднее.

Итоговый код и как он работает

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

Для этого заведем две глобальные переменные «s» (string) и «l» (last). Да, я знаю, что s и l — не очень хорошие названия для переменных, но для одноразового кода, который никто в дальнейшем поддерживать не будет, думаю нормально.

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

# Записываем нач. состояние в переменную,
# выводим его же в консоль, 
# причём только если предыдущего состояния нет,
# то есть на первой иттерации цикла,
# используем оператор or для исполнения кода.
# По факту в сравнение пойдет лишь globals().get("s")),
# которое мы и сравниваем с предыдущим состоянием globals().get("l"))
while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): print('')

Далее, уже в теле цикла мы объявляем фиктивную переменную a которой присваиваем значение длинного длинного сравнения через оператор or. На самом деле, оператор сравнения здесь нужен чтобы выполнить большое количество исполняемого кода, в котром каждая вызываемая функция вернёт None. Возможно, можно было реализовать подобное более красиво, но это самое быстрое рабочее решение, которое пришло мне в голову.

#Скелет
while last_code: a = (func1() or func2() or func3() or 1)

В полном же варианте нарощенном на данный скелет мы обновляем l (предыдущее состояние), проходим один цикл клеточного автомата, перезаписывая переменную s, и выводим новое состояние.

Для хранения состояния используем строку, постепенно обрабатывая её, собираем массив, который содержит новое состояние. Этот массив затем приводим к строке при помощи функции ».join() и перезаписываем глобальную переменную s. Скорее всего, можно было бы обойтись без массива, но оптимизация здесь не слишком важна. Также, при определённых условиях расширяем наблюдаемую область(если в результате работы алгоритма «оживились» клетки, ранее нами не отслеживаемые(поле, естесственно бесконечно), откуда кстати и проблемы с выводом — довольно скоро поле становится ОЧЕНЬ большим). Большую часть кода занимает вычисление следующего состояния на основе предыдущего, это просто множество условий if elif else записанных в одну строчку.

Вот так выглядит финальный код.

while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): a = ( globals().update({"l": (globals().get("s"))}) or globals().update({"s": (''.join(['1' if globals().get("s")[0] == '1' else '']+[('0' if (n != 0 and n!=(len(globals().get("s"))-1) and (globals().get("s")[n-1:n+2] == '000' or globals().get("s")[n-1:n+2] == '100' or globals().get("s")[n-1:n+2] == '111') ) else '0' if (n == (len(globals().get("s"))-1) and ( ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '00' or ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '10') ) else '0'  if (n == 0 and globals().get("s")[0]+(globals().get("s")[1] if len(globals().get("s"))>1 else '0') == '00'  ) else '1') for n in range(0,len(globals().get("s")))]) )})  or (print(globals().get("s")) if globals().get("s") != globals().get("l") else None)  or 1)

Что же в итоге ?

Итак ! Мы написали в одну строчку Тьюринг-полную систему, чем доказали, что однострочники на python обладают Тьюринг-полнотой. Что же это значит ? Это значит, что в одну строчку python кода можно написать всё что угодно ! Даже Windows 11 или ядро Linux.

Правда, скорее всего, код получится слегка нечитаемым да и дебаггинг будет затруднён…)

P. s.

Автор знаком с python на любительском уровне и не пишет на нём ничего серьёзного, поэтому прошу простить, если проглядел какие-то очевидные вещи и возможности. Автор понимает, что написание подобного кода в реальном проекте, чревато некоторым непониманием со стороны коллег и не призывает никого повторять изложенные здесь эксперименты)

Источник

5 декабря 2021, воскресенье

Стелу в честь обороны Москвы поставили в Крюково

4 декабря 2021, суббота

Разыскивают пропавшего в Зеленограде 38-летнего Казбека Голаева. Помогите найти

3 декабря 2021, пятница

Начались продажи квартир в будущем зеленоградском микрорайоне ЦИЭ. Теперь он называется «Зелёный парк»

На зимовку в Зеленоград прилетели первые свиристели и чечётки

Право построить гостиницу напротив 14-го микрорайона получил новый инвестор. Это уже пятая попытка

Муниципальный детский сад в ЖК «Новый Зеленоград» получил разрешение на строительство

Военно-историческая реконструкция «У деревни Крюково…» — 4 декабря в Андреевке

Концерт панк-группы F.P.G — 4 декабря в клубе Sova

2 декабря 2021, четверг

Киберклуб Black открылся после переезда и ремонта по новому адресу

Квартира 39 с директором на кухне — полувековая история Зеленоградского музея, которая только начинается

«Микрон» начал серийное производство компонентов для силовой электроники по технологии Trench MOSFET

400-му автобусу до «Тушинской» добавили еще одну остановку на Кутузовском шоссе. Она будет возле жилого комплекса «Новый Зеленоград»

Концерт jazz-fusion группы Ascorbic Acid — 3 декабря в «Кинематографе». Клуб друзей «Зеленоград.ру» дарит билеты

Сетевой «Магазин постоянных распродаж» появился в 15-м микрорайоне

1 декабря 2021, среда

Две заправки «Лукойл» откроются на М-11 рядом с Шереметьево

Шоу под дождём «Мужчина и женщина» — 23 декабря в КЦ «Зеленоград». Клуб друзей «Зеленоград.ру» и КЦ дарят билеты

Отель Hilton Garden Inn построят в Зеленограде в 2025 году рядом с площадкой ОЭЗ «Алабушево»

30 ноября 2021, вторник

Вывоз мусора для жителей подорожает с января. Теперь эта услуга будет в платежке отдельной строкой

«Пизанская» береза в 4 микрорайоне держится благодаря стулу

Скоростные «Ласточки» до Клина теперь будут ходить и по выходным

Шахматный турнир «Ход конём» — 5 декабря в Культурном центре «Зеленоград»

Автобусы-экспрессы запустили от метро «Ховрино» до Твери. Они едут по М-11 без остановок

29 ноября 2021, понедельник

Светофор начали устанавливать на переходе через Московский проспект возле остановки «Дворец культуры»

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

Советский танк, затонувший 80 лет назад, может лежать под землей возле Школьного озера. Его предлагают поднять и сделать музейным экспонатом

Сделать выделенную полосу для автобусов на Солнечной аллее на пересечении со старым мостом

Ночной вор вынес из «Пятёрочки» алкоголь почти на девять тысяч рублей

Как готовятся к зиме на платной дороге М-11

Поиск по новостям

Источник

8 декабря 2021, среда

Кулинария «Брецель» открылась в 12-м микрорайоне

Сделать новогоднюю фотозону в подъездах жилых домов

Магазин «Дикси» в третьем микрорайоне закрывается

«Субботник» по уборке снега организуют в Голубом

Лекция по безопасности для детей от школы ЛизаАлерт — 12 декабря в библиотеке в корпусе 1106

7 декабря 2021, вторник

Найденная на стройке в 19-м микрорайоне «мина времён войны» оказалась вовсе не снарядом

Женщина попала под машину рядом с больницей. Она переходила дорогу в неположенном месте, хотя рядом переход

Сразу десять новых станций метро открыли в Москве

В каких домах Зеленограда будут делать капитальный ремонт и менять лифты в 2022 и 2023 годах

Всероссийские технологические соревнования «Радиофест 2021» прошли в Зеленограде: задания, участники и победители

Фура перекрыла Ленинградское шоссе возле Чёрной грязи. Пробка растянулась на семь километров

6 декабря 2021, понедельник

Умерла заслуженный учитель Антонина Корешкова. Она стояла у истоков зеленоградского образования

Сайт недвижимости ЦИАН запретил сдавать жилье «только славянам». Риелтор считает, что запретом писать какие-то слова в рекламе проблему не решить

Мину времён войны нашли на стройке новых домов в 19-м микрорайоне

Почему в 400-м экспрессе редко появляются контролеры?

Ночные «Ласточки-экспрессы» пустят между Москвой и Зеленоградом по выходным

«Не умереть — надо уметь». Где в Зеленограде работают группы анонимных алкоголиков и наркоманов

5 декабря 2021, воскресенье

Стелу в честь обороны Москвы поставили в Крюково

4 декабря 2021, суббота

Разыскивают пропавшего в Зеленограде 38-летнего Казбека Голаева. Помогите найти

3 декабря 2021, пятница

Начались продажи квартир в будущем зеленоградском микрорайоне ЦИЭ. Теперь он называется «Зелёный парк»

На зимовку в Зеленоград прилетели первые свиристели и чечётки

Право построить гостиницу напротив 14-го микрорайона получил новый инвестор. Это уже пятая попытка

Муниципальный детский сад в ЖК «Новый Зеленоград» получил разрешение на строительство

Военно-историческая реконструкция «У деревни Крюково…» — 4 декабря в Андреевке

Концерт панк-группы F.P.G — 4 декабря в клубе Sova

2 декабря 2021, четверг

Киберклуб Black открылся после переезда и ремонта по новому адресу

Квартира 39 с директором на кухне — полувековая история Зеленоградского музея, которая только начинается

«Микрон» начал серийное производство компонентов для силовой электроники по технологии Trench MOSFET

400-му автобусу до «Тушинской» добавили еще одну остановку на Кутузовском шоссе. Она будет возле жилого комплекса «Новый Зеленоград»

Концерт jazz-fusion группы Ascorbic Acid — 3 декабря в «Кинематографе». Клуб друзей «Зеленоград.ру» дарит билеты

Сетевой «Магазин постоянных распродаж» появился в 15-м микрорайоне

Поиск по новостям

Источник

  • Рассказ на одну остановку империя
  • Рассказ на одну букву небольшой
  • Рассказ на немецком языке слушать
  • Рассказ на ночь взрослым читать
  • Рассказ на одну букву для детей 1 класса