Category: it

Category was added automatically. Read all entries about "it".

Строка-ограничитель, ответ

Текст задачи

Если у нас алфавит 0…9 и 125 строк, из принципа Дирихле следуют два факта.

1. Хватит трёх цифр.

2. И не просто трёх цифр, а от 000 до 125.

Алгоритм получается такой. Заводим 126 битов — ну или 128 для круглого счёта. В общем, не меньше, чем n+1. Если первые три символа оказались цифрами от 000 до 127, ставим 1 в соответствующей позиции. После этого остаётся найти в массиве нулевой бит.

Где это используется? Бывает, что в текстовом компьютерном языке (языке программирования вроде Си, языке данных вроде HTML) нужно указать строку. Традиционное решение — строка забирается в кавычки: std::string x = "text";. Или наоборот, управляющие конструкции языка забираются в особые символы: первый<br>второй.

Первый вопрос: как добавлять символы, которые играют роль управляющих? Это делается теми же управляющими конструкциями: "\"quoted\""="quoted" в Си и &lt;tag&gt;=<tag> в HTML. Это называется «экранирование управляющих символов».

Если заэкранированных символов слишком много, ручное редактирование становится мучением. И тут на помощь приходит другой формат записи текстов — со строкой-ограничителем. Например, R"QQ("quoted")QQ"="quoted" в Си++. Тут строка )QQ" является ограничителем. И мы решали именно эту задачу — найти подходящую строку-ограничитель. Также подобные задачи решаются в MIME — формате передачи двоичных данных в почтовых сообщениях.

Язык программирования Си является «переносимым ассемблером» — то есть он пользуется ассемблерными утилитами вроде компоновщика и библиотекаря, а значит, первым после ассемблера появляется на новом процессоре. Но в Си сказано: имена, начинающиеся на два подчерка, а также на подчерк и большую букву, использовать нельзя, они зарезервированы за внутренними нуждами компилятора. Например, __imp_XXX при импорте функций из DLL, или __builtin_XXX для внутренних функций компилятора, когда он создаёт одну-две машинных команды по месту. А какое имя брать, если подобных требований нет? И это тоже наша задача.

Мы привыкли к оптимизации по процессору и памяти, но бывают и другие виды оптимизации. По длине документации, по дисковому месту, по простоте и поддерживаемости кода… Наш алгоритм не самый оптимальный, но даёт неплохой компромисс между оптимальностью и простотой.

Задача для программистов: Строка-ограничитель

Есть словарь (в программистском смысле — конечный набор строк в некоем алфавите). Придумать алгоритм, который находит строку из этого алфавита, которая отвечает двум требованиям.

1. Достаточно короткая. Не обязательно самая короткая, но разумной длины ℓ=O(log n).

2. Не является префиксом (началом) ни одной из строк словаря.

То есть QQQQ…QQQ не годится, потому что в худшем случае сравнима по длине со строками из словаря.

Попытайтесь оптимизировать этот алгоритм как по памяти, так и по простоте программирования — не выходя за O(nℓ), разумеется.

Ответ

Идеальная ручная мини-клавиатура

Rii i8 — хорошая штука, но я предлагаю свой вариант для управления компьютером с дивана.

Большой тачпад. Rii i8 и её потомки обладают маленьким тачпадом, и это нехорошо.

Кнопки-стрелки под левым большим пальцем. Их функциональность напоминает игровой пульт, это позволяет даже играть в игры (может, не слишком комфортно).

Кнопки мыши под указательными пальцами, колесо мыши. Это позволяет комфортно сидеть в браузере, перетягивать что-то. Fn+колесо — громкость.

Множество программируемых кнопок. У разных пользователей разные цели, и кому-то нужно управление браузером, кому-то плеером, кому-то кнопки Android…

Множество функциональности через Fn. Вторым слоем должны быть все возможные мультимедийные кнопки и кнопки полной клавиатуры (кроме цифровых).

Caps Lock через Fn. Признаемся: обратного радиоканала не будет. Тогда случайное нажатие Caps Lock будет сильно мешать, потому отнесём его подальше. Возможно, включается утилитой программирования, специально для маководов.

Полный набор клавиш управления курсором: Ins, Del, Home, End, PgUp, PgDn. При этом Del, PgUp и PgDn — напрямую без Fn.

Режим западания клавиш. Точнее, два разных режима. Первый — при нажатии Fn+Shift (AltGr, Ctrl…) загорается индикация западания, и клавиша Shift становится «зажатой». Второй — включается в настройках; короткое холостое нажатие, например, Shift, включает западание. При отпускании любой клавиши, которая не модификатор, запавшие клавиши отпускаются примерно через 200 мс, при нажатии второй — отпускаются принудительно, а сама эта клавиша становится нажатой с запозданием в такт. Связано это с тем, что много софта обрабатывает модификаторы мгновенно, а остальные клавиши — с запозданием.

Подсветка. Белая, двухуровневая, на традиционных белых диодах с люминофором (не RGB-). Покрытие кнопок такое, что при нормальном свете видны без подсветки.

