1

スクラブルのような単語ゲームを分析して、ボードに配置された文字のブロックがそれ以上の文字を配置できなくなるかどうか、つまりゲームを「ロック」できるかどうかを調べています。2x2 ブロックの例で説明してみましょう:

有効な 2x2 ブロック (約 5000 ブロック) のリストを作成しました。リストは次のようになります。

matrix_2x2

AA,AA
AA,AB
AA,AD
AA,AE
etc...

ボード上の「AA,AE」は次のようになります (実際のボードは 15x15 です)。

[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][A][A][ ][ ][ ]
[ ][ ][ ][A][E][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

有効な単語の完全なリストもあります。このように見えます

dic_word

AA
AAH
AAHED
AAHING
AAHS
AAL
etc...

MySQL に両方のリストがあります。

マトリックス リストの各エントリを繰り返し処理し、SELECT クエリを作成することで、コードでこれを実行できることはわかっています。行列の各行は次のようになります。

SELECT COUNT(word) > 0 FROM dic_word d WHERE (INSTR(word, "AA") OR INSTR(word, "AE") OR INSTR(word, "AA") OR INSTR(word, "AE")) AND (word <> "AA" AND word <> "AB" AND word <> "AA" AND word <> "AB")

これを MySQL で完全に実行できるかどうか疑問に思っていました。

アップデート

上記のSQLクエリは機能せず、私が求めているものをうまく説明していません. 私が求めているものを明確にしてみましょう：

QXandQQとがすべて英語で有効な単語であると仮定するとXX、QX,QX が行列リストのエントリになります。

英単語の部分文字列でQXもQQorでもないので、ボードに配置された QX,QX はゲームを「ロック」します (つまり、追加の文字を配置できなくなります)。XX

私はこれらの行列をロックした後、すべての有効な 2x2 行列を調べることから始めます。現在、有効な 3x3 ブロックすべてのリストを作成しています。これまでに 200.000 以上が見つかりました。

補足として、そのようなロックマトリックスが存在することは本当に疑わしいですが、それは私がチェックしているものです。

4

2 に答える 2

1

既存のクエリの問題は、部分文字列のスキャンが非常に非効率的であることです。特に、インデックスは使用できません。そのため、dic_wordテーブルのフル スキャンが必要であり、そのword中のすべてを個別にスキャンして目的の部分文字列を探す必要があります。

代わりに、サフィックスのインデックス付きテーブルを作成します。

CREATE TABLE suffixes (
  suffix VARCHAR(15) NOT NULL,
  word   VARCHAR(15) NOT NULL,
  PRIMARY KEY (suffix, word),
  FOREIGN KEY (word) REFERENCES dic_word (word)
);

次に、次の非常に効率的なクエリを実行できます。

SELECT 1
FROM   suffixes
WHERE (
       suffix LIKE 'AA%'
    OR suffix LIKE 'AE%'
    OR suffix LIKE 'AA%'
    OR suffix LIKE 'AE%'
      ) AND word NOT IN ('AA','AE','AA','AE')
LIMIT  1

ノート：

  • このLIMIT句により、MySQL は単一の結果が見つかるとすぐに検索を停止します。

  • 結果セットには、1 つ以上の可能な単語があることを示す単一のレコードが含まれるか、または可能な単語がないことを示すレコードが含まれません。

  • このクエリは、ボードに残っているスペースを考慮していません。たとえば、部分文字列を含む唯一の単語が長すぎてボードの端からはみ出す場合などです。ただし、追加のフィルターを追加することで簡単に解決CHAR_LENGTH(word)できます必要に応じて、別のインデックス付きの列内に保持されます。

  • 'A__DE____J__'この最適化は、断続的なスペースや既知の文字がある場合など、より複雑な状況には容易に拡張LIKEできません。これが要件に含まれている場合は、データ構造にさらに変更を加えることができます。

suffixesテーブル の設定と維持

この投稿の残りの部分では;;、ステートメントの区切り記号として使用します。これは、それに応じてクライアントを構成する必要があります。MySQL コマンドライン ツールでは、コマンド を使用してこれを実現できますDELIMITER ;;。

テーブルへの入力を支援するために、いくつかのストアド プロシージャを作成できます。suffixes

  1. 指定された単語のすべての接尾辞を追加します。

    CREATE PROCEDURE FillSuffixes(IN p_word VARCHAR(15)) BEGIN
  DECLARE i TINYINT UNSIGNED DEFAULT 1;
  WHILE i <= CHAR_LENGTH(p_word) DO
    INSERT IGNORE INTO suffixes
      (suffix, word)
    VALUES
      (SUBSTRING(p_word, i), p_word)
    ;
    SET i := i + 1;
  END WHILE;
END;;

  2. dic_wordまだ表にない、表内のすべての単語のすべての接尾辞を追加しsuffixesます。

    CREATE PROCEDURE FillAllSuffixes() BEGIN
  DECLARE w VARCHAR(15);
  DECLARE done BOOLEAN DEFAULT FALSE;

  DECLARE cur CURSOR FOR
    SELECT word
    FROM   dic_word LEFT JOIN suffixes USING (word)
    WHERE  suffixes.word IS NULL
  ;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

  OPEN cur;

  read_loop: LOOP
    FETCH cur INTO w;
    IF done THEN
      LEAVE read_loop;
    END IF;
    CALL FillSuffixes(w);
  END LOOP;

  CLOSE cur;
END;;

テーブルへの変更に基づいてテーブルを自動的に維持するトリガーを定義することもできます。suffixesdic_word

CREATE TRIGGER add_suffixes AFTER INSERT ON dic_word FOR EACH ROW
CALL FillSuffixes(NEW.word);;

CREATE TRIGGER upd_suffixes AFTER UPDATE ON dic_word FOR EACH ROW
IF NEW.word <> OLD.word THEN
  DELETE FROM suffixes WHERE word = OLD.word;
  CALL FillSuffixes(NEW.word);
END IF;;

CREATE TRIGGER del_suffixes AFTER DELETE ON dic_word FOR EACH ROW
DELETE FROM suffixes WHERE word = OLD.word;;

最後に、既存のレコードからテーブルにデータを入力します (上記で作成した手順を使用します — 注意、実行には少し時間がかかる場合があります)。

CALL FillAllSuffixes;
于 2012-12-05T12:43:23.037 に答える
0

これまでの私の解決策は次のとおりです。

2x2 文字 (行列) のすべてのブロックをループし、配置できる単語の数をカウントします。次に、結果がテーブル lock2 に挿入されます。マトリックスのカウントが 0 になると、ゲームがロックされた状態になります。

動作していますが、非常に遅いです。パフォーマンスは 2x2 リストでは許容範囲内ですが、3x3 リストでは私の生涯で終わることはありません。

パフォーマンスを向上させるための提案は大歓迎です。

DELIMITER $$

DROP PROCEDURE IF EXISTS `wsolver`.`analyse2_2` $$
CREATE PROCEDURE analyse2_2()
BEGIN
  DECLARE done INT DEFAULT FALSE;
  DECLARE a INT;
  DECLARE b VARCHAR(45);

  DECLARE cur1 CURSOR FOR SELECT Matrix FROM matrix2x2;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

  OPEN cur1;

  read_loop: LOOP
    FETCH cur1 INTO a;

    IF done THEN
      LEAVE read_loop;
    END IF;


      SET @w1 = SUBSTRING(a, 1, 2);
      SET @w2 = SUBSTRING(a, 4, 2);
      SET @w3 = CONCAT(SUBSTRING(@w1, 1, 1), SUBSTRING(@w2, 1, 1));
      SET @w4 = CONCAT(SUBSTRING(@w1, 2, 1), SUBSTRING(@w2, 2, 1));


      SELECT COUNT(*) INTO @w5 FROM dan WHERE (instr(dic_word, @w1) OR instr(dic_word, @w2) OR instr(dic_word, @w3) OR instr(dic_word, @w4)) AND (dic_word NOT IN(@w1,@w2,@w3,@w4));

      INSERT INTO `lock2` (matrix, `count`) VALUES (a, @w5);


  END LOOP;

  CLOSE cur1;

END $$

DELIMITER ;
于 2012-12-05T15:47:54.623 に答える