niedziela, 13 listopada 2016

Project Euler - problem 83

Zadanie 83 jest uogólnieniem zadania 82. Rozwiązanie z zadania 82 było na tyle ogólne, że jego mała modyfikacja pozwoliła rozwiązać zadanie 83.

Rozwiązanie (od razu z kolorowaniem i  żółwikiem):

# encoding=utf-8
from heapq import heappop, heappush, heapify
import turtle
import time
f = open("p082_matrix.txt")
lines = f.readlines()
matrix = [map(int, line.strip().split(",")) for line in lines]
N = len(matrix)  # matrix is square, [0..N-1] x [0..N-1] 
queue = [(matrix[0][0], 0, 0, None)]
heapify(queue)
dist = {}
# Ustawienia malowania
turtle.hideturtle()
turtle.penup()
turtle.tracer(0, 0)
turtle.colormode(255)
def nice_colors():
  step = 7
  x = y = z = 0
  while True:
    yield x, y, z
    if x >= 170 and y >= 255 and z >= 255:
      x = y = z = 0
    elif y == 255 and z == 255:
      y = z = 0
      x = min(x + 3 * step, 255)
    elif z == 255:
      z = 0
      y = min(y + 7 * step, 255)
    else:
      z = min(z + step, 255)    
color_generator = nice_colors()
def draw(wait, (row, col), color=None):
  if not color:
    color = next(color_generator)
  time.sleep(wait)
  turtle.setpos((col * 5 - 200, row * 5 - 200))
  turtle.dot(None, *color)
  turtle.update()
# Wyliczanie odległości i malowanie grafu przeszukiwania.
parent = {}
while queue:
  cost, row, col, prev = heappop(queue)
  curr = row, col
  if curr in dist:
    continue
  parent[curr] = prev
  dist[curr] = cost
  if row == N - 1 and col == N - 1:
    break
  if col < N - 1:
    heappush(queue, (cost + matrix[row][col + 1], row, col + 1, curr))
  if col > 0:
    heappush(queue, (cost + matrix[row][col - 1], row, col - 1, curr))
  if row > 0:
    heappush(queue, (cost + matrix[row - 1][col], row - 1, col, curr))
  if row < N - 1:
    heappush(queue, (cost + matrix[row + 1][col], row + 1, col, curr))
  draw(0.001, curr)

print dist[N - 1, N - 1]

# Malowanie najlepszej ścieżki.
while curr:
  draw(0.2, curr, (255, 0, 0))
  curr = parent[curr]

turtle.exitonclick()

Wizualizacja:


Brak komentarzy :

Prześlij komentarz