1. C++ / Говнокод #24024

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    bool almostIncreasingSequence(std::vector<int> sq) {
    bool b2 = true; 
    int s = sq.size(); 
    if (s > 2) {                                           // Последовательность меньше трех чисел дает истину.                          
        int i = 1;                                         // Проверка начинается со второго элемента.                                             
        int x = -1;                                      // Для записи индекса элемента <= предыдущего, а еще "флаг".           
        while ((b2) && (i < s)) {              // При нахождении 2-го лишнего происходит выход из цикла.                                 
            if (x != -1) {                               // Проверка "флага".                                                                                             
                if (sq[i] <= sq[i - 1]){           // Сравнение с предыдущим элементом.                                                             
                    b2 = false;                        // Если условие истинно, то это уже второй элемент,                                
                }                                             // "конфликтующий" с предыдущим, следовательно, выход и "ложь".
                if ((sq[i] <= sq[x - 1]) && (x != 1) && (sq[i - 1] <= sq[x - 2])) {  // над этим условием я думал слишком долго
                    b2 = false;                       // Если элемент был "убран", индекс конфликтного                                   
                }                                            // элемента записан в "x".                                                                                   
            }     
            else {                                        // Если условие ложно, то записываем индекс элемента, который
                    if (sq[i] <= sq[i - 1]) {     // "конфликтует" с предыдущим.
                        x = i;                             // Нам не известно лишний он или нет.
                    } 
                }
            i++;
            }
        }
      return b2;
}

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

    Запостил: noserdan, 28 Марта 2018

    Комментарии (44) RSS

    • ava g0_1494089160669 28.03.2018 13:24 # 0

      cbf5a8e5968f9c3af26e737a5a4f87e3
      Ответить

      • ava noserdan 28.03.2018 14:46 # +1

        сложна. заинтриговал, скажи хоть на чем это
        Ответить

        • ava noserdan 28.03.2018 14:48 # 0

          md5?
          Ответить

          • ava 1024-- 28.03.2018 18:55 # +2

            Сначала тоже задавался этим вопросом, но потом ещё джва послания марсиан появились: http://govnokod.ru/24025#comment410419, и я уже начал подозревать, что это за рептилоиды.

            http://govnokod.ru/22738#comment409233

            Думаю, ничего полезного в этих комментариях нет, разгадавший их максимум найдёт уязвимость в говнокоде inho или получит IP от какого-нибудь прокси, через который спамит g0_***.
            Ответить

            • ava noserdan 29.03.2018 08:17 # 0

              гугл говорит, что разгадывать подобное - хардкор
              Ответить

            • ava bormand 29.03.2018 08:42 # 0

              Опенсурс же, можно не гадать а тупо прочитать как инхо этот хеш делает.
              Ответить

              • ava noserdan 29.03.2018 14:22 # 0

                в чем смысл сего действия?
                в плане - нах энтот спам, я не разумею
                Ответить

                • ava 1024-- 29.03.2018 16:35 # +1

                  У Вас ссылки некликабельные? Заведите PRO аккаунт.
                  http://govnokod.ru/22738#comment409233

                  Этот спам нужен, чтобы можно было на другом сайте подтвердить свою учётную запись с этого сайта - чтобы в будущем все точно знали, что вот это Борманд, вот это спамер g0_циферки.
                  ссылка доступна для владельцев платных аккаунтов
                  Ответить

              • ava roman-kashitsyn 29.03.2018 14:43 # 0

                > Опенсурс же, можно не гадать а тупо прочитать как инхо этот хеш делает.

                Код не читал, но подозреваю, что это тест трансфера аккаунтов на .xyz, мы как-то обсуждали похожий способ в комментах.
                Ответить

                • ava bormand 29.03.2018 14:45 # 0

                  Ну тогда это просто рандомный токен и скрытого смысла в нём нет.
                  Ответить

                  • ava PaulDenisevich 29.03.2018 16:20 # 0

                    Скрыл свой двадцатиметровый смысл в твоём анусе, проверь.
                    Ответить

    • ava gost 28.03.2018 15:39 # 0

      ?
      bool almostIncreasingSequence(const std::vector<int> & sq)
{
    bool elRemoved = false;
    for (size_t i = 1; i < sq.size(); i++) {
        if (sq[i] <= sq[i - 1]) {
            if (elRemoved) {
                return false;
            } else {
                elRemoved = true;
            }
        }
    }
    return true;
}
      Ответить

      • ava gost 28.03.2018 15:51 # 0

        А нет.
        Ответить

        • ava gost 28.03.2018 15:59 # 0 

          bool almostIncreasingSequence(const std::vector<int> & sq)
{
    bool elRemoved = false;
    for (ptrdiff_t i = 1; i < sq.size(); i++) {
        if (sq[i] <= sq[i - 1]) {
            if (elRemoved) {
                return false;
            } else {
                if (i - 2 >= 0 && sq[i] <= sq[i - 2]) {
                    return false;
                }
                elRemoved = true;
            }
        }
    }
    return true;
}

          Хм, интересно, а можно короче?
          Ответить

          • ava roman-kashitsyn 28.03.2018 16:58 # 0

            > Хм, интересно, а можно короче?

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

            almostIncreasingSequence({1, 2, 0, 3}) => false
            Ответить

    • ava roman-kashitsyn 28.03.2018 16:55 # +1

      Нужно больше алгоритмов
      // https://ideone.com/jeuT8j