Кнопки. Резиновые, металлокупольные — но такие они обычно и есть в мини-клавах. Обязательно убедиться: если рука ослабевает и приотпускает кнопку, но та не щёлкает — кнопка остаётся нажатой.

Энергосбережение. Примерно через 20 секунд отключается подсветка и западание. Через минуту-две гаснет индикация, отключается тачпад. При выходе из такого энергосбережения все кнопки РАБОТАЮТ, и проще всего выйти, чтобы не было нажатий, Fn или колесом.

Индикация. Очень неяркая. Зелёный цвет — работа тачпада. Остальные цвета могут быть какие угодно, но лучше не синий.

ППЗУ. Все настройки — программируемые клавиши, западание, подсветка — сохраняются даже при отключении.

Аккумулятор. Обычный, от телефона, ≈1000 мА·ч.

Разъём зарядки. USB-C (хотя можно и Micro-B, но не Mini-B). Ничего, кроме линий зарядки (и, возможно, программирования через USB2), в нём не разведено.

Как получить график в SVG

Вы хотите отправить в Википедию какой-нибудь график. Например, такой. Как его получить в SVG?

1. Заходим на сайт yotx.ru. Готовим график.

2. Правой кнопкой на графике, Inspect element.

1.png

3. В отладчике находим тэг <svg>, правая кнопка, Copy outer HTML.

4. Вставляем то, что получилось, в текстовый редактор. Удаляем маленький пустой контейнер SVG.

5. Заменим пустотой такие директивы: « shape-rendering="crispEdges"» (лучше, но не обязательно, с пробелом в начале) и « text-rendering="optimizeSpeed"» (тоже с пробелом в начале). Рендерер Википедии их понимает и даёт не очень хорошее качество.

6. Сохраняем получившееся с расширением .svg.

7. Уже можно выкладывать на Википедию, но лучше упростить кривые. Открываем в Inkscape, щёлкаем на каждой кривой, Path → Simplify. Если какая-то из кривых — на поверку прямая, можно её превратить в настоящую прямую (инструмент «редактирование по точкам», команда «в прямую»). Сохраняем.

Восемь ошибок самодеятельного разработчика игр

1. Не проверять свои идеи на других. Разработчик обязательно будет предвзят к своему творению.

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

3. Не иметь управления исходниками. Я давно уже «промышленный» программист — в смысле, производящий продукт — и буквально вчера пинал стажёра за замыкание структур данных на сервер (в идеале сервер должен зависеть от структур, но не наоборот). А ведь у самодеятельных может даже не быть архивации и управления версиями!

4. Некачественный код. Доработка, особенно с привлечением сил со стороны, может выйти боком.

5. Собственный движок. Это дополнительно усложняет жизнь.

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

7. Нет плана тестирования. Проверять надо и основные части игры, и граничные случаи, вроде ввода пустой строки.

8. Не закончить. Начать игру просто, закончить — трудно. Это грустная реальность геймдева: очень немногие игры доходят до конца.

Прогерское: Немного об std::forward

Непрограммисты, спокойно пропускайте.

Смысл шаблона std::forward не очень понятен начинающим программистам. Для начала скажу две вещи: 1) он требует явного указания типа (две перегрузки, которые без пива не различишь); 2) употребляется только в шаблонах.

В Си++11 появились так называемые rvalue references, я их люблю называть «врéменные ссылки». Посмотрим на конструктор.

class Thing
{
public:
   std::string name;

   // В теле конструктора aName — ПРОСТАЯ ссылка, string&, потому нужно std::move
   Thing(std::string&& aName) : name(std::move(aName)) {}
}

int main()
{
  std::string s = "Test";
  // Конструктор принимает только временную ссылку, потому std::move.
  Thing th(std::move(s));

  return 0;
}

Конструктор снаружи требует временную ссылку, потому нужен std::move, объявляющий именованный объект временным. Но внутри конструктора этот параметр — обычный именованный объект, то есть простая ссылка, потому снова без move никуда.

Если у нас два конструктора, по простой ссылке и по временной, можно написать вот так.

Thing(const std::string& aName) : name(aName) {}
Thing(std::string&& aName) : name(std::move(aName)) {}

Для шаблонов в Си++ есть хитрая запись, принимающая и простую ссылку, и временную.

template <class T>
Thing(T&& aName) : name(aName) {}

Как она работает? Ссылки в Си++ «спрессовываются»: ссылка на ссылку — ссылка. И временная ссылка на ссылку — тоже ссылка. Вот и всё. Примет хоть string, хоть string& — никаких проблем. Расшаблонится соответственно в Thing(string&&) и Thing(string&).

Возникает такая задача. Если конструктор расшаблонивается в Thing(string& aName), нужно копирование, если в Thing(string&& aName) — то перемещение. Выведение типов тут не поможет: в обоих случаях aName — это string&.

Вот для этого и служит std::forward.

template <class T>
Thing(T&& aName) : name(std::forward<T>(aName)) {}

Версия std::forward для T делает std::move, для T& — ничего не делает, провоцируя простое копирование.

Странная ошибка

Не так давно на работе случилась странная ошибка. При переходе на x64 самодельная библиотека XLSX отказала при попытке импорта. Забавная, но на задачу не тянет. Проблема была вот в чём.

