Natural computation assessment #1

task.py

#!/usr/bin/env python3

__author__ = "Maigret Aurelien"

"""
$> python3 task.py
|  pos x y  |  north  |  east  |  south  |  west  |  nomove  |  proba  |  stddev  |  probabilities
| --------- | ------- | ------ | ------- | ------ | -------- | ------- | -------- | ---------------
|  7 (0,0)  |    0    |  1/4   |   1/6   |   0    |   7/12   |  0.090  |  0.003   | 0.090 0.087 0.094 0.085 0.088 0.090 0.091 0.093
|  8 (0,1)  |    0    |  1/4   |   1/6   |  1/4   |   1/3    |  0.046  |  0.002   | 0.047 0.047 0.043 0.047 0.044 0.047 0.050 0.047
|  9 (0,2)  |    0    |   0    |   1/6   |  1/4   |   7/12   |  0.000  |  0.000   | 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
|  4 (1,0)  |   1/4   |  1/4   |   1/8   |   0    |   3/8    |  0.211  |  0.004   | 0.209 0.211 0.218 0.211 0.216 0.211 0.204 0.210
|  5 (1,1)  |   1/4   |  1/4   |   1/8   |  1/4   |   1/8    |  0.116  |  0.003   | 0.114 0.121 0.110 0.117 0.116 0.115 0.117 0.121
|  6 (1,2)  |   1/4   |   0    |   1/8   |  1/4   |   3/8    |  0.046  |  0.002   | 0.047 0.044 0.046 0.049 0.048 0.045 0.047 0.044
|  1 (2,0)  |   1/4   |  1/4   |    0    |   0    |   1/2    |  0.246  |  0.004   | 0.252 0.248 0.249 0.241 0.243 0.249 0.249 0.240
|  2 (2,1)  |   1/4   |  1/4   |    0    |  1/4   |   1/4    |  0.166  |  0.004   | 0.165 0.160 0.164 0.172 0.170 0.162 0.168 0.166
|  3 (2,2)  |   1/4   |   0    |    0    |  1/4   |   1/2    |  0.078  |  0.002   | 0.076 0.081 0.076 0.078 0.076 0.080 0.075 0.079
"""


from fractions import Fraction
import random
import math


# CONFIGURATIONS

probabilities = [
	[1.0/6.0, 1.0/6.0, 1.0/6.0],
	[1.0/9.0, 1.0/9.0, 1.0/9.0],
	[1.0/18.0, 1.0/18.0, 1.0/18.0]
]

#probabilities = [
#	[1.0/9.0, 1.0/9.0, 1.0/9.0],
#	[1.0/9.0, 1.0/9.0, 1.0/9.0],
#	[1.0/9.0, 1.0/9.0, 1.0/9.0]
#]

timestep = 3
iterations = 10000
tests = 8
precision = 3


# INITIALISATION

directions = {
	"north": lambda x, y: (x, y - 1),
	"east": lambda x, y: (x + 1, y),
	"south": lambda x, y: (x, y + 1),
	"west": lambda x, y: (x - 1, y)
}

def proba_transition(fr, to):
	if to[1] < 0 or to[1] >= len(probabilities) or to[0] < 0 or to[0] >= len(probabilities[to[1]]):
		return 0
	return 1/4 * min(1, probabilities[to[1]][to[0]] / probabilities[fr[1]][fr[0]])
square = list()
for y in range(len(probabilities)):
	square.append(list())
	for x in range(len(probabilities[y])):
		pos = x, y
		nomove = 1
		val = {"count": 0, "probabilities": list(), "probability": 0, "stddev": 0}
		for direction in directions:
			proba = proba_transition(pos, directions[direction](*pos))
			val[direction] = proba
			nomove -= proba
		val["nomove"] = nomove
		square[y].append(val)


# CALCULATION

def proba_choice(pos, case):
	proba = list()
	sum_proba = 0
	for key in ["north", "east", "south", "west", "nomove"]:
		sum_proba += case[key]
		proba.append((sum_proba, key))
	rand = random.random()
	for elem in proba:
		if rand <= elem[0]:
			if elem[1] == "nomove":
				return pos
			return directions[elem[1]](*pos)
	return pos

for t in range(tests):
	for i in range(iterations):
		pos = (0, 2)
		for p in range(timestep):
			pos = proba_choice(pos, square[pos[1]][pos[0]])
		square[pos[1]][pos[0]]["count"] += 1
	for y in range(len(square)):
		for x in range(len(square[y])):
			square[y][x]["probabilities"].append(square[y][x]["count"] / iterations)
			square[y][x]["count"] = 0

for y in range(len(square)):
	for x in range(len(square[y])):
		square[y][x]["probability"] = sum(square[y][x]["probabilities"]) / tests
		points = map(lambda val: math.pow(val - square[y][x]["probability"], 2), square[y][x]["probabilities"])
		square[y][x]["stddev"] = math.sqrt(sum(points) / tests)


# DISPLAY

print("|  pos x y  |  north  |  east  |  south  |  west  |  nomove  |  proba  |  stddev  |  probabilities")
print("| --------- | ------- | ------ | ------- | ------ | -------- | ------- | -------- | ---------------")
for y in range(len(square)):
	for x in range(len(square[y])):
		print("|  {:^1d} ({:^1d},{:^1d})  | {:^7} | {:^6} | {:^7} | {:^6} | {:^8} | {:^7} | {:^8} | {:s}".format(
			(2 - y) * 3 + x + 1,
			y,
			x,
			str(Fraction(square[y][x]["north"]).limit_denominator()),
			str(Fraction(square[y][x]["east"]).limit_denominator()),
			str(Fraction(square[y][x]["south"]).limit_denominator()),
			str(Fraction(square[y][x]["west"]).limit_denominator()),
			str(Fraction(square[y][x]["nomove"]).limit_denominator()),
			("%%.%df" % precision) % round(square[y][x]["probability"], precision),
			("%%.%df" % precision) % round(square[y][x]["stddev"], precision),
			" ".join(map(lambda val: ("%%.%df" % precision) % round(val, precision), square[y][x]["probabilities"]))
		))