Обновляем мерч: шо, опять?

А англоязычные вернулись? 🤔

От Гарфилда до Кота Саймона: как кошки становятся прототипами героев фильмов, мультиков и игр

Целый мемориал котикам в Talos Principle 2

Литкод изи — это просто

Совершенно верно! Оптимизация перебора -- мастхэв для ускорения решения с ростом размерности задачи. Это не меняет худший случай, зато сильно улучшает средний случай.

Но реализация интеллектуального перебора требует значитнельно больше времени, чем экономится. Сейчас типичное поле решается на 0.05-0.1 сек, практически равно дисперсии времени наведения на кнопку и нажатия на неё. Как быстро окупится 30 минут дополнительного кодинга и усложнение когда при сокращении этого времени даже в 10 раз?

В случае же, если этот код болтается в продакшене, при загрузке проца в полку -- уже интереснее расклад. До тех пор -- только как развлечение.

Литкод изи — это просто

Потому, что если не разминать мозги, они застывают.

Литкод изи — это просто

Там откусывается не сверху, а снизу от факториала несколько строк. С практической точки зрения -- это всё мелкая константа, которой можно пренебречь и считать что оно факториальное.

Total count of solutions: 2 checked: 100

При такой задаче, для поиска всех надо перебрать 100 вариантов. От полного факториала (5!=120) недалеко ушли :)

Первое решение найдено на 56м варианте, второе -- на 81м.

Литкод изи — это просто

У каждой клетки есть цвет, и число цветов равно числу столбцов и рядов. Цвета еще и связные области, но для имеющегося решения это не важно.

Void me

Такую фундаментальную вещь, как уникальность адреса для объектов любых типов, трогать нельзя.

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

Литкод изи — это просто

Не понимаю примера. Можно в цифрах?...

[0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4]

вот это -- каждая строка свой цвет. Данная раскладка имеет 14 решений, но первое находится буквально сразу, как первая же возможная расстановка:

W....
..W..
....W
.W...
...W.

Hidden text

((field)=>{
    var N=Math.sqrt(field.length);
    var rw=Array(N);
    var cl=Array(N);
    var cr=Array(N);
    var sol=Array(N*N);
    var psol=()=>{var k=0;var s='';for(var i=0;i<N;++i){for(var j=0;j<N;++j,++k){s+=sol[k]?'W':'.';}s+='\n';}console.log(s)};
    var id=(r,c)=>r*N+c;
    var nei=(r,c)=>(r>0&&c>0&&sol[id(r-1,c-1)])||
                   (r>0&&     sol[id(r-1,c)])||
                   (r>0&&     sol[id(r-1,c+1)])||
                   (     c>0&&sol[id(r  ,c-1)])||
                   (          sol[id(r  ,c)])||
                   (          sol[id(r  ,c+1)])||
                   (     c>0&&sol[id(r+1,c-1)])||
                   (          sol[id(r+1,c)])||
                   (          sol[id(r+1,c+1)]);
    var ok=(r,c)=>!rw[r]&&!cl[c]&&!cr[field[id(r,c)]]&&!nei(r,c);
    var set=(r,c,v)=>{
        sol[id(r,c)]=v;
        rw[r]=v;
        cl[c]=v;
        cr[field[id(r,c)]]=v;
    };
    var solve=(r)=>{
        var sols = 0;
        for(var c=0;c<N;c++) {
            if(ok(r,c)) {
                set(r,c,true);
                if(r==N-1) { sols ++; psol(); }
                else sols += solve(r+1);
                set(r,c,false);
            }
        }
        return sols;
    };
    console.log("Total count of solutions: ", solve(0));
})([0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4])

Как Unity отказались от своих строк

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

Литкод изи — это просто

У нас в задаче N строк, N столбцов и N разных цветов. То есть если есть только одна область -- задача представляет собой одну единственную клетку 1*1

Литкод изи — это просто

Ну нас интересует не количество валидных расстановок, а поиск какого-либо решения. Мы же не ищем количество решений, ни пытаемся найти какое-то особое решение -- нам устроит любое.

С этой точки зрения, "каждая строка -- отдельный цвет" это лучший, а не худший случай, мы найдём решение практически с первой попытки.

p.s.: ради интересу добавил вывод числа найденных решений в скрипт; сегодня только одно решение. в задаче от 28го (та что в статье) тоже только одно решение. интересно...

Что такое 50% cpu?

для VR очень даже надо рендерить два кадра одновременно.

Литкод изи — это просто

Хм. Чет я и правда затупил. У нас не дерево, а матрица.

Разверну чуть больше.

Рекурсия используется в качестве программного "цикла циклов", соответственно, эквивалентная схема:

  for( i1 in range(N)):
    for( i2 in range(N)):
      for( i3 in range(N)):
        ..
        for( iN in range(N)):

то есть таки да, это цикл на N^N итераций.

Проверки вертикалей (проверки горизонталей всегда true так как циклы работают каждый на своей выделенной горизонтали) превращают в факториал, так как мы заменяем вызов следующих циклов на константную проверку массива.

Проверок диагоналей у нас нет. Проверка соседей меняет выкидывание одной клетки в строке на выкидывание почти трёх:

 0 1 0 0   =>  0 1 0 0  => 0 1 0 0
 ? ? ? ?       ? x ? ?     x x x 0

Но это только в прямо последующей строке. Фактически, снижает с полного факториала до факториала N-2 что не влияет.

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

Таким образом, фактическая сложность получается факториал, а не квадрат.

... что только подтверждает, что решение "в лоб" обычно далеко от эффективности;
... что не меняет того факта, что решатель справляется за практически невидимое для глаза время, так как решение точно существует всегда; задача предполагает решение человеком; и максимальный размер я пока за ~150 дней видел только 15*15.

Литкод изи — это просто

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

Российская Java теперь свободно доступна для скачивания

25 лет суммарно. 300 интернов с опытом по месяцу

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

удивительно, как странно выглядит код в gcc если добавить -fPIC. clang'овый сразу уже позиционно-независим и не меняется от флага

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

Имеется ввиду любая реализация проверки на число элементов.

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

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

sizeof -- размер в байтах, countof -- размер в элементах. Существует как _countof и в вариациях имени типа array_size, ARRAY_SIZE, std::ranges::size и все прочие. Просто проверяем, на момент компиляции, что размер массива сопадает числу элементов ENUMа.

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

Средствами языка и без накладных расходов:

• Когда в массиве элементы перечислены последовательно -- сравнивая countof() в compile-time, мой основной подход;

• Мета-макросы, как @RR_Zz упоминул ниже;

• unit-testing с перечислением всех вариантов (я считаю форменным издевательством для данного случая, впрочем).

Средствами языка с накладными расходами:

• Используя enum class + функцию с case вместо массива;

• Проверки assert()'ы или просто if()'s в функциях доступа для проверок или включая проверки на доступ вне массива

Средставми вне языка без накладных расходов в рантайме:

• стандартные статические анализаторы;

• генератор кода по внешнему источнику (в каком-то смысле вариация x-macro)

• ручной валидатор кода заточенный под конкретный случай, например, автогенерация юнит теста.

Это навскидку