ruby - 文字の 4x4 グリッド - 単語ジェネレーター - 友達とスクランブル

Question

文字の 4x4 グリッドに基づいて単語ジェネレーターを作成しようとしています (以下)。

ルールは次のとおりです。

• 文字を繰り返すことはできません
• 単語は隣接する文字で形成する必要があります
• 単語は、水平、垂直、または斜め左、右、または上下に形成できます

現在、私は 16 文字の入力を受け取り、辞書内のすべての単語をループして、その単語がグリッド上の文字でつづられるかどうかを判断しています。

#!/usr/bin/ruby

require './scores'   # alphabet and associated Scrabble scoring value (ie the wordValue() method)
require './words.rb' # dictionary of English words (ie the WORDS array)

# grab users letters
puts "Provide us the 16 letters of your grid (no spaces please)"
word = gets.chomp.downcase

arr = word.split('')

# store words that can be spelled with user's letters
success = []

# iterate through dictionary of words
WORDS.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
    end

end

# create hash for successful words and their corresponding values
SUCCESS = {}

success.each do |w|
  score = wordValue(w)
  SUCCESS[w] = score
end

# sort hash from lowest to smallest value
SUCCESS = SUCCESS.sort_by {|word, value| value}

# print results to screen
SUCCESS.each {|k,v| puts "#{k}:  #{v}"}

ただし、このアプローチでは、ボード上のタイルの位置が考慮されていません。 4x4 グリッド内の位置に基づいて作成できる単語を見つけるにはどうすればよいでしょうか?

上の画像のボード ゲームの場合、Ubuntu を実行している VM が 1185 の可能な単語を計算するのに約 1.21 秒かかります。/usr/share/dict/words にある Ubunut で提供されている単語の辞書を使用しています

Answer 1

単語を反復処理してその存在を検索する代わりに、グリッド上の各タイルを調べて、そのタイルに由来するすべての単語を見つけます。

まず、辞書をtrieにコンパイルします。試行は、プレフィックス マッチング文字列比較を実行するのに効率的です。これはすぐに役立ちます。

ボード内の単語を見つけるには、16 個のタイルごとに次の手順を実行します。空の文字列から始めますprefix。

1. 現在のタイルの値を に追加しprefixます。
2. トライに で始まる単語が含まれているかどうかを確認しprefixます。
3. 存在する場合、検索を分岐します。このタイルに隣接する正当な (未訪問の) タイルごとに、ステップ 1 (再帰) に戻ります。
4. 一致しない場合は、一致する単語がないため、検索のこのブランチを停止します。

Answer 2

ボード全体を表す単純なグラフを作成します。文字は頂点になります。2 つの文字がボード上で互いに近くにある場合、それらの頂点の間にエッジを作成します。入力が有効かどうかを調べるのは非常に簡単です。グラフに一致するパスがあるかどうかを確認するだけです。

Answer 3

私の最初の答えは、あなたが望んでいたものではありませんでした。辞書から既に特定した単語を検索する代わりに、グリッド内のすべての「単語」のリストを作成していました。これで、特定の単語をグリッドで検索する関数を作成できました。再帰的に動作します。

したがって、アルゴリズムは次のようになります。

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 15

ADJACENT = [
    [1, 4, 5],
    [0, 2, 4, 5, 6],
    [1, 3, 5, 6, 7],
    [2, 6, 7],
    [0, 1, 5, 8, 9],
    [0, 1, 2, 4, 6, 8, 9, 10],
    [1, 2, 3, 5, 7, 9, 10, 11],
    [2, 3, 6, 10, 11],
    [4, 5, 9, 12, 13],
    [4, 5, 6, 8, 10, 12, 13, 14],
    [5, 6, 7, 9, 11, 13, 14, 15],
    [6, 7, 10, 14, 15],
    [8, 9, 13],
    [8, 9, 10, 12, 14],
    [9, 10, 11, 13, 15],
    [10, 11, 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 calls
DEBUG = false

def 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, and return true if the word is found
                if is_word_on_board(word, board_copy, newprefix, c)
                    return true
                end
            end
        end

        # bummer, no word found, so return false
        return false
    end
end

puts "Test board:"
puts
puts "  r u t t"
puts "  y b s i"
puts "  e a r o"
puts "  g h o l"
puts

board = "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"
    end
end

このスクリプトを実行すると、次の結果が得られます。

Test board:

  r u t t
  y b s i
  e a r o
  g h o l

ruby is on the board
bears is on the board
honey is NOT on the board
beast is on the board
rusty is NOT on the board
burb is NOT on the board
bras is on the board
ruttisbyearolohg is on the board
i is on the board

Answer 4

少し前に書いた Boggle ソルバーがあります。Cheeken の概要に従います。呼び出し方が少し異なります (引数として単語リスト ファイルと 4x4 グリッドを含むテキスト ファイルを指定します) が、共有する価値があると思いました。また、「Q」を「QU」として扱うため、そのための追加のロジックがいくつかあることに注意してください。

require 'set'

def build_dict(dict, key, value)
  if key.length == 0
    dict[:a] = value
  else
    if key[0] == "q"
      first = key[0..1]
      rest = key[2, key.length - 1]
    else
      first = key[0]
      rest = key[1, key.length - 1]
    end

    dict[first] = {} unless dict.has_key? first
    build_dict(dict[first], rest, value)
  end
end

dict = {}
#parse the file into a dictionary
File.open(ARGV[0]).each_line do |line|
  real_line = line.strip
  build_dict(dict, real_line, real_line)
end

#parse the board
board = {}
j = 0
File.open(ARGV[1]).each_line do |line|
  line.chars.each_with_index do |l, i|
    board[[j, i]] = l
  end
  j += 1
end

#(0..3).each{|r| puts (0..3).map{|c| board[[r, c]]}.join}

#how can i get from one place to another?
def get_neighbors(slot, sofar)
  r, c = slot
  directions =
   [
    [r+1, c],
    [r+1, c+1],
    [r+1, c-1],
    [r, c+1],
    [r, c-1],
    [r-1, c],
    [r-1, c+1],
    [r-1, c-1]
   ]
  directions.select{|a| a.all?{|d| d >= 0 && d <= 3} && !sofar.include?(a)}
end

#actual work
def solve(board, slot, word_dict, sofar)
  results = Set.new
  letter = board[slot]
  letter = "qu" if letter == "q"
  stuff = word_dict[letter]
  return results if stuff.nil?
  if stuff.has_key? :a
    results << stuff[:a] if stuff[:a].length > 2
  end
  unless stuff.keys.select{|key| key != :a}.empty?
    get_neighbors(slot, sofar).each do |dir|
      results += solve(board, dir, stuff, sofar.clone << slot)
    end
  end
  results
end

#do it!
results = Set.new
all_slots = (0..3).to_a.product((0..3).to_a)
all_slots.each do |slot|
  results += solve(board, slot, dict, slot)
end

puts results.sort