それは紙の上または頭の中で解決でき、不適切なオプションを順次排除します。 ただし、より技術的に解決することもできます。 1つの方法は、プロローグプログラムを作成することです。 しかし、ここでは、より単純なメカニズム（正規表現）を使用して解決したいと思います。 つまり、パズルの条件を正規表現言語に翻訳し、文字列の有効なセット全体から適切な文字列を見つける作業を減らします。 ところで、この一連の線は図に示されています。
アイデア
アイデア自体は私のものではなく、あるビデオ講義で聞いた。 しかし、彼らはそれをあまりにも高度に解決しました。 私はそれをより簡単にそして率直に解決しようとしました。
便宜上、パズルのテキストは次のとおりです。
- ノルウェー人は最初の家に住んでいます。
- イギリス人は赤い家に住んでいます。
- 緑の家は、白い家の左隣にあります。
- デーンはお茶を飲んでいます
- マールボロを吸う人は、猫を飼う人の隣に住んでいます。
- 黄色い家に住んでいる人はダンヒルを吸っています。
- ドイツ人はロスマンスを吸う。
- センターに住んでいる人は牛乳を飲みます。
- マールボロを吸う人の隣人は水を飲む。
- ポールモールの喫煙者は鳥を育てています。
- スウェーデン人は犬を飼っています。
- ノルウェー人は青い家の隣に住んでいます。
- 馬を育てる彼は青い家に住んでいます。
- ウィンフィールドを吸う人は誰でもビールを飲みます。
- 温室でコーヒーを飲みます。
質問： 魚を繁殖させるのは誰ですか？
問題を解決するには、上記のルールを満たすように、家、花、国籍、飲み物、タバコのシーケンスを見つける必要があります
そして、何をどこで見るか。 まず、何らかの形でルールを形式化する必要があります。 5つの家、花、国籍、飲み物、動物、タバコがあります。 「居住者」がいる家の任意のバージョンは次のようになります。
german white cat beer malboro
しかし、これは十分ではありません。家とその中のオブジェクトの相互配置を考慮したルールがあるためです（たとえば、ルール：1、3、5 ...）。 5つの家を連続して並べることで、これを考慮します。
german white cat beer malboro englishman red dog water pallmall norwegian green fish milk winfield dane blue bird tea dunhill swede horse yellow coffee rothmans
上記の行は、アイテムを配置するためのオプションの1つです。 この場合、間違っています。 すべての可能なオプションを構成し、それを1つのテキストに入れると、次のようになります。
ncadsncadsncadsncadsn cads ncadsncadsncadsncadsn cads ncadsncadsncadsncadsn cads ...
ここで、n-国、c-色、a-動物、d-飲み物、s-タバコ。 そして、これらの文字のそれぞれは、その5つの意味の1つを取ることができます。
いいね 残っていることは、ルールを正規表現言語に翻訳することです。
- ^ノルウェー語\ w +
- \ w +英国人赤\ w +
- \ w +デーン\ w \ wティー\ w +
- ...
そして、線がすべてのルールに適合する場合、解決策が見つかりました！ 魚のいる家の国籍を見るだけです。 これが検索の主なアイデアです。テキストを作成し、正規表現でその上を歩きます。
しかし、いくつかの悪いニュースがあります。 検索されるテキストは非常に大きい場合があります。 より正確には、（5！）^ 5行（約240億）のサイズになります。 確認するだけでなく、生成することさえ困難です。 しかし、良いニュースがあります。 このテキストをすべて生成することはできませんが、正規表現を交差させる操作を使用します。 つまり、正規表現*（可能なすべての行）のすべての共通行と、問題のルールの正規表現を提供する行を見つけます 。 交差点の後に残るその線（または線）が問題の解決策になります。
残念ながら、正規表現を横断できるエンジンは知りません。 したがって、正規表現の根底にある有限状態マシンを直接使用する必要があります。
実装
openfstライブラリを使用してステートマシンを構築します。 マシンを構築するために必要なものすべてに加えて、シェルから作業する便利な方法を提供します。 プログラミングをさらに「異常」にするために、私はまったくプログラミングしません:)。 単純なbashスクリプトを除き、コードはありません。
ステップ1-基本オートマトンの構築
すべてのオブジェクトのリストを含むテキストファイルを作成します。 これがアルファベットになります。
norwegian englishman dane german swede white red ...
基本的なオートマトンを構築します。各オートマトンは、アルファベットから1つの単語のみを受け入れます。
j=1 for i in `cat alph`; do echo -e "0 1 $j\n1" | fstcompile --acceptor > $i ((j=$j+1)) done
fstcompileは、オートマトンのテキスト表現をバイナリ形式にコンパイルするopenfstパッケージコマンドです。 これは、後でこのマシンにさまざまな操作を適用するために必要です。
そして、自動ファイルのリストがあります。 彼らは非常に簡単です。 たとえば、ビールマシンは次のようになります。
これは、正規表現「ビール」と同等です。 これまでのところ、すべてが非常に簡単です。 さらに、2つの基本的なオートマトンが必要になります。空のセットと任意の文字列です。 アスタリスク*。 構築中です。
ステップ2-空のマシンとアスタリスクを作成する
空行、自動「空」：
echo '0' | fstcompile --acceptor > empty
スプロケット、自動「スター」：
cp empty star for i in `cat alph`; do fstunion star $i star done fstclosure star star
後者は、基本的なオートマトンとクロージャの単純な結合によって行われます。 正規表現では、これは（englishman | dane | ... | cat | dog | ...）*です。 このマシンは次のようになります。
ステップ3-家を建てる
国籍、色など、より複雑なマシンを作成する場合は、ルールを記述する方が便利です。 繰り返しますが、簡単なスクリプトを使用します。
c="./concat.sh" $c norwegian star > r1 $c star englishman red star > r2 $c star animal drink cigarette nation star > r3 $c star dane color animal tea star > r4 $c star malboro nation color cat star > r5_0 $c star cat drink cigarette nation color animal drink malboro star > r5_1 $c star yellow animal drink dunhill star > r6 $c star german color animal drink rothmans > r7 $c house house nation color animal milk cigarette house house > r8 $c star malboro nation color animal water star > r9_0 $c star water cigarette nation color animal drink malboro star > r9_1 $c star bird drink pallmall star > r10 $c star swede color dog star > r11 $c star norwegian color animal drink cigarette nation blue star > r12_0 $c star blue animal drink cigarette norwegian star > r12_1 $c star blue horse star > r13 $c star beer winfield star > r14 $c star green animal coffee star > r15 fstunion r5_0 r5_1 > r5 fstunion r9_0 r9_1 > r9 fstunion r12_0 r12_1 > r12
ルール5、9、および12は複合です。 各部分を個別に定義してから、結合を行います。 concat.shスクリプトは、引数で渡されたマシンを連結するだけです。
cp empty _c for i in $*; do fstconcat _c $i _c done; cat _c; rm _c;
したがって、出力では、オートマトンr1、r2 ...、r15が得られます。 すべてが最終ステップの準備ができています。
ステップ1-交差点
./intersect.sh r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 > result
intersection.shは、引数内のオートマトンの交差点です。
cp cl _c for i in $*; do fstintersect _c $i _c done; cat _c; rm _c;
これは終了する可能性があります-機械を見て、魚が誰であるかを調べます。 しかし、最初から1つのことを考慮していませんでした-私のルールでは、各単語を繰り返すことができます。 たとえば、2人でビールを1杯飲み、動物を1匹始めることができます。 これは、問題の条件下では当てはまりません。 このようなフィルターの作成は、次のように通常の言語を使用すると非常に不便です。 そのような言葉がすでに存在していたことを「思い出す」方法はありません。 しかし、どういうわけかそれを制限する必要があります。 したがって、最終結果を次のスクリプトに公開します。
i="./intersect.sh" d="fstdifference" for i in `cat alph`; do fstdifference cl $i > differ fstconcat differ $i | fstconcat - differ | fstrmepsilon - | fstdeterminize - | fstminimize - > ${i}_cont done cp result out for i in `ls *_cont`; do echo $i fstintersect $i out | fstrmepsilon - | fstdeterminize - | fstminimize - out done rm differ rm *_cont
このスクリプトは、アルファベットの各単語に対して特別なavtomatを作成し、結果に適用します。 したがって、単語が繰り返されるパスは一掃されます。 その結果、最終結果（および実際には「出力」マシン）は次のようになります。
これはマシンの部分的なイメージです（すべてが適合しませんでした）。 5ワードごとにホームが定義されます。 図からわかるように、ドイツの繁殖魚。
おわりに
ここに問題を解決するためのそのような異常な方法があります。 しかし、とりわけ、彼は通常の言語が非常に強力なものであることを示しています。 さらに、Ulmanによると、 数学的な問題は、特定の言語で文字列を見つけることで表現できます 。 示された。
PSとはい、MSEは本当に倒錯について多くを知っています:)