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
 Challenge - Pick a car combination lock

Author  Topic 

SamC
White Water Yakist

3467 Posts
Posted - 2005-05-14 : 23:05:36
Some automobiles have a five digit keypad which provide a programmable 5 key combination which will unlock the door, usually with 5 keystrokes. This gives 5**5 or 3125 different combinations to unlock the door.

An interesting trait that makes this door lock a little different from other combination locks is that the five digits can appear anywhere within a string. In other words, there's no "beginning" of string.

For example, if the combination is 15334, any string containing 15334 would open the door.

Viewed another way, pressing the keys 23453213 would have tried 4 different combinations: 23453, 34532, 45321, 53213

What is the shortest string which would try all possible combinations?

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2005-05-15 : 06:41:51
If this doesn't fail (And it doesn't!) then it must produce a minimal answer. Just don't ask me to prove that it can't fail. 

CREATE TABLE strings (
  s char(5) PRIMARY KEY
)

INSERT INTO strings
SELECT d4.d + d3.d + d2.d + d1.d + d0.d
FROM
 (SELECT '1' AS d UNION ALL SELECT '2' UNION ALL
  SELECT '3' UNION ALL SELECT '4' UNION ALL SELECT '5') AS d0,
 (SELECT '1' AS d UNION ALL SELECT '2' UNION ALL
  SELECT '3' UNION ALL SELECT '4' UNION ALL SELECT '5') AS d1,
 (SELECT '1' AS d UNION ALL SELECT '2' UNION ALL
  SELECT '3' UNION ALL SELECT '4' UNION ALL SELECT '5') AS d2,
 (SELECT '1' AS d UNION ALL SELECT '2' UNION ALL
  SELECT '3' UNION ALL SELECT '4' UNION ALL SELECT '5') AS d3,
 (SELECT '1' AS d UNION ALL SELECT '2' UNION ALL
  SELECT '3' UNION ALL SELECT '4' UNION ALL SELECT '5') AS d4

DECLARE @ss varchar(3129), @s char(5)
SELECT @ss = MIN(s), @s = MIN(s) FROM strings

SET NOCOUNT ON
BEGIN TRANSACTION

WHILE (1=1) BEGIN
  DELETE FROM strings WHERE s = @s

  SELECT @ss = @ss + RIGHT(s, 1), @s = s
  FROM (
      SELECT MAX(s) AS s
      FROM strings
      WHERE s LIKE RIGHT(@s, 4) + '%'
    ) AS A
  WHERE s IS NOT NULL

  IF @@ROWCOUNT = 0 BREAK
END

COMMIT TRANSACTION
SET NOCOUNT OFF

IF (SELECT COUNT(*) FROM strings) = 0 
  PRINT @ss
ELSE
  PRINT 'Failed!'

DROP TABLE strings
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-05-15 : 22:56:31
Mine is similar, but I couldn't resist. You can change the number of digits to calculate on and it gives all of the shortest paths, there seems to be n many, ie 3 digits has 3 and 4 digits has 4.


Declare @digits int
Set @digits = 3

Create Table #seed (n int)
Insert Into #Seed 
Select 1 union Select 2 Union Select 3 Union Select 4 Union Select 5
Union Select 6 Union Select 7 Union Select 8 Union Select 9 Union Select 0

Create Table #allComb (comb varchar(5), digits int)
Insert Into #allComb Select '', 0

Declare @digitCnt int
Set @digitCnt = 0

While @digitCnt < @digits
Begin
	Insert Into #allComb
	Select 
		comb = comb + n1,
		digits = @digitCnt+1
	From #allComb, (Select n1=convert(varchar,n) From #Seed where n < @digits) newDigits
	Where digits=@digitCnt
	
	Delete From #allComb Where digits=@digitCnt
	Set @digitCnt = @digitCnt + 1
End

Declare @step int,
	@RowCount int

Set @step = 0

Create Table #finalComb (comb varchar(7000), step int)
Insert Into #finalComb
Select 
	Comb,
	Step = @step+1
From #allComb A

Select @rowCount = @@RowCount

While @RowCount>0
Begin
	Select @Step = @step+1

	Insert Into #finalComb
	Select 
		Comb = A.comb + right(min(B.comb),1),
		Step = @step+1
	From #finalComb A
	Inner Join #allComb B
	On right(A.comb,len(B.comb)-1) = left(B.comb,len(B.comb)-1)
	Where A.Step = @step
	and A.comb not like '%'+B.comb+'%'
	Group By A.comb

	Select @rowCount = @@rowcount
End
	

Select * from #finalComb Where Step = @Step

Drop Table #seed
Drop Table #allComb
Drop Table #finalComb


Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2005-05-16 : 04:31:24
But Corey, your method is doing it 'properly': combining each partial result with all the compatible remaining strings. All mine does is take the lexically smallest string as a start and repeatedly add the lexically largest compatible remaining string.
I don't understand why that works! How does it get to every string without failing? Is it some property of this particular de Bruijn graph or does it work for all of them?
Go to Top of Page

SamC
White Water Yakist

3467 Posts
Posted - 2005-05-16 : 08:00:34
It's very interesting that Arnold's solution works if you start with a MIN (or MAX) then append the next MAX or MIN.

I tried selecting ANY (Top 1 unsorted) instead of MIN or MAX and it fails.

quote:
Originally posted by Arnold Fribble

