Skip to content

Instantly share code, notes, and snippets.

@bgreenlee
Created Feb 11, 2014
Embed
What would you like to do?
Rather inefficient Boggle puzzle solver
#!/usr/bin/env ruby
# Boggle(tm) puzzle solver
# by Brad Greenlee <brad@footle.org>
# (Boggle is a trademark of Hasbro Inc., who has no affiliation with this
# program and hopefully couldn't care less about its existence.)
BOARD_SIZE = 4
MAX_WORD_SIZE = 12
MIN_WORD_SIZE = 3
POINTS = [0,0,0,1,2,4,6,9,12] + [16]*(MAX_WORD_SIZE-8) # no idea what the scoring should really be
# load the dictionary and put the words into a hash for easy lookup
def load_words
word_hash = {}
File.read('words').split.each {|w| word_hash[w] = true }
return word_hash
end
# turn the board string into an array we can work with
def init(str)
board = str.split(//).map {|c| {:letter => c == 'q' ? 'qu' : c}}
# precalculate possible next moves for each position
board.each_with_index do |_, i|
(x,y) = [i%BOARD_SIZE, i/BOARD_SIZE]
moves = []
moves << i+1 if x < BOARD_SIZE-1
moves << i+BOARD_SIZE+1 if x < BOARD_SIZE-1 && y < BOARD_SIZE-1
moves << i+BOARD_SIZE if y < BOARD_SIZE-1
moves << i+BOARD_SIZE-1 if x > 0 && y < BOARD_SIZE-1
moves << i-1 if x > 0
moves << i-(BOARD_SIZE+1) if x > 0 && y > 0
moves << i-BOARD_SIZE if y > 0
moves << i-(BOARD_SIZE-1) if x < BOARD_SIZE-1 && y > 0
board[i][:moves] = moves
end
return board
end
# the workhorse. this is called recursively to build up words
def build(board, word, pos)
return if word.size > MAX_WORD_SIZE # don't bother with words over 12 letters (we don't have them in the word list anyway)
elem = board.at(pos) # at is faster than []
elem[:played] = true
# check word
if @words[word] && (word.size >= MIN_WORD_SIZE) && !@found_words[word]
puts "found word: #{word}"
@found_words[word] = true
end
# determine next possible letters
elem[:moves].each { |p| build(board, word + board.at(p)[:letter], p) unless board.at(p)[:played] }
elem[:played] = false
end
# loop through each letter on the board and find all words starting with that letter
def solve(board)
board.each_with_index {|elem, i| build(board, elem[:letter], i) }
end
unless (board_str = ARGV.shift)
puts "Usage: boggler.rb <board string>"
puts " where the board string is all the letters on the board, from left to right"
puts " and top to bottom."
puts " Example: given the board:"
puts " LYLT"
puts " ONZI"
puts " GORO"
puts " RWHO"
puts " the board string would be: lyltonzigororwho (case is ignored)"
puts " the letter 'q' will automatically have a 'u' appended"
exit
end
if board_str.size != BOARD_SIZE ** 2
puts "Error: The board size is #{BOARD_SIZE}, so your board string should be #{BOARD_SIZE**2}"
puts "characters long. Yours was #{board_str.size}."
exit
end
@words = load_words
puts "loaded #{@words.size} words. solving '#{board_str}'..."
board = init(board_str.downcase)
@found_words = {}
solve(board)
puts "found #{@found_words.size} words"
total = @found_words.keys.inject(0) {|sum, w| sum + POINTS[w.size]}
puts "total score: #{total}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment