Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 Site Related Forums
 The Yak Corral
 Obsession #174

Author  Topic 

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 06:07:57
This is it.
My current solution works OK but it is t o o slow (my current results).
Any crucial ideas for speeding it up will be greatly ... and so on.

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2004-07-22 : 06:39:49
Is there a Russian version of this page where the description makes sense?
Edit: Ah, I think I see the tacit assumption that they were making!
The input rows are in the order they were built.
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 06:58:04
Arnold,

I agree with you.. seems it was written by some f.y. linguists.
The main (missed) point of description is that coordinates of walls
in st. input are ordered asc by "time of their creation". You must determine the very first wall that closed a piece of land.
In their sample input the 3rd wall close up a trianle (along with two first walls). But between e.g. the 2nd and 3rd walls would may be e.g. 1000 other walls (single walls, some zigzag like figures and s.o.)
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 07:07:13
Forgot.. there is no russian version.
>I see the tacit assumption that they were making!
I got known this fact from other side-source.
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2004-07-22 : 07:13:18
quote:
two walls can cross only by ends, and walls can't coincide

Do you read this to mean that the input will not contain lines where an endpoint of one line abuts the middle of another line?
i.e. Would something like this:
0022
1011
be disallowed in the input?

I presume that it doesn't disallow >2 line ends at a point?
i.e. Something like this:
0011
1122
1011
would be allowed?
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 07:34:51
0011
1122
1011
would be allowed?

I can bet it is ALLOWED! Otherwise it would be big simplification
of the whole thing!
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 07:41:10
Also, compare my results with results of this man.
I know his algorithm is better than mine and stopped at 5th test but not enough to be accepted.
ps I even dont know how many tests for this problem
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 07:49:18
0022
1011

and of course it is NOT allowed!
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 08:25:41
>and walls can't coincide

think this means that

6 7 88 203000
6 7 88 203000

not allowed.

oh! btw my compilation errors because I write, edit & "test"
my delphi (i dont know C) code in Notepad - have no delphi on
my machines.
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2004-07-22 : 10:10:27
How does your current solution work??

Corey
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 12:00:23
Corey,
if you mean the text of my pascal code then here it is.
Just imagine: complexety of my algorithm is abt. O(N^3), i.e., abt. (200'000)^3,
and I was going to crack this huge number for 3 secs (btw., their testing processor is PIII-666 MHz).
Rare impunity I demonstrate........

program Walls;
{$APPTYPE CONSOLE}
uses SysUtils;

label metka1, metka2; (* in Russian "metka" means "label" :) *)
var
a: array[1..200000, 1..5] of longint;
i, j, k, ss, s1, s2, N: longint;

begin

readln(N);
readln(a[1, 1], a[1, 2], a[1, 3], a[1, 4]);

ss := 1; a[1, 5] := ss;
s1 := 0; s2:= 0;

for i := 2 to N do
begin
readln(a[i, 1], a[i, 2], a[i, 3], a[i, 4]);

for j := 1 to i - 1 do
if
((a[i, 1] = a[j, 1]) and (a[i, 2] = a[j, 2])) or
((a[i, 1] = a[j, 3]) and (a[i, 2] = a[j, 4])) then
begin s1 := a[j, 5]; goto metka1; end;
metka1:

for j := 1 to i - 1 do
if
((a[i, 3] = a[j, 1]) and (a[i, 4] = a[j, 2])) or
((a[i, 3] = a[j, 3]) and (a[i, 4] = a[j, 4])) then
begin s2 := a[j, 5]; goto metka2; end;
metka2:

if (s1 = 0) and (s2 = 0) then
begin ss := ss + 1; a[i, 5] := ss; end
else
if (s1 <> 0) and (s2 = 0) then begin a[i, 5] := s1; s1 := 0; end
else
if (s1 = 0) and (s2 <> 0) then begin a[i, 5] := s2; s2 := 0; end
else
if s1 = s2 then begin write(i); halt; end
else
begin
a[i, 5] := s1;
for k := 1 to i - 1 do
if a[k, 5] = s2 then a[k, 5] := s1;
s1 := 0; s2:= 0;
end;
end;

write(0);
end.
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2004-07-22 : 12:34:48
Cool! I'll have a look at that later...
Go to Top of Page

SamC
White Water Yakist

3467 Posts
Posted - 2004-07-22 : 12:54:19
Is it impossible to find a solution using set-based SQL?
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-07-22 : 13:48:45
i think i have it .... i'll post soon ...

