Няшная / Говнокод #27873 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

typedef struct
{
  int32_t x;
  int32_t y;
} coord;

coord stack[1000000] = {{0,0}};

size_t stack_end = 1;

int checkstack(coord in)
{
  for(size_t i = 0; i < stack_end; i++)
  {
    if((stack[i].x == in.x) && (stack[i].y == in.y)) 
    {
      return 0;
    }
  }
  stack[stack_end] = in;
  stack_end += 1;
  return 1;
}

void consume_char(char ch, coord *c, uint32_t *sum)
{
  switch( ch )
  {
    case '>':
      c->x += 1;
      break;
    case '<':
      c->x -= 1;
      break;
    case '^':
      c->y += 1;
      break;
    case 'v':
      c->y -= 1;
      break;
    default:
      printf("ERROR!!");
      exit(-1);
  }
  *sum += checkstack(*c);
}

const char *arr = "^><^>>>^<^v<v^^vv^><<^.....";


int main(void)
{
  const char *arr_ptr = arr;
  coord crd = {0,0};
  uint32_t sum = 1;
  while (*arr_ptr != '\0')
  {
    //printf("test\n");
    consume_char(*arr_ptr, &crd, &sum);
    arr_ptr++;
  }
  printf("%" PRIu32 "\n", sum);
  return EXIT_SUCCESS;
}

Решил от нехуй делать попроходить https://adventofcode.com/
Вот например https://adventofcode.com/2015/day/3

Запостил: j123123 j123123, (Updated )

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

  • Но вообще это какая-то хуита неоптимальная, каждый раз перепросматривать стек чтоб найти посещенную хуйню в нем. Может тут нужно накопившееся говно периодически сортировать и по нему двоичным поиском искать вхождения, для большей оптимизации? Или вот есть еще такая хуйня: https://ru.wikipedia.org/wiki/Двоичная_куча
    Ответить
    • https://github.com/jtcass01/Advent-of-Code---Day-3/blob/master/day3.cpp
      А вот например решение от какого-то крестушка. Классы-хуяссы какие-то, нахуй это вообще нужно-то? Да и вся хрень в std::set решается, это вообще тупо. Я то хоть стек написал для запоминания хуйни. А всё прочее - какой-то тупой крестобойлерплейт
      Ответить
      • > крестушка
        > using namespace std;
        Это не крестух, это петух проткнутый!
        Ответить
      • bool operator<(const house & other) const{
        	return (x<=other.x);
        }

        А вот тут прямо баги полезли. set использует < чтобы сравнивать эквивалентность. Если a < b == false и b < a == false, значит a и b эквивалентны и b вставлять в сет не надо. Если бы он не использовал <=, то это бы отбрасывало дома с одинаковым х, но разным y. Теперь не отбрасывает, но повторяющиеся дома будет считать разными (наверное, технически запихивать в set что-то не подчиняющееся strict weak ordering — UB).
        Ответить
    • Я вообще подумывал воспользоваться канторовой нумерацией и переводить координаты в одно число. Не знаю, нахуя, скорости это не прибавит, да и превратить 2 32битных числа в одно 64битное для запихивания в известные алгоритмы — тривиально.
      Ответить
  • Надо найти точку где оно наступит на уже пройденные клетки?
    Ответить
      • Завести set пройденных клеток и в конце посмотреть его size?

        O(n) по памяти, O(N*log(N)) по времени.

        З.Ы. Или даже хешмапку.
        Ответить
        • А какой set под это лучше использовать? Обычный, из кретоговняной библиотеки?

          Я на Си тупо через стек хуйнул, мне было лень какой-то set писать.
          Ответить
          • Мне было бы лень сет писать и я бы тупо std::set хуйнула. Но возможно unordered_set тут будет лучше. Х.з., бенчить надо.
            Ответить
          • unordered_set, который хешмапа.

            Хотя на их размерах ввода О(N²) у стека вообще не проблема, не удивлюсь, если из-за накладных расходов на хешмапу она будет медленнее.
            Ответить
            • А сколько там?

              Так то на тыще уже будет миллион чтений против десяти тысяч (мапа) или тысячи (хешмапа)...

              Это надо прям сильно выдрочить стек и написать совсем анскилльную хешмапу, чтобы проиграть.
              Ответить
              • 8192
                У *мап же значения в динамически аллоцируемых нодах хранятся, цена аллокаций может быть слишком велика.
                У unordered с этим вроде получше, там массивы, а у тех, что деревьями реализуются — по аллокации на каждое значение.
                Ответить
                • Аллокации быстрые будут, тут же нету free, куча не фрагментированная.

                  Хрен знает, бенчить надо.
                  Ответить
                  • Кстати, у std::map была проблема, когда при emplace создавалась нода, пыталась вставиться, и, при провале, деаллоцировалась — дрочка памяти на ровном месте. Не помню, затрагивало ли это set, или другие способы вставки.

                    Потом это толи в С++14, толи в 17 пофиксили.
                    Ответить
          • Ну можно ещё выписать все позиции в массив первым проходом за O(n), сортирнуть один раз за O(n*log(n)) и пробежаться глянуть сколько разных...

            qsort то можно на сишке юзать?

            Даже если нет, сортировку легче нахуячить с нуля, чем дерево/хешмапу.
            Ответить
            • Можно периодически сортировать питушню с уже пройденными клетками, и по ним ебашить двоичный поиск. Если не найдено, проверять стек. Если в стеке не найдено, добавлять туда. Когда стек достаточно сильно разжиреет, его можно отсортировать и смержить с сортированной питушней, и там уже ебашить двоичный поиск, и накапливать уже новый стек, если что-то новое появляется
              Ответить
              • А в чём профит по сравнению с "тупо свалить в массив весь маршрут и отсортировать один раз"?

                Более эффективная работа если по одним и тем же местам бегают?
                Ответить
                    • Если путь сгенерирован полностью рандомно, т.е. допустим взяли из ГСЧ последовательность нулей и единиц, и последовательность 00 значит '>', 01 - '<', 10 - '^', 11 - 'v' т.е. если хождение влево вправо вверх или вниз равновероятно, и если очень много шагов, путь будет наслаиваться достаточно часто, чтобы это имело смысл
                      Ответить
    • #inclide <iostream>
      #include <algorithm>
      #include <cmath>
      
      const/*expr*/ int32_t primes[] = {2, 3, ... , 2147483647}; // 400 MB of data
      bool isPrime(int32_t suspected_prime)
      {
          suspected_prime = abs(suspected_prime); // Число Тараса не простое, так что похуй
          return std::binary_search(std::begin(primes), std::end(primes), suspected_prime);
      }
      Рассказываю. Решение работает за константное время между прочим.
      Ответить
      • За логарифмическое. За константное это если в отдельных битиках помечать простоту числа. И учитывая что 2 это единственное четное простое число, количество битиков можно в 2 раза сократить, проверяя для двойки через отдельный if().
        Ответить

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

Из-за тебя ушел bormand, guest!

    А не использовать ли нам bbcode?


    8