class FifteenPuzzleSolver::Board
Attributes
height[R]
width[R]
Public Class Methods
new(blocks, width, height)
click to toggle source
# File lib/fifteen_puzzle_solver/board.rb, line 6 def initialize(blocks, width, height) @blocks = blocks @width = width @height = height end
Public Instance Methods
at_position(x, y)
click to toggle source
Get element value at position
# File lib/fifteen_puzzle_solver/board.rb, line 18 def at_position(x, y) index = get_index(x, y) return nil if index < 0 @blocks[index] end
difference()
click to toggle source
Return difference between blocks and valid system
# File lib/fifteen_puzzle_solver/board.rb, line 98 def difference difference = 0 valid_system = [*1...(@width * @height)] @blocks.each_with_index do |block, index| next if block == 0 difference += 1 unless block == valid_system[index] end difference end
display()
click to toggle source
Display board in output
# File lib/fifteen_puzzle_solver/board.rb, line 72 def display output = "" @width.times do |y| @height.times do |x| output << at_position(x, y).to_s.center(5) end output << "\n" end output end
get_position(value)
click to toggle source
Get element position with specified value
# File lib/fifteen_puzzle_solver/board.rb, line 26 def get_position(value) { x: @blocks.index(value) % @width, y: @blocks.index(value) / @height, } end
invalid_blocks_distance()
click to toggle source
Return invalid blocks distance
# File lib/fifteen_puzzle_solver/board.rb, line 84 def invalid_blocks_distance distance = 0 iterator = 1 @blocks.each do |block| if block != iterator && block != 0 distance += distance(block) end iterator += 1 end distance end
move(direction)
click to toggle source
Move zero-value element
# File lib/fifteen_puzzle_solver/board.rb, line 34 def move(direction) delta = direction_delta(direction) move_element(delta[:dx], delta[:dy]) end
neighbors(parent, order)
click to toggle source
Return neighbors for board element
# File lib/fifteen_puzzle_solver/board.rb, line 53 def neighbors(parent, order) unless !!(/^[udlr]+$/is =~ order) raise Exception.new("Invalid order (only up, down, left or right)") end neighbors = [] position = get_position(0) order.each_char do |direction| delta = direction_delta(direction) if can_move?(position[:x], position[:y], delta[:dx], delta[:dy]) board = FifteenPuzzleSolver::Board.new(@blocks.dup, @width, @height) board.move(direction) neighbors << FifteenPuzzleSolver::Node.new(parent, board, direction) end end neighbors end
state()
click to toggle source
Get unique identifier
# File lib/fifteen_puzzle_solver/board.rb, line 13 def state @blocks.join end
valid?()
click to toggle source
Check if the board is valid
# File lib/fifteen_puzzle_solver/board.rb, line 40 def valid? return false unless @blocks.last == 0 iterator = 1 @blocks.each do |block| return false if block != iterator && block != 0 iterator += 1 end true end
Private Instance Methods
can_move?(x, y, dx, dy)
click to toggle source
Check range exceeding
# File lib/fifteen_puzzle_solver/board.rb, line 137 def can_move?(x, y, dx, dy) x + dx >= 0 && y + dy >= 0 && x + dx < @width && y + dy < @height end
direction_delta(direction)
click to toggle source
Translate direction to delta
# File lib/fifteen_puzzle_solver/board.rb, line 116 def direction_delta(direction) case direction when "u", "U", "up" return { dx: 0, dy: -1 } when "d", "D", "down" return { dx: 0, dy: 1 } when "l", "L", "left" return { dx: -1, dy: 0 } when "r", "R", "right" return { dx: 1, dy: 0 } else raise Exception.new("Invalid direction (only up, down, left or right)") end end
distance(value)
click to toggle source
Return distance between two blocks
# File lib/fifteen_puzzle_solver/board.rb, line 163 def distance(value) block1 = get_position(value) block2 = valid_position_for(value) (block1[:x] - block2[:x]).abs + (block1[:y] - block2[:y]).abs end
get_index(x, y)
click to toggle source
Get index by position
# File lib/fifteen_puzzle_solver/board.rb, line 132 def get_index(x, y) @height * y + x end
move_element(dx, dy)
click to toggle source
Move element by x and y difference
# File lib/fifteen_puzzle_solver/board.rb, line 142 def move_element(dx, dy) position = get_position(0) element_index = get_index(position[:x] + dx, position[:y] + dy) if element_index >= 0 && can_move?(position[:x], position[:y], dx, dy) zero_index = get_index(position[:x], position[:y]) @blocks[zero_index], @blocks[element_index] = @blocks[element_index], @blocks[zero_index] end end
update_state()
click to toggle source
Update state
# File lib/fifteen_puzzle_solver/board.rb, line 111 def update_state @state = @blocks.join end
valid_position_for(value)
click to toggle source
Return valid position for value
# File lib/fifteen_puzzle_solver/board.rb, line 153 def valid_position_for(value) return { x: @width - 1, y: @height - 1 } if value == 0 { x: (value - 1) % @width, y: (value - 1) / @height, } end