Проблемы обучения программизьму — Тогда и Сейчас. В том числе про Python.

Наткнулся на огромную статью о том как полезно учить детей программированию на Python. А у меня есть парочка наблюдений — во многом по работе новичков с Питоном на CodeAbbey (мой бесплатный и опенсорсный сайт — задачи там идут с оооочень плавным нарастанием сложности — аж скучно порой).

Обращение и Вращение Строки

Развернуть строку или сдвинуть её на K символов. Сложность эти задачи представляют только в языке вроде Pascal / C — т.к. операцию нужно осуществить «на месте» — в «мутабельной» строке. А на Питоне строки иммутабельны и «решение» сводится к конструированию новой строки. В жизни такие операции редко нужны — но детям‑то важно логику в голове развивать!

Округление

А здесь наоборот. Питон — язык профессиональный и операция round ведёт себя статистически корректно, но не так как учат в школе: round(1.5) = 2, round(2.5) = 2, round(3.5) = 4 — это настраивается — но новички не читают доки — и могут биться над задачей часами.

Бесконечные целые

Цель задачки «Modular Calculator» — показать принцип модульной арифметики. В обычных языках пока этот принцип не уяснишь — задача не решается из‑за переполнения целых. На Питоне же её пишут «втупую» даже не поняв в чем задача‑то. Пришлось добавить «продвинутую» версию — там «втупую» не дождёшься окончания расчета.

Какие же выводы?

1. Идеального языка для обучения пока нет. Быть может стоит изучать парочку разных!

2. Курсы стремятся показать результат а не развивать мышление.

Напишем код для управления пушкой, сбивающей корабли пришельцев!

Планирую несколько постов о разных технических решениях на моём (теперь опенсорсном!) сайте CodeAbbey. Но начать хочется с чего‑нибудь весёлого — поэтому начнем не по порядку, а с краткого рассказа о сравнительно новом типе задач.

Упражнения на сайте устроены так, что решать можно на любом языке — отправляем код решения и результат вычислений — но проверяется только результат (а код просто чтобы не потерялся). Но хотелось добавить и какой‑нибудь «интерактив» — и один из типов интерактивных задач — это игры, для которых пользователь пишет код выполняемый «с двух сторон»:

• в браузере, чтобы игру и решение пользователя тут же визуализировать

• на сервере, чтобы проверить насколько хорошо код пользователя работает

Первой идеей приходит сделать такие задачи на JavaScript — но т.к. сайт учебный, популярен здесь Python (больше 40% используют его). Пробовал реализации Питона на JS (Skulpt, позже Brython) — но у них есть недостатки... Короче, остановился на Lua — с одной стороны она похожа на Питон, но даже попроще, так что любой освоит в нужном для задачи объёме за 10–15 минут (есть инструкция). С другой — я её смог скомпилировать в JS (с помощью EMCC — вот на github).

Пример кода который пытается сбивать пришельцев «не глядя» — занимает 10–12 строк — он есть в тексте задачи. Есть и предыдущая задача попроще — определять попадание в пришельца. Было бы интересно услышать отзыв того, кто попробует решать не имея опыта в Lua!

CodeAbbey выходит в Opensource. Сайт с задачами по программированию я начал строить осенью 2013. За последнее десятилетие разных ресурсов в этой теме появилоcь невообразимое количество - от LeetCode до Hyperskill. Так что скромный CodeAbbey мало чем выделяется - кроме несколько архаичного дизайна и горстки задач оригинального типа. Упражнения на Brainfuck и машину Тьюринга, интерактив с Атакой Пришельцев, также задачи в которых нужно делать ходы HTTP-запросами на сервер, и наоборот написание веб-краулера.

В начале лета 2024 возникла дискуссия, как сохранить сайт (там ведь и от пользователей уже задач набежало) - на случай если со мной что-то случится :)

Идея с публикацией задач в виде книги энтузиазма не вызвала - а просто поделиться с кем-то доступом к серверу и сказать "разбирайтесь" - и неудобно и вероятно бесполезно.

Поэтому я засучил рукава и стал рефакторить код, выкладывая его по шагам на гитхаб. Каждый шаг получал отдельную ветку и некоторое описание - чтобы легче было поэтапно разобраться что к чему. Уже выложен весь основной функционал - с видео-инструкцией "как за полчаса задеплоиться на бесплатном хостинге". Теперь каждый может запустить подобный сайт для школы или ВУЗа, для коллег по работе.

По ходу оказалось что можно немало рассказать о разных технических мелочах придуманных для сайта. Правда пока не понял можно ли это делать в соответствии с правилами Хабра - можете прояснить в комментариях, кто разбирается :)

(cсылка на код в гитхабе найдётся в футере сайта)

Задачка от Т-Банка, тоже с собеседования - по сравнению с предыдущей что я показывал, от Яндекса, эта кажется ещё менее актуальной для рекрутинга в энтерпрайз - но я просто порадовался что смог её решить в live-coding режиме. Судите сами - хотели бы вы подобное встретить на собесе или нет :)))

Галя приехала на учёбу в большой университет в большом городе. Кампус расположен вдоль дороги, так что иногда между разными корпусами приходится ездить на автобусе. Галя студентка экономная и думает, как минимизировать стоимость билетов, если:

• разовый билет стоит 5 копеек

• безлимитный проездной на 2 дня - 18 копеек

• проездной на 3 дня с лимитом 6 поездок - 22 копейки

Входные данные - массив - сколько поездок пришлось на каждый день в месяце, например:

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 4

(здесь ответ 51)

Как это решается? Если вы знаете про "динамическое программирование" (ДП) то наверное уже поняли что задача об этом - поэтому я и удивился встретив такую задачу на собесе - скорее всего нам это не понадобится в энтерпрайзе (хотя в олимпиадных задачках популярно). Если не знаете про ДП, представьте рекурсию - вы пробуете в цикле каждый из трёх типов билетов, ездите сколько он позволяет - и дальше снова вызываете эту функцию для оставшихся поездок. Просто с рекурсией вы не дождётесь окончания работы, но с "мемоизацией" получите то же ДП "навывоворот". Я возился минут 30, но повтороив задачу у себя на сайте увидел что друзья решают аж в 3-4 строчки (ну, на питоне с @cache).

Задачка с собеседования от Яндекса. Скептически отношусь к ценности таких задачек при собеседовании сеньоров в обычный энтерпрайз - они скорее хороши на районном этапе школьной олимпиады. Но может я не прав? Итак задачка - из 4х предложенных над этой я думал дольше других:

В массиве целых чисел нужно найти фрагмент с заданной суммой.

Например, дан массив a = [4, 3, -8, 4, -1, 12, -5, 2] и целевая сумма 5 - тогда ответом будет фрагмент начиная с 3 и заканчивая -5, то есть в синтаксисе Питона sum(a[1:7]) = 5

В чем тут сложность? Сложность во "временной сложности" - требуется чтобы на массиве из миллиона чисел вычисление не занимало минуты. Поэтому наивный вариант не годится:

target = 5
for i in range(len(a)):
    for j in range(i+1, len(a)+1):
        if sum(a[i:j]) == target:
            print(i, j)

Здесь два вложенных цикла - каждый в среднем совершает число итераций сравнимое с длиной массива. Но функция sum(...) внутри тоже бежит по массиву - итого время выполнения пропорционально длине массива в кубе O(N*N*N)

Одно из усовершенствований заключается в том чтобы построить второй массив, в котором хранить сумму от начала массива до i-го элемента. Это позволит считать sum(i, j) не пробегая массив. Улучшение - теперь время пропорционально квадрату.

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