Книги

Были времена и получше, когда я был готов читать, что угодно в рамках жанров НФ и фэнтези. Были времена, когда я читал книги по условной Computer Science – и тогда "серьёзная" книга была на неделю, а художественная – на вечер.

Но, уже несколько лет как, настали времена, когда мне нужна особая причина, что б начать, а главное – закончить книгу. Действительно: читать книги по программированию? – Полноте, зачем? – Собес в Яндекс я прошёл уж 4 года как, полный список языков и технологий, который я там-сям применял утомит своей длиной любого HR...

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

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

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

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

#today #flood #superflood #books #opinion #ToBeContinued

Дикость

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

Не имея под рукой интересных проблем, что б их описать, решил прибегнуть к помощи небезызвестного (и уже упоминавшегося в канале) сервиса Leetcode. Выбрал задачу Wildcard Matching, уровня hard, их тех, что раньше пробовал решить, но не сумел.

Итак, вот оригинальная формулировка:

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Ограничения:

0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.

Сразу заметим пару моментов: во-первых, строка и образец могут быть достаточно длинны, что б сделать совсем наивные решения неэффективными, во-вторых, строка не может содержать '?' или '*', а в образце – не бывает экранирования, в-третьих, строка должна полностью соответствовать образцу.

Первая приходящая в голову мысль: давайте будем итерироваться по строке и образцу "одновременно", ведь пока мы не встретили "звездочку" – всё абсолютно очевидно. Действительно, представим себе ту же задачу, но символов '*' – нет. Получим следующий набросок решения:

 bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        auto sLen = s.length();
        auto pLen = p.length();
        int starIndex = -1;
        int matchedIndex = 0;

        while (sIndex < sLen)
        {
            // simply match then we increment the both indexes
            if (pIndex < pLen && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
            {          
                pIndex++;
                sIndex++;
                continue;
            }

            return false;
        }

        //still possible to have an unfinished pattern here
        //it matches if and only if the pattern is over 
        return pIndex == pLen;
    }

Продолжение следует.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Дикость продолжается

Кратко объясню идеи сниппета из прошлого поста:
Идём по строке и образцу, если оба символа совпадает, просто наращиваем оба индекса, если в образце стоит знак вопроса - делаем тоже самое, т.к. он совпадает с любым другим символом, при первом же не совпадении – рапортуем о неудаче. Всё предельно просто.

Ну теперь попробуем вернуть "звёздочки": по определению '*' соответствует нулю либо любому иному количеству символов...то есть – она не соответствует ничему – весь вопрос в том, чему соответствует символы за ней...Что если мы попробуем матчить остаток строки остатку шаблона, а если не сможем – просто нарастим индекс в строке? Вот примерно такой набросочек:

class Solution {
public:
    bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        if (p.empty())
        {
            return s.empty();
        }

        return isMatchImpl(s, p, sIndex, pIndex);
    }

    bool isMatchImpl(const string& s, string& p, int sIndex, int pIndex)
    {
        while (sIndex < s.size() && pIndex < p.size())
        {
            if (p[pIndex] == '?')
            {
                ++sIndex, ++pIndex;
                continue;
            }

            if (p[pIndex] == '*')
            {
                while (pIndex < p.size() - 1 && p[pIndex + 1] == '*')
                {
                    ++pIndex;
                }

                return matchStar(s, p, sIndex, ++pIndex);
            }

            if (p[pIndex] == s[sIndex])
            {
                ++sIndex, ++pIndex;
                continue;
            }

            return false;
        }

        if (sIndex < s.size() && (pIndex = p.size()))
        {
            return false;
        }

        if (sIndex == s.size())
        {
            while(pIndex < p.size())
            {
                if (p[pIndex] != '*')
                {
                    return false;
                }

                ++pIndex;
            }

            return true;
        }

        return true;
    }

    bool matchStar(const string& s, string& p, int sIndex, int pIndexAtStop)
    {
        // there is nothing after the star
        if (pIndexAtStop >= p.size())
        {
            return true;
        }

        auto stopCh = p[pIndexAtStop];

        cout << "stopchar = " << stopCh << endl;

        while (sIndex < s.size())
        {
            if (s[sIndex] == stopCh || stopCh == '?')
            {
                auto matched = isMatchImpl(s, p, sIndex + 1, pIndexAtStop + 1);

                if (matched)
                {
                    return true;
                }
            }

            ++sIndex;
        }

        return false;

    }
}

