Andrey Dugin

Код на 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:

N=28:

N=29:

N=30:

N=71:

N=72:

PDF со всеми картинками: dugin.org/dropbox/toster_188303.pdf (11 Mb)

P.S. https://ru.wikipedia.org/wiki/Задача_о_ранце

Решил поизвращаться с функциональным подходом :)

>>> a
["['9', '8', '7', '4']", "['9', '8', '7', '5']", "['9', '8', '7', '6']"]

>>> map(int, map(''.join, map(eval, a)))
[9874, 9875, 9876]

>>> reduce(lambda item, func: map(func, item), (eval, ''.join, int), a)
[9874, 9875, 9876]

>>> eval(','.join(a).translate(None,",' ").replace('][',','))
[9874, 9875, 9876]

>>> from itertools import starmap
>>> map(int, starmap(('{}'*4).format, map(eval, a)))
[9874, 9875, 9876]

>>> import re
>>> eval(re.sub("', '|['\[\]]", '', ','.join(a)))
(9874, 9875, 9876)

>>> map(lambda x: int(re.sub('[^\d]', '', x)), a)
[9874, 9875, 9876]

>>> repl = partial(re.sub, '[^\d]', '')
>>> map(lambda x: int(repl(x)), a)
[9874, 9875, 9876]

>>> reduce(lambda item, func: map(func, item), (repl, int), a)
[9874, 9875, 9876]

>>> reduce(lambda *args: map(*args[::-1]), (repl, int), a)
[9874, 9875, 9876]

>>> reduce(lambda *args: map(*args[::-1]), (eval, ''.join, int), a)
[9874, 9875, 9876]

>>> func = lambda item: int(''.join(char for char in item if char in digits))
>>> map(func, a)
[9874, 9875, 9876]

>>> from textwrap import wrap
>>> map(int, wrap(re.sub('[^\d]', '', str(a)), 4))
[9874, 9875, 9876]

>>> d = set(digits)
>>> fltr = partial(filter, d.issuperset)
>>> map(int, map(fltr, a))
[9874, 9875, 9876]

>>> map(int, re.findall('\d{4}', re.sub('[^\d]', '', str(a))))
[9874, 9875, 9876]

>>> dx = 2
>>> dy = 3
>>> matrix = [[0 for x in xrange(dx)] for y in xrange(dy)]
>>> matrix
[[0, 0], [0, 0], [0, 0]]
>>> matrix[0][0] = 1
>>> matrix
[[1, 0], [0, 0], [0, 0]]

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

Руки надо отрывать за такой говнокод на питоне...
Вот как надо:

data = '[{0}000,{1},{2}],'.format(str(r[i])[:-2], e[i], c[i])
f.write(data)

Что за шаманство с r[i], какого типа эта переменная? Тоже через .format() прогнать.
И что-то мне подсказывает, что здесь хорошо пойдёт json.dumps()

И ответ на сам вопрос:

>>> x = None
>>> x or 0
0

from itertools import izip
...

data = izip(r, e, c)
for trio in data:
    if all(trio):
        entry = '[{:.0f}000,{},{}],'.format(*trio)
        f.write(entry)

from itertools import izip, ifilter
...

for triplet in ifilter(all, izip(r, e, c)):
    entry = '[{:.0f}000,{},{}],'.format(*triplet)
    f.write(entry)

# -*- coding: utf-8 -*-

from difflib import SequenceMatcher
from itertools import combinations, imap

def ratio(pair):
    return (SequenceMatcher(None, *pair).ratio(), pair[0])

def findword(wordlist):
    pairs = combinations(wordlist, 2)
    found = max(imap(ratio, pairs))[1] 
    return found

print findword(['голубец', 'конь', 'голубцы', 'лист'])
print findword(['стол', 'день', 'свет', 'клинок', 'светильник'])
print findword(['восток', 'дань', 'исток', 'жир', 'голубь', 'да'])

Результат:

голубец
свет
восток

Родил такое решение:

def tree(levels=0, func=None):
	if levels > 0 and func:
		return defaultdict(reduce(lambda f, i: lambda: defaultdict(f), xrange(levels-1), func))
	else:
		return defaultdict(tree)

Проверяем:

>>> d = tree()
>>> d[1][2][3][4][5] = 6
>>> d = tree(3, float)
>>> d
defaultdict(<function <lambda> at 0x0280E3F0>, {})
>>> d[1][2][3]
0.0
>>> d[7][8][9] += 10
>>> d[7][8][9]
10.0

P.S. https://gist.github.com/hrldcpr/2012250

P.P.S. Ещё вариант:

def tree(func=lambda: tree(), depth=0):
	return defaultdict(reduce(lambda f, i: lambda: defaultdict(f), xrange(depth-1), func))

В итоге я сделал полный перебор с исключением заведомо неоптимальных решений. Судя по википедии, это "Метод ветвей и границ". По моим наблюдениям, в зависимости от исходных данных, обсчёт набора из 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

# -*- coding: utf-8 -*-
import re

text = u"""Вася - 10
Ваня - 20
Петя - 30"""

d = dict(re.findall(u"^(.+?) - (\d+?)$", text, flags=re.M|re.U))

print d

Если нужен именно список словарей - то, например, так:

p = re.compile(u"^(?P<name>.+?) - (?P<value>\d+?)$", flags=re.M|re.U)
d = [match.groupdict() for match in p.finditer(text)]

Перехватить трафик на сетевом интерфейсе с помощью tcpdump/tethereal/wireshark

tethereal -i eth01 -f 'tcp port 21'
tcpdump -i eth01 -f 'tcp port 21'