#!/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}"