life.py

# -*- mode: python; coding: utf-8; -*-

# (def nbr-deltas [[-1 -1][-1 0][-1 1][0 -1][0 1][1 -1][1 0][1 1]])
# (defn nbr-cells [[x y]] (map (fn [[a b]] [(+ x a)(+ y b)]) nbr-deltas))
# (defn cell-table [cell] (apply conj {cell 10} (map #(vec [% 1]) (nbr-cells cell))))
# (defn all-table [cells] (apply merge-with + (map cell-table cells)))
# (defn next-gen [cells] (keys (filter #(#{3 12 13} (second %)) (all-table cells))))
# (defn n-next-gen [n cells] (if (== n 0) cells (recur (- n 1) (next-gen cells))))
# (def r-pentomino [[0 1][1 1][2 1][1 2][2 0]])

def merge_with(f, maps):
    result = {}
    for map in maps:
        for key, val in map.iteritems():
            if key in result:
                result[key] = f(result[key], val)
            else:
                result[key] = val
    return result

nbr_deltas = (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)
nbr_cells = lambda c: [(c[0] + d[0], c[1] + d[1]) for d in nbr_deltas]
cell_table = lambda cell: dict((c, v) for c, v in [(cell, 10)] + [(nbr, 1) for nbr in nbr_cells(cell)])
merge_with_plus = lambda maps: merge_with(lambda x,y: x+y, maps)
all_table = lambda cells: merge_with_plus(cell_table(cell) for cell in cells)
next_gen = lambda cells: [cell for cell, val in all_table(cells).iteritems() if val in (3, 12, 13)]

def nnext_gen(cells, n):
    gen = cells
    for i in range(0, n):
        gen = next_gen(gen)
    return gen

r_pentamino = (0, 1), (1, 1), (2, 1), (1, 2), (2, 0)

# Ура! Все работает. Расчет занял 12 секунд на МacBook Pro (2.53 GHz
# Intel Core 2 Duo, 4GB RAM), то есть около 100 поколений в секунду.
# (count (n-next-gen 1103 r-pentomino)) 116

# Расчет занял 12 секунд на безымянном нетбуке Российской сборки, Atom N450 1.4, 2G RAM
print len(nnext_gen(r_pentamino, 1103))
# 116

Вместо

if cell not in big_table:
    big_table[cell] = val
else:
    big_table[cell] += val

можно сделать так:

big_table[cell] = val + big_table.get(cell, 0)

Мне это очень не нравится. Очень. Поведение get неявное.

        big_table[cell] = (big_table[cell] if cell in big_table else 0) + val

Если основным критерием является прозрачность кода, то соглашусь, оригинал вне конкуренции (а в третьем варианте три поиска по словарю вместо двух).

На Core2Duo 1.8 GHz, кстати, считалось чуть меньше четырёх с половиной секунд.

Как ни странно, но мой вариант работает быстрее, чем твой c get.

А что странного? Тратится время на вызов и исполнение функции.
Совсем немного, правда.

В конце концов читаемость всегда превыше.