Crazy or just plain fun Reader's Challenge? - SQL Server Forums

Home | Weblogs | Forums

Site Sponsored By: SQLDSC - SQL Server Desired State Configuration

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

Crazy or just plain fun Reader's Challenge?

Author

Topic

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-26 : 09:44:56

I watched Pirates Of The Caribbean yesterday, and I got an idea for a Reader's Challenge!

Write code to solve following problem.

The prelude is that you get yourself drunk at a bar and wake up at the Black Pearl. Your job is to cut some ropes between Black Pearl and the trading ship that is under attack, before boarding, or die.

The crew at Black Pearl, as skilled as they might be, also get drunk sometimes.
So at the moment of boarding, they position themself at the nearest battlestation on Black Pearl. This means that some battlestations on Black Pearl are not manned at all.

Before boarding, they throw their hooks and ropes across the gap between the two ships. As there can be more than one pirate at a battle station, they can throw their hooks and ropes to any battlestation at the trading ship. The pirates though, are skilled enough to never throw two or more ropes from their battlestation to the same trading ship battlestation! However, any other battlestation on Black Pearl can throw a rope to the same battlestation on the trading ship as any other battlestation on Black Pearl does.

This means that the ropes at some point are going to be tangled and crossed! Your job forced upon you is to cut some ropes so there can be no tangle, or crossed ropes.

You must to this as efficient as possible, that is to cut the minimum number of ropes as possible to keep as many ropes as possible left for boarding. The ropes not cut by you, must not be tangled nor crossed with any other rope. Also there can be no more than one rope from any Black Pearl battlestation after you have done cutting.

This Reader's Challenge can be stated as

1) There are m number of battlestations at the trading ship and n number of battlestations at the Black Pearl
2) There can be none, or any number of pirate at a battle station on Black Pearl.
3) The pirate, or pirates, at a battlestation can throw any number of hooks and ropes over to the trading ship, but never more than one rope to the same enemy battlestation. However, any other pirate battlestation can throw a hook and a rope to the same enemy battlestation.
4) You job is to keep as many ropes as possible left before boarding, by cutting a minimum amount of ropes so that the ropes left are not crossed nor tangled. Also to avoid confusion for the drunk pirates, there can be no more than one rope left from any Black Pearl battlestation. Also there can be no more than attached rope left at any trading shop battle station.

I hope I am clear with the prerequisites.

Here is an example

Here there are only pirates at battlestations (BS) 2 and 6 at the Black Pearl. BS2 now throw hooks and ropes to trading ship BS2 and BS4.
Also the BS6 at Black Pearl throws hooks and ropes to trading ship BS2 and BS4! In a matrix kind of view that can be represented as

Now you have two ropes from Black Pearl BS2 and two ropes from BS6. In this scenario you must cut the two ropes TS2-BP6 and TS4-BP2, because they cross or tangle. They are also confusing for the pirates, having more than one rope from their respectively battle station thrown to the enemies.

This example

Black Pearl BS1 throws a rope to trading ship BS1. BP BS2 throws a rope to TS BS4. BP BS4 throws a rope to TS BS6. BP BS5 throws a rope to both TS BS2 and TS BS7. BP BS6 throws a line to TS BS8. This matrix looks like

Here the rope TS2-BP5 crosses the ropes TS4-BP2 and TS6-BP4. Also there are two ropes from BP5. So with one swing with your knife, you cut the TS2-BP5 rope to save the other 5 ropes.

If you have any question, please post them.

How would your code look like to solve the problem stated?

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 03:43:23

Here is my swing at it.

DECLARE	@Test TABLE (ts INT, bp INT)

INSERT	@Test
SELECT	1, 1 UNION ALL
SELECT	2, 4 UNION ALL
SELECT	4, 2 UNION ALL
SELECT	6, 4 UNION ALL
SELECT	7, 5 UNION ALL
SELECT	8, 6

