Xbgdvs

from itertools import product
import heapq
import math
import random
import sys

def smooth(t):
    return t * t * (3. - 2. *t)

def lerp(t, x, y):
    return x + t * (y - x)

class PerlinNoise(object):
    def __init__(self, dimension, octaves=1, tile=(), unbias=False):
        self.dimension = dimension
        self.octaves = octaves
        self.tile = tile + (0,) * dimension
        self.unbias = unbias
        self.scale_factor = 2 * dimension ** -0.5
        self.gradient = {}

    def _generate_gradient(self):
        if self.dimension == 1:
            return (random.uniform(1, -1),)
        random_point = [random.gauss(0, 1) for _ in range(self.dimension)]
        scale = sum(n * n for n in random_point) ** -0.5
        return tuple(coord * scale for coord in random_point)


    def get_plain_noise(self, *point):
        if len(point) != self.dimension:
            raise ValueError("Expected {} values, got {}".format(self.dimension, len(point)))
            print()

        grid_coords = []
        for coord in point:
            min_coord = math.floor(coord)
            max_coord = min_coord + 1
            grid_coords.append((min_coord, max_coord))

        dots = []
        for grid_point in product(*grid_coords):
            if grid_point not in self.gradient:
                self.gradient[grid_point] = self._generate_gradient()
            gradient = self.gradient[grid_point]
            dot = 0
            for i in range(self.dimension):
                #print(gradient)
                dot += gradient[i] * (point[i] - grid_point[i])
            dots.append(dot)

        dim = self.dimension
        while len(dots) > 1:
            dim -= 1
            s = smooth(point[dim] - grid_coords[dim][0])
            next_dots = []
            while dots:
                next_dots.append(lerp(s, dots.pop(0), dots.pop(0)))

            dots = next_dots
        return dots[0] * self.scale_factor

    def __call__(self, *point):
        ret = 0
        for o in range(self.octaves):
            o2 = 1<< o
            new_point = []
            #print(*point)
            for i, coord in enumerate(point):
                coord *= o2
                if self.tile[i]:
                    coord %= self.tile[i] * o2
                new_point.append(coord)
                #print(new_point)
            ret += self.get_plain_noise(*new_point) / o2
        ret /= 2 - 2**(1 - self.octaves)
        if self.unbias:
            r = (ret + 1) / 2
            for _ in range(int(self.octaves / 2 + 0.5)):
                r = smooth(r)
            ret = r * 2 - 1
        return ret

class Vertex:
	def __init__(self, node):
		self.id = node
		self.adjecent = {}
		self.distance = int(sys.maxsize - 1)
		self.visited = False
		self.previous = None

	def add_neighbor(self, neighbor, weight=0):
		self.adjecent[neighbor] = weight

	def get_connections(self):
		return self.adjecent.keys()

	def get_id(self):
		return self.id

	def get_weight(self, neighbor):
		return self.adjecent[neighbor]

	def set_distance(self, dist):
		self.distance = dist

	def get_distance(self):
		return self.distance

	def set_previous(self, prev):
		self.previous = prev

	def set_visited(self):
		self.visited = True

	def __str__(self):
		return str(self.id) + " adjecent: " + str([x.id for x in self.adjacent])

class Graph:
	def __init__(self):
		self.vert_dict = {}
		self.num_vertices = 0

	def __iter__(self):
		return iter(self.vert_dict.values())

	def add_vertex(self, node):
		self.num_vertices = self.num_vertices + 1
		new_vertex = Vertex(node)
		self.vert_dict[node] = new_vertex
		return new_vertex

	def get_vertex(self, n):
		for n in self.vert_dict:
			return self.vert_dict[n]
		else:
			return None

	def add_edge(self, frm, to, cost = 0):
		if frm not in self.vert_dict:
			self.add_vertex(frm)
		if to not in self.vert_dict:
			self.add_vertex(to)

		self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
		self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

	def get_vertices(self):
		return self.vert_dict.keys()

	def set_previous(self, current):
		self.previous = current

	def get_previous(self, current):
		return self.previous


def shortest(v, path):
	if v.previous:
		path.append(v.previous.get_id())
		shortest(v.previous, path)
	return

def dijkstra(aGraph, start, target):
	start.set_distance(0)
	unvisited_queue = [(v.get_distance(), v) for v in aGraph]
	heapq.heapify(unvisited_queue)
	while len(unvisited_queue):
		uv = heapq.heappop(unvisited_queue)
		current = uv[1]
		current.set_visited()

		for next in current.adjecent:
			if next.visited:
				continue
			new_dist = current.get_distance() + current.get_weight(next)

			if new_dist > next.get_distance():
				next.set_distance(new_dist)
				next.set_previous(current)
				print('updated : current = %s next = %s new_dist = %s' %(current.get_id(), next.get_id(), next.get_distance()))
			else:
				print('not updated : current = %s next = %s new_dist = %s' %(current.get_id(), next.get_id(), next.get_distance()))

		while len(unvisited_queue):
			heapq.heappop(unvisited_queue)

		unvisited_queue = [(v.get_distance(), v) for v in aGraph if not v.visited]
		heapq.heapify(unvisited_queue)

arraySize = int(input("Size: "))
frameSize = 2
PNFactory = PerlinNoise(frameSize)
array = []
for i in range(arraySize):
    array.append([])
    for j in range(arraySize):
        array[i].append([])
for i in range(arraySize):
    for j in range(arraySize):
        array[i][j] = PNFactory(i/frameSize+ 0.6, j/frameSize + 0.6)
playerSpawn = int(arraySize/2)
array[playerSpawn][playerSpawn] = 100
array[arraySize - 1][arraySize - 1] = 101
for i in range(len(array)):
	for j in range(len(array[i])):
		if array[i][j] == 101:
			print("E ", end="")
		elif array[i][j] == 100:
			print("P ", end="")
		elif array[i][j] > 0:
			print(1, " ", sep="", end="")
		else:
			print(0, " ",sep="", end="")
	print()
#TEST CODE
for i in range(3): print()
print("MaxInteger:", sys.maxsize)
print()
g = Graph()
g.add_vertex("a")
g.add_vertex("b")
g.add_vertex("c")
g.add_vertex("d")
g.add_vertex("e")
g.add_vertex("f")
g.add_edge('a', 'b', 7)
g.add_edge('a', 'c', 9)
g.add_edge('a', 'f', 14)
g.add_edge('b', 'c', 10)
g.add_edge('b', 'd', 15)
g.add_edge('c', 'd', 11)
g.add_edge('c', 'f', 2)
g.add_edge('d', 'e', 6)
g.add_edge('e', 'f', 9)

print("Graph data:")
for v in g:
	for w in v.get_connections():
		vid = v.get_id()
		wid = w.get_id()
		print("(%s, %s, %3d)" % (vid, wid, v.get_weight(w)))
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))

target = g.get_vertex("e")
path = [target.get_id()]

shortest(target, path)

print('The shortest path : %s' %(path[::-1]))