Last active
August 29, 2015 14:22
-
-
Save michaelminter/d41ef547bcd5a9afafb4 to your computer and use it in GitHub Desktop.
Boggle Solver Challenge
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Board | |
attr_accessor :board | |
# Establishes new Boggle board | |
# | |
# @return [Array] an array of 4 rows containing an array of 4 columns of letters | |
def initialize | |
@board = (0..3).map{ Array.new(4){ [*'a'..'z'].sample } } | |
@words = [] | |
end | |
def solve | |
@board.each_with_index do |r,ri| | |
r.each_with_index do |c,ci| | |
letters = filter_letters(ri,ci) | |
File.new('/usr/share/dict/words', 'r').each_line do |word| | |
# @todo update regex to allow only single instance of each character in word | |
@words << word.chomp if /^[#{letters.join}]{3,}$/ =~ word.chomp | |
end | |
end | |
end | |
puts @words.uniq[0..100] | |
end | |
# Returns an array of object and adjacent letters | |
# | |
# @params [Integer] row row index | |
# @params [Integer] column column index | |
# | |
# @return [Array] possible object and adjacent letters | |
def filter_letters(row, column) | |
result = [@board[row][column]] # object letter | |
result << filter_horizontal(row, column) | |
result << filter_vertical(row, column) | |
result << filter_down_right_diagonal(row, column) | |
result << filter_down_left_diagonal(row, column) | |
result << filter_up_right_diagonal(row, column) | |
result << filter_up_left_diagonal(row, column) | |
result.flatten | |
end | |
# Returns array of letters adjacent to object row | |
def filter_horizontal(row, col) | |
result = @board[row].dup | |
result.delete_at(col) | |
result | |
end | |
# Returns array of letters adjacent to object column | |
def filter_vertical(row, col) | |
result = @board.map{|a|a[col]}.dup | |
result.delete_at(row) | |
result | |
end | |
def filter_down_right_diagonal(row, col) | |
result = [] | |
3.times do | |
row += 1 | |
col += 1 | |
result << @board[row][col] if row < 4 && col < 4 | |
end | |
result.flatten | |
end | |
def filter_down_left_diagonal(row, col) | |
result = [] | |
3.times do | |
row -= 1 | |
col += 1 | |
result << @board[row][col] if row >= 0 && col < 4 | |
end | |
result.flatten | |
end | |
def filter_up_right_diagonal(row, col) | |
result = [] | |
3.times do | |
row += 1 | |
col -= 1 | |
result << @board[row][col] if row < 4 && col >= 0 | |
end | |
result.flatten | |
end | |
def filter_up_left_diagonal(row, col) | |
result = [] | |
3.times do | |
row -= 1 | |
col -= 1 | |
result << @board[row][col] if row >= 0 && col >= 0 | |
end | |
result.flatten | |
end | |
def preview | |
@board.each do |row| | |
puts ' ' + row.join(' | ') | |
end | |
end | |
end |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
require File.dirname(__FILE__) + '/board' | |
board = Board.new | |
board.preview | |
board.solve |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment