Skip to content

Instantly share code, notes, and snippets.

@jamis
Created August 4, 2015 22:25
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jamis/195cf7a4749922a192a9 to your computer and use it in GitHub Desktop.
A program for solving Sam Lloyd's "Back from the Klondike" puzzle.
__________xxx__________
_______xxx477xxx_______
_____xx544833463xx_____
____x1451114517135x____
___x494967555876685x___
__x37298356739187585x__
__x14784292711822763x__
_x7218553113133428613x_
_x4267252422543281773x_
_x4165111914344319827x_
x435232232425351135537x
x271511315332423775427x
x252261244634121265188x
_x4375193445294195748x_
_x4167834341312323624x_
_x7326153923215758954x_
__x16734811121228941x__
__x25478756135787293x__
___x656467252263474x___
____x2312333213211x____
_____xx744573447xx_____
_______xxx334xxx_______
__________xxx__________
# A class that solves puzzles in the style of Sam Lloyd's
# "Back From the Klondike" puzzle.
#
# (see https://en.wikipedia.org/wiki/Back_from_the_Klondike)
#
# This solver works in two steps:
#
# 1. Convert the puzzle into a graph.
# 2. Apply Dijkstra's algorithm to the graph to find the
# shortest solution.
class Node
attr_reader :row, :col
attr_accessor :distance
attr_accessor :previous_dir
attr_accessor :previous_node
def initialize(row, col)
@neighbors = {}
@row, @col = row, col
@goal = false
@distance = 1_000_000_000
end
def [](direction)
@neighbors[direction]
end
def []=(direction, neighbor)
@neighbors[direction] = neighbor
end
def goal?
@goal
end
def goal!
@goal = true
end
end
class Graph
def self.from_field(field)
graph = new
field.each do |value, row, col|
next unless value
node = Node.new(row, col)
graph.add_node(node)
end
graph.each do |node|
row, col = node.row, node.col
if field[row, col] == :goal
node.goal!
else
distance = field[row, col]
if field.valid_span?(row, col, row-distance, col)
node[:n] = graph[row-distance, col]
end
if field.valid_span?(row, col, row-distance, col-distance)
node[:nw] = graph[row-distance, col-distance]
end
if field.valid_span?(row, col, row-distance, col+distance)
node[:ne] = graph[row-distance, col+distance]
end
if field.valid_span?(row, col, row+distance, col)
node[:s] = graph[row+distance, col]
end
if field.valid_span?(row, col, row+distance, col-distance)
node[:sw] = graph[row+distance, col-distance]
end
if field.valid_span?(row, col, row+distance, col+distance)
node[:se] = graph[row+distance, col+distance]
end
if field.valid_span?(row, col, row, col-distance)
node[:w] = graph[row, col-distance]
end
if field.valid_span?(row, col, row, col+distance)
node[:e] = graph[row, col+distance]
end
end
end
graph
end
def initialize
@nodes = {}
end
def add_node(node)
@nodes[node.row] ||= {}
@nodes[node.row][node.col] = node
end
def [](row, col)
@nodes[row][col]
end
def each
@nodes.each do |row, rows|
rows.each do |col, node|
yield node
end
end
self
end
end
class Field
def self.from_file(filename)
lines = File.readlines(filename)
lines.map! { |line| line.chomp }
lengths = lines.map { |l| l.length }.uniq
rows = lines.length
cols = lengths.first
new(rows, cols).tap do |field|
lines.each_with_index do |line, row|
line.each_char.with_index do |character, col|
# Assign each location in the field, based on
# the corresponding character in the file.
field[row, col] = case character
when "_" then nil
when "x" then :goal
when /[1-9]/ then character.to_i
else raise "invalid (#{character.inspect})"
end
end
end
end
end
attr_reader :rows, :columns
def initialize(rows, columns)
@rows, @columns = rows, columns
@field = Array.new(rows) { Array.new(columns) }
end
def [](row, col)
@field[row][col]
end
def []=(row, col, value)
@field[row][col] = value
end
def each
@field.each_with_index do |row, row_idx|
row.each_with_index do |col, col_idx|
yield col, row_idx, col_idx
end
end
self
end
def valid_span?(row, col, to_row, to_col)
drow = _delta(to_row - row)
dcol = _delta(to_col - col)
while row != to_row || col != to_col
return false if row < 0 || row >= rows
return false if col < 0 || col >= columns
return false if self[row, col].nil?
return false if self[row, col] == :goal
row += drow
col += dcol
end
row >= 0 && row < rows &&
col >= 0 && col <= columns &&
self[row, col]
end
def _delta(value)
return 0 if value.zero?
(value < 0) ? -1 : 1
end
end
class Solution
attr_reader :graph
attr_reader :goal
attr_reader :root
def initialize(field, start_row, start_column)
@graph = Graph.from_field(field)
@root = @graph[start_row, start_column]
_compute_solution
end
def path
path = []
node = @goal
while node != root
path.unshift node.previous_dir
node = node.previous_node
end
path
end
def _compute_solution
root.distance = 0
frontier = [ root ]
while frontier.any?
new_frontier = []
frontier.each do |node|
%i(n s e w nw ne sw se).each do |dir|
next unless node[dir]
if node[dir].distance > node.distance+1
node[dir].distance = node.distance + 1
node[dir].previous_dir = dir
node[dir].previous_node = node
if node[dir].goal?
if @goal.nil? || @goal.distance > node[dir].distance
@goal = node[dir]
end
else
new_frontier << node[dir]
end
end
end
end
frontier = new_frontier
end
end
end
field = Field.from_file(ARGV.first || "grid.txt")
solution = Solution.new(field, field.rows/2, field.columns/2)
solution.path.each do |step|
puts " - #{step}"
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment