# ‘D’atabases : The Hidden ‘D’NA of our lives

February 15th, 2011

### Almost TSP!! : Travelling Salesman Problem Solution through PL/SQL

Posted by Ritesh Anand in Uncategorized

Hi!!!!

/* PROBLEM STATEMENT

Here, the salesman is given the distance chart by his/her manager based on which

(s)he has to cover all the cities in the distance chart but ensure that (s)he

covers the MINIMUM DISTANCE. For better text, read http://en.wikipedia.org/wiki/Travelling_salesman_problem.

*/

/

drop table salesmans_scrambled_dist_chart;

create table salesmans_scrambled_dist_chart

(

source      varchar2(5),

destination varchar2(5),

distance    number(5,0)

);

truncate table salesmans_scrambled_dist_chart;

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-DEL-’,250);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-PTN-’,700);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-GYA-’,800);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-ALD-’,300);

insert into salesmans_scrambled_dist_chart values (‘-GYA-’,‘-ALD-’,500);

insert into salesmans_scrambled_dist_chart values (‘-ALD-’,‘-PTN-’,333);

insert into salesmans_scrambled_dist_chart values (‘-ALD-’,‘-DEL-’,601);

insert into salesmans_scrambled_dist_chart values (‘-GYA-’,‘-PTN-’,100);

insert into salesmans_scrambled_dist_chart values (‘-PTN-’,‘-DEL-’,1050);

insert into salesmans_scrambled_dist_chart values (‘-DEL-’,‘-GYA-’,1100);

commit;

create or replace view v_distance_chart as

select distinct

source,

destination,

distance

FROM

(

SELECT

source,

destination,

distance

FROM

salesmans_scrambled_dist_chart

UNION ALL

SELECT

destination AS source,

source  AS destination,

distance

FROM

salesmans_scrambled_dist_chart);

/

create or replace view v_all_cities as

select

city,

rownum as sno

from

(select distinct

source as city

from

v_distance_chart);

/

drop table all_cities;

create table all_cities

(

sno   number(2,0),

city  varchar2(5)

);

truncate table all_cities;

insert into all_cities(sno, city) select sno, city from v_all_cities;

commit;

/

create or replace package pkg_salesman_scramble is

procedure scramble_cities;

function get_sql_city_sequence return varchar2;

end pkg_salesman_scramble;

/

create or replace package body pkg_salesman_scramble is

procedure scramble_cities is

v_retval    number(2,0);

begin

dbms_output.put_line(‘uninplemented!!!’);

end scramble_cities;

function get_sql_city_sequence return varchar2 is

v_sql_stmt        varchar2(4000);

v_sql_col1        varchar2(1000);

v_sql_col2        varchar2(1000);

v_sql_tbl         varchar2(500);

v_sql_where       varchar2(1500);

v_no_of_elements  number(2,0);

v_index                 number(2,0);

v_inner_index           number(2,0);

v_bool                  number(1,0);

v_pipe                  varchar2(4);

v_comma                 varchar2(3);

v_and             varchar2(5);

begin

v_bool := 0;

select count(*) into v_no_of_elements from all_cities;

v_pipe := ;

v_comma := ;

v_and := ;

for v_index in 1..v_no_of_elements

loop

–if v_index = v_no_of_elements

–then

v_index_X := 1;

–else

v_index_X := v_index + 1;

–end if;

v_sql_col1 := v_sql_col1 || v_pipe || ‘nvl(t’ || v_index || ‘.CITY,””)’;

if v_index > 1 then

v_sql_col2 := v_sql_col2 || v_add || ‘distance_between_cities(t’ ||  v_index || ‘.city, t’ || to_char(v_index - 1) || ‘.city)’;

else

v_sql_col2 := 0;

end if;

v_sql_tbl := v_sql_tbl || v_comma || ‘all_cities t’ || v_index;

v_inner_index := v_index + 1;

for v_inner_index in v_index + 1 .. v_no_of_elements

loop

if v_bool = 1 then

v_pipe := ‘ || ‘;

v_add := ‘ + ‘;

v_comma := ‘ , ‘;

v_and := ‘ AND ‘;

end if;

v_sql_where :=  v_sql_where || v_and || ‘ t’|| v_index ||‘.SNO != t’|| v_inner_index ||‘.SNO ‘;

v_bool := 1;

end loop;

end loop;

–v_sql_stmt := ’select CITY as combinations from scrambler_2011 where sno != 0 union all ‘;

v_sql_stmt :=  v_sql_stmt ||‘ select ‘ || v_sql_col1 ||‘ as route, ‘ || v_sql_col2 ||‘ as distance_to_be_covered FROM ‘ || v_sql_tbl || ‘ WHERE ‘ || v_sql_where || ‘ order by distance_to_be_covered’;

return(v_sql_stmt);

end get_sql_city_sequence;

end pkg_salesman_scramble;

/

create or replace function distance_between_cities( v_city1 varchar, v_city2 varchar) return number is

v_retval    number(5,0);

begin

select

distance into v_retval

from v_distance_chart

where

source = v_city1

and   destination = v_city2;

