Есть ли более сжатый /pythonic способ сделать это? (считая самый длинный ряд головок, хвостов в переворотах монет)

Ответ 1

def coins(num):
    lst = [random.randrange(2) for i in range(num)]
    lst = [(i, len(list(j))) for i, j in itertools.groupby(lst)]
    tails = max(j for i, j in lst if i)
    heads = max(j for i, j in lst if not i)
    return {1: tails, 0: heads}

Ответ 2

import collections, itertools, random

def makesequence(choices=2, length=200):
  return [random.randrange(choices) for _ in itertools.repeat(None, length)]

def runlengths(sequence):
  runlength_by_item = collections.defaultdict(set)
  for key, group in itertools.groupby(sequence):
    runlength_by_item[key].add(sum(1 for _ in group))
  return dict((k, max(v)) for k, v in runlength_by_item.items())

Как вы заметили, это гораздо более "развязано" - runlengths - это полностью общий способ определения максимальной длины выполнения различных хешируемых элементов в любом итерабельном (очень многократно используемом, если вам нужны такие длины выполнения в разных контекстах), так же, как makesequence - это полностью общий способ составить список случайных чисел, заданных длиной списка и количеством вариантов для каждого случайного числа. Помещение этих двух вместе может не дать оптимального решения точки для данной, весьма специфической проблемы, но она приблизится, и создание вашей маленькой библиотеки многоразовых "строительных блоков" будет иметь гораздо более высокую долгосрочную отдачу, чем просто решение каждой специфическая проблема с помощью полностью выделенного кода.

Ответ 3

Вы можете использовать itertools, что намного более возможно для Pythonic:

def toss(n):
    rolls = [random.randrange(2) for i in xrange(n)]
    maximums = [0, 0]
    for which, grp in itertools.groupby(rolls):
        maximums[which] = max(len(list(grp)), maximums[which])

    print "Longest sequence of heads %d, tails %d" % tuple(maximums)

Ответ 4

Другое неэффективное решение: -)

import random, re
s = ''.join(str(random.randrange(2)) for c in range(10))
print s
print max(re.findall(r'0+', s))
print max(re.findall(r'1+', s))

>>> 
0011100100
00
111
>>> 

Ответ 5

>>> def toss(count):
        result = []
        for i in range(count):
            result.append("HT"[random.randrange(0, 2)])
        return ''.join(result)

>>> s = toss(200)
>>> h_max = max(len(x) for x in s.split("T"))
>>> t_max = max(len(x) for x in s.split("H"))
>>> print h_max, t_max
4 6

Ответ 6

На самом деле это не очень pythonic, как пытка, но здесь короткая версия (с бессмысленными 1-символьными именами переменных, не менее!)

import random
x = ''.join([chr(random.randrange(2)) for i in range(200)])
print max([len(s) for s in x.split(chr(0)) + x.split(chr(1))])

Ответ 7

Вероятно, это аксиома, что любой код можно сделать более кратким. Тем не менее, вы выглядите прекрасно pythonic.

Собственно, по размышлению, возможно, нет такой аксиомы лаконичности. Если succinct означает "помечен компактным точным выражением без потерь впустую", а если под словами "слова" мы подразумеваем слова кода, а не слова памяти, то одно слово-программа не может быть более сжатой (если, возможно, это не "выходная" программа).

Если pythonic означает "необычайного размера и мощности", то это кажется антагонистичным для лаконичности, если мы не ограничим наше определение только силой, Я не убежден, что ваша программа вообще похожа на пророческий оракул, хотя вы можете реализовать ее как портрет аськи конкретного пророческого оракула. Это не похоже на змею, поэтому там есть место для улучшения.

import random

def toss(n):
    '''
     ___     ____________
<<<((__O\   (__<>___<>__ \   ____
       \ \_(__<>___<>__)\O\_/O___>-<  hiss
        \O__<>___<>___<>)\___/

    '''
    count = [0,0]
    longest = [0,0]
    for i in xrange(n):
        coinface = random.randrange(2)
        count[coinface] += 1
        count[not coinface] = 0

        if count[coinface] > longest[coinface]:
            longest[coinface] = count[coinface]
        #print coinface, count, longest

    print "longest sequence heads %d, tails %d" %tuple(longest)

if __name__ == '__main__':
    toss(200)

Нифти, да?

Ответ 8

import random, itertools

def toss(n):
    faces = (random.randrange(2) for i in range(n))
    longest = [0, 0]
    for face, seq in itertools.groupby(faces):
        longest[face] = max(longest[face], len(list(seq)))
    print "longest sequence heads %d, tails %d" % tuple(longest)

Ответ 9

Алгоритм сканирования строк

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

def search_longest_substring(s):
    """
    >>> search_longest_substring('AABBBBCBBBBACCDDDDDDAAABBBBCBBBBACCDDDDDDDAAABBBBCBBBBACCDDDDDDA')
    (7, 'D')
    """
    def find_left(s, midc, mid, left):
        for j in range(mid-1, left-1, -1):
            if s[j] != midc:
                return j + 1
        return left
    def find_right(s, midc, mid, right):
        for k in range(mid+1, right):
            if s[k] != midc:
                return k
        return right
    i, longest = 0, (0, '')
    while i < len(s):
        c = s[i]
        j = find_left(s, c, i, i-longest[0])
        k = find_right(s, c, i, len(s))
        if k-j > longest[0]:
            longest = (k-j, c)
        i = k + longest[0]
    return longest

if __name__ == '__main__':
    import random
    heads_or_tails = "".join(["HT"[random.randrange(0, 2)] for _ in range(20)])
    print search_longest_substring(heads_or_tails)
    print heads_or_tails

Этот алгоритм O (n) в худшем случае (все развороты монет идентичны) или O (n/m) в среднем случае (где m - длина самого длинного совпадения). Не стесняйтесь исправить меня по этому поводу.

Код не особенно питонов (т.е. он не использует списки или itertools или другие вещи). Это в python и это хороший алгоритм.

Micro-оптимизации

Для толпы микрооптимизации здесь есть изменения, которые заставляют это действительно кричать на python 2.6 на ноутбуке Windows Vista:

def find_left(s, midc, mid, left):
    j = mid - 1
    while j >= 0:
        if s[j] != midc:
            return j + 1
        j -=  1
    return left
def find_right(s, midc, mid, right):
    k = mid+1
    while k < right:
        if s[k] != midc:
            return k
        k += 1
    return right

Результаты синхронизации для 1000 итераций с помощью timeit:

range: 2.670
xrange: 0.3268
while-loop: 0.255

Добавление psyco импорта в файл:

try:
    import psyco
    psyco.full()
except ImportError:
    pass

0.011 на 1000 итераций с psyco и while-loop. Таким образом, с разумной микро-оптимизацией и импортом psyco, код работает в 250 раз быстрее.