Class: SlidingPuzzle::Oracle

Inherits:
Object
  • Object
show all
Defined in:
lib/sliding_puzzle/oracle.rb

Constant Summary collapse

OPPOSITES = 
{
  left: :right,
  right: :left,
  up: :down,
  down: :up,
}

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(lookup_table) ⇒ Oracle

Returns a new instance of Oracle.



72
73
74
 
# File 'lib/sliding_puzzle/oracle.rb', line 72

def initialize(lookup_table)
  self.lookup_table = lookup_table
end

Class Method Details

.basename(puzzle) ⇒ Object 



68
69
70
 
# File 'lib/sliding_puzzle/oracle.rb', line 68

def self.basename(puzzle)
  puzzle.tiles.map { |row| row.join(",") }.join(":")
end

.lookup(goal_state) ⇒ Object 



61
62
63
64
65
66
 
# 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

.precompute(goal_state, debug: false) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# 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) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# 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) ⇒ Object 



98
99
100
101
102
103
 
# 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

Instance Method Details

#solve(sliding_puzzle) ⇒ Object 



76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# 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) ⇒ Object 



91
92
93
94
95
96
 
# 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