Find path in a labyrinth

labyrinth.rb

#!/usr/bin/env ruby

class Coord
    attr_reader :x, :y

    def initialize x, y
        @x = x
        @y = y
    end

    def left;  offset -1,  0 end
    def right; offset +1,  0 end
    def up;    offset  0, -1 end
    def down;  offset  0, +1 end

    def eql? other
        to_a.eql? other.to_a
    end

    def hash
        to_a.hash
    end

    alias_method :==, :eql?

    def to_s
        "(#{@x}, #{@y})"
    end

    protected

    def to_a
        [@x, @y]
    end

    private

    def offset dx, dy
        Coord.new @x + dx, @y + dy
    end
end

class Labyrinth
    def initialize width, height, wall_percent = 50
        if width < 3 || height < 3
            raise "Too short/narrow"
        end

        @width = width
        @height = height

        generate wall_percent
    end

    def solve
        visited = {@start => nil}
        front = [@start]

        while !front.empty?
            cell = front.shift

            if cell == @finish
                set_cell cell, PATH while (cell = visited[cell]) != @start
                return true
            end

            [:left, :right, :up, :down].each do |direction|
                neighbour = cell.send direction
                unless wall? neighbour or visited.key? neighbour
                    visited[neighbour] = cell
                    front.push neighbour unless wall? neighbour
                end
            end
        end

        false
    end

    def to_s
        chars = {
            EMPTY  => " ",
            WALL   => "X",
            START  => "S",
            FINISH => "F",
            PATH   => "."
        }

        @cells.map { |row| row.map { |i| chars[i] }.join " " }.join "\n"
    end

    private

    EMPTY = 0
    WALL = 1
    START = 2
    FINISH = 3
    PATH = 4

    def cell c
        @cells[c.y][c.x]
    end

    def set_cell c, what
        @cells[c.y][c.x] = what
    end

    def wall? c
        cell(c) == WALL
    end

    def generate wall_percent
        @cells = [nil] * @height
        @cells[0] = [WALL] * @width
        1.upto @height - 2 do |row|
            @cells[row] = [WALL] + [0] * (@width - 2) + [WALL]
        end
        @cells[@height - 1] = [WALL] * @width

        cells = (1..@height - 2).flat_map { |y| (1..@width - 2).map { |x| Coord.new(x, y) } }.shuffle

        @start = cells.pop
        @finish = cells.pop

        (cells.size * wall_percent / 100).times do |i|
            set_cell cells[i], WALL
        end

        set_cell @start, START
        set_cell @finish, FINISH
    end
end

l = Labyrinth.new 10, 10, 40

puts "Original:"
p l

if l.solve
    puts "Solved:"
    p l
else
    puts "No solution"
end

sample-output.txt

Original:
X X X X X X X X X X
X   X X X X X F   X
X X X   X   X     X
X       X         X
X                 X
X X     X   X     X
X X       X X X   X
X   X     S X X   X
X X X       X X   X
X X X X X X X X X X
Solved:
X X X X X X X X X X
X   X X X X X F   X
X X X   X   X .   X
X       X     .   X
X     . . . . .   X
X X   . X   X     X
X X   .   X X X   X
X   X . . S X X   X
X X X       X X   X
X X X X X X X X X X