Clever Geek Handbook

スロボマニヤ-言葉を推測します。 パート1、ルビー

スロボマニア スロベニアを初めて見たときは、言葉を推測しながら果てしなく時間を費やして、 スロベニアにひたすら沈みました。 ゲームの本質：4x4グリッドがあり、各セルに文字があります。 プレーヤーの仕事は、文字を1つずつつなげて単語を構成することです

一定の時間の後、アイデアが浮上しました。単語を解くプロセスを自動化するとどうなるでしょうか。 結局のところ、私自身が単語を追加しようとして組み合わせの単純な列挙を行うことがよくあります。 明らかに、コンピューターはそのようなタスクに誰よりもはるかに生産的に対処します。 もちろん、言葉が現場ですぐに「見える」場合を除いて、この問題はすでに脳によって解決されているため、脳とコンピューターの間の分業に対処することが決定されました。



まず、フィールド上の単語を見つけるタスクが利用可能なコンピューティングパワーで実行可能であることを理解するためにプロトタイプを作成する必要がありました（4 GBのメモリとLinode 1024サーバーを搭載したMacBook Core 2 Duo 2.2Ghz Late 2007）。 私は最近Ruby On Railsを積極的に開発してきたので、Rubyをテスト環境として採用することにしました。 明らかに、私たちのタスクには大きな計算能力が必要であり、Rubyの場合、ほぼすべての操作に大きなオーバーヘッドがあるため、戦闘状況のために他の何かを使用する必要があります（たとえば、Cなど）。 ただし、明確なプラスを無視することはできません-これが開発の速度です。



行きましょう。 プログラムは次のように機能します。

  1. 文字のすべての可能なレイアウトオプションを並べ替えます
  2. 結果を辞書と一致させる
  3. 辞書でオプションが見つかった場合-単語が推測された場合、プレーヤーに表示できます


最初のステップは、依存する辞書を整理することでした。 Yandexで簡単に検索した後、通常のテキストファイルの形式でいくつかの辞書が見つかりました（各行には個別の単語があります）。 辞書はSQLiteデータベースにアップロードされます。 これで、プログラムの作成に直接進むことができます。 最も興味深い点のみを説明します。完全なソースコードへのリンクは記事の最後にあります。 このプログラムは、「GoFブックのすべてのデザインパターンを使用して可能な限り美しく作成する」のではなく、「できるだけ高速に作業バージョンを作成する」スタイルで作成されていることに注意してください。



私の頭の中で開発された次のアクションのアルゴリズム：

  1. 座標（x、y）でセルに到達します（原点の左下隅を取りました）。 座標（パス）の特別なリストにある現在のセルの位置を覚えています。
  2. 各方向（北、南、西、東、北東、南東、南西、北西）に1セルずつ交代します。
  3. 各パスに対して、座標の新しいリストを作成します
  4. 座標のリストを使用して、単語を形成します
  5. 辞書に単語があるかどうかを確認します（ある場合は、プレーヤーを表示します）
  6. 新しい位置ごとに、特定の語長（つまり、座標リストの長さ）に達するまで手順2に進みます。 長さは、ゲーム内で可能な最大の語長、または計算能力の2つの要因によって決まります。
  7. 次のセルに移動し、最初からやり直します。


したがって、フィールド全体を再帰的に処理して、可能なすべての組み合わせを並べ替えます。 同時に、各セルが各単語に一度しか関与できないことを忘れてはなりません。したがって、段落（2）では、リストにこのセルの座標があるかどうかを確認する必要があります。 また、競技場を超えていないことを忘れないでください。

さらにもう1つ確認します。ゲームの規則に従って、単語は少なくとも3文字で構成されているため、その長さ（パスの長さ）が2を超える場合にのみ辞書で単語を探します。



これは次のようなものです。



ゲームネット 


@@w = [ "", "", "", "" ]




座標クラス 


 class Coord attr_accessor :x, :y def initialize(x,y) self.x = x self.y = y end end




隣接バイパス 


 def lookup(coords, deep) print_word coords if deep >= 3 last = coords[-1] #up lookup_next coords, Coord.new(last.x + 1, last.y), deep #up-right lookup_next coords, Coord.new(last.x + 1, last.y + 1), deep #right lookup_next coords, Coord.new(last.x, last.y + 1), deep #right-down lookup_next coords, Coord.new(last.x + 1, last.y - 1), deep #down lookup_next coords, Coord.new(last.x, last.y - 1), deep #left-down lookup_next coords, Coord.new(last.x - 1, last.y - 1), deep #left lookup_next coords, Coord.new(last.x - 1, last.y), deep #left-up lookup_next coords, Coord.new(last.x - 1, last.y + 1), deep end def lookup_next(coords, new_coord, deep) return if deep > 6 return if new_coord.x < 0 or new_coord.y < 0 or new_coord.x > 3 or new_coord.y > 3 unless coords.find{|c|cx == new_coord.x and cy == new_coord.y} lookup coords.dup + [new_coord], deep + 1 end end




辞書で単語を検索して印刷する 


 def print_word coords word = "" coords.each do |c| word += @@w[3 - cy].split('')[cx] end return if @@words.include?(word) @@db.execute( "select * from words where (word)=('#{word}')" ) do |row| return if @@words.include?(word) @@words << word puts word end end




画面に同じ単語が表示されないように、見つかった単語はすべてグローバル変数@@ wordsに保存されます。



検索を開始します 


 0.upto(3) do |x| 0.upto(3) do |y| lookup [Coord.new(x, y)], 0 end end




この実装の欠点の1つは、検索がグリッドの左下隅から開始することであり、おそらくプログラムがフィールド全体を巡回するのに十分な時間がないため、別のストリームで反対側の隅から単語の検索を開始できることです。 



 Thread.new { 3.downto(0) do |x| 3.downto(0) do |y| lookup [Coord.new(x, y)], 0 end end }




比較的遅いRubyを使用していますが、プログラムは実行可能であり、単語を完全に検出します。 次の記事では、ncurses、分散メモリ、セマフォ、およびブラックジャックを使用したC実装について説明します。



ソースコード

語彙



正義が勝利しました：今、最もクールなコンピューターを持っている人が勝ちます！


More articles:


All Articles