Ответы пользователя по тегу Алгоритмы
  • Как оптимизировать код на Python?

    adugin
    @adugin Куратор тега Python
    Один из вариантов "в лоб" (без использования допфункций типа takewhile):
    def days_till_warming(T):
        counts = []
        for i, curr_temp in enumerate(T):
            for j, next_temp in enumerate(T[i+1:], i + 1):
                if next_temp > curr_temp:
                    delta = j - i
                    break
            else:
                 delta = 0
            counts.append(delta)
        return counts
    Ответ написан
    Комментировать
  • Процедурная генерация случайного мира из 100 на 100 клеток?

    adugin
    @adugin
    Вот упрощённый вариант "на пальцах":
    import cv2
    import numpy as np
    from PIL import Image
    from itertools import product
    
    N = 42
    W = 200
    H = 200
    
    def distance(p1, p2):
        y1, x1 = p1
        y2, x2 = p2
        return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    
    canvas = np.zeros((H, W, 3), dtype=np.uint8)
    centers = np.unravel_index(np.random.randint(0, W * H, N), canvas.shape[:2])
    canvas[centers] = np.random.randint(0, 256, (N, 3))
    centers = list(zip(*centers))
    
    for x in range(0, W):
        for y in range(0, H):
            cy, cx = min(centers, key=lambda center: distance(center, (y, x)))
            canvas[y, x] = canvas[cy, cx]

    Результат:
    6000b60d39a64183863109.png
    Для получения невыпуклых многоугольников можете случайным образом пообъединять смежные области. Например, берёте случайный центр, ищете ближайший к нему (или один из ближайших), закрашиваете области одним цветом, в списке центров вместо двух вставляете один. И так далее.
    Ответ написан
    Комментировать
  • Как найти все ближайшие связки чисел из массива?

    adugin
    @adugin Куратор тега Python
    nums = '1 2 2 2 5 8 12 12 13 15 15 21 25 26 32'
    nums = sorted(map(int, nums.split()))
    
    result = [x1 for x1, x2 in zip(nums[:-1], nums[1:]) if x2 - x1 == 1]
    
    print(*result)
    Ответ написан
    Комментировать
  • Как найти арифметическую прогрессию в списке?

    adugin
    @adugin Куратор тега Python
    import numpy as np
    from collections import deque
    from itertools import combinations
    
    # data = np.array([1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741])
    
    np.random.seed(42)
    data = np.random.randint(0, 100000, 1000)
    data.sort()
    
    # Интуитивный подход (baseline), O(n^3)
    def find_evenly_spaced_v1(data):
        for a, b, c in combinations(data, 3):
            if b - a == c - b:
                yield a, b, c
                
    # Эмпирическая оптимизация, O(n^2)
    def find_evenly_spaced_v2(data):
        dataset = set(data)
        for a, c in combinations(data, 2):
            b, mod = divmod(a + c, 2)
            if (mod == 0) and (b in dataset):
                yield a, b, c
    
    # Векторный вариант
    def find_evenly_spaced_v3(data):
        grid = data.reshape(-1, 1) + data.reshape(1, -1)
        divs, mods = np.divmod(grid, 2)
        mask = np.tri(*grid.shape, -1, dtype='bool') & np.isin(divs, data) & ~ mods.astype('bool')
        for c, a in zip(*np.where(mask)):
            b = divs[a, c]
            a, c = data[[a, c]]
            yield a, b, c

    Измерения скорости для 1000 элементов:

    5d95912c852ea517827440.png
    Ответ написан
  • Как просумировать два хэша?

    adugin
    @adugin
    Ответ написан
    Комментировать
  • Как найти алгоритм по поиску внешних сторон?

    adugin
    @adugin
    1) Любую плоскость можно описать вектором нормали к ней.
    2) Если центр координат разместить внутри дома, то можно сравнить направление нормали и направление к центру.
    Ответ написан
    4 комментария
  • Как сделать чтобы функция перебирала только целочисленные значения x?

    adugin
    @adugin Куратор тега Python
    Для случаев вида x = 1.0:
    if int(x) == x:
        ...

    Потому что:
    assert int(1.0) == 1.0
    Можно ещё так, но это будет работать только для истинно целых чисел (int, а не float):
    if type(x) is int:
        ...

    UPD
    data = [1.0, 1.23, 2.0, 2.71, 3.0, 3.14]
    for x in filter(float.is_integer, data):
        print(x)
    Ответ написан
    6 комментариев
  • Почему данный код является рабочим?

    adugin
    @adugin Куратор тега Python
    Если бы был конкурс на написание самого кривого планировщика событий (task scheduler) - этот код, несомненно, занял бы первое место) Попробуйте, например, delayed calls в asyncio.

    UPD Пример простого решения "в лоб", без асинхронности:
    from time import time, sleep
    from operator import attrgetter
    
    class Article:
    
        def __init__(self, timestamp, text):
            self.timestamp, self.text = timestamp, text
    
        def post(self):
            print(f"planned={self.timestamp:.0f}, posted={time():.0f}, text={self.text}")
    
    class Scheduler:
        
        def __init__(self, *articles):
            self.articles = sorted(articles, key=attrgetter("timestamp"))
    
        def execute(self):
            for article in self.articles:
                sleep(max(article.timestamp - time(), 0))
                article.post()
    
    if __name__ == "__main__":
    
        now = time()
    
        Scheduler(
            Article(now + 7, "post3"),
            Article(now + 2, "post1"),
            Article(now + 3, "post2"),
        ).execute()
    Ответ написан
    4 комментария
  • Как инвертировать словарь без использования дополнительной памяти?

    adugin
    @adugin Автор вопроса, куратор тега Python
    Пока додумался до такого метода:
    xcache = dict()
    while cache:
        	key, val = cache.iteritems().next()
        	xcache[cache.pop(key)] = key
    Такой способ в 3 раза величивает время исполнения скрипта (с 60 до 180 секунд на моём ноутбуке) по сравнению с традиционным методом инвертирования "в лоб". Есть ли способ лучше?

    Update #1: Тоже тормозит.
    xcache = dict()
    cpop = cache.pop
    while cache:
        key = cache.iterkeys().next()
        xcache[cpop(key)] = key
    del cache

    Update #2: Вот так скорость вернулась на значение 60 секунд. Что ещё?
    xcache = dict()
    cpop = cache.popitem
    while cache:
        key, val = cpop()
        xcache[val] = key
    del cache
    Ответ написан
    Комментировать
  • Как отправить смайлики за минимальное количество операций?

    adugin
    @adugin Куратор тега Python
    Код на Python для расчёта "в лоб" (перебором) и выявления закономерностей:
    # -*- coding: utf-8 -*-
    
    import matplotlib.pyplot as plt
    from itertools import product
    
    def process(existing, required):
        for opcount in xrange(existing+required):
            for combo in product('dcv', repeat=opcount):
                buffer = 0
                smiles = existing
                data_y = [existing]
                for char in combo:
                    if char == 'd':
                        smiles -= 1
                    elif char == 'v':
                        smiles += buffer
                    else:
                        buffer = smiles
                    data_y.append(smiles)
                if smiles == required:
                    data_x = xrange(opcount+1)
                    plt.plot(data_x, data_y, linewidth=1)
                    print required, data_y
                    return ''.join(combo)
        return '-'
    
    for required in xrange(2, 101):
        plt.clf()
        plt.grid(True)
        plt.title('Target: %s' % required)
        plt.autoscale(enable=True, axis='both', tight=False)
        for existing in xrange(1, (required//2)+1):
            result = process(existing, required)
        plt.savefig('{:02d}.png'.format(required), dpi=96, bbox_inches='tight')

    Задача распадается на 2:
    1) Если M >= N div 2, то нужно удалить всё до половины, скопипастить, и по необходимости удалить 1 смайл.
    2) Если п.1 не выполняется, то нужно рассчитать делители N (если N простое - то взять следующие несколько чисел больше N) и спуститься к ближайшему наибольшему делителю N, который меньше M. Удалять смайлы, чтобы попадать в наблюдаемые на картинках горизонтальные уровни, соответствующие делителям.

    В общем случае решение не единственное - например, соседние группы D и V можно смешивать в любых последовательностях: DDVVV = VVVDD = VDVDV = ...

    N=12. Для M=5 видим DCVV (фиолетовая линия). Уровни (делители) - 6, 4, 3, 2, 1:
    042d326f2b1a45d2916c5ce012fca2f6.png
    N=28:
    c832673197de486aa072d81b56de27c4.png
    N=29:
    4e0ee3d81d9b47e38127cf8211c2c48f.png
    N=30:
    2629d000169449c1896414c348b61874.png
    N=71:
    5037b1d5028b4330aed51516ec81887f.png
    N=72:
    89fd833e066f423993665d4c54e8f6cc.png
    PDF со всеми картинками: dugin.org/dropbox/toster_188303.pdf (11 Mb)

    P.S. https://ru.wikipedia.org/wiki/Задача_о_ранце
    Ответ написан
    Комментировать
  • Как найти повторяющееся слово в строке?

    adugin
    @adugin Куратор тега Python
    def find_word(line):
        for step in xrange(1, len(line)):
            for start in xrange(step):
                if len(set(line[(start or None)::step])) != 1:
                    break
            else:
                return line[:step]
        return line
    
    print find_word('HELLOHELLOHELLOHEL')
    print find_word('HHHELLOHHHELLOHHHELLOHHH')
    print find_word('_HHELLOHHELLOHHELLOHHELLOHHELLOHHE')

    Результат:
    HELLO
    HHHELLO
    _HHELLOHHELLOHHELLOHHELLOHHELLOHHE
    Ответ написан
    Комментировать
  • Балансировка нагрузки: как разбить набор чисел на две части с примерно равными суммами?

    adugin
    @adugin Автор вопроса
    В итоге я сделал полный перебор с исключением заведомо неоптимальных решений. Судя по википедии, это "Метод ветвей и границ". По моим наблюдениям, в зависимости от исходных данных, обсчёт набора из 25 чисел может занять от всего ~20 и вплоть до 3.5М циклов. На Python 2.7:

    # -*- coding: utf-8 -*-
    
    from random import randint
    from itertools import combinations
    
    #data = [53, 50, 74, 4, 11, 68, 65, 50, 25, 84, 65, 63, 14, 54, 49, 17, 65, 48, 74, 66]
    data = [randint(1,100) for i in xrange(25)]
    #data = [990,1,2,3,1000]
    
    data.sort(reverse=True)
    limit = float(sum(data))/2
    # Pre-calculate min and max possible number of elements in a group
    bounds = [0, 0]
    for i in (0,1):
        maxsum = 0
        for n, item in enumerate(data[::(1,-1)[i]], 1):
            cursum = maxsum + item
            if cursum <= limit:
                maxsum = cursum
            else:
                bounds[i] = n - int(n > 1)
                break
    nmin, nmax = bounds
    # Main calculations
    maxsum, cycles = 0, 0
    for n in xrange(nmin, nmax+1):
        # The following check could be efficient with integer numbers, not float
        if maxsum == limit:
            # One of exact solutions has been found
            break
        else:
            # Iterate through all possible combinations:
            # combinations('ABCD', 2) --> AB AC AD BC BD CD
            for vector in combinations(data, n):
                cycles += 1
                cursum = sum(vector)
                if maxsum < cursum <= limit:
                    maxsum = cursum
                    solution = vector
                    # The following check could be efficient with integer numbers, not float
                    if maxsum == limit:
                        # One of exact solutions has been found
                        break
                elif cursum <= maxsum:
                    # No reason to continue because data is sorted in descending order 
                    # and all of the following sums in this loop will be even smaller
                    break
    # Print result
    print 'data =', data
    print 'nmin =', nmin
    print 'nmax =', nmax
    print 'solution =', solution
    print 'cycles =', cycles
    print 'limit =', limit
    print 'sum =', maxsum
    Ответ написан
    Комментировать