Функция многозначная, поэтому и квантор. Ну да я особо не задумывался о красивой нотации. Можно переписать в виде однозначной функции, возвращающей множество цепочек.
В языках с генераторами списков удобно иметь дело с многозначностью, нежели энергично рожать множества.
Множество чисел, являющихся квадратами натуральных чисел, и лежащих в диапазоне от 1 до 2n. Потому что для пар чисел (x,y) из диапазона от 1 до n, их сумма лежит в диапазоне.... а, ну да, конечно, от 2 до 2n.
Красная шапка с её TOO LONG TERM SUPPORT - это лютый ад. Хотите самые древние версии компиляторов? Хотите, чтобы ваши клиенты с редхатом / центосью задалбывали вас обратной совместимостью? Хотите задолбать ваших партнёров обратной совместимостью с вашим редхатом? Тогда этот путь - ваш.
3) делаем рекурсивную функцию, строящую цепочки (W - множество использованных в цепочке чисел)
4) запускаем её для всех стартовых значений
Это будет тупой перебор, но в нём не будет ничего лишнего :)
Представление таблицы смежности как двоичной матрицы - не очень эффективно, потому что заставит бегать по строке матрицы, в которой порядка √n единичек и (n-√n) ноликов.
Видимо, мейнтейнеры питона, включая пожизненного диктатора, побоялись устраивать второе ледовое побоище, им 2to3 хватило.
Ну а что касается скорости, то инкременты-декременты на каждый чих не выглядят большими затратами по сравнению с бизнес-логикой, а уборка мусора и так и этак сожрёт положенное ей время, будь то детерминизм на рефкаунтах или какие-либо отложенные сценарии. Единственный по-настоящему дешёвый сборщик мусора - это убийство процесса.
Это литкод и уровень easy. Сгодится абсолютно любое решение.
Проверяльщик смотрит там лишь на то, чтобы поля val у списка результатов были равны ожидаемым. Типизация утиная, можно вместо ListNode вернуть TsilEdon - и он сожрёт.
На эрланге в принципе не получится вернуть не копию. А на питоне можно и так и этак.
Причём стресс-теста для этой задачи нет, O(n) по памяти отлично проходит.
А вот алгоритмом маляра Шлемюэля я проверяльщика не удосужился проверить, хотя думаю, что и O(n^2) по времени тоже пролезет, ну будет в общем зачёте первое место с конца.
В первом приближении очень интересно, и, хотя мне оно на практике не требуется, но вкурить в эти методы, однозначно, стоит. Завтра на свежую голову в рабочее время вместо работы :))
Как решать задачИ - vs как решить задачУ. Я уже написал выше.
Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)
Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.
Вообще же, литкод уровня медиум и хард - это такое олимпиадное программирование. Говнокодить write-only, лишь бы пролезло по ограничениям на производительность, - ради бога.
Один раз по приколу я сграбил все тестовые входные данные и написал табличное решение, и его засчитали, ахаха. Куда уж оптимальнее.
Параметры для оптимизации скажите. Вы ведь, как сеньор, знаете, что их несколько.
1) Скорость исполнения. Тут фортран и фортранный стиль рулят.
2) Устойчивость к ошибкам. Тут надо заметно сдвигаться в сторону функциональщины.
3) Читаемость и сопровождаемость. Посреди между фортраном и фп.
Движок литкода смотрит только на скорость исполнения. Но для задач уровня easy это вообще ни разу не является критерием. Можно, конечно, поучаствовать в олимпиаде "ваше решение выполнилось быстрее и сожрало меньше памяти, чем 99.99% других", но для питона перфтесты слишком шумят. А может, там сам тестовый стенд криво настроен и плохо изолирован. Сами убедитесь, запустите ваше решение десять раз и получите десять разных измерений.
Я сейчас запостил и ваше, и мои решения, - и внезапно мои оказались капельку быстрее.
Ну блин, если бы вам предложили решить какую-нибудь простенькую задачку по математике, которую почему-то вы забыли, как решали в 9 классе, - то тоже бы расписали? Для 9-классника это норма, для 8-классника это подвиг, для сеньора - это детство.
Я на ютубе встречал каналы по математике с таким контентом, но их ведут репетиторы для школьников, там очень адресная аудитория.
И, на мой взгляд, "один ролик/пост - одна задачка" - это хлебный мякиш. Либо задача должна быть со звёздочками, либо охват предмета должен быть большой: например, класс задач и системный подход к ним, или всевозможные закоулки одной задачи.
Вот, например, алгоритмы бисекции содержат такие закоулки (граничные условия), и наивная реализация "с листа" у многих программистов получается с багами. Можно ли такое сказать про переворот списка?
Я-то, как раз, могу раскрыть тему. Но статью писать мне, пардон, лень. Это надо план изложения продумать и всё такое.
Могу накидать направления работы:
как решать эту задачу с мутабельными и иммутабельными структурами (с мутабельными уже показано)
виды циклов и рекурсий
выразительные возможности разных языков (а не единственное решение в духе "на любом языке можно писать на фортране")
Просто покажу, как можно на ровном месте сделать чуть красивее.
def revert_sequential_and_verbose(head):
prev = None
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
return prev
def revert_using_tuple_assign(head):
prev = None
while head:
head, prev, head.next = head.next, head, prev
return prev
А можно чуть изощрённее, - избавиться от цикла while на верхнем уровне
def iterate_single_linked(head):
while head:
#####################
# здесь был спойлер #
#####################
def revert_using_for_loop(head):
prev = None
for curr in iterate_single_linked(head):
curr.next, prev = prev, curr
return prev
def revert_using_reduce(head):
def op(prev, curr):
#####################
# здесь был спойлер #
#####################
return functools.reduce(op, iterate_single_linked(head), None)
Разумеется, использование генераторов и ФВП (и даже кортежей) на питоне вносит лишние накладные расходы по сравнению с наивным строго последовательным "сишно-фортрановым" решением. Но, тем не менее...
Вот, что мы бы тут ожидали увидеть на хабре от автора.
Первое и самое главное: этическая сторона дела. Задача на интервью предназначена для проверки самостоятельного мышления соискателя. Выкладывать её успешное решение на всеобщий обзор - это вносить смещение в объективность следующих интервью. Проще говоря: автор выложил спойлер.
Сама по себе задача очень простая (на литкоде имеет уровень easy). Это значит, что обсуждать её есть смысл, когда есть что добавить интересного к эталонному решению. Ну вот выше уже упомянули про терабайтные наборы. Или, например, обсудить существенно разные реализации (в существенно разных языках - или в разных парадигмах на одном и том же питоне). Или ещё что-нибудь... Иначе это как-то не соответствует заявленному автором званию Senior.
Уже сам по себе старт: "давайте сделаем дефолтную реализацию с O(n) дополнительной памяти, а потом разгоним" выглядит странно. Ну ок, тогда давайте поиграем в другой жанр, в ненормальное программирование: найти самый медленный и прожорливый алгоритм? Есть же соревнование в замедлении сортировки, почему бы и в замедление разворота списка не посоревноваться?
В общем, решение на пятёрочку, а статья на двоечку с плюсом. За это и минусы. А не за мифические обидки.
Все эти штуковины решаются однообразно с помощью алгебры.
Допустим, сумма p-й степени чисел - это полином (p+1)-й степени.
И решаем уравнение "для произвольного n", получаемое из утверждения индукции.
которое рассыпается на систему уравнений над переменными a[k].
Странно, что для четвёртой степени потребовалась тысяча лет. Ну да это, наверно, влияние пифагоровского очарования целочисленно-геометрическими методами.
Функция многозначная, поэтому и квантор. Ну да я особо не задумывался о красивой нотации. Можно переписать в виде однозначной функции, возвращающей множество цепочек.
В языках с генераторами списков удобно иметь дело с многозначностью, нежели энергично рожать множества.
Множество чисел, являющихся квадратами натуральных чисел, и лежащих в диапазоне от 1 до 2n. Потому что для пар чисел (x,y) из диапазона от 1 до n, их сумма лежит в диапазоне.... а, ну да, конечно, от 2 до 2n.
У вас в КПДВ логотип старого центоса, а на сайте в конфигураторе - центос стрим 9. Ай-яй-яй, небрежность.
Красная шапка с её TOO LONG TERM SUPPORT - это лютый ад. Хотите самые древние версии компиляторов? Хотите, чтобы ваши клиенты с редхатом / центосью задалбывали вас обратной совместимостью? Хотите задолбать ваших партнёров обратной совместимостью с вашим редхатом? Тогда этот путь - ваш.
Казалось бы,
1) получаем множество квадратов
2) получаем таблицу смежности
3) делаем рекурсивную функцию, строящую цепочки (W - множество использованных в цепочке чисел)
4) запускаем её для всех стартовых значений
Это будет тупой перебор, но в нём не будет ничего лишнего :)
Представление таблицы смежности как двоичной матрицы - не очень эффективно, потому что заставит бегать по строке матрицы, в которой порядка √n единичек и (n-√n) ноликов.
Видимо, мейнтейнеры питона, включая пожизненного диктатора, побоялись устраивать второе ледовое побоище, им 2to3 хватило.
Ну а что касается скорости, то инкременты-декременты на каждый чих не выглядят большими затратами по сравнению с бизнес-логикой, а уборка мусора и так и этак сожрёт положенное ей время, будь то детерминизм на рефкаунтах или какие-либо отложенные сценарии. Единственный по-настоящему дешёвый сборщик мусора - это убийство процесса.
Как легаси поведение тоже.
Типичный код вида
с рефкаунтом объекты финализируются сразу после использования.
Без рефкаунта это произойдёт в непредсказуемый момент времени сильно позже.
Разумеется, безопасно писать
но это более громоздко.
И опять же, существует легаси код и легаси стиль, с которым надо что-то делать, а не радикально ломать обратную совместимость.
Это литкод и уровень easy. Сгодится абсолютно любое решение.
Проверяльщик смотрит там лишь на то, чтобы поля val у списка результатов были равны ожидаемым. Типизация утиная, можно вместо ListNode вернуть TsilEdon - и он сожрёт.
На эрланге в принципе не получится вернуть не копию. А на питоне можно и так и этак.
Причём стресс-теста для этой задачи нет, O(n) по памяти отлично проходит.
А вот алгоритмом маляра Шлемюэля я проверяльщика не удосужился проверить, хотя думаю, что и O(n^2) по времени тоже пролезет, ну будет в общем зачёте первое место с конца.
Хабр - торт!
В первом приближении очень интересно, и, хотя мне оно на практике не требуется, но вкурить в эти методы, однозначно, стоит. Завтра на свежую голову в рабочее время вместо работы :))
Я уже предложил в комментарии. Кортежи работают эффективнее последовательных присваиваний. Но вы только и знаете, что лепить минусы.
Как решать задачИ - vs как решить задачУ. Я уже написал выше.
Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)
Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.
Вообще же, литкод уровня медиум и хард - это такое олимпиадное программирование. Говнокодить write-only, лишь бы пролезло по ограничениям на производительность, - ради бога.
Один раз по приколу я сграбил все тестовые входные данные и написал табличное решение, и его засчитали, ахаха. Куда уж оптимальнее.
Параметры для оптимизации скажите. Вы ведь, как сеньор, знаете, что их несколько.
1) Скорость исполнения. Тут фортран и фортранный стиль рулят.
2) Устойчивость к ошибкам. Тут надо заметно сдвигаться в сторону функциональщины.
3) Читаемость и сопровождаемость. Посреди между фортраном и фп.
Движок литкода смотрит только на скорость исполнения. Но для задач уровня easy это вообще ни разу не является критерием. Можно, конечно, поучаствовать в олимпиаде "ваше решение выполнилось быстрее и сожрало меньше памяти, чем 99.99% других", но для питона перфтесты слишком шумят. А может, там сам тестовый стенд криво настроен и плохо изолирован. Сами убедитесь, запустите ваше решение десять раз и получите десять разных измерений.
Я сейчас запостил и ваше, и мои решения, - и внезапно мои оказались капельку быстрее.
Ну блин, если бы вам предложили решить какую-нибудь простенькую задачку по математике, которую почему-то вы забыли, как решали в 9 классе, - то тоже бы расписали? Для 9-классника это норма, для 8-классника это подвиг, для сеньора - это детство.
Я на ютубе встречал каналы по математике с таким контентом, но их ведут репетиторы для школьников, там очень адресная аудитория.
И, на мой взгляд, "один ролик/пост - одна задачка" - это хлебный мякиш. Либо задача должна быть со звёздочками, либо охват предмета должен быть большой: например, класс задач и системный подход к ним, или всевозможные закоулки одной задачи.
Вот, например, алгоритмы бисекции содержат такие закоулки (граничные условия), и наивная реализация "с листа" у многих программистов получается с багами. Можно ли такое сказать про переворот списка?
Я-то, как раз, могу раскрыть тему. Но статью писать мне, пардон, лень. Это надо план изложения продумать и всё такое.
Могу накидать направления работы:
как решать эту задачу с мутабельными и иммутабельными структурами (с мутабельными уже показано)
виды циклов и рекурсий
выразительные возможности разных языков (а не единственное решение в духе "на любом языке можно писать на фортране")
А с чего вы взяли, что кто-то лепит минусы на всё подряд?
Просто покажу, как можно на ровном месте сделать чуть красивее.
А можно чуть изощрённее, - избавиться от цикла while на верхнем уровне
Разумеется, использование генераторов и ФВП (и даже кортежей) на питоне вносит лишние накладные расходы по сравнению с наивным строго последовательным "сишно-фортрановым" решением. Но, тем не менее...
Вот, что мы бы тут ожидали увидеть на хабре от автора.
Первое и самое главное: этическая сторона дела. Задача на интервью предназначена для проверки самостоятельного мышления соискателя. Выкладывать её успешное решение на всеобщий обзор - это вносить смещение в объективность следующих интервью. Проще говоря: автор выложил спойлер.
Сама по себе задача очень простая (на литкоде имеет уровень easy). Это значит, что обсуждать её есть смысл, когда есть что добавить интересного к эталонному решению. Ну вот выше уже упомянули про терабайтные наборы. Или, например, обсудить существенно разные реализации (в существенно разных языках - или в разных парадигмах на одном и том же питоне). Или ещё что-нибудь... Иначе это как-то не соответствует заявленному автором званию Senior.
Уже сам по себе старт: "давайте сделаем дефолтную реализацию с O(n) дополнительной памяти, а потом разгоним" выглядит странно. Ну ок, тогда давайте поиграем в другой жанр, в ненормальное программирование: найти самый медленный и прожорливый алгоритм? Есть же соревнование в замедлении сортировки, почему бы и в замедление разворота списка не посоревноваться?
В общем, решение на пятёрочку, а статья на двоечку с плюсом. За это и минусы. А не за мифические обидки.
Одни ставят минусы, а кое-кто другой обиделся.
Какой интересный подход! Берём частичную функцию и говорим: на каком подмножестве она определена, на таком типе она и тотальна. Ахтыжхитраяжопа!
Взяли SGML, зачем-то сказали, что это HTML и пытаетесь тут нас обмануть.
Всех этих тэгов for, def, call в HTML нет.
А пользовательские тэги нафигачить и пользовательским парсером их обработать - дурное дело нехитрое.
Все эти штуковины решаются однообразно с помощью алгебры.
Допустим, сумма p-й степени чисел - это полином (p+1)-й степени.
И решаем уравнение "для произвольного n", получаемое из утверждения индукции.
которое рассыпается на систему уравнений над переменными a[k].
Странно, что для четвёртой степени потребовалась тысяча лет. Ну да это, наверно, влияние пифагоровского очарования целочисленно-геометрическими методами.