«Коллеги, пришлите сроки!» — сага о том, как я открыла портал в ад на Хабре

Ты осторожнее с вопросами, вдруг нас ждет еще один пост с ответом именно на этот вопрос))

Про решаемость пятнашек

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

Про сложность говорить смысла особо нету, так как размер доски небольшой и оба алгоритма отработают мгновенно.

Про решаемость пятнашек

Что-то я накосячил с оформлением формул в пост скриптуме. Я хотел написать ".. O(mn), а не O(mn log(mn))".

Про решаемость пятнашек

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

Теперь непосредственно про вычисление характеристики.

1. Необходимо обойти головоломку "змейкой", то есть обойти в следующем порядке:

   1  2  3  4
   8  7  6  5
   9 10 11 12
  16 15 14 13

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

2. Выписать встретившиеся значения фишек, то есть выписать только ненулевые значения ячеек. Полученная набор чисел является перестановкой множества чисел от 1 до 15.

Для приведенного автором статьи примера

  12 13 11  2
   4  5  3 14
   1  9 15  6
   8  7  0 10

 числа будут выписаны в следующем порядке: 12, 13, 11, 2, 14, 3, 5, 4, 1, 9, 15, 6, 10, 7, 8.

3. Характеристикой является четность описанной в прошлом пункте перестановки. Как посчитать четность? Отсортировать массив, подсчитав количество swap'ов. Четностью перестановки будет четность количества swap'ов.

Какова сложность данного алгоритма?

По памяти: .

По времени: .

P.S. Может возникнуть вопрос почему сложность по времени , а не . Ошибки здесь нету. Все дело в том, что в данной задаче массив имеет специфичный вид и за счет этого его можно отсортировать за линейное время. Кому интересно предлагаю самостоятельно разобраться почему это так, я же просто оставлю код сортировки массива, являющегося перестановкой множества :

for (int i = 0; i < perm.length; i++) {
    while (perm[i] != i) {
        // swap(a, i, j) меняет местами a[i] и a[j]
        swap(perm, i, perm[i]);
    }
}

Отмечу, что в отсортированном массиве perm[i] == i для всех i от 0 до perm.length и что именно это свойство является ключевым.

Об одной изящной задаче

Можно строки заменить на векторы: x = (1, 0, 0), y = (0, 1, 0), z = (0, 0, 1). Либо самому написать простенький класс, либо, например, воспользоваться numpy.

Как, блуждая по Stack Overflow, можно набрести на Branch predictor

При исполнении байт кода у JVM есть два сценария: 1. интерпретировать байт код; 2. компилировать байт код. В первом случае, как мне кажется, накладные расходы на интерпретацию будут слишком высоки и прироста в скорости работы заметить не получится. Во втором же случае происходит ровно тоже, что и в случае С++, поэтому ускорение должно наблюдаться.

Где-то я читал, что начиная с какой-то версии JVM всегда компилирует байт код. Мог не так понять. В любом случае, желательно код перед бенчмарками "прогреть", то есть выполнить многократный вызов функции с кодом, чтобы вызвать срабатывание механизма компиляции.

Еще, на сколько мне известно, JVM может обнаружить, что один и тот же код выполняется в цикле и оптимзировать это. Поэтому, возможно, придется как-то аккуратно запускать бенчмарк.

Linux на ПК получил 4% рынка десктопов. Это новый рекорд, но чем он объясняется?

На ubuntu, как и на большинство дистрибутивов легко можно накатить другое окружение рабочего стола. Или сразу скачать версию с другим окружением рабочего стола: ubuntu - gnome, xubuntu - xfce, kubuntu - kde, ubuntu mate - mate и т.д. Для fedora есть fedora spins (xfce, kde, mate, etc.).

Автоматическое Обновление Версии Прошивки

В некоторых случаях будет достаточно отслеживать не дату пуша коммита, а дату сборки проекта. Для этих целей есть макросы DATE и TIME:

LOG_INFO(FILE_PC, "Build: %s %s", __DATE__, __TIME__);
// Выведет: "Build: Feb  6 2024 23:53:52"

