Ответы пользователя по тегу Python
  • Python массивы не пашет нужна помощь, что делать?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас массив интов создается:
    massive = array('i', [])

    А пихаете вы туда символ:
    massive.append(random.choice(string.ascii_letters))


    О чем вам интерпретатор и говорит:
    TypeError: an integer is required (got type str)
    Ответ написан
  • Как работают классы в Python?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    https://docs.python.org/3/tutorial/classes.html#cl... - инструкции внутри class выполняются один раз.
    Обычно там пишут определения методов и членов класса. Точно так же, как у вас в коде ниже написано определение функции test_def. Определение всегда выполняется.
    Ответ написан
  • Как составить массив из чётных элементов матрицы на Python?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    В заголовке у вас про четные, а в теле задания - плолжительные. Программа как бы ищет четные. Но числа float же, для них четность не имеет смысла. Вам нужно вместо float при вводе приводить к int.

    edit:
    А еще у вас при обходе матрицы только один цикл. А надо так же как при вводе делать двумя вложенными циклами.
    Ответ написан
  • Как максимально оптимизировать код Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Проблема не в коде, а в алгоритме. Долго строить всю строку и считать в ней нули.

    Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

    Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

    Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.
    Ответ написан
  • Какой алгоритм для поиска подстрок в списке кортежей будет быстрее comprehension?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Алгоритм Ахо-Корасика.

    Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.
    Ответ написан
  • Как построить функцию декодирования классического кода Элиаса, если прямое кодирование работает правильно?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Опишите словами, что делает это кодирование, что оно пишет в файл?

    И читайте это:
    1) подсчитайте сколько нулей идет в начале строки.
    2) Это сколько бит надо прочитать дальше и перевести в десятичную систему счисления.
    3) Это столько бит, сколько нужно прочитать дальше и перевести в десятичную систему, чтобы раскодировать число.
    Ответ написан
  • Python. Найти расстояние от точки до прямой, зная координаты этой точки?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Составьте уравнение прямой вида a*x+b*y+c=0.
    Подставьте в это уравнение координаты точки. Возьмите по модулю и поделите на sqrt(a^2+b^2).
    Ответ написан
  • Как решить задачу по рекурсивным алгоритмом на python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вы, похоже, забыли обнулять счетчик восьмерок (k) для каждого значения f.
    Ответ написан
  • Почему не работает алгоритм Брона-Кербоша?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас две большие ошибки с языком питон. Вы в цикле в alg итерируетесь по списку add, меняя его. Так делать нельзя. Ломаются итераторы и вы пропускаете половину элементов.

    Вместо этого используйте цикл while:

    while add:
      item = add[0]
      add.remove(item)
      s.append(item)
    ...


    Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

    С этими двумя изменениями должно работать. Ну, и у вас главная оптимизация алгоритма не реализована. Надо в начале цикла проверить, что среди оставшихся вершин в add есть хоть одна соединенная с каждой вершиной из exists. Если таковых нет - нужно вывалится из цикла.

    Еще по коду:
    range(n) в python возвращает 0..5. У вас там цикл по ребрам в __main__ и там идет обращение к i-1 в массиве graf. Т.е. обращение к [-1]. Вряд ли вы это хотели. Работает по чистой случайности, потому что в питоне a[-1] дает последний элемент.

    И вообще, вы матрицу смежности строите, но нигде не используете.

    Вместо функции check(), вы сделайте нормальный список смежности один раз, а то просто глаз режет от неоптимальности.
    neighbors = [[] for i in range(count_vershin)]
    for edge in graf:
      neighbors[edge[0]-1].append(edge[1]-1)
      neighbors[edge[1]-1].append(edge[0]-1)
    Ответ написан
  • Как доработать алгоритм?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это не совсем ним (где несколько кучек и за ход можно взять сколько угодно камней). Судя по коду, игроки могут брать 1,2 или 3 камня и кучка одна. Кажется, у вас выигрывает тот, кто возьмет последний камень.

    Сначала немного теории игр.
    Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

    Поэтому для 8 камней, если начинает бот, и человек действует правильно - бот всегда проиграет.

    Правильная функция choize должна быть:
    def choose(s):
      if s%4 == 0: return 1
      else return s%4


    Тогда бот обязательно выиграет, если выигрышная позиция есть, или если человек допустит ошибку, хоть у него и была выигрышная стратегия.

    Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
    Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.
    Ответ написан
  • Как найти изоморфизм графов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех i, j проверяйте, что a[p[i]][p[j]] == b[i][j].

    Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

    Как только нашли перестановку, для которой матрицы совпали - выводите перестановку в ответ и вываливайтесь из перебора.

    Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

    Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

    Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).
    Ответ написан
  • Как праильно определить лотерейные билеты в соответствии с условиями задачи?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    И меня не устраивает "единственный" проблемный отрывок кода:
    if ndata[i] % 2 != 0 and nf % 2 != 0: lucky += 1

    Там вообще какой-то бред написан. При чем тут проверка на четность вообще?!

    Вам надо подсчитать солько чисел из trda есть в ndata и вывести Lucky, если насчитали хотя бы 3 (перечитайте же условие задачи).

    Соответственно должно быть что-то вроде
    if nf == ndata[s]: cnt+=1
    ...
    if cnt >=3:  print('Lucky')
        else: print('Unlucky')


    Еще у вас вложенные циклы по одной и той же переменной i, может в питоне так и можно, но это обычно очень плохая идея.
    Ответ написан
  • Как для каждого делителя из одного массива найти делители из другого массива с остатком 0?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если я правильно понял задачу, то надо подсчитать для каждого i
    sum_{j=1..n} (i%j?1:0) % 2.

    Или - есть n ламп в ряд изначально не горящих. Переключаются каждая первая, каждая вторая, третья и т.д. Вопрос - а какие лампы горят в конце.

    Разверните условие. Не переключайте каждую 1-ую, 2-ую и т.д. лампу, а подсчитайте для каждой лампы, сколько раз она будет переключена (потому что переключать их все по одной - это медленно. Надо как-то агрегировать вычисления)?

    Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

    Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

    Итого ответ - проставить true в массиве по всем индексам i*i.
    Ответ написан
  • Алгоритм пропуска числа?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это обобщение известной задачи, где пропущено одно число. Там можно, например, вычесть все числа из n(n+1)/2. Или про-xor-ить все числа от 1 до n и все числа в массиве.

    Для двух чисел нужно составить какие-то 2 уравнения, Например, найдите сумму двух чисел и сумму их квадратов: Сумма пропущенных чисел - это n*(n+1)/2 - (сумма всех чисел в массиве). Здесь надо аккуратно не забыть о возможном переполнении (если ваш язык, например, С++). Сумма квадратов: сумма квадратов всех чисел от 1 до n минус квадраты всех чисел в массиве.

    Итак, вы за O(n) двумя не вложенными циклами (один для суммы квадратов 1..n, другой для обработки всех чисел массива) нашли X+Y=A и X^2 + Y^2=B.

    Теперь решите уравнения относительно X и Y: Выразите X через Y из первого уравнения и подставьте во второе. Решите квадратное уравнение и получите:
    X = (A-sqrt(2B-A^2))/2, Y = (A+sqrt(2B-A^2))/2.

    Тут, хоть и есть квадратные корни, они в итоге дают целые числа.
    Ответ написан
  • Как реализовать алгоритм рекурсией?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Нужна рекурсивная функция, которая обрабатывает строку и возвращает распакованную версию и где ее конец в заданной строке.

    Ваша ошибка в том, что в слуае "2(с)3(a)" вы попытаетесь 2 раза повторить результат распаковки строки "с)3(a"

    def process(s, begin):
      i = begin;
      ans = ""
      while i < len(s):
        // Внетренность скобок обрабатывается рекурсивно. ) - это конец строки для нас.
        if s[i] == ')': break;
        if '0' <= s[i] and s[i] <= '9':  // если встретили цифру
          k = 0
          // выделяем в k числовое значение записанного числа
          while i < len(s) and '0' <= s[i] and s[i] <= '9':
            // пока встречаются цифры берем их численное значение и приписываем в конец к k
            k = 10*k + ord(s[i]) - ord('0')
            i+=1
          // если после числа идет бува, то просто копируем ее нужное количетсво раз
          if  'a' <= s[i] and s[i] <= 'z': 
            ans += s[i:i+1]*k
            i+=1
          else:
            // иначе - должна быть скобка.
            assert(s[i] == '(')
            // рекурсивно обрабатываем внутренность скобок. Функция вернет нам, где
           // закрывающая скобка для данной.
            (i, cur) = process(s, i+1)
           // копируем результат распаковки строки внутри скобок нужное количетво раз
            ans += cur * k;
        else:
         // цирфы не было. Просто символ без множителя идет в ответ.
          assert('a' <= s[i] and s[i] <= 'z')
          ans += s[i:i+1]
          i += 1
      // мы могли закончить цикл на закрывающей скобке или в конце строки.
      // но скобку надо пропустить. Прибавляем 1 к счетчику.
      if i < len(s): i+=1
      return (i,ans)
    
    
    
    print (process("abc", 0))
    print (process("3a", 0))
    print (process("3(a)", 0))
    print (process("2(ab)", 0))
    print (process("10(a)", 0))
    print (process("2(b2(a))", 0))
    Ответ написан
  • Как выловить ошибку в коде?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

    Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

    Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.
    Ответ написан
  • Как применить бинарный поиск к массиву строк на Пайтон??

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.

    В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.

    Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.
    Ответ написан
  • Какой у этого решения time и space complexity?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Давайте составим рекурентное соотношение. Пусть F(n) - сколько работает ваша функция при входе в n элементов.

    В функции:
    - Выделяется новый массив: n операций
    - Вызывается функция для укороченного массива: F(n-1) операций
    - Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
    - Вложенный цикл по позициям: n*(n-1)! = n! повторений
    - вложенное в циклы построение новой перестановки: n*n! операций

    Итого F(n) = n + F(n-1) +n*n!

    Можно раскрыть рекурсивно и получим:
    F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
    Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
    В итоге, F(n) = O(n*n!).

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

    Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

    Это хорошая ассимптотика - для построения всех перестановок меньше нельзя.
    Однако, если вам не надо все перестановки хранить в памяти (да и для кэша, кстати) будет заметно быстрее генерировать следующую перестановку из текущей на месте, как описано тут. Хоть и с такой же ассимптотикой, этот алгоритм будет работать в несколько раз быстрее.
    Ответ написан
  • Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Немного пальцем в небо, но попробуйте заменить "/" на "//". Вам же надо в целых числах считать. Возможно, питон пытается блинные числа приводить к даблу и потом назад к длинными и теряет точность.

    Вместо ceil(a/b) используйте (a+b-1)//b
    Вместо floor(a/b) или, когда делится без остатка используйте a//b

    В логике решения ошибки я не вижу.
    Ответ написан
  • Обход Binary-Tree, как сделать быстрее?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:
    1
     \
      2
       \
        3
    
        3
       /
      2
     /
    1

    Тут оба обхода вернут 1,2,3.

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

    Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

    Очень логично реализовывается в виде DFS (ниже псевдокод):
    Equals(t1, t2):
       // обработать случай null одного или обоих деревьев.
       return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)


    Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

    Кстати, ваше решение, если его исправить, тоже будет за O(n).
    Ответ написан