template <class It, class Less>
bool almost_increasing_seq(It begin, It end, Less cmp) {
  const auto lbound = std::adjacent_find(begin, end, std::not2(cmp));
  if (lbound == end) {
    return true; // already sorted
  }
  const auto rbound = lbound + 1;
  if (rbound == end || (rbound + 1) == end) {
    return true; // can just drop the last one
  }
  return std::adjacent_find(rbound, end, std::not2(cmp)) == end &&
         (lbound == begin || cmp(*lbound, *(rbound + 1)) ||
          cmp(*(lbound - 1), *rbound));
}
      Ответить

      • ava noserdan 29.03.2018 08:11 # 0

        я еще слишком слаб, для меня это пока эльфийская грамота =^_^=
        Ответить

        • ava noserdan 29.03.2018 08:15 # 0

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

          • ava roman-kashitsyn 29.03.2018 12:03 # +2

            > нахреначить сложных проверок

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

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

            Если в голове последовательности приклеить виртуальную минус-бесконечность, которая меньше всех элементов массива, а к хвосту ­— виртуальную плюс-бесконечность, которая больше всех элементов массива, то примерно половина проверок не нужна, т.к. тогда каждая подпоследовательность либо будет пустой, либо будет состоять из двух элементов и более. Вот только для инта таких бесконечностей не существует.
            Ответить

            • ava roman-kashitsyn 29.03.2018 12:51 # +1

              Что-то вроде
              // https://ideone.com/LCUKpY
data ExtInt = NegInfty | Normal Int | PosInfty deriving (Show, Eq, Ord)

adjacentZipper :: (a -> a -> Bool) -> [a] -> ([a], [a])
adjacentZipper cmp items = go [] items
  where go front [] = (front, [])
        go [] (x:rest) = go [x] rest
        go ys@(y:_) xs@(x:rest) = if cmp x y then go (x:ys) rest else (ys, xs)

