ruby – 4×4字母网格 – 单词生成器 – 与朋友争夺

概述我正在尝试创建一个基于4×4字母网格的字生成器(下图). 以下是规则： >信件不能重复 >单词必须由相邻的字母组成 >可以在左,右或上下水平,垂直或对角形成单词 目前,我采用16个字符的输入并遍历字典中的每个单词,确定该单词是否可以拼写为网格上的字母. #!/usr/bin/rubyrequire './scores' # alphabet and associated Scrabble 我正在尝试创建一个基于4×4字母网格的字生成器(下图).

以下是规则：

>信件不能重复
>单词必须由相邻的字母组成
>可以在左,右或上下水平,垂直或对角形成单词

目前,我采用16个字符的输入并遍历字典中的每个单词,确定该单词是否可以拼写为网格上的字母.

#!/usr/bin/rubyrequire './scores'   # Alphabet and associated Scrabble scoring value (IE the wordValue() method)require './words.rb' # dictionary of English words (IE the WORDS array)# grab users lettersputs "ProvIDe us the 16 letters of your grID (no spaces please)"word = gets.chomp.downcasearr = word.split('')# store words that can be spelled with user's letterssuccess = []# iterate through dictionary of wordsWORDS.each do |w|    # create temp arrays    dict_arr = w.split('')    user_arr = arr.dup    test = true    # test whether users letters spell current word in dict    while test        dict_arr.each do |letter|            if (user_arr.include?(letter))                i = user_arr.index(letter)                user_arr.delete_at(i)            else                test = false                break            end        end        # store word in array        if test             success << w            test = false        end    endend# create hash for successful words and their corresponding valuesSUCCESS = {}success.each do |w|  score = wordValue(w)  SUCCESS[w] = scoreend# sort hash from lowest to smallest valueSUCCESS = SUCCESS.sort_by {|word,value| value}# print results to screenSUCCESS.each {|k,v| puts "#{k}:  #{v}"}

但是,这种方法没有考虑到电路板上瓷砖的位置.您如何建议我根据他们在4×4网格中的位置找到可以创建的单词？

对于上图中的棋盘游戏,我的VM运行Ubuntu大约需要1.21秒来计算1185个可能的单词.我在/usr/share / dict / words中使用Ubunut提供的词典

解决方法 我原来的答案不是你想要的.我正在创建所有的列表
网格中的“单词”,而不是搜索您已识别的单词
来自字典.现在我编写了一个搜索网格的函数
特别的话.它以递归方式工作.

那么,现在的算法是：

1)从用户处获取16个字母
2)搜索包含这些字母的所有单词的字典
3)使用每个单词调用is_word_on_board以查看是否匹配

#!/usr/bin/ruby# This script searches a board for a word## A board is represented by a string of letters,for instance,the string# "abcdefghijklmnop" represents the board:##    a b c d#    e f g h#    i j k l#    m n o p## The array ADJACENT Lists the cell numbers that are adjacent to another# cell.  For instance ADJACENT[3] is [2,6,7].  If the cells are numbered##     0  1  2  3#     4  5  6  7#     8  9 10 11#    12 13 14 15ADJACENT = [    [1,4,5],[0,2,5,6],[1,3,7],[2,1,8,9],9,10],7,10,11],[4,12,13],13,14],[5,11,14,15],[6,[8,[9,[10,14]]# function:  is_word_on_board## parameters:#   word   - word you're searching for#   board  - string of letters representing the board,left to right,top to bottom#   prefix - partial word found so far#   cell   - position of last letter chosen on the board## returns true if word was found,false otherwise## Note:  You only need to provIDe the word and the board.  The other two parameters# have default values,and are used by the recursive calls.# set this to true to log the recursive callsDEBUG = falsedef is_word_on_board(word,board,prefix = "",cell = -1)    if DEBUG        puts "word = #{word}"         puts "board = #{board}"        puts "prefix = #{prefix}"        puts "cell = #{cell}"        puts    end    # If we're just beginning,start word at any cell containing    # the starting letter of the word    if prefix.length == 0        0.upto(15) do |i|            if word[0] == board[i]                board_copy = board.dup                newprefix = board[i,1]                # put "*" in place of letter so we don't reuse it                board_copy[i] = ?*                # recurse,and return true if the word is found                if is_word_on_board(word,board_copy,newprefix,i)                    return true                end            end        end        # we got here without finding a match,so return false        return false    elsif prefix.length == word.length        # we have the whole word!        return true    else        # search adjacent cells for the next letter in the word        ADJACENT[cell].each do |c|            # if the letter in this adjacent cell matches the next            # letter of the word,add it to the prefix and recurse            if board[c] == word[prefix.length]                newprefix = prefix + board[c,1]                board_copy = board.dup                # put "*" in place of letter so we don't reuse it                board_copy[c] = ?*                # recurse,c)                    return true                end            end        end        # bummer,no word found,so return false        return false    endendputs "Test board:"putsputs "  r u t t"puts "  y b s i"puts "  e a r o"puts "  g h o l"putsboard = "ruttybsIEaroghol"for word in ["ruby","bears","honey","beast","rusty","burb","bras","ruttisbyearolohg","i"]    if is_word_on_board(word,board)        puts word + " is on the board"    else        puts word + " is NOT on the board"    endend

运行此脚本会产生以下结果：

Test board:  r u t t  y b s i  e a r o  g h o lruby is on the boardbears is on the boardhoney is NOT on the boardbeast is on the boardrusty is NOT on the boardburb is NOT on the boardbras is on the boardruttisbyearolohg is on the boardi is on the board

总结

以上是内存溢出为你收集整理的ruby – 4×4字母网格 – 单词生成器 – 与朋友争夺全部内容，希望文章能够帮你解决ruby – 4×4字母网格 – 单词生成器 – 与朋友争夺所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。