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