Chaos Construction

Закончился в Питере очередной Chaos Construction. Жаль, не удалось побывать самому.

Один из конкурсов, от которого меня реально вставляет – это Realtime Chip Hack.

Вкратце суть: вам дается тестер, пара проводков и светодиодов. С помощью данного нехитрого набора требуется в некоторой реальной работающей схеме определить тип микросхемы, маркировка которой спилена. Еще как вариант – дается устройство-индикатор обратного отсчета (типа бомба). И надо с таким же набором юного сапера ее обезвредить (перерезать дорожку, или наоборот добавить проводок). Но, например, неверное действие может ускорить «бомбу» или просто сразу ее взорвать.

Я однозначно нахожу это крайне близкой темой к reverse-engineer’ингу, где надо просто взять и разобраться, как программа, например, проверяет ключ, и написать ключелку или битхак.

И прелесть тут в том, что все, что отделяет тебя от победы – это не мегабайты кода, а всего 1-2 байтика (или проводочка), которые найти и исправить.

Снова головоломки или сайт hackquest.com

Любое общение с собратьями по разуму традиционно приносит новые и новые интересные штучки.

На этот раз это сайт hackquest.com. Не знаю, сколько он уже существует, но я только сейчас о нем узнал.

Итак, это сборник разнообразных головоломок на около компьютерные тематики: логика, JavaScript, Java, reverse engineering, криптография, интернет, взломы, Flash, программирование и т.д.

Я вчера посидел пару часов и порешал задачки из своей любимой темы reverse engineering'а. Получил удовольствие.

Рекомендую.

Роб Пайк критикует С++ и Java

Из этого небольшого видео, где автор и идеолог языка GO Роб Пайк делится своим недовольством языками С++ и Java, я вынес для себя классную мысль: в С++ и Java очень "важно" знать и использовать паттерны (какой уважающий себя программист на этих языках не знает хотя бы одного паттерна?), но наличие паттернов (а особенно их обилие) - это отрицательное свойство! То есть знание языка как такового - это еще полдела, так как затем надо еще и знать "правильные" паттерны.

Вобщем, я становлюсь фанатом этого дядьки.

Update: А комментарий с семью различными типами умных указателей в Бусте - это вообще шедевр.

Решение кубика Рубика максимум на 20 шагов

Вроде как поставлена новая планка в алгоритме Бога для кубика Рубика. 35 машинолет были потрачены, чтобы доказать, что для решения любой позиции кубика надо не более 20 движений.

http://www.cube20.org/

Update: У нас тут есть свои блумберговские кубики, на грани которых кроме цвета нанесена корпоративная атрибутика. Подобное "улучшение" сильно осложняет сборку, так как необходимо правильно сориентировать остов до начала сборки слоев. Причем данная ориентация может съехать при неосторожной попытке сборки начального слоя.

Странные скобки в С++

Недавно более часа потратил на поиск проблемы в куске кода, упрощенный вариант которого привожу ниже:

#include <iostream>
int x;
struct A {
  A(int a) {
    x = a;
  }
};
struct B {
  B(A a) {
    A local_a = a;
  }
};
int main() {
  x = 0;
  std::cout << "Case #0: " << x << std::endl;
  B b1(A(1));
  std::cout << "Case #1: " << x << std::endl;
  int t;
  t = 2;
  B b2(A(t));
  std::cout << "Case #2: " << x << std::endl;
  t = 3;
  B b3((A(t)));
  std::cout << "Case #3: " << x << std::endl;
  return 0;
}

Как вы думаете, что должна вывести эта программа? Числа 0, 1, 2 и 3 последовательно для каждого случая?

А она печатает:

Case #0: 0
Case #1: 1
Case #2: 1
Case #3: 3

Почему для случая #2 не произошло присваивание? Куда делась двойка?

Ответ на этот вопрос кроется в наличии рудиментов языка С в грамматике С++.

Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.

Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.

Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно "прикладывается" с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.

Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).

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

P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.

volatile - это очень сильный модификатор в С++

Как-то по многим блогам эта тема недавно пробегала, но надо отдать должное, вопрос почему эта программа, будучи откомпилированной в Студии, печатает "1" вместо "0", озадачивает даже опытных программистов на С++ (или по крайней мере они дают неправильное объяснение причины происходящего).

#include <iostream>
volatile const char* p = "0";
int main() {
  std::cout << p << std::endl;
  return 0;
}

Для получение схожего эффекта в GCC надо заменить "0" на "false".