こんにちは。 宣言型アプローチを説明することで長い間あなたの注意を保持しません。問題の定式化とその解決策を宣言的に見るためのオプションとして、論理プログラミング言語を使用してもう1つの問題を解決することを提案します。

タスク391. 完全な長方形

N> 0のN軸に沿った長方形が与えられた場合、それらがすべて一緒に長方形領域の正確なカバーを形成するかどうかを決定します。

各長方形は、左下のポイントと右上のポイントとして表されます。 たとえば、単位正方形は[1,1,2,2]として表されます。 （左下の点の座標は（1、1）で、右上の点の座標は（2、2）です）。



例1：長方形= [

[1,1,3,3]、

[3,1,4,2]、

[3,2,4,4]、

[1,3,2,4]、

[2,3,3,4]]

trueを返します。 5つの長方形はすべて、長方形の領域の正確なカバーを形成します。

...

例3：長方形=

[[1,1,3,3]、

[3,1,4,2]、

[1,3,2,4]、

[3,2,4,4]]

falseを返します。 上部中央に隙間があるためです。

文言を考えると、2日目が過ぎますが、これは確かにビンテージランプをオンにする1週間のレッスンではありませんが、それでもタスクの作業の結果を提示したいと思います。 使用可能なすべてのテストを解決するには、いくつかの試みが必要でした。

初期データはリストで表されます。簡単に説明すると、 リストは[Head | Tail]です。Tailはリストで、リストも空[]です。

策定します1

すべての長方形が面積を均一にカバーすることを意味する場合、すべての長方形の合計面積を計算し、それらすべてを記述する長方形の最大サイズを見つけ、これら2つの合計を比較する必要があります。 同時に、長方形が交差していないことを確認します。新しい長方形をリストに追加します。条件により、前の長方形すべてと重ならないようにします。

これを行うには、サイクルを表すための最も「命令的な」方法であるテール再帰（降下時の再帰）を使用します。 そのような「サイクル」では、面積の合計量と、記述している長方形の最小左角と最大右角をすぐに見つけ、ハイキングし、図の一般的なリストを蓄積し、交差点がないことを確認します。

このように：

findsum([], Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T], Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectList):- mincon(Lx:Ly,LConerCur,LConerCur2), maxcon(Rx:Ry,RConerCur,RConerCur2), Scur2 is Scur+(Rx-Lx)*(Ry-Ly), not(chekin([Lx,Ly,Rx,Ry],RectList)), findsum(T, Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,[[Lx,Ly,Rx,Ry]|RectList]).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Prologでは、変数は不明であり、変更することはできません。空または値があります。これには、初期変数と結果変数が必要です。リストの最後に到達すると、現在の値が結果になります（ルールの最初の行）。 命令型言語とは異なり、 サポートする プログラム行を理解するには、それに至るまでのパス全体を想像する必要があります。すべての変数は、独自の累積の「履歴」を持つことができます。プログラムの各行は、現在のルールのコンテキスト、それに影響するすべての状態にのみ存在します あります エントリールール。

だから：

 %   mincon(X1:Y1,X2:Y2,X1:Y1):-X1=<X2,Y1=<Y2,!. mincon(_,X2:Y2,X2:Y2). %  maxcon(X1:Y1,X2:Y2,X1:Y1):-X1>=X2,Y1>=Y2,!. maxcon(_,X2:Y2,X2:Y2).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、角度を表すために、X：Yの形式の「構造化された用語」が使用されます。いくつかの値を構造に結合する機会です。 また、「！」をクリッピングすると、ルールの2行目に条件を指定しないようにできます。これにより、計算の効率が向上します。

そして判明したように、最も重要なことは、長方形の交差していない部分をチェックすることです。それらはリストに蓄積されます。

 %    chekin(X,[R|_]):-cross(X,R),!. chekin(X,[_|T]):-chekin(X,T). %     ,    cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). %,       cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11<Y22,Y22=<Y12,!.%rt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11<Y22,Y22=<Y12,!.%lt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11=<Y21,Y21<Y12,!.%rb cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11=<Y21,Y21<Y12. %lb
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

