#IT #c_plus_plus #leetcode #today #ToBeContinued

Не надо плавать

В прошлых постах я довольно подробно расписал подводные камни работы с числами с плавающей точкой, которые моделируют дробные(рациональные) числа. И тут есть интересный момент: это не единственный вариант работы с такими числами (Википедия не даст соврать), я и сам уже упоминал это, но… в C++ их нет ни как базового типа, ни как класса в стандартной библиотеке. Зато, в C++ есть вызывающая много споров возможность перегружать операторы, что подталкивает нас попробовать создать так называемые числа с фиксированной точке “на коленке”, сделав свой класс и перегрузив (хотя бы часть) арифметических операторов.

Тут прежде, чем изливать тонны кода, давайте остановимся на основах: почему это возможно и как это сделать. Итак, язык нам предоставляет базовые integral types, обычно 1,2,4, 8 байтовые со знаком или без (ну уж точно на x86-64 платформе это так) и предоставляет нам арифметические операторы для этих типов. Рассмотрим базовые моменты работы арифметических операторов на примере типов uint8_t, int8_t:
• Сложение для uint8_t происходит по модулю 256 т.е. 1+2 = 3, но 1+255=0
• Сложение знаковых чисел происходит той же самой инструкций ассемблера, т.е. для CPU нет никаких отрицательных чисел, границы этого типа -128…+127
• Перемножение двух int8_t дает результат типа int16_t
• Частное от деления int16_t \ int8_t дает результат типа int8_t, остаток отбрасывается

А теперь основная идея (или трюк, если хотите), я могу взять переменную типа int8_t и мысленно сказать, что она хранит не целое число…а например, число четвертей, то есть мысленно поставить точку после двух левых разрядов. Давайте на примере десятичной системы: я возьму какие-то числа, например 3.14 и 2.71 и скажу – “у меня есть 314 сотых, а также 271 сотая”. Если меня попросят их сложить или вычесть это можно сделать, не выходя за нотацию сотых прямо сразу: 314 + 271 = 585, 314 – 271 = 43. Давайте попробуем умножить, 314*271 = 85094 эм...это точно в сотых? Нет, это точно не в них – правильно будет вот так 851 т.е. сдвинуть на 2 разряда вправо. А причём тут сотые, и какие-то четверти, которые я упоминал ранее? Четверти – это одни четвертые (богатый русский язык), для двоичной системы, это тоже самое, что сотые для десятичной.

В следующий раз понемногу начну показывать код.

#IT #job #c_plus_plus #math #weird #ToBeContinued

Не надо плавать

Часть 2

Поскольку код вышел на Хабре, и более-того, комментаторы и я сам нашли довольно большое количество ошибок и переусложненных моментов, хотелось бы тут остановиться ещё раз на идее.
В языке C++ есть типы double и float, реализованные в соответствии со стандартом IEEE-754.

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

Смысл статьи на Хабре и потуг предыдущего поста состоит в том, что можно взять целое число произвольного размера (но из тех, что нативно поддерживается компилятором) и сказать, что теперь я трактую n правых разрядов как значение идущее после точки – дробную часть числа, а остальные разряды как левую часть числа, вот пример для 8 битного числа где 2 младших разряда я отдаю под дробную часть 0000 1101, это тоже самое что 11.01 (2) = 3.25 (10) .

Соответственно, написанный код – всего лишь является отражением этой идеи.

#today #IT #c_plus_plus #math #habr #ToBeContinued

Книги

Были времена и получше, когда я был готов читать, что угодно в рамках жанров НФ и фэнтези. Были времена, когда я читал книги по условной 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

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

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

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

#today #c_plus_plus #leetcode #algo #ToBeContinued

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

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

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

#today #c_plus_plus #leetcode #algo #ToBeContinued

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

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

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

#leetcode #algo #ToBeContinued #English

Будет длинно и путано — не читайте.

Собираясь в отпуск, выбирал книгу для чтения в дороге — из того, что есть на полке в мягкой обложке. В итоге положил в сумку "На западном фронте без перемен" Ремарка. В дороге сил читать не было — читал в отпуске.

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

Лучшее ли это чтение в отпуске? — наверное, нет. Наверное, стоило взять книгу похожую на "Имя Розы". Книгу безусловно трагическую, но горести и несуразности которой столь оторваны от дня сегодняшнего, что для человека далёкого от знания истории, сравнимы с палеозойской эрой. Первая Мировая война же — наш позавчерашний день, в котором герцоги и кайзеры причудливо сочетаются с почти современным оружием, с реалиями недалеко отстоящими от наших .

Первая Мировая война — для нас затенена Революцией, войной гражданской и Второй Мировой. Для Европы — наверное, нет.

#flood #books #tobecontinued

Из дела № 7514 о незаконных доходах жителей N-ска: “Согласно отчётам следственных органов, зафиксированное за последние годы увеличение нелегальных доходов жителей N-ска (см. прил. 1 и прил. 2. Бюро Экономических Исследований с приведенными данными о покупках квартир и машин) не может быть объяснено традиционными незаконными или теневыми доходами (см. Рапорты в прил. 3). Таким образом следственные действия должны быть продолжены...”

К. ф. м. Пугалина О.А., Обсерватория небесных явлений: “…Инструментальное исследование неба над N-ском и N-ской областью не нашло никаких следов атмосферных явлений, широко описываемых его жителями. Довожу до сведения руководства обсерватории, что дальнейшее исследование выглядит бесперспективно: явление лежит в плоскости массовой истерии, и заниматься им должны люди компетентные в вопросах…”

Фрагмент христианской радиопередачи: “Помните, Сатана – Князь мира сего. Не только тварная плоть – царство его, но и всё, созданное руками человека. Только церковь…”

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

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

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

“Тупая шутка”, – с сомнением подумал он, вспомнив странные слухи, расползающиеся по Городу в последнее время. В курилках на кухнях повторяли: “Иванычу такое пришло на той недели – и они на отдых улетели”, “Лёха вчера согласился. Видел, на какой машине он теперь разъезжает?” Каждый раз они обрастали новыми деталями и могли бы быть приняты за обычные сплетни, если б Иваныч и Леха не были его знакомыми, которые вдруг и вправду стали богаче. Он звонил им обоим: разговор шёл в обычной манере, только все вопросы об этом – обтекаемо скатывались к обсуждению общих коллег и знакомых – стена казалась непробиваемой.

Карман пальто казался непривычно тяжелым – под твидовой тканью угадывались очертания смартфона. Он уже знал, что, если достать телефон и включить это – он опять не сможет ни удалить, ни заблокировать тот чат: всякий раз кровь начинала стучать в висках, в глазах мутнело, и на лбу выступала испарина, когда же он приходил в себя – экран телефона был темным – неведомые отправители хорошо позаботились о том, чтобы придать вес своему сообщению. Длинное, ветвисто написанное, предложение пестрило непривычными терминами: единица индивидуального восприятия реальности, конгломерат равнодействующих мыслительных процессов…однако, неизбежно сулило весомые жизненные блага любому вступившему в Общество – неожиданно выплаченный кредит Иваныча, как и Лехина новая машина служили яркими иллюстрациями этих финальных, самых понятных ему строк.

(Продолжение)

#city_life #ToBeContinued