Search
Write a publication
Pull to refresh
-1
0
Send message

Использование монад в С++. Часть 1: монада списка

Reading time10 min
Views34K
Часть 1
Часть 2

Иногда программисты на С++ просят привести пример задачи, которая не может быть решена без использования монад. Начнём с того, что этот вопрос неверен сам по себе — это всё-равно, что спрашивать, существует ли задача, которая не может быть решена без циклов. Очевидно, если в вашем языке есть поддержка оператора goto, вы можете обойтись без использования операторов цикла. Что монады (и циклы) могут сделать для вас, это упростить ваш код и помочь лучше его структурировать. Как использование циклов превращает спагетти-код в нормальный, так и использование монад может превратить ваш код в императивном стиле в декларативный. Эта трансформация может помочь легче писать, понимать, поддерживать и расширять ваш код.

Ну и вот вам задачка, которая может попасться на собеседовании. Она не совсем тривиальна, возможно несколько подходов к решению и лучший из них не сразу очевиден — как-раз то, над чем стоит подумать.
Вам предлагается следующий пазл:

  s e n d
+ m o r e
---------
m o n e y


Каждая буква соответствует цифре от 0 до 9. Нужно написать программу, которая подберёт такие соответствия, чтобы написанная операция сложения была верной. Перед тем, как продолжить чтение статьи — подумайте минутку, как бы вы решили эту задачу?
Читать дальше →

Пишем на JS в функционально-декларативном стиле

Reading time9 min
Views22K


Введение


Я люблю функциональные языки за их простоту, ясность и предсказуемость. Пишу в основном на Elixir / Erlang / OTP, пробовал другие языки, но Erlang с его акторами пока мне гораздо ближе чем например Lisp или Haskell. Как известно Erlang == web, а у чего-либо написанного для веба порой бывает клиентский веб-интерфейс: html, css, js — содержимое. Увы js это стандарт современного веба, для него есть библиотеки почти под любую задачу почти на все случаи жизни, да и это более-менее единственное доступное средство что-то выполнить в браузере на стороне клиента. Поэтому нам всё-таки нужен js. Сперва мне подумалось «Лямбды и функции высшего порядка есть, значит писать на js будет просто. Выучу синтаксис и буду писать так же как пишу в Erlang/Lisp/Haskell». Как же я ошибался.
Читать дальше →

Сборка Кубика Рубика генетическим алгоритмом online без смс

Reading time9 min
Views53K


В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…

Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.

Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.