return v_retval;

end distance_between_cities;

/

– select pkg_salesman_scramble.get_sql_city_sequence() from dual; — pick the output and execute the dynamic sql, say str_dyn_sql so generated.

– execute str_dyn_sql

February 14th, 2011

### Oracle Package / Stored Procedure to generate distinct scrambled combination of given elements

Posted by Ritesh Anand in Uncategorized

Due to my ‘lazy’ mind fidgeting around, I came up with the following

1. the following article gives the complete code (yes, it’s redistributable!) to generate the distinct alphabets that are possible, if the list of alphabets to be used are known [in the table - elements_for_scramble] (through Oracle PL/SQL - pkg_scrambler )
2. as a part of solving the business problem, you will also learn the basics of SQL and  PL/SQL in oracle).

So, without further ado, here it goes:

/

drop table elements_for_scramble;

/

create table elements_for_scramble

(

sno     number(5,0),

avlbl_alphabet  varchar2(5)

);

/

truncate table elements_for_scramble;

insert into elements_for_scramble values (0,NULL); - THIS IS THE CRITICAL PIECE. SPEND SOME TIME TO UNDERSTAND THIS ENTRY.

insert into elements_for_scramble values (1,‘O’);

insert into elements_for_scramble values (2,‘N’);

insert into elements_for_scramble values (3,‘E’);

insert into elements_for_scramble values (4,‘K’);

commit;

/*

=: FRAMEWORK - for 3 elements in the elements_for_scramble table. :=

select

AVLBL_ALPHABET as combinations

from

elements_for_scramble

where

sno   != 0

union all

select distinct

t1.AVLBL_ALPHABET|| t2.AVLBL_ALPHABET || t3.AVLBL_ALPHABET as combinations

from

elements_for_scramble t1,

elements_for_scramble t2,

elements_for_scramble t3

where

(     t1.sno != t2.sno

AND   t1.sno != t3.sno

AND   t2.sno != t3.sno);

*/

–=: GENERIC :=

create or replace package pkg_scrambler is

procedure scramble_elements;

function get_sql_stmt return varchar2;

end pkg_scrambler;

/

create or replace package body pkg_scrambler is

v_no_elements     number(2,0);

begin

dbms_output.put_line(‘Hello!’);

procedure scramble_elements is

v_sql_stmt        varchar2(4000);

begin

v_sql_stmt := get_sql_stmt();

execute immediate v_sql_stmt;

end scramble_elements;

function get_sql_stmt return varchar2 is

v_sql_stmt        varchar2(4000);

v_sql_col1        varchar2(1000);

v_sql_col2        varchar2(1000);

v_sql_tbl         varchar2(500);

v_sql_where       varchar2(1500);

v_no_of_elements  number(2,0);

v_index                 number(2,0);

v_inner_index           number(2,0);

v_bool                  number(1,0);

v_pipe                  varchar2(4);

v_comma                 varchar2(3);

v_and             varchar2(5);

begin

v_bool := 0;

select count(*) - 1 into v_no_of_elements from elements_for_scramble;

for v_index in 1..v_no_of_elements

loop

–if v_index = v_no_of_elements

–then

v_index_X := 1;

–else

v_index_X := v_index + 1;

–end if;

v_sql_col1 := v_sql_col1 || v_pipe || ‘nvl(t’ || v_index || ‘.AVLBL_ALPHABET,””)’;

v_sql_col2 := v_sql_col2 || v_pipe || ‘to_char(t’ || v_index || ‘.SNO)’;

v_sql_tbl := v_sql_tbl || v_comma || ‘elements_for_scramble t’ || v_index;

v_inner_index := v_index + 1;

for v_inner_index in v_index + 1 .. v_no_of_elements

loop

if v_bool = 1 then

v_pipe := ‘ || ‘;

v_comma := ‘ , ‘;

v_and := ‘ AND ‘;

else

v_pipe := ;

v_comma := ;

v_and := ;

end if;

v_sql_where :=  v_sql_where || v_and || ‘ (t’|| v_index ||‘.SNO != t’|| v_inner_index ||‘.SNO OR t’|| v_index ||‘.SNO = 0)’;

v_bool := 1;

end loop;

end loop;

–v_sql_stmt := ’select AVLBL_ALPHABET as combinations from elements_for_scramble where sno != 0 union all ‘;

v_sql_stmt :=  v_sql_stmt ||‘ select distinct ‘ || v_sql_col1 || ‘ as combination_AVLBL_ALPHABET,’ || v_sql_col2 ||‘ as SNO FROM ‘ || v_sql_tbl || ‘ WHERE ‘ || v_sql_where ;

v_sql_stmt := ’select distinct combination_AVLBL_ALPHABET from (’ || v_sql_stmt || ‘) where combination_AVLBL_ALPHABET IS NOT NULL ORDER BY length(combination_AVLBL_ALPHABET), combination_AVLBL_ALPHABET;’;

return(v_sql_stmt);

end get_sql_stmt;

end pkg_scrambler;

/

• ## Meta

Bad Behavior has blocked 491 access attempts in the last 7 days.