NB. Breadth-first Search wr =: 1!:2&2 rd =: 1!:1 NB. Data =============================== NB. A - B - D - F NB. | | | NB. + - C - E - G head =: {. behead =: }. tail =: {: curtail =: }: index_of =: i. ~ NB. Interval Data Base DA =: 'AB';'AC';'BC';'BD';'CE';'DE';'DF';'EG' DC =: 'AB';'AC';'BC';'BG' NB. New Version / OK! - 2013/11/9 -------------------------------- DC1 =: 'AB';'AC';'BC';'CB';'BG' DA1 =: 'AB';'AC';'BC';'CB';'BD';'DE';'CE';'EC';'DE';'ED';'DF';'EG' NB. e.g. DC1 make <'AB' => NB. +---+---+ NB. |ABC|ABG| NB. +---+---+ NB. DC1 make <'AC' => NB. +---+ NB. |ACB| NB. +---+ make =: 3 : 0"(1 0) : DB =. x. if. 0 = # > y. do. '' return. end. NB. revised 2013/11/12 Key =. tail > y. Lk =. Key -.~ (> Key e. L:0 DB)#DB LL =. Lk -. y. LLL =. (Key = > head L:0 LL) # LL LR =. ~. (< curtail > y.) ,L:0 (LLL) tdouble =. */ L:0 ~: L:0 LR NB. test of double LR =. (> tdouble) # LR ) breadth =: 3 : 0 : DB =. x. Level =. y. D =. <'A' j =. 0 while. j < Level do. wr 'Level: ', ": j D =. , DB make D wr D wr testD =. # L:0 D wr tt =. (j + 2) = L:0 testD wr (, > tt) # D j =. j + 1 end. '*** end. ***' ) search =: 3 : 0 : DB =. x. 'Start Goal' =. y. D =. Start Level =. 10 j =. 0 while. j < Level do. NB. wr 'Level: ', ": j D =. , DB make"(1 0) D testD =. # L:0 D tt =. (j + 2) = L:0 testD NB. wr (#D), (#> tt) if. (#D) ~: (#> tt) do. '*** end ***' return. end. D =. (, > tt) # D NB. wr D Hit =. (> Goal e. L:0 D) # D if. 0 < #Hit do. wr > Hit end. j =. j + 1 end. '*** end ***' ) NB. rename for comparing Prolog calc. 2013/11/30 ============================ WAY =: 'ab';'bc';'ae';'ef';'fe';'bf';'fb';'fg';'gf';'cg';'gc';'eh';'hi';'ih';'fi';'if';'ij';'gj' NB. Hiro's Home Page ============================================ WAYH =: 'ab';'bc';'cb';'af';'ae';'eh';'he';'hi';'ih';'ij';'ji';'jk';'ef';'fe';'fi';'if';'fg';'gf';'fb';'bf';'fj';'jf';'gj';'jg';'gc';'cg';'cd' NB. (way data) route ('Start, Goal') route =: 3 : 0 : DB =. x. Level =. 50 'Start Goal' =. y. D =. Start HN =. 1 j =. 0 while. j < Level do. NB. wr 'Level: ', ": j D =. , DB make D testD =. # L:0 D tt =. (j + 2) = L:0 testD NB. wr (#D), (#> tt) if. (#D) ~: (#> tt) do. goto_fin. end. D =. (, > tt) # D if. 0 = #D do. goto_fin. end. Hit =. (> Goal = L:0 (tail @ ,) L:0 D) # D if. 0 < #Hit do. HNO =. HN + i. # Hit HNN =. ,. HNO NN =. ((# Hit),3)$'No.' NNN =. NN ,. ": HNN NB. wr > Hit HH =. ' ',"(0 1) > Hit NB. wr '-------' wr NNN ,. HH end. HN =. HN + # Hit j =. j + 1 end. label_fin. '*** ', (": {: HNO), ' routes found ***' ) RD3 =: 3 3$'ABCDEFGHI' NB. , 2 <\ "(1) RD3 NB. +--+--+--+--+--+--+ NB. |AB|BC|DE|EF|GH|HI| NB. +--+--+--+--+--+--+ NB. <"(1) |: ,. > |: (L:0) 2 <\ RD3 NB. +--+--+--+--+--+--+ NB. |AD|DG|BE|EH|CF|FI| NB. +--+--+--+--+--+--+ NB. connect vertex to interval data ============================= condata =: 3 : 0 C0 =. , 2 <\ "(1) y. C1 =. , 2 <\ "(1) |: y. C0, C1 (] , (|. L:0)) C0, C1 ) WAY3 =: condata RD3 RD4 =: 4 4$'ABCDEFGHIJKLMNOP' WAY4 =: condata RD4 RD5 =: 5 5$'ABCDEFGHIJKLMNOPQRSTUVWXY' WAY5 =: condata RD5