DECLARE	@Tangles TABLE (Row INT, ts1 INT, bp1 INT, ts2 INT, bp2 INT, Hits INT, m INT)

INSERT		@Tangles
		(
			ts1,
			bp1,
			ts2,
			bp2
		)
SELECT		m1.ts,
		m1.bp,
		m2.ts,
		m2.bp
FROM		@Test m1
INNER JOIN	@Test m2 ON m2.bp <= m1.bp AND m2.ts >= m1.ts OR m2.bp >= m1.bp AND m2.ts <= m1.ts

DECLARE @Hits TABLE (Row INT IDENTITY(0, 1), ts INT, bp INT, Hits INT)

INSERT		@Hits
		(
			ts,
			bp,
			Hits
		)
SELECT		m1.ts,
		m1.bp,
		SUM(CASE WHEN m2.bp <= m1.bp AND m2.ts >= m1.ts OR m2.bp >= m1.bp AND m2.ts <= m1.ts THEN 1 ELSE 0 END)
FROM		@Test m1
CROSS JOIN	@Test m2
GROUP BY	m1.ts,
		m1.bp
ORDER BY	3 DESC,
		ABS(m1.ts - m1.bp) DESC

UPDATE		t
SET		t.Row = h.Row,
		t.Hits = h.Hits,
		t.m = h.Hits
FROM		@Tangles t
INNER JOIN	@Hits h ON h.ts = t.ts1 AND h.bp = t.bp1

UPDATE		t
SET		t.m = (SELECT COUNT(*) FROM @Hits h WHERE h.ts = t.ts2 AND h.bp = t.bp2 AND h.Row > t.Row)
FROM		@Tangles t

SELECT		ts1 ts,
		bp1 bp,
		CASE WHEN MAX(m) > 0 THEN 'Cut' ELSE 'Keep' END Action
FROM		@Tangles
GROUP BY	ts1,
		bp1

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 08:55:47

fine fine... I'll bite.


DECLARE	@Test TABLE (ts INT, bp INT)

INSERT	@Test
--Select 1, 1 Union All Select 4, 2 Union All Select 6, 4 Union All Select 2, 5 Union All Select 7, 5 Union All Select 8, 6
SELECT 1, 1 UNION ALL SELECT 2, 4 UNION ALL SELECT 4, 2 UNION ALL SELECT 6, 4 UNION ALL SELECT 7, 5 UNION ALL SELECT 8, 6

Select * From @test

Declare @ts int,
	@bp int

While exists(Select * From @test A, @test B Where abs(sign(A.ts - B.ts) - sign(A.bp - B.bp))=2)
Begin
	Select top 1
		@ts = A.ts, @bp = A.bp
	From @test A, @test B
	Where abs(sign(A.ts - B.ts) - sign(A.bp - B.bp))=2
	Group By A.ts, A.bp 
	Order By count(*) desc
	
	Select 'Cut ts:' + convert(varchar,@ts) + ' bp:' + convert(varchar,@bp)

	Delete From @test Where ts = @ts and bp = @bp
End

Select * From @test

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 09:07:31

Strange... It doesn't work with first example {(2,2) (2,4) (6,2) (6,4)}.
(2,2) and (6,4) is kept and (2,4) and (6,2) is to be cut.

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 09:11:16

i'll check it...

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 09:16:03

This test data

should produce following output

6	1	Cut
4	3	Keep
3	4	Cut
7	4	Keep
8	5	Keep
9	6	Keep

or this is also acceptable

6	1	Keep
4	3	Cut
3	4	Cut
7	4	Keep
8	5	Keep
9	6	Keep

Why is the first more acceptable? It breaks the line of trading ship battle stations into smaller pieces.

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 09:31:38

Slightly revised:


DECLARE @Test TABLE (ts INT, bp INT)

INSERT @Test
Select 2, 2 Union All Select 2, 4 Union All Select 6, 2 Union All Select 6, 4
--Select 1, 1 Union All Select 4, 2 Union All Select 6, 4 Union All Select 2, 5 Union All Select 7, 5 Union All Select 8, 6
--SELECT 1, 1 UNION ALL SELECT 2, 4 UNION ALL SELECT 4, 2 UNION ALL SELECT 6, 4 UNION ALL SELECT 7, 5 UNION ALL SELECT 8, 6
--Select 3, 4 Union All Select 4, 3 Union All Select 6, 1 Union All Select 7, 4 Union All Select 8, 5 Union All Select 9, 6

Select * From @test

Declare @loop int,
	@ts int,
	@bp int

Set @loop = 2
While (@loop >= 1)
Begin
	While exists(Select * From @test A, @test B Where abs(sign(A.ts - B.ts) - sign(A.bp - B.bp))=@loop)
	Begin
		Select top 1 @ts = A.ts, @bp = A.bp
		From @test A, @test B
		Where abs(sign(A.ts - B.ts) - sign(A.bp - B.bp))=@loop
		Group By A.ts, A.bp 
		Order By count(*) desc
		
		Select 'Remove ts:' + convert(varchar,@ts) + ' bp:' + convert(varchar,@bp)
	
		Delete From @test Where ts = @ts and bp = @bp
	End

	Select @loop = @loop - 1
End

Select * From @test

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 09:55:07

Good!

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 10:06:21

Maybe it was too easy?

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 10:25:11

I don't know... i read the problem about 10 times before I could figure out what was desired. I think the details about pirates confused me

I did use 'sign' for the first time in a query...

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 10:30:17

Good for you!
I tought I had to contribute something, after I posted a solution to your Reader's Challenge with SSN substitution and replacement problem.

I have already found a use for this problem! And that is Levenstheins distance algorithm across a table, not just one word at a time.

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 14:33:11

quote:

I have already found a use for this problem! And that is Levenstheins distance algorithm across a table, not just one word at a time.

I'd really like to see where you get with this experiment... maybe I can contribute something else as well...

Edit: How do you plan on applying it to Levensthein's distance algorithm?

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 15:14:30

The ropes that are cut by my algorithm, are "false matches". Have them cut, only real matches between words are left.

123456
Jennie
Peter
12345

The matches here are {(2,2) (2,4) (6,2) (6,4)}. You want to remove (2,4) and (6,2), since they are "false matches". Left are (2,2) and (6,4).

For first word Jennie, the sequences left are 1 (J), 3-5 (nni).
For second word Peter, the sequences left are 1 (P), 3 (t) and 5 (r).

These sequences are grouped and ordered as

J    1
nni  2

and

P    1
t    2
r    3

For each group, we take the maximum size and add them. For Jennie/Peter, that gives

J    1  P  1
nni  2  t  3
     3  e  1

. The distance is 5!

Another example is Saturday/Sunday.

1 - S  S - 1
2 - a  u - 2
3 - t  n - 3
4 - u  d - 4
5 - r  a - 5
6 - d  y - 6
7 - a
8 - y

Matches are {(1,1) (2,5) (4,3) (6,4) (7,5) (8,6)}. Now (2,5) should be removed since it is a "false match" (the rope is crossed or tangled). Now sequences for Saturday is

1 - at n - 1  MAX 2
2 - r         MAX 1

Distance is 3!

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-28 : 15:48:32

Something like this

DECLARE	@Word1 VARCHAR(100),
	@Word2 VARCHAR(100)

SELECT	@Word1 = 'saturday',
	@Word2 = 'sunday'

DECLARE	@Test TABLE (ts INT, bp INT)

INSERT		@Test
		(
			ts,
			bp
		)
SELECT		w1.Number,
		w2.Number
FROM		(
			SELECT	DISTINCT Number,
				SUBSTRING(@Word1, Number, 1) c
			FROM	master.dbo.spt_values
			WHERE	Number BETWEEN 1 AND LEN(@Word1)
		) w1
FULL JOIN	(
			SELECT	DISTINCT Number,
				SUBSTRING(@Word2, Number, 1) c
			FROM	master.dbo.spt_values
			WHERE	Number BETWEEN 1 AND LEN(@Word2)
		) w2 ON w2.c = w1.c

DECLARE	@Tangles TABLE (Row INT, ts1 INT, bp1 INT, ts2 INT, bp2 INT, Hits INT, m INT)

INSERT		@Tangles
		(
			ts1,
			bp1,
			ts2,
			bp2
		)
SELECT		m1.ts,
		m1.bp,
		m2.ts,
		m2.bp
FROM		@Test m1
INNER JOIN	@Test m2 ON m2.bp <= m1.bp AND m2.ts >= m1.ts OR m2.bp >= m1.bp AND m2.ts <= m1.ts

DECLARE @Hits TABLE (Row INT IDENTITY(0, 1), ts INT, bp INT, Hits INT)

INSERT		@Hits
		(
			ts,
			bp,
			Hits
		)
SELECT		m1.ts,
		m1.bp,
		SUM(CASE WHEN m2.bp <= m1.bp AND m2.ts >= m1.ts OR m2.bp >= m1.bp AND m2.ts <= m1.ts THEN 1 ELSE 0 END)
FROM		@Test m1
CROSS JOIN	@Test m2
GROUP BY	m1.ts,
		m1.bp
ORDER BY	3 DESC,
		ABS(m1.ts - m1.bp) DESC

UPDATE		t
SET		t.Row = h.Row,
		t.Hits = h.Hits,
		t.m = h.Hits
FROM		@Tangles t
INNER JOIN	@Hits h ON h.ts = t.ts1 AND h.bp = t.bp1

UPDATE		t
SET		t.m = (SELECT COUNT(*) FROM @Hits h WHERE h.ts = t.ts2 AND h.bp = t.bp2 AND h.Row > t.Row)
FROM		@Tangles t

DECLARE	@ts TABLE (i INT, Grp INT)

INSERT		@ts
		(
			i
		)
SELECT		t.ts
FROM		@Test t
LEFT JOIN	(
			SELECT		ts1,
					bp1
			FROM		@Tangles
			GROUP BY	ts1,
					bp1
			HAVING		MAX(m) = 0
		) q ON q.ts1 = t.ts
WHERE		q.ts1 IS NULL
		AND t.ts IS NOT NULL

UPDATE		a
SET		a.Grp = q.Seq
FROM		@ts a
INNER JOIN	(
			SELECT		z.i,
					COUNT(y.i) Seq
			FROM		@ts z
			INNER JOIN	(
						SELECT		a.i 
						FROM		@ts a
						LEFT JOIN	@ts b ON a.i - 1 = b.i
						WHERE		b.i IS NULL
					) y ON y.i <= z.i
			GROUP BY	z.i
		) q ON q.i = a.i

DECLARE	@bp TABLE (i INT, Grp INT)

INSERT		@bp
		(
			i
		)
SELECT		t.bp
FROM		@Test t
LEFT JOIN	(
			SELECT		ts1,
					bp1
			FROM		@Tangles
			GROUP BY	ts1,
					bp1
			HAVING		MAX(m) = 0
		) q ON q.bp1 = t.bp
WHERE		q.bp1 IS NULL
		AND t.bp IS NOT NULL

UPDATE		a
SET		a.Grp = q.Seq
FROM		@bp a
INNER JOIN	(
			SELECT		z.i,
					COUNT(y.i) Seq
			FROM		@bp z
			INNER JOIN	(
						SELECT		a.i 
						FROM		@bp a
						LEFT JOIN	@bp b ON a.i - 1 = b.i
						WHERE		b.i IS NULL
					) y ON y.i <= z.i
			GROUP BY	z.i
		) q ON q.i = a.i

SELECT		SUM(Items)
FROM		(
			SELECT		COUNT(*) Items
			FROM		@ts a
			FULL JOIN	@bp b ON b.Grp = a.Grp
			GROUP BY	ISNULL(a.Grp, b.Grp)
		) x

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-28 : 16:28:32

I see that you worked a sample out as well...

I love the concept... very nicely thought out!

here is mine:


Declare @strList table (str2 varchar(100))
Insert Into @strList
Select 'Sunday' Union Select 'Monday' Union Select 'Tuesday' Union Select 'Wednesday' Union Select 'Thursday' Union Select 'Friday' Union Select 'Saturday' Union
Select 'January' Union Select 'February' Union Select 'March' Union Select 'April' Union Select 'May' Union Select 'June' Union Select 'July' Union Select 'August' Union Select 'September' Union Select 'October' Union Select 'November' Union Select 'December' Union
Select 'Robert' Union Select 'Corey' Union Select 'Peso' Union Select 'James' Union Select 'Matthew'

Declare @str1 varchar(100)
Set @Str1 = 'Jamie'

DECLARE	@Test TABLE (str2 varchar(100), char1 INT, char2 INT)

INSERT	@Test
Select B.str2, char1, char2 
From (Select charVal1 = substring(@str1,number,1), char1 = number From dbo.getSequence(1,100,1) Where number <= len(@str1)) A
Inner Join (Select Z.str2, charVal2 = substring(Z.str2,number,1), char2 = Y.number From @strList Z, dbo.getSequence(1,100,1) Y Where number <= len(Z.str2)) B
On A.charVal1 = B.charVal2

Declare @loop int,
	@str2 varchar(100),
	@char1 int,
	@char2 int

Set @loop = 2

While (@loop >= 1)
Begin
	While exists(Select * From @test A Inner Join @test B On A.str2 = B.str2 Where abs(sign(A.char1 - B.char1) - sign(A.char2 - B.char2))=@loop)
	Begin
		Select top 1 @str2=A.str2, @char1 = A.char1, @char2 = A.char2
		From @test A
		Inner Join @test B
		On A.str2 = B.str2
		Where abs(sign(A.char1 - B.char1) - sign(A.char2 - B.char2))=@loop
		Group By A.str2, A.char1, A.char2 
		Order By count(*) desc
		
		Delete From @test Where str2 = @str2 and char1 = @char1 and char2 = @char2
	End

	Select @loop = @loop - 1
End

Declare @distances table (segment int identity(1,1), str2 varchar(100), x int, y int)

Insert Into @distances (str2, x, y)
Select * From @test Union 
Select str2, 0, 0 From (Select distinct str2 From @test) A Union
Select str2, len(@str1)+1, len(str2)+1 From (Select distinct str2 From @test) A
Order By str2, 2

Select 
	str1 = @str1, 
	str2, 
	distance = case when distance <= len(str2) or distance <= len(@str1) then distance when len(str2) >= len(@str1) then len(str2) else len(@str1) end
From 
	(
	Select A.str2, distance = sum(case when B.x - A.x >= B.y - A.y then B.x - A.x else B.y - A.y end - 1)
	From @distances A
	Inner Join @distances B
	On A.str2 = B.str2 and
	A.segment+1 = B.segment
	Group By A.str2
	) Z
Order By 3

EDIT: Correction in blue

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-29 : 00:49:58

Nice work! However, there are some discrepancies. Here is the output from your code and I have added a fourth column that calculates the right distance.
And for fairness, I added the result of my first algorithm. (I think I need to revise the code

21 steps for a 7-letter word?)

Str1	Str2		CorDist	Original	PesoDist
-------	-------		----	--------	--------
Jamie	James		2	2		1
Jamie	June		3	3		6
Jamie	March		4	4		10
Jamie	July		4	4		12
Jamie	April		4	4		4
Jamie	May		4	4		4
Jamie	Peso		4	5		6	
Jamie	Monday		5	6		12
Jamie	Corey		5	5		13
Jamie	December	5	6		10
Jamie	Friday		5	6		9
Jamie	January		5	5		15
Jamie	Matthew		5	5		8
Jamie	Sunday		5	6		7
Jamie	Thursday	5	8		9
Jamie	Tuesday		5	7		12
Jamie	Wednesday	5	8		20
Jamie	August		6	6		8
Jamie	November	6	6		10
Jamie	October		6	6		21
Jamie	Robert		6	6		14
Jamie	Saturday	7	7		19
Jamie	September	8	7		12
Jamie	February	8	8		10