長方形の交差点。これらは、最初の頂点を他の内側にヒットするための4つのオプションです。

そして最後の声明：

 isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= (RconerX-LconerX)*(RconerY-LconerY).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

入力である数字のリストで、左と右の角度の初期値の最初の値を取得し、すべてを調べて合計面積を計算し、結果の量を比較します。 長方形の交差点があった場合、量の検索は「失敗」し、「落下」を返します。これは、量を比較するものがないことを意味します。 入力リストに単一の数字がない場合、同じことが起こります。失敗があり、検証するものはありません...

次に、既存のテストでこの実装を実行し、最初の40を引用します。

 %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]),true). :-assert_are_equal(isRectangleCover([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[0,0,4,1]]),false).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[2,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,3,2],[1,0,2,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[0,3,1,4]]),true). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[2,0,3,1],[3,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,2,2],[1,1,3,3],[2,0,3,1],[0,3,3,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[1,0,2,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,2,1],[0,1,2,2],[0,2,1,3],[1,0,2,1]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[0,1,1,2],[1,0,2,1],[0,2,3,3],[2,0,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,4],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,3],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,5,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,2,1,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,4,4],[1,3,4,5],[1,6,4,7]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[2,0,3,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[1,1,2,2],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[2,1,3,2],[2,1,3,2],[2,1,3,2],[3,1,4,2]]),false). :-assert_are_equal(isRectangleCover([[0,1,2,3],[0,1,1,2],[2,2,3,3],[1,0,3,1],[2,0,3,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,2,1,3],[1,1,2,2],[2,0,3,1],[2,2,3,3],[1,0,2,3],[0,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[1,0,2,1],[1,0,2,1],[1,2,2,3],[2,0,3,1],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[-1,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[1,0,3,1],[3,0,4,1]]),false). :-assert_are_equal(isRectangleCover([[1,2,4,4],[1,0,4,1],[0,2,1,3],[0,1,3,2],[3,1,4,2],[0,3,1,4],[0,0,1,1]]),true).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、これは終わりではありません。「ハード」セクションのタスクは、41個のテストで10,000個の長方形のリストを提供します。

 test 41:length=10000 goal->ok:212/sec test 42:length=3982 goal->ok:21/sec test 43:length=10222 goal->ok:146/sec test 44:length=10779 goal->ok:41/sec test 45:length=11000 goal->ok:199/sec
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

入力値を取り込むことができず、エディターに適合しません。このようにテスト41を添付します。

言葉遣い2

リストを使用して数字を蓄積する以前のアプローチは、非常に効果がないことがわかりました。この変更は、複雑さn ^ 2ではなく、n * log（n）を示しています。 ツリーを使用して、四角形のリストの交差を確認できます。

Prologのバイナリツリーも構造化された用語であり、リストとして再帰的に定義されているため、 ツリーは空であるか、値と2つのサブツリーを含んでいます 。

このために、トリプルファンクタt（LeftTree、RootValue、RightTree）を使用します。空のツリーは[]になります。

左の順序が小さく、右の順序が大きい単純な数値ツリーは、次のように表現できます。

 add_to_tree(X,[],t([],X,[])). add_to_tree(X,t(L,Root,R),t(L,Root,NewR)):- X<Root,!,add_to_tree(X,R,NewR). add_to_tree(X,t(L,Root,R),t(NewL,Root,R)):- add_to_tree(X,L,NewL).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

I. Bratkoの古典的な本「人工知能のためのPrologでのプログラミング」には、AVLによってバランスがとれた2〜3本の木の多くの実現があります。

次のように長方形の順序付けの問題を解決することを提案します。長方形が他の長方形の右側にある場合、それらは交差せず、左側にある長方形の交差をチェックする必要があります。 そして、右側では、1つの右隅が2番目の左隅よりも小さい場合です。

 righter([X1,_,_,_],[_,_,X2,_]):-X1>X2.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、ツリーに図形を蓄積し、さらに交差をチェックするタスクは、新しい長方形がルートにある長方形の右側にある場合、右にチェックする必要があります。そうでなければ、左に交差をチェックする必要があります。

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すぐに別のものを考慮 トリック 長方形の幅が同じで、共通の面を持っている場合、それらを1つに結合してツリーに追加せずに、1つのノードの長方形のサイズを変更するだけです。 テスト41はこれをプッシュしています。[[0、-1,1,0]、[0,0,1,1]、[0,1,1,2]、[0,2,1、 3]、[0,3,1,4]、[0,4,1,5]、[0,5,1,6]、[0,6,1,7]、[0,7,1、 8]、[0,8,1,9]、[0,9,1,10]、[0,10,1,11]、[0,11,1,12]、[0,12,1、 13]、[0,13,1,14]、...、[0,9998,1,9999]]。

これらの改善を以前のソリューションと組み合わせて、いくつか改善を加えて完全に提供します。

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. findsum([],Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T],Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectTree):- coner(Lx:Ly,LConerCur,=<,LConerCur2), coner(Rx:Ry,RConerCur,>=,RConerCur2), Scur2 is Scur+abs(Rx-Lx)*abs(Ry-Ly), treechk([Lx,Ly,Rx,Ry],RectTree,RectTree2),!, findsum(T,Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,RectTree2). isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= abs(RconerX-LconerX)*abs(RconerY-LconerY). coner(X1:Y1,X2:Y2,Dir,X1:Y1):-apply(Dir,[X1,X2]),apply(Dir,[Y1,Y2]),!. coner(_,XY,_,XY). cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). cross2([X11,Y11,X12,Y12],[_,_,X22,Y22]):-X11<X22,X22=<X12, Y11<Y22,Y22=<Y12,!. %right-top cross2([X11,Y11,X12,Y12],[X21,_,_,Y22]):-X11=<X21,X21<X12, Y11<Y22,Y22=<Y12,!. %left-top cross2([X11,Y11,X12,Y12],[_,Y21,X22,_]):-X11<X22,X22=<X12, Y11=<Y21,Y21<Y12,!. %right-bottom cross2([X11,Y11,X12,Y12],[X21,Y21,_,_]):-X11=<X21,X21<X12, Y11=<Y21,Y21<Y12. %left-bottom
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「重い」テストの実行時間は次のとおりです。

 goal-true->ok:0/sec 41:length=10000 goal-true->ok:0/sec 42:length=3982 goal-true->ok:0/sec 43:length=10222 goal-true->ok:2/sec 44:length=10779 goal-false->ok:1/sec 45:length=11000 goal-true->ok:1/sec
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この改善を完了します。すべてのテストに正しく合格し、時間が十分です。 興味のある方は、 オンラインまたはこちらをお試しください。

合計

関数型プログラミングに関連する記事は、一定の頻度でポータルにあります。 宣言型アプローチの別の側面、つまり論理プログラミングに触れます。 論理的な説明を使用してタスクを表すことができます。事実とルール、前提と結果、関係、再帰関係があります。 タスクの説明は、それを記述する一連の関係に変換する必要があります。 結果は、問題をより単純なコンポーネントに分解した結果です。

宣言型言語のプログラムは、結果を作成する一連のステートメントとして使用できます。これは、成功した定式化における問題の解決策です。 最適化は、たとえば、長方形の交点を制御する方法の「カーソル」の説明に明確化が必要な場合があるため、より効率的な計算のためにツリー構造を構築することができます。

そして...ソースコードのスタイルからPrologが消えたどこかで、半年前にそれを使用しました。 「姉妹」アーランを指定する必要がありました。 しかし、それは「人気」のように見えません、FortranとBASICはリストにありません、言語の評価は何ですか？