Это почти работает, в следующий раз – объясню в чём загвоздка и завершу этот маленький цикл.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Закончим эту дикость

Не секрет, что для алгоритмов есть понятие корректности и сложности выполнения. С корректностью – всё нормально, с пространственной сложностью – всё сносно, она линейна от длины образца (тратим стек на каждую звездочку), со временной сложностью – плоховато...Позвольте мне не заниматься тут этими вычислениями – достаточно заметить, что платформа выдает Time Limit Exceeded на паттернах типа этого: "b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a".

Что же делать? На самом деле у нас очень много лишних действий...Предположим у нас есть часть выражение p1 даже с несколькими '*' и мы нашли, что оно матчит часть строки s1 (т.е. по сути части между звездочками в паттерне матчатся), и пусть в остатке шаблона p2 тоже есть "звездочки", тут важно понять, что вне зависимости от дальнейших сравнений – нет смысла заново сравнивать уже совпавшую часть шаблона p1. Действительно, при новом сравнении мы получили бы s1', уходящую правее, чем s1 – но в этом нет никакого смысла, т.к. звездочки в p2 итак могут "съесть" эти символы.

А вот и код:

class Solution {
public:
    bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        auto sLen = s.length();
        auto pLen = p.length();
        int starIndex = -1;
        int matchedIndex = 0;

        while (sIndex < sLen)
        {
            // simply match then we increment the both indexes
            if (pIndex < pLen && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
            {          
                pIndex++;
                sIndex++;
            }
            // if it's a star then memorize its position, memorize the string position and go further to the next pattern index
            // note that here we can "consume" several stars going in the row
            else if (pIndex < pLen && p[pIndex] == '*') 
            {
                starIndex = pIndex;
                matchedIndex = sIndex;
                pIndex++;
            }
            // it's a mismatch but there is a star somewhere before it
            // then let's get back to the next index after the star in the pattern
            // and the star has eaten another symbol in the string
            else if (starIndex != -1)
             {
                pIndex = starIndex + 1;
                matchedIndex++;
                sIndex = matchedIndex;
            }
            //either mismatch or the pattern is over when the string is not
            else
            {
                return false;
            }
        }

        //still possible to have an unfinished pattern here
        // advance it while it's a star
        while (pIndex < pLen && p[pIndex] == '*') {
            pIndex++;
        }

        //it matches if and only if the pattern is over 
        return pIndex == pLen;
    }

};

#today #c_plus_plus #leetcode #algo

Результаты решения

#today #c_plus_plus #leetcode #algo #picture

Попроще

Честно признаюсь: предыдущая задача – сложная. Решить её без практики строковых/backtrace алгоритмов, и, тем паче, в рамках собеседования, – маловероятно. Рассмотрим задачу попроще, которая пару дней назад была daily challenge. Продублирую условие:

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.
Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

И ограничения:

1 <= num1, num2 <= 10^9

Догадываюсь, что с первого взгляда кажется, что написана какая-то ерунда. Действительно: в этой задаче главное – понять условие правильно. По сути нам нужно "создать" новое число и в него поставить столько единичек, сколько их в num2. Это можно сделать многими способами, но у нас есть дополнительное условие: XOR-сумма с num1 должна быть минимальна. Как известно 1 XOR 1 = 0, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, т.е. имеет смысл идти по битам числа num2 слева направо копируя их в результат (не забывая, что вообще говоря num2 может содержать больше битов, чем нам нужно). А если вдруг мы скопировали весь num2, но битов не хватает – не теряемся, просто заполняем пустые разряды res уже теперь справа налево.

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

class Solution {
public:
    constexpr static const int bin_size = 30;
    using bits = bitset<bin_size>;

    int minimizeXor(int num1, int num2) {
        bits b1 = num1;
        bits b2 = num2;
        bits res = 0;

        int count = b2.count();
        auto index = bin_size - 1;

        while (count && index >= 0)
        {
            if (b1[index])
            {
                res.set(index);
                count--;
            }

            index--;
        }

        index = 0;

        while (count)
        {
            if (!res[index])
            {
                res.set(index);
                count--;
            }
            
            index++;
        }

        return res.to_ulong();
    }
};