I think, in your case, the difference is due to "false matches". In my case

it is the grouping that creates duplicates.
I am certain that my idea is correct, it is just my implementation that is very, very wrong at the moment.

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-29 : 01:21:39

quote:
Originally posted by Seventhnight

I see that you worked a sample out as well...

I love the concept... very nicely thought out!

Yes, the sequence numbering code supplied by you, have come very handy in all sorts of situations.

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-29 : 02:25:30

I got it. The last part of my code should be

SELECT		SUM(CASE WHEN ISNULL(w1.c, 0) > ISNULL(w2.c, 0) THEN ISNULL(w1.c, 0) ELSE ISNULL(w2.c, 0) END)
FROM		(
			SELECT		a.Grp,
					COUNT(*) c
			FROM		@ts a
			GROUP BY	a.Grp
		) w1
FULL JOIN	(
			SELECT		b.Grp,
					COUNT(*) c
			FROM		@bp b
			GROUP BY	b.Grp
		) w2 ON w2.Grp = w1.Grp

Now the output with Corey's data is

Str1	Str2		CorDist	Original	PesoDist
-------	-------		----	--------	--------
Jamie	James		2	2		1
Jamie	June		3	3		3
Jamie	March		4	4		4
Jamie	July		4	4		4
Jamie	April		4	4		4
Jamie	May		4	4		4
Jamie	Peso		4	5		6
Jamie	Monday		5	6		7
Jamie	Corey		5	5		5
Jamie	December	5	6		6
Jamie	Friday		5	6		6
Jamie	January		5	5		5
Jamie	Matthew		5	5		5
Jamie	Sunday		5	6		7
Jamie	Thursday	5	8		9
Jamie	Tuesday		5	7		8
Jamie	Wednesday	5	8		8
Jamie	August		6	6		8
Jamie	November	6	6		6
Jamie	October		6	6		6
Jamie	Robert		6	6		6
Jamie	Saturday	7	7		7
Jamie	September	8	7		7
Jamie	February	8	8		10

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-29 : 03:37:23

I have found that my idea was almost right, but now I have a case that do not conform to my theory.
It is "Jamie / sunday".


1 - J   S - 1
2 - a   u - 2
3 - m   n - 3
4 - i   d - 4
5 - e   a - 5
        y - 6

The only match here is (2,4). According to my theory

J    1  Sund   4
mie  2  y      3

the sum would be 7. But it is not, the distance is 6.

Thank you Corey anyway for participating!

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-29 : 05:01:53

However JANE/PALM works. Maybe it's connected to where the "ropes" are?

Peter Larsson
Helsingborg, Sweden

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2006-08-29 : 07:23:52

I think the idea works... but there is a caveat.... sometimes it is a better option to simply replace every single letter in the longest word rather than modify the segments where the words don't match.

for example
Jamie/Sunday.... the distance is 6 because the length of the longest word is six.

The trick to this part comparing the distance to the lengths. I think that my query didn't work in your test because of the red in the below code. I will fix it in the full post of the code above.


Select 
	str1 = @str1, 
	str2, 
	distance = case when distance <= len(str2) or distance <= len(@str1) then distance when len(str2) >= len(@str1) then len(str2) else len(@str1) end
From 
	(
	Select A.str2, distance = sum(case when B.x - A.x >= B.y - A.y then B.x - A.x else B.y - A.y end - 1)
	From @distances A
	Inner Join @distances B
	On A.str2 = B.str2 and
	A.segment+1 = B.segment
	Group By A.str2
	) Z
Order By 3

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources