class SlidingPuzzle::Oracle
Constants
- OPPOSITES
Attributes
lookup_table[RW]
Public Class Methods
basename(puzzle)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 68 def self.basename(puzzle) puzzle.tiles.map { |row| row.join(",") }.join(":") end
lookup(goal_state)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 61 def self.lookup(goal_state) filename = "#{basename(goal_state)}.dat" path = File.expand_path("#{__dir__}/../../oracles/#{filename}") read(path) if File.exist?(path) end
new(lookup_table)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 72 def initialize(lookup_table) self.lookup_table = lookup_table end
precompute(goal_state, debug: false)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 10 def self.precompute(goal_state, debug: false) goal_state = goal_state.clone queue = [goal_state] lookup_table = { goal_state => :goal } until queue.empty? puts "queue size: #{queue.size}" if debug puzzle = queue.shift puzzle.moves.each do |direction| next_puzzle = puzzle.slide(direction) unless lookup_table[next_puzzle] lookup_table[next_puzzle] = OPPOSITES[direction] queue.push(next_puzzle) end end end new(lookup_table) end
precompute_all(max_tiles: 8, directory: "oracles", debug: false)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 33 def self.precompute_all(max_tiles: 8, directory: "oracles", debug: false) FileUtils.mkdir_p("oracles") 1.upto(5) do |rows| 1.upto(5) do |columns| number_of_tiles = rows * columns - 1 next if number_of_tiles > max_tiles numbers = 1.upto(number_of_tiles).to_a 0.upto(number_of_tiles) do |position| numbers_with_blank = numbers.dup.insert(position, 0) tiles = numbers_with_blank.each_slice(columns).to_a goal_state = SlidingPuzzle.new(tiles) path = "#{directory}/#{basename(goal_state)}.dat" print "Precomputing #{path}... " if debug oracle = precompute(goal_state) oracle.write(path) puts "Done." if debug end end end end
read(path)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 98 def self.read(path) gzip = File.binread(path) data = Zlib::Inflate.inflate(gzip) Marshal.load(data) end
Public Instance Methods
solve(sliding_puzzle)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 76 def solve(sliding_puzzle) moves = [] next_puzzle = sliding_puzzle loop do direction = lookup_table[next_puzzle] return nil unless direction return moves if direction == :goal moves.push(direction) next_puzzle = next_puzzle.slide(direction) end end
write(path)
click to toggle source
# File lib/sliding_puzzle/oracle.rb, line 91 def write(path) data = Marshal.dump(self) gzip = Zlib::Deflate.deflate(data) File.open(path, "wb") { |f| f.write(gzip) } end