If this doesn't fail (And it doesn't!) then it must produce a minimal answer. Just don't ask me to prove that it can't fail.
Arnold... can you prove why this technique must succeed?
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2005-05-16 : 08:51:47
I just wandered around looking at stuff about de Bruijn cycles until I found a little program doing what I did and saying they didn't know why it worked. I had wondered whether it was possible to use an approach like Warnsdorff's algorithm on Knight's Tour (see [url]http://www.sqlteam.com/Forums/topic.asp?TOPIC_ID=32232[/url]), but it doesn't seem to be necessary.
This tests it for different small values of @a (number of symbols in alphabet) and @l (length of string). It keeps the combinations as numbers to make it simpler:

CREATE TABLE results (
  a int NOT NULL,
  l int NOT NULL,
  ok bit NOT NULL,
  PRIMARY KEY (a,l)
)

DECLARE @aa int, @ll int
SET @aa = 2
WHILE @aa <= 316 BEGIN

SET @ll = 2
WHILE @ll <= 16 BEGIN

DECLARE @a int, @l int, @ncombs int, @ncombs1 int, @n int
SET @a = @aa
SET @l = @ll
SET @ncombs = POWER(@a, @l)
SET @ncombs1 = POWER(@a, @l-1)

IF @ncombs > 100000 BREAK

CREATE TABLE combs ( n int PRIMARY KEY )

SET NOCOUNT ON
BEGIN TRANSACTION

SET @n = 0
WHILE @n < @ncombs BEGIN
  INSERT INTO combs SELECT @n
  SET @n = @n + 1
END

SET @n = 0
WHILE (1=1) BEGIN
  DELETE FROM combs WHERE n = @n

  SELECT @n = n
  FROM (
      SELECT MAX(n) AS n
      FROM combs
      WHERE n BETWEEN @n%@ncombs1*@a AND @n%@ncombs1*@a+@a-1
    ) AS A
  WHERE n IS NOT NULL

  IF @@ROWCOUNT = 0 BREAK
END

COMMIT TRANSACTION
SET NOCOUNT OFF

INSERT INTO results SELECT @a, @l,
  CASE WHEN (EXISTS (SELECT * FROM combs)) THEN 0 ELSE 1 END

DROP TABLE combs

SET @ll = @ll + 1
END

SET @aa = @aa + 1
END

SELECT * FROM results

DROP TABLE results
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2005-05-16 : 09:07:45
quote:
Originally posted by SamC
It's very interesting that Arnold's solution works if you start with a MIN (or MAX) then append the next MAX or MIN.

The ordering of the letters in the alphabet is arbitrary, so swapping MAX and MIN is just like relabelling ABCDE to EDCBA. So really, you'd expect it to work both ways round if it works one way.
Go to Top of Page

rockmoose
SQL Natt Alfen

3279 Posts
Posted - 2005-05-16 : 10:37:59
Cory, I ran yours, up to 4 digits, 5 took forever.
That there are n many solutions is not very surprising, because you can start with any of the n letters in the alphabet.

Does anyone have Mathematica and can try their function: DeBruijnSequence[a, n] ???

I still haven't grasped why AF's solution is guaranteed to give a minimal solution.


rockmoose
Go to Top of Page

SamC
White Water Yakist

3467 Posts
Posted - 2005-05-16 : 10:58:29
quote:
Originally posted by Arnold Fribble

The ordering of the letters in the alphabet is arbitrary, so swapping MAX and MIN is just like relabelling ABCDE to EDCBA. So really, you'd expect it to work both ways round if it works one way.

Not surprising.

What I don't get is why the solution works by selecting the MAX each time and working it's way down in order. I fails if I pick an arbitrary match: 

      SELECT Top 1 s
      FROM strings
      WHERE s LIKE RIGHT(@s, 4) + '%'


and it fails. What made you believe MAX / MIN might work?
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2005-05-16 : 11:04:40
just for kicks... the changes in orange return symmetrical paths.

(5 took 21 seconds for me)

Declare @digits int
Set @digits = 5

Create Table #seed (n int)
Insert Into #Seed 
Select 1 union Select 2 Union Select 3 Union Select 4 Union Select 5
Union Select 6 Union Select 7 Union Select 8 Union Select 9 Union Select 0

Create Table #allComb (comb varchar(5), digits int)
Insert Into #allComb Select '', 0

Declare @digitCnt int
Set @digitCnt = 0

While @digitCnt < @digits
Begin
	Insert Into #allComb
	Select 
		comb = comb + n1,
		digits = @digitCnt+1
	From #allComb, (Select n1=convert(varchar,n) From #Seed where n < @digits) newDigits
	Where digits=@digitCnt
	
	Delete From #allComb Where digits=@digitCnt
	Set @digitCnt = @digitCnt + 1
End

Declare @step int,
	@RowCount int

Set @step = 0

Create Table #finalComb (comb varchar(7000), step int)
Insert Into #finalComb
Select 
	Comb,
	Step = @step+1
From #allComb A
Where comb = reverse(comb)

Select @rowCount = @@RowCount
--Select @rowCount = 0

While @RowCount>0
Begin
	Select @Step = @step+1

	Insert Into #finalComb
	Select 
		Comb = right(min(B.comb),1) + A.comb + right(min(B.comb),1),
		Step = @step+1
	From #finalComb A
	Inner Join #allComb B
	On right(A.comb,len(B.comb)-1) = left(B.comb,len(B.comb)-1)
	Where A.Step = @step
	and A.comb not like '%'+B.comb+'%'
	Group By A.comb

	Select @rowCount = @@rowcount
End
	

Select * from #finalComb Where Step = @Step

Drop Table #seed
Drop Table #allComb
Drop Table #finalComb


Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2005-05-17 : 04:43:07
quote:
What made you believe MAX / MIN might work?

Only the existence of this posting from comp.compression:
[url]http://groups-beta.google.com/group/comp.compression/msg/eda6c7b54b63eec1?dmode=source&hl=en[/url]
Go to Top of 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