#today #c_plus_plus #leetcode #algo

Результаты решения

#today #c_plus_plus #leetcode #algo

Daily question

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

Если вкратце: дано два, возможно довольно длинных, целочисленных массива, нужно найти XOR всех возможных пар. Т.е. если в первом массиве 10 элементов, во втором 11, то нужно найти XOR 110 пар – что было бы квадратичным (неэффективным) алгоритмом. Советую решить самим прежде чем читать спойлер и код.

Нам понадобится два свойства операции XOR: её коммутативность, и факт, что XOR-сумма любого числа с самим с собой равна нулю при чётном числе элементов и равна самому элементу при нечётном числе элементов. В гигантском XOR всех-всех пар друг с другом каждый элемент первого массива встретится столько раз, сколько элементов во втором массиве, и аналогично для второго массива. Иначе говоря, всё зависит только от чётности длин массива, и в худшем случае мы получим алгоритм линейный от совокупных длин массива, а в лучшем случае и вовсе – O(1).

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2)
    {
        int res = 0;

        if (nums2.size() % 2 == 1)
        {
            for (const auto& x: nums1)
            {
                res ^= x;
            }
        }

        if (nums1.size() % 2 == 1)
        {
            for (const auto& x: nums2)
            {
                res ^= x;
            }
        }

        return res;
    }
};

#today #c_plus_plus #leetcode #algo

Результаты решения

#today #c_plus_plus #leetcode #algo

Daily question, again

На Leetcode похоже ежемесячник смешных задач на XOR. Всё остальное сразу убираю под спойлер.

Итак, сразу понятно, что о каком-либо переборе всех возможных массивов original с пересчётом их deriverd речь идти не может – это было бы экспоненциальное время работы. Вместо этого внимательно посмотрите на Example 1: в расписанных формулах для элементов derived каждое значение original фигурирует ровно дважды – это значит, что XOR-сумма элементов валидного derived, полученного из произвольного original обязана быть равна нулю.

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int res = 0;

        for (const auto& x: derived)
        {
            res ^= x;
        }

        return res == 0;
    }
};

#today #c_plus_plus #leetcode #algo

Хорош ли номер

Эта серия с Leetcode подзатянулась, но это не значит, что я её не продолжу:) Сегодня предлагаю просто почитать задачу уровня Hard, с удивительно низким для меня уровнем Acceptance порядка 20 процентов – решение я опубликую потом.

Сразу скажу: решение довольно простое, укладывающееся в сотню строк; причём достаточно использовать только сравнение символов, итерирование по строке и прочие низкоуровневые штуки, использовать тут regexp – неспортивно.

#today #c_plus_plus #leetcode #algo #ToBeContinued

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

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

Твин Пикс – шедевр, где эти две составляющие взаимообогащают друг друга, формируя целостное, многослойное кинополотно, поглощающее зрителя с первого эпизода. Путь Агента Купера до Чёрного вигвама – не банальное путешествие из точки А в точку Б, да и проходит он вовсе не в физическом мире...

#sorrow #books #movies

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

Вернёмся к задаче из поста: решение я всё ещё придержу. Кстати, в данном случае использование конечных автоматов, предложенных тут в комментариях, в принципе оправдано, хотя – в своём решении я не использую их. Если кто-то из подписчиков реши(л|т), используя этот формализм, – предлагаю привести решение в комментариях.

Я же тут, пока что написал регулярное выражение подходящее под условие (\-\+)?((\d)+)|((\d*\.\d+)|(\d+\.\d*))((e|E)\d+)? – считайте это подсказкой.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Кстати, всё, что я писал раньше о программировании – это всего лишь забавные игрушки. А вот он – каждодневный труд https://www.reddit.com/r/programminghorror/comments/16lttzw/callback_hell_from_ages_ago_when_coding_my_first/

#today #flood #superflood #humor

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

Однако, хоть это и смутный и неверный, но шанс на улучшение ситуации. Не зря же давеча приснился мне сон, что я – там, на инаугурации Трампа; и все вокруг удивляются, что кругом снег, хотя откуда он, если его нет и в Москве? :)

В любом случае: дата 20.01.2025 историческая. Let's make something great again.

#today #news #history #USA #Trump

Хорош ли номер ч. 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