1. Си / Говнокод #27873

    0

    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
    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, 13 Декабря 2021

    Комментарии (34) 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битное для запихивания в известные алгоритмы — тривиально.
        Ответить
    • О! В этом году тоже adventofcode сделали!
      Ответить
    • Надо найти точку где оно наступит на уже пройденные клетки?
      Ответить
      • Посчитать уникальные клетки.
        Ответить
        • Завести 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 то можно на сишке юзать?

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

                  Более эффективная работа если по одним и тем же местам бегают?
                  Ответить
                  • И еще экономия памяти
                    Ответить
                    • Только если путь реально наслаивается.
                      Ответить
                      • Если путь сгенерирован полностью рандомно, т.е. допустим взяли из ГСЧ последовательность нулей и единиц, и последовательность 00 значит '>', 01 - '<', 10 - '^', 11 - 'v' т.е. если хождение влево вправо вверх или вниз равновероятно, и если очень много шагов, путь будет наслаиваться достаточно часто, чтобы это имело смысл
                        Ответить
    • когда сделаешь - раскажешь.... https://www.codewars.com/kata/5262119038c0985a5b00029f/train/cpp
      Ответить
      • #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().
          Ответить
          • Всё же за константное. O(log(1)) = O(1). Размер массива константен и сложность поиска не зависит от числа (N).
            Ответить

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