Project Euler - problem 82

Zadanie 82 polega na znalezieniu drogi z lewej kolumny do prawej kolumny, która będzie przechodzić po polach dających najmniejszą możliwą sumę. Zadanie można sprowadzić do poszukiwania najkrótszej ścieżki w grafie, dla odpowiednio skonstruowanego grafu (takie zadanie można już np. rozwiązać algorytmem Dijkstry).

Zastosowałem małą modyfikację tego algorytmu, ponieważ oryginalny algorytm służy do szukania najkrótszej ścieżki w grafie, w którym wagi przejść mają krawędzie. W tym zadaniu wagi mają wierzchołki, ale pomysł pozostał ten sam.

Rozwiązanie:

from heapq import heappop, heappush, heapify

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[row][0] + matrix[row][1], row, 1) for row in range(N)]
dist = {(row, 0): matrix[row][0] for row in range(N)}
heapify(queue)

while queue:
  cost, row, col = heappop(queue)
  if col == N - 1:
    print cost, row, col
    break
  if (row, col) in dist:
    continue
  dist[(row, col)] = cost
  heappush(queue, (cost + matrix[row][col + 1], row, col + 1))
  if row > 0:
    heappush(queue, (cost + matrix[row - 1][col], row - 1, col))
  if row < N - 1:
    heappush(queue, (cost + matrix[row + 1][col], row + 1, col))

Pomyślałem, że można nieco rozwinąć to rozwiązanie i spróbować je namalować. Z biblioteką turtle jest to w miarę możliwe. Oto efekty:

Dla ciekawych, kod:

# 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[row][0] + matrix[row][1], row, 1, None) for row in range(N)]
heapify(queue)
dist = {(row, 0): matrix[row][0] for row in range(N)}

# 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 col == N - 1:
    parent[curr] = prev
    break
  if curr in dist:
    continue
  parent[curr] = prev
  dist[curr] = cost
  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)

# Malowanie najlepszej ścieżki.

while curr:
  draw(0.2, curr, (255, 0, 0))
  curr = parent[curr]

turtle.exitonclick()