バルダ、彼女は魔方陣です。 プレーヤーは各ステップで1文字を追加して、可能な限り最大の意味のある単語を取得します。
古い学校のプログラマー（FORTRAN、PL1、およびパンチカードのスタック）であるため、コードを書く対象はまったく同じだと思います。 プログラミングの歴史の中で発生した基本的なアイデアのうち、オブジェクト指向とリレーショナルデータモデルのみに言及する価値があります（通常の手続き型アプローチとは対照的に、機能的プログラミング、およびおそらくあらゆる種類のラムダのことです）。 それにもかかわらず、主なものはアルゴリズムです！ これらはすべて、ドナルドクヌースによる7巻の「プログラミングの基礎」で基本的に説明されています。 そして、どのコマンドを使用すると、ウィンドウ、アイコン、その他の喜びが描画されますか？ Knuthの7巻の本と、IBM Research CenterのEdgar Coddのリレーショナルデータベースに関する基本的な記事は、60年代後半に登場しました。 つまり、ほぼ半世紀前です。 だからこそ、私はVBAで書いており、新しいものに気を取られていません。
2つの課題がありました（英語の課題のこのトレーシングペーパーは好きではありませんが、慣れています！）ゲームを書くとき。 再帰アルゴリズムを正しく登録してから、辞書内の単語の検索を最適化します。
アルゴリズム自体では、すべてが非常に簡単です。 すでに文字が入力された5 x 5のプレイフィールドがあります。 両側の既存の文字（対角線を除く）に隣接する別の文字を追加し、文字で満たされた競技場の「バイパス」の考えられるすべてのバリエーションについて、考えられるすべての単語のバリエーションを辞書で調べる必要があります。 これが再帰が発生する場所です。
任意の文字から順番に開始し、別の文字がある任意の方向に進みます。 そのため、確認のために単語が入力されます。 検査対象の単語にすでに含まれている文字自体は、その単語が交差点とはならないため（同じ文字を2回使用することはできません）、以降の検査から除外する必要があります。
各段階で、辞書にある入力された文字列を探します。 単語が見つかった場合、このオプションを覚えていますが、再帰を中断することなく検索を続行します。同じ始まりの長い単語もある可能性があるためです（CATを見つけた後、CATOVASIA、CATHOVODYEなども見つける機会を逃しません）
再帰を終了するためのシグナル（これは、再帰関数を記述する上で最も重要な部分です）は、このステップで考えられるすべての動きが使い果たされた（チェックされている単語に既に含まれているか、その場所から届かない場合）別の文字を選択できないことです私たちがこの段階にいた競技場）。 その後、終了します。つまり、1ステップ戻り、反対方向に移動しようとします。 可能なすべてのオプション、つまり文字でフィールドをバイパスするすべてのルートを通過すると、再帰から完全に終了します。
この場合、追加したばかりの文字は、チェックしている単語に該当するはずです。 ただし、このルールを先験的に含めることはできません。この文字が最後の文字になることが判明する可能性があるため、辞書を検索する前に最後にのみこのチェックを行う必要があります。
この時点で、発生するオプションの数に驚きました。 ゲームの最中（競技場はすでにいっぱいですが、十分な空きセルがある場合）、システムはすべてのステップで100,000（単語-10万）を超える単語のバリエーションをスキャンします！ フィールドサイズの指数関数的な複雑さの問題（NP完全性？）を明らかに扱っています。 したがって、元のアイデアから-すべてのゲームを計算して、敵に長い単語を与えないオプションを選択するために多くの動きを進めます（もちろん、同じ辞書を使用することを条件に！）拒否しなければなりませんでした。
ところで、再帰の深さは非常に小さいです-説明したアルゴリズムから明らかなように、現時点ではフィールド上の文字数を超えていません。
辞書として、Zaliznyakの辞書を使用しました（これは、ロシア語の形態に関する表であり、語形の形成に関する表が、Microsoft Word 6.0でのIgor Agamirzyanによる構文チェックの基礎となった言語学者と同じです）。 バルダの規則によれば、主格の名詞のみが単数形で使用でき、私が使用した辞書の名詞は「ABAZHUR」から「FMD」まで正確に43 304でした。
そのため、10万語のバリエーション（ピーク時-最大15万語）があり、43 304語の辞書を調べる必要があります。 計算を間違えなければ、60億を超える辞書ビューが表示されます。 プログラムの最初のバージョンは、数分間、各動きについて考えましたが、この不名誉はもちろん耐えられませんでした。 プログラムを使用して実際のライバルに対処する場合、コースを検討するのに1分しか与えられないという事実は言うまでもありません。 しかし、私はまた、少なくとも一歩先を見据えて、彼のターンで敵を超長単語に置き換えないようにします。
だから、最適化。 まず、すべての作業はRAMでのみ実行する必要があります。RAMが許可するデータ量です。 辞書全体がテーブルから配列に読み込まれ、配列が検索されます。 しかし、これは明らかに十分ではありません。
最適化するための理解できる2番目の方法は、インデックス作成です。 2文字バージョンで作成しました。 インデックスは、すべての可能な2文字のペアで構成される別の配列に追加されました。これらの同じ2文字で始まる単語は、完全な辞書を持つ配列に配置されています。 インデックス配列で必要な2文字を最初に検索しないようにするために、完全に作成されました。つまり、辞書に1つの単語を含まない文字のペアも含まれていました。 したがって、インデックス配列のインデックスは、探している単語の最初の2文字から直接、つまり非常に迅速に計算されました。
インデックス配列も多くのメモリを消費せず、その長さは32 x 32 = 1024要素です。 実際、インデックスを3文字にすることも難しくありませんでしたが、これは経験が示しているように、さらなる加速につながっていません。
これがすべての最適化ではありません！ また、元の辞書をハッシュで拡張しました。実際、同じ単語でしたが、各文字が1回しか出現しませんでした（POTOP-VET）。 その結果、最速の検索オプションはこれでした：
-辞書全体をソートし、探している単語と同じ文字を含む単語のみを残します。
-この簡略化された辞書2文字のインデックスに基づいて作成します。
-インデックスを使用して目的の単語を探しています。
結果-各移動での単語のすべてのバリエーションの検索は2秒以内に完了しますが、先ほど言ったように、辞書で最大150,000の単語が検索され、最大数百の移動のバリエーションがあります-4文字以上の単語。 また、発見された単語のバリエーションごとに、対戦相手の可能な将来の動きを計算することもできます-1つのバリエーションに対して2秒の価格で。
次にMS Accessについて。 このプログラムは、完全に許容できるリレーショナルデータベースエンジン、シンプルなインターフェイスの構築、および舞台裏の強力なVisual Basic for Applicationsを組み合わせているため、私はこのプログラムが大好きです。
後者は、文字列情報の処理速度においてC ++ / C＃よりも劣っていないと言います。これは、プログラムの最適化によって実証されました。
データベースに関しては、これは少なくとも何らかの構造が存在するデータを保存するための唯一の正しい形式だと思います。 また、「累積」プログラム、つまり計算に何日もかかるプログラムを作成することもできます（これらは、私が時々手を出したあらゆる種類の言語タスクです）。 中間結果を失わないために、それらは一定の規則でテーブルにスローされる必要があります。これにより、基本的な計算のパフォーマンスが低下することはありません。 そのため、常にいくつかの出発点があります。
プログラムインターフェイス。 システムは、長さの降順にソートされたすべての動きを提供します。 必要に応じて、単語の1つまたは別のバリエーションを選択すると、敵の次の動きを予測できます。
そして、これが対戦相手との試合です。 あなたは彼の動きを注意深くする必要があり、プログラムはあなたに最良の選択肢を教えてくれます。
不誠実で私をscりたいですか？ しかし、私は自分でプログラムを書いて最適化しました！ さらに、彼は興味のためにプレーしましたが、利益のためではありませんでした。 さらに、ほとんどすべてのライバルが同様のものを使用しますが、自分で書いたものではありません-これはすぐに見ることができます。 プロフィールには猫の写真がたくさんある15歳の男は、PROZELITISMという言葉をどこで知っていますか？ （「小さなティファニーは、量子物理学の教科書を手にして、朝の不利な地域で何をするのか？」）