PAM backdoor by artrone ЧАСТЬ 1/2

Безопасный компьютер -- выключенный компьютер =)

Разворачиваем Telegram бота на Raspberry Pi Zero 2W с автозапуском: шаг за шагом

Хорошей идеей будет отложить запуск бота до появления сети:

[Unit]
Wants=network-online.target
After=network-online.target

Алгоритм для аппроксимации плоскости

Для симметричной матрицы можно найти все собственные значения и собственные векторы без нахождения корней характеристического уравнения

Корни характеристического уравнения и собственные значения это одно и тоже =)

Метод вращений можно реализовать более эффективно. Сперва за одно вращение (!) зануляется элемент a31. Затем с помощью пары итераций значение a32 делается достаточно малым. Можно, кстати, ускорить сходимость используя сдвиги. А затем матрица принимает вид

a11 a12  0
a21 a22  0
 0   0  a33

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

Что нам недодали в C++

Мы вынуждены использовать enum class, так как иначе нельзя будет создать элемент COUNT в более чем одном енуме.

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

enum class MyEnum { A = 10, B, C, COUNT };

то это будет эквивалентно

enum class MyEnum { A = 10, B = 11, C = 12, COUNT = 13 };

Это приводит к тому, что мы не можем использовать COUNT для вычисления размера енума (в результате работы программы будет выведена строка "3 13"):

template<typename EnumT>
constexpr int enum_size() {
  return static_cast<int>(EnumT::COUNT);
}

enum class GoodEnum { A, B, C, COUNT };
enum class BadEnum { A = 10, B, C, COUNT };

int main() {
  printf(
    "%d %d\n",
    enum_size<GoodEnum>(),
    enum_size<BadEnum>()
  );
}

Оптимизируя неоптимизируемое: ускорение компиляции C++

Существуют ли какие-то утилиты, которые можно натравливать на исходники в Pre-Build Event? 

В компиляторе gcc есть атрибут `format`, с помощью которого можно заставить компилятор проверять аргументы функции:

int Printf (const char *format, ...)
__attribute__ ((format (printf, 1, 2)));

См. https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html

Для MSVS есть `_Printf_format_string_`, см. https://stackoverflow.com/a/6849629/12479250

Для clang наверняка тоже можно найти нечто подобное.

Байт-код — это просто! Как сделать DI по-настоящему быстрым

Понял. Спасибо!

Байт-код — это просто! Как сделать DI по-настоящему быстрым

Работает ли scout корректно с generic классами?

Пишем графический ASCII-калькулятор с помощью стандартной библиотеки Си

Аааа. Если предварительно построить эту обратную польскую запись, то да. Просто я подумал, что Вы предлагаете с деревом работать и на этапе вычисления.

Пишем графический ASCII-калькулятор с помощью стандартной библиотеки Си

Дерево, может, и удобнее, но явно проигрывает по скорости. Например, дерево придется обходить рекурсивно. А если пытаться оптимизировать вычисление, то все равно придем либо к ОПЗ, либо к чему-то среднему между AST и ОПЗ.

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

Пишем графический ASCII-калькулятор с помощью стандартной библиотеки Си

Очень важно отметить, что поскольку эта программа написана на Си (или, говоря точнее, на компилируемом языке программирования), то, когда дело доходит до использования чисел с плавающей запятой, возникают присущие таким языкам неточности.

О каких неточностях идет речь? Почему эти неточности присущи только си и компилируемым языкам? В каких языках таких неточностей нету?

Циркуль и линейка. Часть 1

В конструкторе класса выражение

np.linalg.norm(center - left) != np.linalg.norm(center - right)

лучше заменить на

np.allclose(np.linalg.norm(center - left), np.linalg.norm(center - right))

Переаттестация мудрецов

Формулировка задачи оказалась неоднозначной. Я подумал, что таблички даны не для "озвучивания" предположения о цвете своей шляпы, а для коммуникации между мудрецами. И что ответ надо по прежнему выкрикивать. Перечитав несколько раз формулировку и предложенное автором решение я понял, что неверно интерпретировал условие.

Знатно я, однако, опростоволосился =)