• Как найти подряд три идущих единицы с использованием битовой логики?

    SynCap
    @SynCap
    Делаю интернет с 1998 года
    Судя по всему задание - учебное, задание, скорее всего, составлял спец по алгоритмам. Поэтому готового решения задачи приводить не буду, а дам подсказки.

    1. Массив Map можно конвертировать в массив байтов или просто рассматривать каждую строку, как массив битовых значений, соответствующих байту.
    Внешним циклом на этом этапе, будет перебор строк.
    В таком случае можно применять битовую логику:
    byteVal = Map[idx][0]*128+ Map[idx][1]*64+ Map[idx][2]*32+ Map[idx][3]*16+ Map[idx][4]*8+ Map[idx][5]*4+ Map[idx][6]*2+Map[idx][7]*1;


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

    2. теперь, последовательно сравним byteVal с числами, содержащими подряд 3 единицы в битовом выражении. Таких чисел, будет всего 6(!) - поиграйтесь с калькулятором, чтобы убедиться.
    Это можно записать в одну операцию (чисел для сравнения небольшое количество, их легко подготовить с помощью калькулятора и назначить константам), либо использовать операцию сдвига, взяв за основу число 7, которое есть 7 и одинаково 7 и в 8ми, и в 10ти, и в 16ти разрядных записях - все-равно: 7 = 0x7 = 0o7, и все остальные, нужные для тестирования значения получать в цикле используя побитовый сдвиг.
    Т.е. внутри цикла перебора строк, после вычисления значения байта:

    var testVal = 7;
    
    for (var i = 0; i < 6 OR ; i++) {
        if ( profit = byteVal & testVal === testVal )
            console.log('Profit найден в позиции %i', 6-i);
       testVal <<= 1;  // то же, что и возведение 2 в следующую степень
    }


    UPD: кого-то может удивить, а где оптимизация сдвига? дело в том, что принцип необходимо и достаточно, никто не отменял. Для слишком длинных строк, такой способ непременим - ограничение размера сдвига для Javascript - 32.
    Для вычисления актуального размера сдвига нужно ГОРАЗДО больше операций, чем лишние пару циклов с побитовым сравнением. Это справедливо даже для ассемблера, а для любой реализации Javascript в частности - ваабче в 100500 раз. Мы уже на каждой итерации внешнего цикла в данном шаге экономим пару циклов.

    Код приведен в соответствие со стандартами ECMA262 (ES5), новых фишек ES6 (ES2015) в нем нет.

    3. Внешний цикл, в отличие от предыдущего шага, лучше будет сделать - для тестового значения. Внутренний цикл - для номера строки, начинающей блок сравнения, состоящий из 3 смежных строк - для просмотра, совпадений по вертикали, проходим циклом по строкам 6(!) раз, вычисляем byteVal для каждой из 3х строк блока сравнения, будем проверять значения на совпадение одного бита, т.е. начальное значение testVal = 1, сдвигать влево, тоже будем на 1 бит.
    Для оптимизации алгоритма, будем сравнивать сначала byteVal для 1й тестируемой строки, если не совпадает, сразу увеличиваем индекс начальной строки на 1 и уходим на следующий шаг, иначе - (если 1е сравнение == profit) сравнение второй строки набора сравнения, если неудачно - прибавляем к индексу 2, а если сравнение неудачно только на 3й строке - 3, и соответственно - следующий шаг сравнений.
    Оптимизация заключается в том, что мы пропускаем комбинации строк, где заведомо не будет подряд значений. Т.е. если при проверке 3й строки мы выяснили, что профита не светит, то мы начинаем проверку, со следующей строки, но считаем ее первой строкой проверяемого набора, т.е. сдвигаем указатель начала проверяемого блока сразу на 3 позиции, т.к. последовательная проверка блоков со смещением +1 и +2 - заведомо не дадут профита, т.к. мы уже точно знаем, что на этом участке с профитом - облом.

    4. Второй вариант решения по нахождению совпадений по столбцам - это транспонировать ("развернуть" массив, сделав строки столбцами) массив Map, и к нему применить шаги 1 и 2. Либо относиться к нему как к заведомо транспонированному, заменив перебор строк, на перебор позиций, тогда при вычислении byteVal, каждое Map[idx][x], заменить на Map[x][idx].

    Подробнее о битовых операциях на DevDocs.io и на Javascript.ru (по-русски)

    По алгоритмам поиска, на основе которого построена оптимизация поиска, советую почитать Дональд Кнут "Сортировка и поиск", либо Томас Кормэн и др. "Алгоритмы. Построение и анализ".

    P.S.: Честно говоря, на написание рабочего решения, мне понадобилось, в 20(!) раз меньше времени и раз в 5 меньше текста. Цените ленивые неучи, для вас старался, а то помрет старая гвардия и ваши рабочие места займут старательные индусы и дотошные китайцы!

    UPD2: в литературе по графике, распознаванию образов и еще каким-то анализаторами, такие задачи встречаются, как части, только массивы данных дец поширше, и знаааачительно подлиннее.
    Ответ написан
    Комментировать
  • Стоит ли читать SICP?

    dimonchik2013
    @dimonchik2013
    non progredi est regredi
    ага, Кнут,
    за уши не притянешь
    Ответ написан
    2 комментария
  • Как лучше обойти массив, не выходя за его пределы?

    mmmaaak
    @mmmaaak
    Или прибавить функциональщины, воспользовавшись методом forEach. Там и индексы, и все остальное. Ну и если вы обращаетесь к элементу массива - проверку на его существование никто за вас делать не будет.
    Ответ написан
    1 комментарий
  • Как лучше обойти массив, не выходя за его пределы?

    In4in
    @In4in
    °•× JavaScript Developer ^_^ ו°
    Почему "нагромождения"? Вам нужно всего лишь проверить есть ли:
    if(Arr[i+10]&&Arr[i + 10][j + 10] === 1) {.....}

    А вообще, можно устанавливать вот это 100 (оно же не из неоткуда берется?) через:
    var s = Math.min(100, Arr.length);
    Ответ написан
    Комментировать
  • Как лучше обойти массив, не выходя за его пределы?

    @dmitryKovalskiy
    программист средней руки
    должно быть свойство length у массива. А если вам не до смерти нужные индексы i,j то попробуйте использовать циклы типа foreach
    Ответ написан
    Комментировать
  • Почему алгоритм работает некорректно?

    index0h
    @index0h
    PHP, Golang. https://github.com/index0h
    Ужос. Где var перед переменной a? Зачем вам явный тройной цикл, есть же indexOf

    var data = [],
        count = 42,
        tmpVar;
    while (data.length < count) {
        tmpVar = Math.floor(Math.random() * count);
        if (data.indexOf(tmpVar) === -1) {
            data.push(tmpVar);
        }
    }
    Ответ написан
    Комментировать
  • Почему алгоритм работает некорректно?

    Petroveg
    @Petroveg
    Миром правят маленькие с#@&ки
    Про неверный синтаксис do while уже написали.
    Я бы делал примерно так

    var x = set(42);
    
    console.log(x);
    
    function set (max_number) {
    	var array = [];
    
    	set.unic = [];
    
    	while (array.length < max_number) {
    		array.push(get());
    	}
    
    	delete set.unic;
    	return array;
    
    	function get (a) {
    		do {
    			a = Math.floor(Math.random() * max_number);
    		} while (isFinite(set.unic[a]));
    
    		return a;
    	}
    }
    Ответ написан
    Комментировать
  • Почему алгоритм работает некорректно?

    @Kano
    Не могу понять от куда у вас могла взяться приписка после второго while
    { 
         a = Math.floor(Math.random() * 42);
      }

    Уберите этот код и объявите переменную в начале кода через var a; а то судя по коду вы используете глобально определенную переменную "а" или же объявляете её глобально, а это не очень правильный подход
    Ответ написан
    Комментировать
  • Почему алгоритм работает некорректно?

    @serega_kaktus
    Программист-самоучка, фрилансер
    var arr, max_number, i, unic;
    arr = [];
    max_number = 42;
    while (arr.length < 42) {
      do {
        unic = true;
        a = Math.floor(Math.random() * 42);
        for (i = 0; i < arr.length; i++) {
          if (a == arr[i]) {
            unic = false;
            break;
          }
        }
      } while (!unic);
      arr.push(a);
    }

    Вы сначала находили в цикле do уникальное значение, а потом присвоили переменной a новое значение после цикла.
    Ответ написан
    Комментировать
  • Кто может объяснить, зачем мне GIT?

    hell0w0rd
    @hell0w0rd
    Просто разработчик
    Суть в том, что вы можете четко контролировать в какой момент получилось плохо. Вы можете проследить цепь событий которая к этому привела. И главное — вы можете спокойно откатиться на тот момент когда все было хорошо.
    В случае с гитом и доступом к ssh вы делаете так, на локальной машине
    git push
    на сервере
    git pull
    И собственно все!
    Если вы работаете с композером, то можно например настроить composer up на выполнение git pull перед обновлением зависимостей. Таким образом вы весь проект приводите к актуальному состоянию одной командой.
    И да, у вас по хорошему должна быть отдельная БД, в которой лежат тестовые данные, ведь вам важны схемы таблиц, а не их содержание по ходу разработки?
    Также по поводу гита — представьте что вы на столько любите женщин, что хотите встречаться с несколькими одновременно. В реальности трудно удержать более n-кол-ва паралельно, они столкнутся и вам будет плохо. А в git вы просто создаете ветки и то процедуры слияния они друг о друге не подразумевают. По хорошему каждая фича вашего приложения должна создаваться как отдельная ветка(branch), таким образом вы сможете просматривать историю разработки конкретно этой фичи отдельно.
    Сумбурно, но это ощущение после полугодичного использования гита.
    PS также представьте что вы сейчас вероятно один работаете, а каково работать таким образом в команде. Если это делать без VCS — высока возможность перезаписать файл который только что изменили и тд и тп
    Ответ написан
    Комментировать