Хорош ли номер ч. 3

Закончим задачу из поста.

Итак, в прошлый раз я уже писал regexp, теперь проговорю словами: по сути валидное число это decimal или integer, которые могут быть продолжены символом 'e' или 'E' за которым идёт integer. Очень читабельное решение получается при разбиении строки на две части – до и после 'e/E'. Полученные части будут достаточно просты, что б проверить их циклом в один проход.

Код будет в комментарии. Обратите внимание на функцию isDecimal: на самом деле она не отличает decimal от integer, но это работает:) – Да, углы немного срезаны. Итоговая сложность, очевидно, линейна.

#today #c_plus_plus #leetcode #algo

Обычно я пишу заметки в тот момент, когда у меня на руках уже есть готовое решение – возможно, оно сделано несколько лет назад, возможно – сегодня.

Однако, часто так бывает, что найти хорошее решение, не изобретая велосипед, – практически невозможно. Неожиданный пример такой проблемы: умножение двух uint64_t по модулю в C++. Тут важны все слова: умножить без модуля – не очень сложно, использовать uint32_t – легко, не в C++ – окей, кто знает – тот знает.

А в чём собственно проблема? – в том, что, вообще говоря, произведение двух uint64_t не влезет в uint64_t, а стандартного типа uint128_t – нет.

Но есть же какая-то библиотека, где это уже сделано? – конечно, тот же gmp, но это не то решение, которое я ищу.
А что, если разбить uint64_t на две половинки по 32 бита, как-то их перемножить и т.д.? – к сожалению, это тоже не работает, в какой-то момент в формуле всё равно вылезет необходимость перемножить два uint64_t. Есть пара похожих вариантов, которые мне лень расписывать, и которые тоже не работают.
А есть же расширение __int128? – Да, есть, но только для GCC.
И что ничего нельзя сделать, если хочется получить самописную платформонезависимую реализацию данной операции? – Можно, вот только потребует это удивительно много строк кода.

Рассмотрим пару вариантов:
1) реализовать сначала обычное умножение с сохранением в пару uint64_t, потом по-честному поделить на модуль, вернув остаток
2) использовать алгоритм Монтгомери

Относительно первого варианта: реализовать умножение – сравнительно легко, вот с делением будет проблема: стандартный алгоритм (примерно то, что изучается в школе) потребует явный цикл...есть другие алгоритмы, но они ещё более неприятны в имплементации (например, рассмотренный мной метод Ньютона-Рафсона)

Относительно второго варианта – он выходит за рамки среднестатистических знаний об алгоритмах (включая, и мои знания на данный момент), но вот вам ссылка.

Вишенка на этом торте безумной "удобности" C++ является то, что процессор это умеет: можно посмотреть тут. Можно в godbolt дизассемблерить простой листинг для GCC.

typedef unsigned __int128 uint128_t;
uint128_t mult(uint64_t a, uint64_t b)
{
    return uint128_t(a) * uint128_t(b);
}

Так что вы говорите там будет интересного в новом стандарте?

#today #c_plus_plus #algo #hatred

Вернемся к задачам на Leetcode: часто такое бывает, что читаешь условие – и не можешь понять, что нужно сделать, перечитываешь снова, смотришь testcases, и только тогда – понимаешь. С этой сложной задачей всё абсолютно наоборот – сложно представить себе условие сформулированное ещё проще, тут даже разработчиком быть не обязательно.

Convert a non-negative integer num to its English words representation. То есть записать данное положительное целое число прописью.

Решение будет опубликовано спустя несколько дней. Кстати, на всякий случай уточню: задачи Leetcode не привязаны к определенному ЯП – просто на данный момент мне проще решить их на C++, но если вам более знаком Python, C#, you name it – просто используйте их, скорее всего платформа его поддерживает.

#leetcode #algo #ToBeContinued #English

На разных этапах карьеры — разные уровни спокойствия

#кек

Книги ч.2

Стиль и сюжет – не единственный способ рассуждения о книгах. Забавно, но можно увидеть аналогию между всем произведением и его малой составляющей – предложением. Как известно, приличное предложение должно состоять хотя бы из одной пары подлежащего и сказуемого, так вот – это и есть сюжет, а именно: подлежащее – главный герой (герои), сказуемое – его поступки. Карл/командор/принцесса родился/полетел/пошёл на войну, затем попал в Пентагон/ нашёл миллион/ познакомился – и так далее.

А ещё есть всякие второстепенные члены предложения: обстоятельства, определения, дополнения. Поскольку это аналогия, а любая аналогия – фаль^W^неточна – я укорочу этот список, так же как и содержание этих категорий. В данном контексте определение – лишь то, что характеризует главных героев, включая изначальную репрезентацию, а обстоятельство – всё что угодно их окружающее и являющееся фоном повествования, включая и повседневное толкование этого слова, дополнений же – не существует вовсе.

Итак, главный герой какой он там и откуда: отважный/сонный капитан дальнего плавания родом из Харбина, увлекающийся поэзией/квантовой физикой, – это всё его определение, которое может изменяться и/или развиваться в процессе повествования. Где и на каком фоне происходят события – в Париже начала 20-го века, в Средиземье, во сне – обстоятельство.

Возвращаясь к озвученному в прошлом посте: сюжет – последовательность действий главных героев (подлежащее и сказуемое), стиль – совокупность второстепенных членов предложения...Нет! Стиль – это метакатегория, это инструмент, которым создаётся всё повествование, но в тоже время, включающий в себя обстоятельства и определения.

Кстати, всё вышеизложенное я в шутку окрестил "Лингвистической теорией разбора". Не претендую на истину в последней инстанции.

#today #flood #superflood #books #humor

Продолжим то, что начали в прошлый раз.

Несмотря на простую, формулировку testcases пригодятся: язык хоть мне и знакомый, но не родной – редко приходится озвучивать числительные да и ещё такие большие.

Итак, для 1 234 567 нужно выдать "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven". Думаю довольно очевидно, что все уникальные числительные будут константами так или иначе организованными в листинге, а именно это числа 0-19, 20, 30...90, 100, 1000, 1000 000, 1000 000 000. Далее, по большей части я вынужден перефразировать подсказки данные в условии (честно скажу, что я прочёл их уже после успешного submit).

Рассмотрите отдельные тройки разрядов, обратите внимания, что их звучание однотипно – отличие только в том, что одна группа это Million, другая Thousand, ну а последняя (Ones) – суффикса не требует. Так же нам везёт, что все эти Million/Thousand сами не склоняются по числу ( не требует 's'). Внутри же этой тройки разрядов всё достаточно просто: озвучиваем первую значащую цифру, прибавляя Hundred, далее если в оставшихся двух разрядах число старше 19, то озвучиваем сначала десяток, потом вторую цифру, если число не старше 19 – озвучиваем сразу две цифры. И да – нули не озвучиваем.

Как выделяются тройки разрядов и обработку corner-cases – посмотрите в листинге или в подсказках на платформе. Листинг в комментарии к посту.

#leetcode #algo #c_plus_plus #English

Разница в подходах

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

Удивило меня другое: на Leetcode нет нужды писать ввод-вывод, ну и самое главное – если после Submit решение упадёт на каком-либо из testcases – платформа покажет это. Также можно добавлять свой пользовательский вывод и его тоже будет видно. На Я.Ке нужно писать весь ввод и вывод данных самому, не видно содержания testcases, и невозможно ничего распечатать и увидеть это где-либо. То есть, при любой малейшей ошибке нет ни одного шанса обнаружить её с помощью этой платформы – остается только самому придумывать тестовые данные и локально отлаживать.

В двух задачах из трёх я столкнулся с ситуацией, что решение не проходит N-ый testcase: не забить окончательно на такую неразговорчивую платформу и довести до конца, помогла только мысль, что задачи-то простые.

Вывод: для изучения алгоритмов либо поддержания себя в тонусе для собесов, Leetcode гораздо удобнее – подход Я.К требует гораздо большей мотивации (которой нет).

#today #algo #leetcode

Сетки

сделали уже очень много хайпа, неоднократно появляясь в околоайтишных новостях. Было бы странно если бы я, решая все эти задачи на Lettcode, не попробовал бы хоть раз насколько эффективна ChatGPT/DeepSeek в решении подобных проблем. А я и попробовал.

Итак, ни разу мне не удалось получить корректного решения задач уровня Hard (как разобранных на этом канале так и нет) : каждый раз это что-то рядом, чем-то похожее на структуру возможного решения, но не решение. Уточняющие подсказки, как правило, бесполезны. С задачами уровня middle получше, но всё ещё возможны косяки.

Пробовал несколько инстансов ChatGpt/DeepSeek, русский и английский ввод.

Вывод: сетки могут быть полезны, чтоб автоматизировать рутину, набросать скелет какого-то решения, но они не могут заменить программиста (собственно иначе программистов уже бы не осталось).