Что мы знаем о Кубике? Число его состояний описывается как
(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000
.
Читать дальше →

Используем встроенный микроконтроллер в Intel Edison

Reading time7 min
Views21K
Думаю, что многие из вас уже знакомы с Intel Edison по предыдущим заметкам, и у некоторых после прочтения спецификации, вероятно, возникал вопрос — а что это за второй загадочный процессор MCU, работающий на частоте 100 МГц? Зачем он нужен? Как его использовать?
Между тем роль MCU в некоторых случаях исключительно важна. Те, кто пробовал применять Edison для работы с различными сенсорами, возможно, уже заметили — Intel Edison не обеспечивает real-time отклика на их показания при работе из Linux. И тут на помощь приходит MCU. Пришло время немного рассказать про этот встроенный микроконтроллер, его архитектуру, области применения и рассмотреть практический пример.
Читать дальше →

Windows 10 можно активировать бесплатно, если установить Insider Preview

Reading time2 min
Views161K


Для получения активированной легальной копии Windows 10 RTM необязательно иметь лицензионную копию Windows 7 или 8.1.

Microsoft опубликовала сообщение в официальном блоге, где разъяснила момент с обновлением Windows 10 Insider Preview на финальную версию Windows 10 RTM, которая выйдет 29 июля 2015 года.
Читать дальше →

Автоматический поиск и выявление уязвимостей

Reading time3 min
Views7K


Большинство сайтов взламываются «в лоб» — злоумышленники используют популярные сканеры и утилиты, выявляют потенциальные уязвимости и эксплуатируют их.

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

Алгоритм сортировки Radix Compact. Часть 1: реализация на CPU

Reading time6 min
Views22K
В одном из моих проектов, который был связан с компьютерным зрением, возникла задача сортировки большого массива чисел (около 100 млн. элементов). Код сортировки должен был выполняться как можно быстрее, причем с возможностью исполнения на нескольких процессорах, и желательно на GPU. Сортировка реализованная в стандартной библиотеке C++ не подходила: она основана на алгоритме Quick Sort, который на данный момент не поддается массивному распараллеливанию на GPU. Поиск других способов привел к алгоритму Radix Sort, но в найденных источниках описывалась реализация требующая большого расхода памяти, точнее памяти требовалось: (количество элементов массива) * (размер radix массива). Для массива 100 млн. элементов и radix массиве размером 256 элементов памяти потребовалось бы 25.6 Гб, мало реальное требование, на текущий момент развития вычислительной техники. Но для распараллеливания вычислений алгоритм Radix Sort подходит неплохо, собственно поэтому автор попытался доработать этот способ, чтобы уменьшить расход памяти до приемлемых значений.
Читать дальше →

Эльфийский язык программирования

Reading time6 min
Views38K
Как известно, если ты серьёзный программист, синтаксический сахар тебе не нужен, это баловство. Ещё несколько лет назад Python считался детской погремушкой именно из за этого. Чем вам фигурные скобки мешали? Ребячество какое-то придумали: заменить фигурные скобки на отступы табуляции. Сказал солидный дядя. Маличики согласно покивали, виновато глядя в потолок. Через год все работали в коллективах где Питон основной язык.
Читать дальше →

«Во загнули!» или достоинства и недостатки изогнутых телевизоров

Reading time5 min
Views77K
Три года – примерно столько понадобилось маркетинговой инкубации для того, чтобы идея изогнутых телевизоров из новостных лент технических изданий воплотилась в виде автономного сегмента продуктов. За это время заоблачные цены за искривленные панели снизились до разумных (но всё ещё немалых) сумм, а производители стали обещать полное вовлечение, небывалую реалистичность картинки и плоский живот взамен на отказ от плоских телевизоров.



Тенденцию к искривлению экранов можно было бы назвать чистейшей эволюцией, как например параллельное внедрение 4K. Однако если достоинства повышения разрешения предельно понятны без объяснений, то в случае с изогнутыми дисплеями часто приходится руководствоваться только маркетинговыми текстами. В рамках данного поста попробуем проанализировать, насколько производители честны с потребителями, говоря о достоинствах данного сегмента продуктов.
Читать дальше →

Lua, ООП и ничего лишнего

Reading time4 min
Views69K
Однажды судьба свела меня с ней. С первого взгляда я был ослеплен и долгое время не мог отвести от нее взгляд. Шло время, но она не переставала меня удивлять, иногда казалось, что я изучил ее вдоль и поперек, но она снова переворачивала все мои представления. Ее гибкости не было предела, а потом я узнал, что она умеет еще и… ООП!

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

После прочтения множества умных книжек и разбора нескольких ужасных реализаций ООП, я, крупица за крупицей, собирал все самое полезное и простое, пока не выработал свой стиль объектно ориентированного программирования на lua.
Читать дальше →

Прототипное ООП для Lua

Reading time3 min
Views13K
Привет, я придумал свой велосипед для реализации прототипного подхода ООП в Lua.

Основные фишки
  • Single inheritance
  • Traits
  • LuaJIT


Перейдем сразу к примерам.

-- подключаем модуль
local object = require("object")

-- определяем наш класс, который на самом деле объект
local HelloClass = object:extend(function(class)
  -- конструктор (необязательно)
  function class:init(name)
    self.name = name
  end

  -- метод класса
  function class:sayHello()
    print("Hello " .. self.name)
  end
end)

local hello = HelloClass:new("John")
hello:sayHello()

Читать дальше →

История успеха российского гаджета Lightpack, собравшего на Kickstarter $500 тысяч за 36 дней

Reading time1 min
Views6.6K
В мае 2013 года российский hardware-проект Lightpack, производящий фоновую подсветку для мониторов и телевизоров, собрал на Kickstarter 500 тысяч долларов.

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


Читать дальше →

Метапрограммирование: какое оно есть и каким должно быть

Reading time11 min
Views38K

Метапрограммирование — вид программирования, связанный с созданием программ, которые порождают другие программы как результат своей работы (wiki). Это достаточно общий термин, к которому, согласно той же википедии, относится и генерация исходного кода внешними инструментами, и различные препроцессоры, и «плагины к компилятору» — макросы с возможностью модификации синтаксического дерева не посредственно в процессе компиляции, и даже такая экзотическая возможность, как самомодифицирующийся код — модификация программы самой программой непосредственно во время выполнения.

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

Метапрограммирование реализовано в той или иной мере в очень разных языках; если не рассматривать экзотические и близкие к ним языки, то самым известным примером метапрограммирования является С++ с его системой шаблонов. Из «новых» языков можно рассмотреть D и Nim. Одна из самых удачных попыток реализации метапрограммирования — язык Nemerle. Собственно, на примере этой четверки мы и рассмотрим сабж.

Метапрограммирование — интереснейшая тема; в этой статье я попытаюсь разобраться, что же это такое, и каким оно должно быть в идеальном случае.
Читать дальше →

Что такого особенного в Nim?

Reading time7 min
Views82K


Язык программирования Nim (ранее именовался Nimrod) — захватывающий! В то время как официальная документация с примерами плавно знакомит с языком, я хочу быстро показать вам что можно сделать с Nim, что было бы труднее или невозможно сделать на других языках.

Я открыл для себя Nim, когда искал правильный инструмент для написания игры, HoorRace, преемник моей текущей DDNet игры/мода Teeworlds.

(прим. пер. На синтаксис Nim имели влияние Modula 3, Delphi, Ada, C++, Python, Lisp, Oberon.)

Запускаем!


Да, эта часть всё ещё не захватывает, но просто следите за продолжением поста:

for i in 0..10:
  echo "Hello World"[0..i]

Читать дальше →

Мессенджер Bleep от BitTorrent вышел из альфы и доступен для всех основных платформ

Reading time2 min
Views15K
imageКомпания BitTorrent вчера представила новую версию программы для обмена сообщениями Bleep, которая вышла из стадии альфа-тестирования и теперь доступна на всех основных платформах. Кроме этого, в обновлении появилась возможность отправки самоуничтожающихся whisper-сообщений («шёпот»), которые удаляются через 25 секунд после их просмотра.

Bleep — программа, позволяющая обмениваться сообщениями, медиаконтентом и даже звонками без участия серверов, по схеме peer-2-peer. Передача информации происходит между контактами напрямую. Программа умеет досылать сообщения контакту, который в момент отправки находился в офлайне. Вся передающаяся информация шифруется по схеме end-to-end, ключи шифрования хранятся только на самих устройствах.

Защите приватности разработчики уделяют много внимания. Для использования программы вам не понадобится регистрация – достаточно выбрать никнейм. Ни емейл, ни номер телефона использовать не обязательно. Для добавления нового контакта вам нужно получить лишь его ключ, который можно передать любым способом, включая сканирование с экрана при личной встрече. Но если вы захотите, вы можете привязать к никнейму емейл или телефон, и тогда ваши друзья смогут легко найти ваш контакт, когда они установят себе Bleep.
Читать дальше →

Неизвестный Smalltalk

Reading time10 min
Views32K


Уважаемые читатели хабра. Прежде всего я хочу объяснить, что обзор языка Smalltalk делает в корпоративном блоге FLProg. Дело в том, что и сама программа FLProg и сайт программы написаны на этом замечательном языке. Его возможности и огромная скорость разработки на нём позволяют мне одному поддерживать и постоянно увеличивать функциональность как сайта, так и программы. Если интересно, как мне это удается – прошу под кат.
Подробности

Изменения в Visual C++

Reading time12 min
Views36K
Когда вы захотите обновить версию Visual C++ компилятора (например, перейти с Visual Studio с 2013 на 2015), будет не лишним узнать, почему вы можете столкнуться с тем, что код, который прежде успешно компилировался и выполнялся, теперь будет вызывать ошибки компиляции и/или ошибки времени выполнения.
Эти проблемы могут быть вызваны многочисленными изменениями компилятора для соответствия стандарту С++, изменениями в сигнатурах функций или изменениями расположения объектов в памяти.
Узнать подробнее

Правим баг без исходных кодов

Reading time9 min
Views39K
image

В предыдущей статье мы разобрали, как реверс-инжиниринг может помочь в получении каких-либо преимуществ перед остальными пользователями. Сегодня мы поговорим ещё об одном применении обратной разработки — исправлении багов в отсутствии исходных кодов приложения. Причин заниматься подобными вещами может быть целое море — разработка программы давным-давно заброшена, а её сорцы автор так и не предоставил общественности / разработка ведётся совершенно в другом русле, и авторам нет никакого дела до возникшего у вас бага / etc, но их объединяет общая цель — исправить сломанный функционал, который постоянно вам досаждает.

Что ж, ближе к делу. Есть такая широко известная в узких кругах программа под названием «Govorilka». Как объясняет её автор, это ничто иное, как «программа для чтения текстов голосом». По сути, так оно и есть. При помощи неё было озвучено множество популярных и не очень видео, рапространившихся по всей сети. Программа имеет консольную версию под названием «Govorilka_cp», которую удобно вызывать из своих собственных приложений, что, собственно, я и сделал в одном из своих проектов.

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

Учитывая, что говорилка не обновлялась уже несколько лет, а сам автор оставил вот такое «послание» на своём сайте

image

, я понял, что надеяться мне не на кого, и решать проблему придётся самому.

Как протекал процесс, и что из этого вышло, читайте под катом (осторожно, много скриншотов).
Читать дальше →

Как заработать очки, даже не запуская игру

Reading time10 min
Views37K
image

Как-то вечером, сидя за компьютером, я наткнулся на одну инди-игру под названием «Shoot First» (игру можно скачать абсолютно бесплатно с сайта автора, а за донат любого размера вы получите специальную версию с двумя новыми видами оружия и ещё одним видом уровней). Геймплей её довольно незамысловат — игроку необходимо бегать по этажам в поисках прохода на следующий уровень, при необходимости собирая различные предметы (карты, ключи, etc) и попутно убивая встретившихся на его пути врагов. В общем, этакий action roguelike. Несмотря на кажущуюся простоту, игра меня довольно сильно зацепила, и я потратил не один час, пытаясь добраться как можно дальше и заработать как можно больше очков.

Кстати, об очках. После смерти персонажа и ввода имени игра отображает онлайн-таблицу рекордов:

image

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

Как протекал процесс, и что из этого вышло, читайте под катом (осторожно, много скриншотов).
Читать дальше →

Information

Rating
Does not participate
Registered
Activity