almostIncreasing :: [Int] -> Bool
almostIncreasing nums = check ([NegInfty] ++ map Normal nums ++ [PosInfty])
  where check items = case adjacentZipper (>) items of
                        (_, []) -> True
                        ((x2:x1:_), right@(y1:y2:_)) -> (x1 < y1 || x2 < y2) && sorted right
        sorted = null . snd . adjacentZipper (>)
              Ответить

              • ava noserdan 29.03.2018 14:03 # 0

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

                вот если так говорить, это только еще больше запутывает, особенно дальнейшее объяснение)
                Ответить

                • ava vistefan 01.04.2018 12:37 # 0

                  Посмотрите мой ответ ниже.

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

                  • ava bormand 01.04.2018 12:39 # 0

                    1 2 3 4 5 2 3 4
                    Ответить

                    • ava vistefan 01.04.2018 12:43 # +1

                      А ты посмотри на код ниже, там же если возник элемент меньше предыдущего, то current не перезаписывается. На твоей последовательности вернет False.
                      Ответить

                    • ava vistefan 01.04.2018 12:51 # 0

                      Если на словах говорить точнее, можно рассматривать последовательность как график дискретной функции. Нас интересуют такие графики невозрастающие графики, из которых можно убрать одну точку так, чтобы они стали возрастающими. То есть проходим по точкам и убеждаемся, что для точки ai должно выполняться: количество точек aj при j > i, таких, что aj < ai должно быть не больше единицы, и точек, для которых это число не равно нулю тоже не больше одной.

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

              • ava vistefan 01.04.2018 12:33 # +1

                > Идея решения на самом деле простая: исходная последовательность должна быть конкатенацией двух строго возрастающих подпоследовательностей, которые можно склеить вместе, выкинув хвост первой или голову второй.

                Чо-то хуйня какая-то. Вот же:
                def check(a):
    current = a[0]
    count = 0
    for i in range(1, len(a)):
        if a[i] < current:
            count += 1
            if count > 1:
                return False
        else:
            current = a[i]
    
    return count == 1

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

                • ava noserdan 02.04.2018 13:48 # 0

                  я ща проверю там на тестах
                  Ответить

                • ava noserdan 02.04.2018 14:03 # 0

                  Валится на тесте "1,3,2". Я неверно переписал?

                  int current = a[0];
    int count = 0;
    for (int i = 1; i < a.size(); i++)
    {
        if (a[i] < current)
        {
            count += 1;
            if (count > 1)
                return false;
        }
        else
            current = a[i];
    }
    return (count == 1);
                  Ответить

                  • ava noserdan 02.04.2018 14:05 # 0

                    ошибся, на примере "1,2,1,2"
                    10, 1, 2, 3, 4, 5
                    Ответить

                    • ava vistefan 02.04.2018 14:15 # 0

                      На [1, 2, 1, 2] не должно валиться. Проверь условия задачи, тебе нужна строго возрастающая или неубывающая последовательность. В зависимости от этого, возможно нужно поправить сравнение в условии на <=.

                      Про случай, когда надо выкинуть первый элемент [10, 1, 2, 3, 4, 5] я совсем не подумал. Но должно хватить костылика:
                      int current = min(a[0], a[1]);
                      Понимаешь, почему это сработает, да?
                      Ответить

                  • ava noserdan 02.04.2018 14:10 # 0

                    1, 2, 3, 4, 5, 3, 5, 6
                    1, 2, 3, 4, 99, 5, 6
                    123, -17, -5, 1, 2, 3, 12, 43, 45
                    Ответить

                    • ava vistefan 02.04.2018 14:22 # 0

                      [1, 2, 3, 4, 99, 5, 6]

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

                      • ava noserdan 02.04.2018 14:29 # 0

                        да я уже сделал) мой пример из поста.
                        переписывать стоит, если понял решение, а там есть вещи мне незнакомые
                        Ответить

                      • ava roman-kashitsyn 03.04.2018 13:20 # +2

                        > А, да, этот пример показывает, что мой метод полная хуйня.

                        Я не понимаю, почему все хотят решить задачу в одном цикле, это же неудобно, надо хранить какие-то лишние состояния (removed/count/b2/etc).
                        Если решать так, как я объяснял, то никакой мутабельности и сложных переходов: находим, где одна подпоследовательность рвётся и начинается другая, пытаемся приклеить. Не надо трекать в уме никакие состояния. Код лучше декомпозируется, разделяется на простые функции:
                        • функция поиска первого места, где подпоследовательность перестаёт быть возрастающей;
                        • функция, проверяющая, можно ли объединить две возрастающие подпоследовательности, возможно, выкинув один элемент из одной из них.
                        Ответить

                        • ava 1024-- 03.04.2018 19:59 # +2

                          > Я не понимаю, почему все хотят решить задачу в одном цикле, это же неудобно
                          > Если решать так, как я объяснял, то никакой мутабельности и сложных переходов
                          Вероятно, Вы просто лучше продвинулись по лестнице абстракции. Там у Вас хорошо, дует ветерок, всё просто и понятно.
                          У нас внизу всё гораздо печальней. Получается либо сложный цикл, либо простой, но за квадратичное время. А написать сложный цикл всё ещё легче, чем подняться на ту же ступеньку абстракции и написать простой цикл.
                          Ответить

                          • ava 3.14159265 04.04.2018 17:58 # 0

                            >У нас внизу всё гораздо печальней. Получается либо сложный цикл

                            Что если сохранить начальные индексы отсортированных subsequence in array?

                            А потом просто сравнить значения по индексам-брейкерам?

                            //arr= [1, 2, 3, 4, 99, 5, 6]
                            Сохраняем:
                            indx=[0, 4, 5]
                            Делаем все сложные проверки (массив не больше 3х, indx[2]-indx[1]==1, arr[indx[2]]>arr[indx[1]-1]).
                            Ответить

                            • ava 1024-- 08.04.2018 12:40 # 0

                              Подумал над этим. Мне это не кажется сильным упрощением, просто некоторые проверки перешли в другой цикл. Столь сильного математического смысла, как у Романа, чтобы можно было думать в новых категориях, тут вроде бы нет.
                              Ответить

                        • ava 3.14159265 04.04.2018 17:44 # +1

                          >Я не понимаю, почему все хотят решить задачу в одном цикле

                          Потому что Царь живёт в каждом.
                          В смысле 1 проход оптимальнее.
                          Любое разумное существо на интиутивном уровне стремится делать что-то за 1 раз.
                          Ответить

                          • ava bormand 04.04.2018 18:29 # +2

                            > 1 проход оптимальнее
                            Ну 2 цикла ещё не подразумевают 2 прохода (и тем более — квадратичность). К примеру, первый по первой половине последовательности пробежал, а второй ­— по оставшейся.
                            Ответить

                          • ava roman-kashitsyn 05.04.2018 01:07 # 0

                            > В смысле 1 проход оптимальнее.

                            Оптимально не делать лишних проверок. Например, когда печатаешь список, разделённый запятыми, оптимально сразу проверить на пустоту и вывести первый элемент, а потом написать простой цикл, а не долбить if (first) в цикле.
                            Ответить

                            • ava subaru 05.04.2018 01:11 # 0

                              > не долбить if (first) в цикле
                              Бранчпредиктор зарешает.
                              Ответить

    • ava 1024-- 02.04.2018 20:06 # 0 

      const ordered = (a, b) => a < b;