- Jeff
Go to Top of Page

SamC
White Water Yakist

3467 Posts
Posted - 2004-07-22 : 13:53:18
Ahh. The Dr. is at it again...
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-07-22 : 14:08:15
how's this:


-- this is the table of walls:
declare @t table (Step int primary key, X1 int, Y1 int, X2 int, Y2 int)

insert into @t
select 1,0,0,1,0 union
select 2,0,1,0,0 union
select 3,1,0,0,1 union
select 4,2,2,5,7

-- our working table:
declare @paths table (Path int, X int, Y int)

declare @i int;
set @i =1;

-- now loops through the walls table:

while (@i <= (select count(*) from @t))
   begin

   -- with each wall's coordinates, check versus our paths table
   -- to determine if it closes any up.
   --
   -- if both sets of coordinates exist for a given path, then
   -- we know we are done -- this wall will close up a region:  
   if exists(
     select path 
     from @paths a
     inner join @t b
        on (a.x=b.x1 and a.y=b.y1) or (a.x=b.x2 and a.y=b.y2)
     where
        step = @i
     group by path
     having count(*) = 2 )
   begin
      print 'done at step: ' + convert(varchar(10), @i)
      break
   end

   -- If either of these two points exist in an existing path,
   -- add the other point to that path:
   insert into @Paths (path, x,y)
   select p.Path, a.OtherX, a.OtherY
   from 
     (select Step, x1 as x, y1 as y, x2 as OtherX, y2 as OtherY from @t union
      select Step, x2, y2, x1 as OtherX, y1 as OtherY from @t) a
   inner join
     @Paths p
   on 
      p.x = a.y and p.y = a.y
   where Step = @i

   -- if the above didn't add anything, then we have a new distinct wall
   -- with no connections.  So, start a new path:
   if (@@rowcount = 0)
       insert into @Paths (path, x,y)
       select isnull((select max(path) from @paths),0)+1, x,y
       from      
           (select Step, x1 as x, y1 as y from @t union
            select Step, x2, y2 from @t) a
       where
           a.Step = @i
 
  -- here's how our table is looking:
   select * from @Paths

   -- and continue onward ....
   set @i = @i +1
   end


Does it work for all cases? is the alorgithm sound? don't know !

(it looks much longer than it really is, with all the comments ...)

- Jeff
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 14:09:25
Jeff, Sam,
if you mean pure SQL then I give up.....
As to D-SQL, then my dummy straightforward solution
can be easily rewritten on it (but it's very inefficient -
in fact efficiency is the main point of the thing).
Next thing. Where can we get good test data?
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-07-22 : 14:11:45
Stoad -- by the way, it is great to have you back, haven't seen you for a while.

yes -- we need some good sample data. i will try to generate some ...

- Jeff
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-07-22 : 14:14:00
based on the rules (no walls can intersect, no walls can touch anywhere except at the ends) it becomes a simple graph problem.

think of it as:

a - b
b - c
a - c

instead of in terms of coordinates -- makes it much easier. Or am I wrong with this assumption?

- Jeff
Go to Top of Page

Stoad
Freaky Yak Linguist

1983 Posts
Posted - 2004-07-22 : 14:18:18
Thanks Jeff, glad to see you in fine p & m shape.. I was/am lost in some obsessions.
Now I'll examine your d-sql (i was scared waiting for a non-d-sql solution).
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-07-22 : 14:24:26
not sure what you mean by d-sql, my solution is pretty much 100% SQL ... no cursor, nothing dynamic. there is a loop but that was unavoidable due to recursion requirements.

I am still testing with other sets of points, so far so good.

The alogorithm:

definition: a "Path" is a distinct set of points.

for each wall
- check to see if both points exist in a "path"
- if both exist in 1 path then this wall forms an enclosure and you are done
- for all existing paths in which 1 point from this wall exists, add the other point to that path
- if the above step added no entries, create a new path and put both points from the wall in it
- EDIT: merge paths that intersect (see below)
continue until no walls left

a more storage efficient alogorithm would check for paths that can be "merged", which this doesn't do ... but that is unnecessary.

EDIT: it IS necessary, as I think about it and as Stoad points out ... that step must be added to the algorithm. However, it is not currently present in my t-sql code until i think of the most efficient way to do it .


- Jeff
Go to Top of Page
    Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources

Articles

Forums

Blogs

Contact Us

About the Site