В компьютерах есть две стратегии работы с многобайтовыми числами. Число 90AB16 может записать в два байта как 90 AB (порядок Motorola, или big-endian), или AB 90 (порядок Intel, или little-endian). x86 и x64 относятся ко вторым, раз уж они Intel.

А ещё некоторые машины для упрощения схемы не могут обращаться к 4-байтовым числам, чей адрес не кратен четырём. То есть по адресам 0 и 4 могут, а по адресам 1, 2, 3 — уже нет. Машины x86 и x64 свободны от такого ограничения (правда, по некратным адресам обращение несколько медленнее), а вот у несовместимого с ними Itanium это ограничение есть.

Задача: сравнить пять байтов с «xmlns». Неоптимальный способ: сравнивать по байту или вызвать стандартную функцию сравнения. Оптимальный: сравнить четыре байта с «xmln» и пятый с «s». Но для этого нужно, чтобы эти четыре байта схватило одним махом (нет ограничения на адреса). И, разумеется, константа «xmln» по-разному переводится в число в зависимости от того, Intel машина или Motorola. На Intel старший байт «n», на Motorola — «x».

Код такой (простите, не хочу проверять, как в ЖЖ работают хэштэги — потому пускай будет «собака»).

@ifdef _M_IX86
  @define LITTLE_ENDIAN
  @define UNALIGNED
@endif
// аналогично для x64, проверяется макрос _M_IX64

@ifdef UNALIGNED
  @ifdef LITTLE_ENDIAN
    // Константа для порядка байтов Intel
  @else
    // Константа для порядка байтов Motorola
  @endif
  // Оптимальный вариант
@else
  // Неоптимальный вариант
@endif

Ошибка случилась двойная. Макрос проверки на машину x64, _M_IX64, оказался неверным (вроде правильно _M_AMD64), но где-то глубоко в хедерах MinGW определён макрос UNALIGNED. А теперь посмотрите на вторую часть кода. Макрос UNALIGNED есть — включается оптимизация. Макроса LITTLE_ENDIAN нет — оптимизация под порядок байтов Motorola. Вот и говорит, что в XML нет пространств имён: вместо префикса «xmlns» искало «nlmxs».

Как исправить? Уже замена UNALIGNED → MACHINE_UNALIGNED (и аналогично для LITTLE_ENDIAN) всё решает методом выключения оптимизации. Ну и _M_IX64 → _M_AMD64, чтобы оптимизация-то включилась.

Выводы. 1) Макросы — зло, но замены этому злу пока не придумали. 2) По-хорошему, все системные макросы должны иметь такие префиксы, чтобы с ними было сложно пересечься. 3) Хотелось бы иметь в языке возможность преобразовать несколько символов в число на уровне компилятора, с учётом порядка байтов. В Турбо-Паскале было, но в плохом виде было: машина x86 всё-таки Intel, и чтобы одним махом сравнить два байта, надо было писать 'mx', а не 'xm'. 4) Если ты придумал ветку под какую-то машину, но не можешь её проверить, поскольку этой машины нет — ставь аварийный останов с сообщением: «Ветка не проверена, испытывайте на свой риск».

Ребус Генри Форда, ответ

Текст задачи, ответ без D=5

Вот что поначалу известно про наш пример DONALD+GERALD=ROBERT (скажу честно: добавил его для SEO, ведь всё решение в картинках).

UPD. Исправляю свою ошибку. Вторая цифра говорит, что O+E=O. Ноль занят, так что E=9, был перенос в 1-ю цифру, и был перенос из 3-й.

1-я цифра говорит, что R>5. Пятая — что он нечётный. Значит, 7. Угадываются G и A.

Раскидываем оставшиеся три цифры — и тадам!

Как я уже сказал, задача имеет единственное решение даже без указания, что D=5. Вот попытка получить хоть одно решение.

Я быстренько наваял программу на «си с крестами», и она говорит: одно решение.

Занимательная задача: Версия компилятора

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

Компилятор 1-й версии определяет символ VER01.

Компилятор 2-й версии определяет символ VER02. VER01 не определяет.

Компилятор 3-й версии определяет символ VER03. Предыдущих двух не определяет.

И так далее. Версий компилятора штук 20 и постоянно появляются новые.

Предположим, с двенадцатой версии компилятора появилась некоторая важная функция.

Мы можем лишь проверить, есть символ, например, VER12 или нет. Как определить, есть наша классная функция или нет?

P.S. Как картинка связана с задачей — объясню в ответе.

Ответ

Кодоскептицизм: хаос в буквах

По интернету ходит вот такая вирусная фраза:

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

Не щёлкает вам, скептики? «Анонимный авторитет» — это даже не лампочка, а мигалка с сиреной! А ещё заметно, что ни одна буква далеко не ушла: считаные единицы сместились на три позиции, большинство букв — на позицию-две.

Написал программку на Java, которая переставляет буквы действительно хаотично, и получилось вот что:

По рульзеататм ианедивсслой онодго асйоилнгкго утритеиевнса, не иеемт зиченаня, в ккоам пкдоряе

Задрали с фейками и ложью!