function almostIncreasingSequence(xs) {
  for(var i=0, removed = false; i<xs.length - 1; ++i) {
    if(!ordered(xs[i], xs[i+1])) {
      
      // если раньше убирали, а теперь непоследовательность второй раз
      // или уберём сейчас левый или правый, а последовательности не будет
      if(removed ||
         i > 0 && !ordered(xs[i-1], xs[i+1]) &&
         i + 2 < xs.length && !ordered(xs[i], xs[i+2])) return false;
      
      // если выкинуть один, xs[0]..xs[i+1] - упорядочена
      removed = true;
    }
  }
  
  return true;
}


      Вроде работает. Сравнивал с наивной квадратичной питушнёй:
      const least = -Infinity;

const isIncreasingSequence1 = (_, n, xs) => xs.reduce((r, x, i) =>
  i == n ? r : [r[0] && ordered(r[1], x), x], [true, least])[0];

const almostIncreasingSequenceNaive = xs =>
  isIncreasingSequence1(null,-1, xs) || xs.some(isIncreasingSequence1);

      Сравнение:
      function seqInc(xs) {
  const dmin = -3, dmax = 3;
  for(var i=0; i<xs.length; ++i) {
    if(++xs[i] > dmax) xs[i] = dmin;
    else break;
  }
  if(i >= xs.length) {
    for(var i=0; i<xs.length; ++i) xs[i] = dmin;
    xs.push(dmin);
  }
}

var seq = [];

while(seq.length < 7) {
  var a = almostIncreasingSequence(seq);
  var an = almostIncreasingSequenceNaive(seq);
  if(a != an) console.error(seq, a, an);
  seqInc(seq);
}

      https://ideone.com/Dba2sx
      Ответить

      • ava vistefan 02.04.2018 22:58 # 0 

        def almostIncreasingSequence(seq):
	border = -1;
	for i in range(0, len(seq) - 1):
		if seq[i] > seq[i + 1]:
			if border > -1:
				return False
			else:
				border = i + 1

	return border == 1 or \
		   border == len(seq) - 1 or \
		   seq[border - 1] <= seq[border + 1] or \
		   seq[border - 2] <= seq[border]
        Ответить

        • ava 1024-- 03.04.2018 06:20 # 0

          Эта питушня работает, или я не прав?

          Поправил ordered на <= (кстати, в моём коде можно только < на <= в ordered поменять, чтобы поддерживались и неубывающие питухи). Загнал её в своё сравнение с наивным питухом - в итоге даже выдаёт false на массивах длины два.
          https://ideone.com/G2RQgO
          Ответить

    Добавить комментарий