bertos3.py

# -*- coding: utf8 -*-
import collections
import operator
import array

# una namedtuple, scritta a mano perché dovevo aggiungere __add__ e avevo paura
# che subclassando non avrebbe funzionato qualcosa.
class Point(tuple):
    __slots__ = ()

    def __new__(cls, x, y):
        return tuple.__new__(cls, (x, y))

    def __repr__(self):
        return "Point(x=%d, y=%d)" % self

    @property
    def __dict__(self):
        return collections.OrderedDict(('x', self[0]), ('y', self[1]))

    def __getnewargs__(self):
        return tuple(self)

    def __add__(self, point):
        return tuple.__new__(Point, (self[0]+point[0], self[1]+point[1]))

    x = property(operator.itemgetter(0), doc='Alias for field number 0')
    y = property(operator.itemgetter(1), doc='Alias for field number 1')


directions = dict((Point(x, y), weight) for weight, x, y in
                ((0.2, 1, 0), (0.2, -1, 0), (0.3, 0, -1), (0.3, 0, 1)))

def dfs(MAX_DEPTH=13):

    weights = array.array('d')
    tot = [0] # trick in mancanza di nonlocal

    weights.append(1)

    def visit(path, u, depth):
        if depth == MAX_DEPTH:
            tot[0] += weights.pop()
            return

        path.add(u)
        for direction in directions:
            v = u + direction
            if v not in path:
                weights.append(weights[-1] * directions[direction])
                visit(path, v, depth+1)
        path.remove(u)
        if weights: weights.pop()

    visit(set(), Point(0, 0), 0)
    return tot[0]


# 0.0118839917111129954
# soluzione(?): 0.98811600828887

import random
import heapq


# funzione utilizzata per farmi un'idea del risultato
def test(times=1000000, depth=13):

    def simulate():
        pos = Point(0, 0)
        Q = [pos]
        for _ in xrange(depth):
            r = random.randrange(9)
            if r < 2:
                pos += Point(+1, 0)
            elif r < 4:
                pos += Point(-1, 0)
            elif r < 7:
                pos += Point(0, -1)
            else:
                pos += Point(0, +1)

            if pos in Q:
                return 0
            heapq.heappush(Q, pos)
        return 1

    return sum(simulate() for _ in xrange(times))


if __name__ == '__main__':
    print(1 - dfs())