#today #flood #IT #NN

Массовые увольнения в ру-сегменте IT: что происходит?

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

Кого уволят первым: разрабы, чьи задачи легко автоматизировать, неэффективных менеджеров с высокими ЗП и сотрудников без инициативы и гибкости.

А вы боитесь остаться без работы?
😎 — Нет, уверен в себе
😭 — Да

#новости

Январь, начавшись в брызгах шампанского и бенгальских огнях, набрал разбег, пронесся стремительной, гулкой кавалькадой праздников, разбился о монолит будних дней, закончившись в невиданной оттепели...

...Под его финал, неожиданно для самого себя, я оказался в уютном кресле, читающим две книги одновременно. Читаю по-новому: не гонясь за скоростью, представляю всё, что описывает автор – пейзажи, персонажей, ситуации – выстраиваю в голове экспозицию, прокручиваю сюжет туда-сюда, смотрю на построение предложений.

Одну книгу читаю на английском, в рамках очень занимательного книжного клуба, – Ready Player One, вторую – на русском – её я называть не стану. На английском само-собой выходит небыстро, на русском – одергиваю себя: какой-никакой завалявшийся автор старался, выписывал образы, придумывал мир, делал картину объёмной – зачем же мне нестись напролом, увлекшись сюжетом?

#today #flood #books #English

👍 - Фил увидел свою тень
😡 - дайте нормальную зиму
🤷 - что за тень?

Вечер

...Морозный ветер обжигал лицо, отвыкшее от холодов, норовил залезть под куртку. Воздух был необычайно прозрачен для города: не было ни малейшей дымки или тумана. Уличные фонари подобно гигантским ножницам вырезали ровные освещенные конусы из окружающей темноты, внутри которых мир имел форму и цвет, вне – сжимался до одномерных серых контуров.

...Дальше, дальше, вдоль чуть изогнутого многоблочного дома, через маленькое подобие площади, мимо аккуратного , приятно-вишневого цвета, домика управы...

Неубранные до февраля новогодние елки сюрреалистично возвышались над тротуарами, покрытыми лёгким слоем пыли, – снега не было и в помине.

...По оживленному, суетливому переходу, за линию высоток...

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

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

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

Казалось, они просто ускользают от взгляда: поверни чуть-чуть голову и увидишь царские сани, подъезжающие ко Дворцу, дворян в праздничных платьях, спускающихся по главной лестнице и почтительно вытягивающихся перед важной персоной, окруженной фрейлинами и камергерами; или окунешься в шумный бал-маскарад, многоголосой хмельной толпой растекшийся по Английскому саду. Чуть прикрой глаза и услышишь звон колокола, исправно снаряженного в Церкви, зовущий к вечерни...

#superflood

Российским айтишникам придется подтверждать свою квалификацию. Для этого Минцифры придумали специальное тестирование.

С 31 мая 2025 года каждый желающий может пройти тест и выполнить практическое задание по 21 направлению — Python, Java, Git и другие.

При прохождении испытания выдается сертификат на Госуслугах. Действует он только один год — после навыки придется подтверждать снова.

Эксперимент начнется уже завтра.

Странно было бы ожидать что-то другое...

Давно ничего не писал, но сегодня последний день зимы, которой почти не было, и последний рабочий день на неделе, иначе говоря — пятница.

Есть в разработке такой тренд: переходить на функциональные языки программирования, либо добавлять такие фичи в уже существующие языки. Уже никого давно не удивить лямбдами в C++ (хотя, как обычно, синтаксис их уродлив).

Иногда, в фоне, ковыряю Elixir — функциональный язык, но не настолько теоретический как, скажем, Haskell.

Вот пример взятия корней из полных квадратов, реализованный через бинарный поиск и рекурсию:

defmodule SquareRoot do
  @doc """
  Calculate the integer square root of a positive integer
  """
  @spec calculate(radicand :: pos_integer) :: pos_integer
  def calculate(0), do: 0
  def calculate(1), do: 1
  
  def calculate(radicand) when is_number(radicand) and radicand > 0, do: calculate(radicand, 0, radicand)

  defp calculate(_, left, right) when left >= right, do: nil 

  defp calculate(radicand, left, right) do
    mid = div(left + right, 2)
    sq = mid * mid
    cond do
      sq == radicand -> mid
      sq > radicand -> calculate(radicand, left, mid)
      true -> calculate(radicand, mid, right)
    end
  end
end

#today #friday #elixir